Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs

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.

Authors

• Shayegan Omidshafiei
• Ali-Akbar Agha-Mohammadi
• Christopher Amato
• Shih-Yuan Liu
• Jonathan P. How
• John Vian

Keywords

• Decision making
• History
• Probabilistic logic
• Uncertainty
• Robot sensing systems
• Synchronization
• Cross-entropy
• Cross-entropy Method
• Optimal Combination
• Markov Decision Process
• Decision-making Framework
• Decision-making Under Uncertainty
• Package Delivery
• Learning Rate
• State Space
• Probability Density Function
• Transition Probabilities
• Local Optimum
• Parameter Vector
• Joint Action
• Optimal Policy
• State Machine
• Convergence Time
• Transition Function
• Decision-making Problems
• Joint State
• Joint Policy
• Monte Carlo Search
• Ground Robots
• Aerial Robots
• Set Of Robots
• Graph Size
• Swarm Robotics
• Collective Policy
• Solution Quality
• Continuous State Space