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...
| Main Authors: | , , , , , |
|---|---|
| Outros Autores: | |
| Formato: | Artigo |
| Idioma: | en_US |
| Publicado em: |
Institute of Electrical and Electronics Engineers (IEEE)
2016
|
| Acesso em linha: | http://hdl.handle.net/1721.1/105797 https://orcid.org/0000-0003-0903-0137 https://orcid.org/0000-0002-9838-1221 https://orcid.org/0000-0001-8576-1930 |
| _version_ | 1826215497910190080 |
|---|---|
| author | Agha-mohammadi, Ali-akbar Amato, Christopher Vian, John Omidshafiei, Shayegan Liu, Shih-Yuan How, Jonathan P |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Agha-mohammadi, Ali-akbar Amato, Christopher Vian, John Omidshafiei, Shayegan Liu, Shih-Yuan How, Jonathan P |
| author_sort | Agha-mohammadi, Ali-akbar |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:32:02Z |
| format | Article |
| id | mit-1721.1/105797 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:32:02Z |
| publishDate | 2016 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1057972022-09-29T20:05:13Z Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs Agha-mohammadi, Ali-akbar Amato, Christopher Vian, John Omidshafiei, Shayegan Liu, Shih-Yuan How, Jonathan P Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Omidshafiei, Shayegan Liu, Shih-Yuan How, Jonathan P 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. Boeing Company 2016-12-12T20:21:36Z 2016-12-12T20:21:36Z 2016-05 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-8026-3 http://hdl.handle.net/1721.1/105797 Omidshafiei, Shayegan et al. “Graph-Based Cross Entropy Method for Solving Multi-Robot Decentralized POMDPs.” IEEE, 2016. 5395–5402. https://orcid.org/0000-0003-0903-0137 https://orcid.org/0000-0002-9838-1221 https://orcid.org/0000-0001-8576-1930 en_US http://dx.doi.org/10.1109/ICRA.2016.7487751 IEEE International Conference on Robotics and Automation, 2016. '16 ICRA Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Other univ. web domain |
| spellingShingle | Agha-mohammadi, Ali-akbar Amato, Christopher Vian, John Omidshafiei, Shayegan Liu, Shih-Yuan How, Jonathan P Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs |
| title | Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs |
| title_full | Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs |
| title_fullStr | Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs |
| title_full_unstemmed | Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs |
| title_short | Graph-based Cross Entropy method for solving multi-robot decentralized POMDPs |
| title_sort | graph based cross entropy method for solving multi robot decentralized pomdps |
| url | http://hdl.handle.net/1721.1/105797 https://orcid.org/0000-0003-0903-0137 https://orcid.org/0000-0002-9838-1221 https://orcid.org/0000-0001-8576-1930 |
| work_keys_str_mv | AT aghamohammadialiakbar graphbasedcrossentropymethodforsolvingmultirobotdecentralizedpomdps AT amatochristopher graphbasedcrossentropymethodforsolvingmultirobotdecentralizedpomdps AT vianjohn graphbasedcrossentropymethodforsolvingmultirobotdecentralizedpomdps AT omidshafieishayegan graphbasedcrossentropymethodforsolvingmultirobotdecentralizedpomdps AT liushihyuan graphbasedcrossentropymethodforsolvingmultirobotdecentralizedpomdps AT howjonathanp graphbasedcrossentropymethodforsolvingmultirobotdecentralizedpomdps |