Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
6-2012
Abstract
Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on 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 find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limits. 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.
Keywords
Multi-agent Planning, Lagrangian Relaxation
Discipline
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Publication
Proceedings of the 11th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2012), 4-8 June, Valencia, Spain
First Page
1227
Last Page
1228
ISBN
9780981738130
Identifier
10.1109/WI-IAT.2012.252
Publisher
ACM
City or Country
Valencia, Spain
Citation
GORDON, Geoff; VARAKANTHAM, Pradeep Reddy; YEOH, William; SRINIVASAN, Ajay; LAU, Hoong Chuin; and CHENG, Shih-Fen.
Lagrangian relaxation for large-scale multi-agent planning. (2012). Proceedings of the 11th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2012), 4-8 June, Valencia, Spain. 1227-1228.
Available at: https://ink.library.smu.edu.sg/sis_research/1565
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, Business Commons, Operations Research, Systems Engineering and Industrial Engineering Commons