Heuristic Search of Multiagent Influence Space
Multiagent planning under uncertainty has seen important progress in recent years. Two techniques, in particular, have substantially advanced efficiency and scalability of planning. Multiagent heuristic search gains traction by pruning large portions of the joint policy space deemed suboptimal by he...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100717 https://orcid.org/0000-0001-6054-7145 |
| _version_ | 1826189067239292928 |
|---|---|
| author | Witwicki, Stefan J. Oliehoek, Frans A. Kaelbling, Leslie P. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Witwicki, Stefan J. Oliehoek, Frans A. Kaelbling, Leslie P. |
| author_sort | Witwicki, Stefan J. |
| collection | MIT |
| description | Multiagent planning under uncertainty has seen important progress in recent years. Two techniques, in particular, have substantially advanced efficiency and scalability of planning. Multiagent heuristic search gains traction by pruning large portions of the joint policy space deemed suboptimal by heuristic bounds. Alternatively, influence-based abstraction reformulates the search space of joint policies into a smaller space of influences, which represent the probabilistic effects that agents' policies may exert on one another. These techniques have been used independently, but never together, to solve larger problems (for Dec-POMDPs and subclasses) than previously possible. In this paper, we take the logical albeit nontrivial next step of combining multiagent A* search and influence-based abstraction into a single algorithm. The mathematical foundation that we provide, such as partially-specified influence evaluation and admissible heuristic definition, enables an investigation into whether the two techniques bring complementary gains. Our empirical results indicate that A* can provide significant computational savings on top of those already afforded by influence-space search, thereby bringing a significant contribution to the field of multiagent planning under uncertainty. |
| first_indexed | 2024-09-23T08:09:20Z |
| format | Article |
| id | mit-1721.1/100717 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:09:20Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1007172022-09-30T07:57:24Z Heuristic Search of Multiagent Influence Space Witwicki, Stefan J. Oliehoek, Frans A. Kaelbling, Leslie P. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Oliehoek, Frans A. Kaelbling, Leslie P. Multiagent planning under uncertainty has seen important progress in recent years. Two techniques, in particular, have substantially advanced efficiency and scalability of planning. Multiagent heuristic search gains traction by pruning large portions of the joint policy space deemed suboptimal by heuristic bounds. Alternatively, influence-based abstraction reformulates the search space of joint policies into a smaller space of influences, which represent the probabilistic effects that agents' policies may exert on one another. These techniques have been used independently, but never together, to solve larger problems (for Dec-POMDPs and subclasses) than previously possible. In this paper, we take the logical albeit nontrivial next step of combining multiagent A* search and influence-based abstraction into a single algorithm. The mathematical foundation that we provide, such as partially-specified influence evaluation and admissible heuristic definition, enables an investigation into whether the two techniques bring complementary gains. Our empirical results indicate that A* can provide significant computational savings on top of those already afforded by influence-space search, thereby bringing a significant contribution to the field of multiagent planning under uncertainty. Fundacao para a Ciencia e a Tecnologia Carnegie Mellon Portugal Program (Project CMU-PT/SIA/0023/2009) United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (Project FA9550-09-1-0538) NWO of the Netherlands (CATCH Project 640.005.003) 2016-01-06T14:51:29Z 2016-01-06T14:51:29Z 2012-06 Article http://purl.org/eprint/type/ConferencePaper 978-0-9817381-2-3 http://hdl.handle.net/1721.1/100717 Stefan J. Witwicki, Frans A. Oliehoek, and Leslie P. Kaelbling. 2012. Heuristic search of multiagent influence space. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2 (AAMAS '12), Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 973-980. https://orcid.org/0000-0001-6054-7145 en_US http://dl.acm.org/citation.cfm?id=2343836 Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '12) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Witwicki, Stefan J. Oliehoek, Frans A. Kaelbling, Leslie P. Heuristic Search of Multiagent Influence Space |
| title | Heuristic Search of Multiagent Influence Space |
| title_full | Heuristic Search of Multiagent Influence Space |
| title_fullStr | Heuristic Search of Multiagent Influence Space |
| title_full_unstemmed | Heuristic Search of Multiagent Influence Space |
| title_short | Heuristic Search of Multiagent Influence Space |
| title_sort | heuristic search of multiagent influence space |
| url | http://hdl.handle.net/1721.1/100717 https://orcid.org/0000-0001-6054-7145 |
| work_keys_str_mv | AT witwickistefanj heuristicsearchofmultiagentinfluencespace AT oliehoekfransa heuristicsearchofmultiagentinfluencespace AT kaelblinglesliep heuristicsearchofmultiagentinfluencespace |