Solving Multiagent Planning Problems with Concurrent Conditional Effects
It addresses planning for multiple agents acting in parallel, a domain-specific problem, but is incremental as it builds on existing classical planning methods.
The paper tackles the problem of multiagent planning with concurrent conditional effects by compiling it to classical planning, enabling the use of off-the-shelf planners to generate concurrent plans without exponential blowup. The approach is theoretically sound and complete, and empirically solves challenging problems requiring concurrent actions.
In this work we present a novel approach to solving concurrent multiagent planning problems in which several agents act in parallel. Our approach relies on a compilation from concurrent multiagent planning to classical planning, allowing us to use an off-the-shelf classical planner to solve the original multiagent problem. The solution can be directly interpreted as a concurrent plan that satisfies a given set of concurrency constraints, while avoiding the exponential blowup associated with concurrent actions. Our planner is the first to handle action effects that are conditional on what other agents are doing. Theoretically, we show that the compilation is sound and complete. Empirically, we show that our compilation can solve challenging multiagent planning problems that require concurrent actions.