Abstract
In order to generate plans for agents with multiple actuators, agent teams, or distributed controllers, we must be able to represent and plan using concurrent actions with interacting effects. This has historically been considered a challenging task requiring a temporal planner with the ability to reason explicitly about time. We show that with simple modifications, the STRIPS action representation language can be used to represent interacting actions. Moreover, algorithms for partial-order planning require only small modifications in order to be applied in such multiagent domains. We demonstrate this fact by developing a sound and complete partial-order planner for planning with concurrent interacting actions, POMP, that extends existing partial-order planners in a straightforward way. These results open the way to the use of partial-order planners for the centralized control of cooperative multiagent systems.
Introduction
Coordinating multiple agents or actuators—such as a team of robots or a dual-armed manipulator—presents a fundamental challenge in automated planning: the need to handle concurrent, interacting actions. In these environments, actions performed simultaneously can interact in complex ways. Negative interactions occur when concurrent actions interfere, such as two agents attempting to use a shared resource simultaneously. Conversely, positive interactions are often necessary for success, such as two agents lifting a heavy table together; if only one lifts, the objects on the table may slide off.
Historically, the AI community believed that managing these interactions required either explicit temporal logic to reason about time intervals or the construction of "joint actions" that combine all possible simultaneous agent behaviors. The former adds significant complexity, while the latter leads to an exponential explosion in the action space as the number of agents grows. This paper demonstrates that neither approach is strictly necessary. By extending classical partial-order planning (POP) frameworks, the authors introduce a method to represent and plan for concurrent interactions efficiently.
Representing Interacting Actions
The authors propose an augmented version of the STRIPS representation to capture concurrency without explicit time. This is achieved through two primary extensions:
- Concurrency Constraints: Actions are extended with lists of required or forbidden concurrent actions. An action can specify that for its effects to manifest, another specific action must occur simultaneously, or conversely, that a certain action must not occur at the same time.
- Conditional Effects: Utilizing
whenclauses allows actions to have different outcomes based on the state of the world or other concurrent actions. For example, in a "table movers" domain, the effect of Agent A lifting its side of the table is conditional on whether Agent B is also lifting its side.
This distributed representation is significantly more compact than joint-action models, as it focuses on individual agent capabilities and their specific interactions rather than every possible combination of behaviors.
The POMP Algorithm
The core contribution is the Partial-Order Multiagent Planning (POMP) algorithm, which builds upon the standard UCPOP planner. POMP adapts the traditional partial-order planning cycle—selecting subgoals, choosing actions to satisfy them, and resolving threats—to a multiagent context.
Ordering and Concurrency
Standard POP uses strict inequality constraints ($A < B$) to order actions. POMP introduces equality constraints ($A = B$) to enforce simultaneity and non-concurrency constraints to prevent conflicting actions from overlapping. This allows the planner to reason about "time steps" logically rather than numerically.
Resolving NC-Threats
A significant addition is the concept of Non-Concurrency (NC) threats. In single-agent planning, a threat occurs when an action might delete a required precondition. In POMP, an NC-threat arises when the concurrent execution of two actions ruins an intended effect, even if they don't conflict when executed sequentially. POMP resolves these threats using three main strategies:
- Promotion: Forcing action A to occur strictly before action B.
- Demotion: Forcing action A to occur strictly after action B.
- Weak Promotion: A novel technique that forces action A to occur concurrently with action B to satisfy a positive interaction requirement.
Theoretical Foundations and Results
The authors provide rigorous proofs for the POMP framework. They demonstrate that POMP is both sound (it only produces valid plans) and complete (it will find a plan if one exists).
The proof of completeness relies on a reduction to an Equivalent Single Agent (ESA) problem. By showing that any multiagent problem with concurrent interactions can be mapped to a single-agent problem, and that POMP's search process emulates a standard POP planner solving that ESA problem, the authors establish that the added complexity of concurrency does not break the underlying planning logic.
Discussion and Future Work
While POMP provides a robust solution for centralized multiagent planning, it operates under the assumption of a global controller and synchronized execution. It does not yet address the challenges of distributed planning, where agents may have limited communication or conflicting local goals.
Furthermore, the introduction of concurrency constraints increases the search space. Future research directions include developing more sophisticated heuristics to guide the planner and adapting these concurrent representations to more modern planning architectures, such as Graphplan or SAT-based systems. There is also potential in using dynamic Bayesian networks to represent interacting actions in stochastic environments.
Conclusion
This work demonstrates that the gap between single-agent and multiagent planning is smaller than previously thought. By treating concurrency as a logical constraint rather than a temporal one, the POMP algorithm provides a powerful, sound, and complete tool for coordinating agent teams without the overhead of complex temporal reasoning.
Summary updated