Recursive Small-Step Multi-Agent A* for Dec-POMDPs
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.
Cite
Text
Koops et al. "Recursive Small-Step Multi-Agent A* for Dec-POMDPs." International Joint Conference on Artificial Intelligence, 2023. doi:10.24963/IJCAI.2023/600Markdown
[Koops et al. "Recursive Small-Step Multi-Agent A* for Dec-POMDPs." International Joint Conference on Artificial Intelligence, 2023.](https://mlanthology.org/ijcai/2023/koops2023ijcai-recursive/) doi:10.24963/IJCAI.2023/600BibTeX
@inproceedings{koops2023ijcai-recursive,
title = {{Recursive Small-Step Multi-Agent A* for Dec-POMDPs}},
author = {Koops, Wietze and Jansen, Nils and Junges, Sebastian and Simão, Thiago D.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2023},
pages = {5402-5410},
doi = {10.24963/IJCAI.2023/600},
url = {https://mlanthology.org/ijcai/2023/koops2023ijcai-recursive/}
}