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.