Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
12-2012
Abstract
Multi-agent planning is a well-studied problem with various applications including disaster rescue, urban transportation and logistics, both for autonomous agents and for decision support to humans. Due to computational constraints, existing research typically focuses on one of two scenarios: unstructured domains with many agents where we are content with heuristic solutions, or domains with small numbers of agents or special structure where we can provide provably near-optimal solutions. By contrast, in this paper, we focus on providing provably near-optimal solutions for domains with large numbers of agents, by exploiting a common domain-general property: if individual agents each have limited influence on the overall solution quality, then we can take advantage of randomization and the resulting statistical concentration to show that each agent can safely plan based only on the average behavior of the other agents. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs, (b) a proof of convergence of our algorithm to a near-optimal solution. We demonstrate the scalability of our approach with a large-scale illustrative theme park crowd management problem.
Keywords
Gradient Descent, Lagrangian Relaxation, Multi-Agent Systems
Discipline
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Intelligent Systems and Optimization
Publication
2012 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2012: Proceedings, Macau, December 4-7
First Page
494
Last Page
501
ISBN
9780769548807
Identifier
10.1109/WI-IAT.2012.252
Publisher
IEEE
City or Country
Piscataway, NJ
Citation
GORDON, Geoffrey J.; VARAKANTHAM, Pradeep; YEOH, William; LAU, Hoong Chuin; ARAVAMUDHAN, Ajay S.; and CHENG, Shih-Fen.
Lagrangian relaxation for large-scale multi-agent planning. (2012). 2012 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2012: Proceedings, Macau, December 4-7. 494-501.
Available at: https://ink.library.smu.edu.sg/sis_research/4364
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/WI-IAT.2012.252
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons