Decentralized control of multi-robot partially observable Markov decision processes using belief space macro-actions
Abstract
This work focuses on solving general multi-robot planning problems in continuous spaces with partial observability given a high-level domain description. Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) are general models for multi-robot coordination problems. However, representing and solving Dec-POMDPs is often intractable for large problems. This work extends the Dec-POMDP model to the Decentralized Partially Observable Semi-Markov Decision Process (Dec-POSMDP) to take advantage of the high-level representations that are natural for multi-robot problems and to facilitate scalable solutions to large discrete and continuous problems. The Dec-POSMDP formulation uses task macro-actions created from lower-level local actions that allow for asynchronous decision-making by the robots, which is crucial in multi-robot domains. This transformation from Dec-POMDPs to Dec-POSMDPs with a finite set of automatically-generated macro-actions allows use of efficient discrete-space search algorithms to solve them. The paper presents algorithms for solving Dec-POSMDPs, which are more scalable than previous methods since they can incorporate closed-loop belief space macro-actions in planning. These macro-actions are automatically constructed to produce robust solutions. The proposed algorithms are then evaluated on a complex multi-robot package delivery problem under uncertainty, showing that our approach can naturally represent realistic problems and provide high-quality solutions for large-scale problems.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 01, 2017
- Source ID
- 10.1177/0278364917692864
Entities
People
- Ali‐akbar Agha‐mohammadi
- Christopher Amato
- John Vian
- Jonathan How
- Shayegan Omidshafiei
- Shih–yuan Liu
Organizations
- Boeing
- Massachusetts Institute of Technology
- Office of Naval Research
- University of New Hampshire