Theory for Coordinating Concurrent Hierarchical Planning Agents Using Summary Information

AAAI 1999

TL;DR

This paper introduces a formal theory for coordinating concurrent hierarchical planning agents by using "summary information" derived from abstract plans. This approach allows agents to reason about potential conflicts and interactions at higher levels of abstraction, enabling more efficient and robust coordination without premature commitment to detailed plan refinements.

What Problem Does This Paper Address?

Coordinating multiple agents that are planning and executing actions concurrently is a significant challenge, especially when those agents use hierarchical planning (like Hierarchical Task Networks or HTNs). HTN planners break down complex tasks into abstract sub-tasks, which are then refined into more concrete actions. When agents interleave planning, coordination, and execution, decisions made at abstract levels can have far-reaching consequences. If these abstract decisions lead to conflicts that can only be resolved at much lower, detailed levels, it can result in costly backtracking or even outright failure, particularly if some actions have already been executed. The core problem this paper addresses is how to enable agents to make sound coordination decisions at abstract levels, avoiding these costly failures by anticipating potential conflicts and interactions before plans are fully refined.

Methods

The authors propose a formal framework for Concurrent Hierarchical Plans (CHiPs) that extends traditional planning representations with "inconditions" (conditions that must hold during execution). They then define "summary information" for these plans, which includes abstract representations of their preconditions, inconditions, and postconditions. This summary information is derived recursively from the plan's structure and the summary information of its subplans.

Key aspects of their method include:

  • Formalizing CHiPs: Defining plans as tuples of preconditions, inconditions, postconditions, type (primitive, and, or), subplans, and temporal ordering constraints among subplans.
  • Deriving Summary Information: A recursive procedure to compute summary conditions (presum, insum, postsum) for any given plan. This involves identifying external preconditions and postconditions, as well as conditions that must hold throughout execution.
  • Temporal Relation Determination: Using the derived summary information to establish temporal relationships between plans. They define rules for determining if two plans can definitely overlap (Can AnyWay) or might overlap (MightSomeWay), based on their summary conditions. This allows for reasoning about interactions without needing to explore all possible detailed refinements.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and uses a simple illustrative example (agents moving through a doorway) rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Abstract Reasoning for Coordination: The most crucial insight is that effective coordination of concurrent hierarchical planning agents requires reasoning about potential conflicts and interactions at abstract levels, not just at the level of primitive actions.
  • Summary Information as a Bridge: Summary information acts as a powerful abstraction, capturing the essential preconditions and effects of a hierarchical plan without revealing all its internal details. This allows for efficient reasoning about inter-agent dependencies.
  • Avoiding Premature Commitment: By using summary information, agents can make coordination decisions (like merging or synchronizing plans) early in the planning process, thereby avoiding costly backtracking or failures that arise from detailed plan execution.
  • Formalizing Temporal Interactions: The paper provides a formal way to characterize temporal relationships (like overlap) between abstract plans, which is essential for building sound and complete coordination mechanisms.

Key Results

The paper presents a formal theory for CHiPs and a method for deriving summary information. It proves the soundness and completeness of rules for determining temporal relations (specifically, overlaps) between plans based on their summary information. This theoretical foundation is presented as a basis for building provably correct coordination and planning mechanisms. While no quantitative results are presented, the theoretical contributions are significant for the field of multi-agent planning and coordination.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Downward Solution Property: The current theory assumes the "downward solution property," meaning that every "or" plan in the hierarchy can be refined successfully through at least one of its subplans. Relaxing this assumption is a key area for future work.
  • Other Temporal Relations: The paper focuses on overlap but suggests that similar rules can be developed for other temporal relations (e.g., before, meets, starts).
  • Other Summary Information Types: Exploring alternative or richer forms of summary information beyond preconditions, inconditions, and postconditions could be beneficial.
  • General Algorithm and Evaluation: The authors mention prior work on a general algorithm for merging hierarchical plans using summary information and a preliminary evaluation, indicating that further empirical validation and refinement of the proposed theory are planned.
  • Interleaving Planning, Coordination, and Execution: A significant future direction is to fully integrate the developed theory into systems that can effectively interleave planning, coordination, and execution.

Summary updated

BibTeX
@inproceedings{1999theory,
  title = {{Theory for Coordinating Concurrent Hierarchical Planning Agents Using Summary Information}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure