Partial-Order Planning with Concurrent Interacting Actions

Craig Boutilier, Ronen I. Brafman

TL;DR

This paper demonstrates that coordinating multiple agents to perform concurrent, interacting actions doesn't actually require complex temporal planners. By making surprisingly simple modifications to classic action representations (STRIPS) and standard partial-order planning algorithms, the authors introduce POMP—a sound and complete centralized planner for multiagent teams.

What Problem Does This Paper Address?

In multiagent or multi-actuator systems (like a team of robots or a robot with two arms), agents often need to perform actions at the exact same time. Crucially, these concurrent actions often interact.

Sometimes this interaction is negative (e.g., two agents trying to transmit data over a half-duplex line simultaneously will corrupt the signal). Other times, it is positive and necessary (e.g., two agents must lift opposite sides of a table simultaneously; if one lifts alone, the blocks on the table will slide off).

Historically, AI researchers believed that handling these interacting, concurrent actions required planners with an explicit, complex representation of time. Alternatively, researchers would combine every possible simultaneous action into massive "joint actions," which causes the action space to explode exponentially as more agents are added. The authors tackle the problem of how to naturally represent and plan for these concurrent interactions without explicit temporal logic or exponential blowups.

Methods

The authors solve this through two main contributions: a new representation and a modified planning algorithm.

  1. Augmented STRIPS Representation: They extended the classic STRIPS action language by adding a concurrent action list to an action's preconditions and effects. An action can now explicitly state: "For my effect to happen, Action X must happen at the same time, and Action Y must not happen at the same time." They also utilize when clauses to handle conditional effects (e.g., when Agent 2 lifts the other side of the table, the table rises; when Agent 2 does not, the blocks fall).
  2. The POMP Algorithm (Partial-Order Multiagent Planning): They modified UCPOP, a standard partial-order planner. Standard planners order actions using strict inequalities (Action A must happen before Action B). POMP introduces equality constraints (Action A must happen at the exact same time as Action B) and non-concurrency constraints.
  3. Expanded Threat Resolution: In partial-order planning, a "threat" occurs when one action destroys the preconditions needed by another. POMP introduces "NC-threats" (Non-Concurrency threats), where the mere act of performing two actions at the same time ruins an intended effect. POMP resolves these using standard techniques like promotion (forcing A before B), demotion (forcing B before A), and a new technique called weak promotion (forcing A to happen concurrently with B).

Datasets

Not discussed in the paper. The authors use a theoretical "table movers" domain (a multiagent variant of the classic blocks world) to conceptually illustrate and trace the algorithm, but no empirical benchmark datasets are evaluated.

Key Insights and Ideas

  • Time is a red herring in multiagent planning: You don't need explicit timelines or temporal logic to handle concurrent interactions. Logical constraints on action orderings (before, after, simultaneous) are entirely sufficient to capture the synergies of multiagent teamwork.
  • Distributed representation beats joint actions: By specifying concurrency constraints on individual actions rather than defining every possible "joint action" for the whole team, the representation remains compact and scales much better as the number of agents increases.
  • Old dogs can learn new tricks: Classic, single-agent partial-order planners are surprisingly close to being multiagent planners out-of-the-box. They primarily just need the ability to understand equality in ordering constraints and to check for concurrent threats.

Key Results

  • Creation of POMP: The authors successfully developed a working partial-order planner capable of generating coordinated, multiagent plans with interacting actions.
  • Theoretical Guarantees: The authors mathematically prove that POMP is both sound (any plan it outputs is guaranteed to achieve the goal) and complete (if a valid sequence of concurrent actions exists to solve the problem, POMP will find it).
  • Equivalent Single Agent (ESA) Reduction: They proved completeness by showing that any multiagent planning problem can be reduced to an ESA problem, and that POMP's steps perfectly emulate a standard, proven planner (POP) solving that ESA problem.

Limitations and Future Work

  • Centralized Control Assumption: POMP is a centralized planner. It assumes a single "brain" is generating the plan for all agents and that the agents have a global clock or synchronization mechanism to execute actions at the exact same time. It does not address distributed planning where agents must negotiate or plan with limited communication.
  • Computational Overhead: The authors acknowledge that adding concurrency choices significantly increases the search space. Without highly tuned heuristics for choosing which subgoals to achieve first, the planner's computational performance can suffer.
  • Future Directions: The authors suggest applying this concurrent representation to newer, faster planning architectures (like Graphplan or SAT-based planners). They also suggest exploring dynamic Bayes nets to represent complex, interacting actions more concisely, especially in stochastic domains.

Summary updated

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.
BibTeX
@article{boutilier2001partial,
  author = {Craig Boutilier and Ronen I. Brafman},
  title = {{Partial-Order Planning with Concurrent Interacting Actions}},
  journal = {J. Artif. Intell. Res.},
  year = {2001},
  url = {https://openreview.net/forum?id=2gkt2dF8YN},
}

Loading related content...

Figure