Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs
Shayegan Omidshafiei, Ali-akbar Agha-mohammadi, Christopher Amato, Shih-Yuan Liu, Jonathan P. How, John Vian
Abstract
This paper introduces a probabilistic algorithm for multi-robot decision-making under uncertainty, which can be posed as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP). Dec-POMDPs are inherently synchronous decision-making frameworks which require significant computational resources to be solved, making them infeasible for many real-world robotics applications. The Decentralized Partially Observable Semi-Markov Decision Process (Dec-POSMDP) was recently introduced as an extension of the Dec-POMDP that uses high-level macro-actions to allow large-scale, asynchronous decision-making. However, existing Dec-POSMDP solution methods have limited scalability or perform poorly as the problem size grows. This paper proposes a cross-entropy based Dec-POSMDP algorithm motivated by the combinatorial optimization literature. The algorithm is applied to a constrained package delivery domain, where it significantly outperforms existing Dec-POSMDP solution methods.
BibTeX
@inproceedings{icra2016_graphbasedcrosse,
title = {Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs},
author = {Shayegan Omidshafiei and Ali-akbar Agha-mohammadi and Christopher Amato and Shih-Yuan Liu and Jonathan P. How and John Vian},
booktitle = {ICRA 2016},
year = {2016}
}