This paper presents a software component, the plan manager, which provides the services needed to build and execute plans in a multi-robot context. This plan manager handles fully dynamic plans (insertion and removal of tasks), provides tools for safe concurrent execution and modification of plans, and handles distributed plan supervision without permanent robot-to-robot communication. The proposed concept is illustrated by a scenario which involves the navigation of a rover and an UAV in an initially unmapped environment.