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

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

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},
}

Loading related content...

Figure