Abstract
Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) provide a robust framework for multi-agent planning under uncertainty but are notoriously difficult to solve due to their NEXP-complete complexity and the requirement for exact probability specifications. This paper proposes Qualitative Dec-POMDPs (QDec-POMDPs), which replace quantitative probabilities with a possibility-based model. By compiling QDec-POMDPs into classical planning problems, the authors leverage efficient off-the-shelf planners to solve multi-agent coordination tasks that are orders of magnitude larger than those handled by traditional quantitative methods.
The Complexity of Multi-Agent Planning
Planning for multiple agents in uncertain environments is a fundamental challenge in AI. The standard Dec-POMDP model requires agents to maximize expected rewards based on precise probabilities of action outcomes and sensor readings. However, this approach faces two major hurdles:
- Computational Intractability: The search space for optimal policies grows exponentially with the number of agents and history length.
- Specification Difficulty: In real-world scenarios, it is often impossible to determine exact probabilities (e.g., the 0.123 probability of a sensor failure).
The authors address this by moving to a qualitative model. Instead of maximizing expected reward, the goal is to find a plan that guarantees reaching a target state regardless of which possible outcome occurs.
The QDec-POMDP Framework
The authors introduce the Qualitative Dec-POMDP (QDec-POMDP) to simplify the planning process. Key innovations include:
- Factored Representation: Using a propositional model (similar to PDDL) allows for a compact description of complex states, avoiding the exponential explosion of "flat" state enumerations. For instance, a $3 \times 3$ box-pushing task that would require over 1GB in a flat format was represented in just 15KB.
- Classical Planning Compilation: The core contribution is a method to translate multi-agent, partially observable problems into single-agent classical planning tasks. This allows the use of highly optimized heuristics from the classical planning community, such as the Fast Downward planner.
- Distinguishability Logic: The compilation tracks the "belief states" of agents—sets of possible worlds they cannot distinguish between—ensuring that the generated plans are executable in a decentralized manner.
Experimental Evaluation: The Box Pushing Domain
The approach was evaluated using the Box Pushing domain, where two agents must coordinate to move light and heavy boxes to target locations. Heavy boxes require simultaneous pushing by both agents, necessitating tight coordination.
The researchers scaled the domain from a $2 \times 2$ grid with 2 boxes up to a $3 \times 3$ grid with 3 boxes. While the theoretical complexity remains NEXP-complete, the qualitative abstraction significantly simplifies the search space in practice.
Key Results and Performance
The experimental results demonstrate a dramatic performance advantage for the qualitative approach. The QDec-POMDP solver handled the largest instances with nearly 60,000 states in approximately 66 seconds, whereas traditional quantitative solvers like IPG and GMAA-ICE either timed out or failed to scale.
As shown in the table, the QDec-POMDP approach maintains manageable computation times even as the state space ($|S|$) grows exponentially. In contrast, GMAA-ICE took 732 seconds on a medium instance that the QDec-POMDP approach solved in under 50 seconds.
Conclusion and Future Directions
By "compiling away" uncertainty into a qualitative framework, this research opens new avenues for solving large-scale multi-agent problems. While currently optimized for deterministic actions with multiple possible outcomes, future work aims to extend this to more complex non-deterministic effects and online planning. Additionally, qualitative plans could serve as powerful heuristics to guide more precise quantitative solvers in hybrid planning architectures.
Summary updated