Recursive Small-Step Multi-Agent A* for Dec-POMDPs

Wietze Koops, Nils Jansen, Sebastian Junges, Thiago D. Simão

Abstract

This paper introduces RS-MAA (Recursive Small-Step Multi-Agent A), an exact algorithm for solving Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs). By decomposing massive joint decision rules into incremental "small steps" and employing a tight, recursive heuristic computed on-the-fly, RS-MAA* significantly extends the solvability of these NEXP-hard problems, reaching horizons previously considered unreachable for exact solvers.

Introduction

Dec-POMDPs model cooperative scenarios where multiple agents must achieve a shared goal despite having only partial, local observations and no free communication. The primary challenge in solving these optimally using the classical Multi-Agent A (MAA) approach is the search tree's "outdegree." A single node expansion requires choosing a joint decision rule—a mapping of every possible observation history for every agent to an action—leading to a double-exponential explosion in children per node. This typically causes solvers to exhaust memory or time as the horizon ($h$) increases.

Methodology

RS-MAA* addresses the complexity of Dec-POMDPs through three core innovations:

1. Small-Step Search Tree

Instead of deciding actions for all agents and histories simultaneously, RS-MAA makes incremental decisions: picking a single action for one agent for one specific observation history. This transforms a shallow tree with a massive outdegree into a much deeper tree with a constant outdegree, allowing the A algorithm to prune sub-optimal branches far more effectively.

The RS-MAA* small-step search tree structure, breaking down joint decision rules into incremental agent-history actions.

2. Recursive On-the-Fly Heuristics ($Q_d$)

Unlike solvers that rely on expensive precomputed heuristics, RS-MAA* computes heuristic values dynamically. This heuristic uses a "communication relaxation," assuming agents can share observations starting at a future time step $d$. This provides a tight, admissible upper bound that is more effective than standard MDP or POMDP approximations.

3. Optimization Techniques

To maintain efficiency, the algorithm can terminate heuristic calculations early if a path is clearly sub-optimal. It also utilizes "lossless clustering" to group observation histories requiring the same action, and dynamically adjusts the depth of the communication relaxation to balance heuristic tightness with computational overhead.

Evaluation and Key Results

The algorithm was evaluated on standard Dec-POMDP benchmarks, including DECTIGER, BOXPUSHING, GRID, HOTEL, RECYCLING, and BROADCAST.

Performance comparison between RS-MAA* and state-of-the-art GMAA*-ICE across standard benchmarks.

RS-MAA demonstrated a massive leap in performance over the previous state-of-the-art (GMAA-ICE):

  • Horizon Scaling: In the RECYCLING domain, RS-MAA* scaled to a horizon of 1500, a vast improvement over the previous limit of 80. In DECTIGER, it reached a horizon of 12, doubling the previous record.
  • Computational Efficiency: On the MARS benchmark at horizon 9, RS-MAA* found the optimal solution in 160 seconds, while competing solvers timed out or ran out of memory.
  • Memory Management: By computing heuristics on-the-fly and avoiding the massive memory overhead of precomputation, RS-MAA* remains robust where other solvers fail due to memory constraints.

Conclusion

RS-MAA effectively shifts the challenge of Dec-POMDP solving from managing breadth to managing depth. By stretching the decision process into smaller steps, the algorithm leverages its recursive heuristic to prune the search space much earlier. While performance is most dramatic in domains where observation histories can be clustered, RS-MAA sets a new benchmark for exact solvers. Future research may involve integrating approximate solvers into the heuristic computation to further push scalability boundaries.

Summary updated

Abstract

We present recursive small-step multi-agent A* (RS-MAA*), an exact algorithm that optimizes the expected reward in decentralized partially observable Markov decision processes (Dec-POMDPs). RS-MAA* builds on multi-agent A* (MAA*), an algorithm that finds policies by exploring a search tree, but tackles two major scalability concerns. First, we employ a modified, small-step variant of the search tree that avoids the double exponential outdegree of the classical formulation. Second, we use a tight and recursive heuristic that we compute on-the-fly, thereby avoiding an expensive precomputation. The resulting algorithm is conceptually simple, yet it shows superior performance on a rich set of standard benchmarks.
BibTeX
@inproceedings{koops2023recursive,
  author = {Wietze Koops and Nils Jansen and Sebastian Junges and Thiago D. Simão},
  title = {{Recursive Small-Step Multi-Agent A* for Dec-POMDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/600},
}
Figure