Approximate Dec-POMDP Solving Using Multi-Agent A*
Wietze Koops, Sebastian Junges, Nils Jansen
Abstract
We present an A*-based algorithm to compute policies for finite-horizon Dec-POMDPs. Our goal is to sacrifice optimality in favor of scalability for larger horizons. The main ingredients of our approach are (1) using clustered sliding window memory, (2) pruning the A* search tree, and (3) using novel A* heuristics. Our experiments show competitive performance to the state-of-the-art. Moreover, for multiple benchmarks, we achieve superior performance. In addition, we provide an A* algorithm that finds upper bounds for the optimum, tailored towards problems with long horizons. The main ingredient is a new heuristic that periodically reveals the state, thereby limiting the number of reachable beliefs. Our experiments demonstrate the efficacy and scalability of the approach.
BibTeX
@inproceedings{ijcai2024p745,
title = {Approximate Dec-POMDP Solving Using Multi-Agent A*},
author = {Koops, Wietze and Junges, Sebastian and Jansen, Nils},
booktitle = {Proceedings of the Thirty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-24}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Kate Larson},
pages = {6743--6751},
year = {2024},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2024/745},
url = {https://doi.org/10.24963/ijcai.2024/745},
}