MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs

Daniel Szer, François Charpillet, Shlomo ZilbersteinUAI 2005

TL;DR

This paper introduces MAA, the first complete and optimal heuristic search algorithm for solving decentralized partially-observable Markov decision problems (DEC-POMDPs) with finite horizons. MAA offers a significant advantage over existing methods by efficiently finding optimal plans for cooperative multi-agent systems operating under uncertainty, with promising results on benchmark problems.

What Problem Does This Paper Address?

Cooperative multi-agent systems, such as coordinating robots or managing network traffic, often operate in environments where outcomes are uncertain and agents have incomplete information about the global state. This problem is formalized as Decentralized Partially-Observable Markov Decision Processes (DEC-POMDPs). The complexity of solving DEC-POMDPs is notoriously high, even for simple scenarios, making it a significant challenge for AI planning. Existing approaches struggle with this complexity, especially when dealing with finite-horizon problems where optimal solutions are desired. This paper aims to bridge this gap by developing an efficient and optimal algorithm for solving these challenging problems.

Methods

The core contribution of this paper is the MAA (Multi-Agent A) algorithm. It's a heuristic search algorithm that extends the classical A search to the domain of DEC-POMDPs. Instead of searching through states, MAA searches through policy vectors, where each agent has its own policy (a mapping from its observation history to an action).

Key aspects of the method include:

  • Policy Vector Search Space: MAA* operates on a search tree where nodes represent partial policy vectors. Expanding a node involves generating new, more complete policy vectors.
  • Heuristic Function: A crucial component is the development of admissible heuristic functions. The paper proposes several, including:
  • MDP Heuristic: Using the solution of the underlying fully observable Markov Decision Process (MDP) as an optimistic estimate.
  • POMDP Heuristic: Leveraging solutions from centralized POMDPs.
  • Recursive MAA*: Using MAA* itself to compute a tighter heuristic, leading to more pruning.
  • Anytime Search: MAA* is designed to be an "anytime" algorithm, meaning it can provide increasingly better solutions over time. It can report suboptimal solutions as soon as they are found, which is valuable when optimal solutions take too long to compute.
  • Incremental Node Expansion: To manage complexity, MAA* expands nodes incrementally, rather than fully expanding all children at once. This allows for early pruning of suboptimal branches.

Datasets

The paper evaluates MAA* on three benchmark problems:

  • Multi-agent Tiger Problem (Versions A and B): A classic problem involving two agents trying to find riches behind one of two doors, with the tiger behind the other. Agents have partial information about the tiger's location.
  • Multi-access Broadcast Channel Problem: Simulates message transmission in a shared network where collisions can occur if agents transmit simultaneously. Agents have noisy observations of collision events.

These problems are standard benchmarks in the DEC-POMDP literature.

Key Insights and Ideas

  • Policy Space Search is Viable: The paper demonstrates that searching in the space of policy vectors, rather than states or beliefs, is a tractable and effective approach for DEC-POMDPs.
  • Heuristics are Key to Scalability: The effectiveness of MAA heavily relies on the quality of its admissible heuristic functions. Tighter heuristics (like the recursive MAA heuristic) lead to significantly more pruning and better performance.
  • Anytime Property is Crucial: For complex DEC-POMDPs, finding an optimal solution can be computationally prohibitive. MAA*'s ability to provide good suboptimal solutions quickly is a major practical advantage.
  • Recursive Heuristics Offer Strong Pruning: While computationally more expensive, using MAA* recursively to compute the heuristic provides the tightest possible estimate, leading to substantial pruning of the search space.

Key Results

  • MAA is shown to be complete and optimal* for finite-horizon DEC-POMDPs.
  • Experimental results demonstrate that MAA significantly outperforms dynamic programming approaches in terms of memory requirements* and can tackle larger problems. For instance, it's claimed to be the first general optimal algorithm for the horizon-4 tiger problem.
  • On the channel problem, MAA* with the MDP heuristic explored only 3% of the policy pairs required by a brute-force approach for horizon-4.
  • The recursive MAA* approach generally performs better than the MDP heuristic, despite its higher computational cost, due to more effective pruning.
  • Runtimes for MAA* range from milliseconds for short horizons (T=2) to hours for longer horizons (T=4), indicating its scalability.

Limitations and Future Work

  • Finite Horizon Limitation: The current MAA algorithm is designed for finite-horizon DEC-POMDPs. The authors acknowledge that extending it to infinite horizon problems* is an important open problem.
  • Stochastic Policies: The current work focuses on deterministic policies derived from policy trees. Investigating stochastic policies and their integration with heuristic search is a promising direction.
  • Generalizing to Finite State Controllers: The paper notes that extending the theory of finite state controllers, which has been applied to single-agent POMDPs, to multi-agent settings using heuristic search is a significant open problem.
  • State Value Definition: The paper raises the question of whether state values can be defined in a similar way for decentralized POMDPs as they are for centralized ones, suggesting this is an area for further research.

Summary updated

BibTeX
@inproceedings{szer2005maa,
  author = {Daniel Szer and François Charpillet and Shlomo Zilberstein},
  title = {{MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2005},
}
Figure