Recursive Small-Step Multi-Agent A* for Dec-POMDPs
Lists
Only you see this
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...