Sound and complete algorithms for hierarchical refinement planning and centralized plan coordination for actions with temporal extent, supporting flexible plan execution systems.

An agent can reduce backtracking during planning by selectively interleaving the refinement of its plan with predicting and resolving potential interdependencies between its evolving plan and the plans that will be asynchronously executed by other agents. Other research has also found benefit in guiding refinement with conditions specified at higher levels in the plan hierarchy to guide refinement [Sacerdoti, 1974, Young, Pollack, Moore, 1994, Tsuneto, Hendler, Nau, 1998]. We show that our algorithms improve on these capabilities by exploiting the hierarchical structure using summary information to more efficiently converge on coordinated plans, which can then be further refined individually and in parallel by the participating agents.

This ability to coordinate at abstract levels rather than over detailed plans allows each of the agents to retain some local flexibility to refine its operators as best suits its current or expected circumstances without jeopardizing coordination or triggering new rounds of renegotiation. In this way, summary information supports robust execution systems such as PRS [Georgeff Lansky, 1986], UMPRS [Lee, Huber, Durfee, Kenny, 1994], RAPS [Firby, 1989], JAM [Huber, 1999], etc. that interleave the refinement of abstract plan operators with execution.

Our approach also extends plan coordination (plan merging) techniques [Georgeff, 1983, Lansky, 1990, Ephrati Rosenschein, 1994] by utilizing plan hierarchies and a more expressive temporal model. Prior techniques assume that actions are atomic, meaning that an action either executes before, after, or at exactly the same time as another. In contrast, we use interval point algebra [Vilain Kautz, 1986] to represent the possibility of several actions of one agent executing during the execution of one action of another agent. Because our algorithms can choose from alternative refinements in the HTN dynamically in the midst of plan coordination, they support interleaved local planning, multiagent coordination, and concurrent execution.