Synchronization of multi-agent plans

Consider an intelligent agent constructing a plan to be executed by several other agents; correct plan execution will often require that actions be taken in a specific sequence. Therefore, the planner cannot simply tell each agent what action to perform; explicit mechanisms must exist for maintaining the execution sequence. This paper outlines such mechanisms. A framework for multiple-agent planning is developed, consisting of several parts. First, a formalism is adopted for representing knowledge about other agents' beliefs and goals, and is extended to allow representation of their capabilities. Communication primitives are defined that allow selective acceptance of goals and facts, and an explicit means of inducing an agent to perform an act is introduced. Finally, the ordering mechanisms (consisting of sequencing operators and a planning heuristic) arc presented, along with a specific example of their use.