Lagrangian Relaxation for Large-Scale Multi-Agent Planning

Author

Geoffrey J. Gordon, Carnegie Mellon University
Pradeep VARAKANTHAM, Singapore Management UniversityFollow
William YEOH, Singapore Management UniversityFollow
Hoong Chuin LAU, Singapore Management UniversityFollow
Ajay Srinivasan Aravamudhan, Singapore Management UniversityFollow
Shih-Fen CHENG, Singapore Management UniversityFollow

Publication Type

Report

Version

publishedVersion

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 limit. 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 | Theory and Algorithms

First Page

1

Last Page

5

Publisher

Singapore Management University, LARC

City or Country

Singapore

Embargo Period

4-4-2014

Citation

Gordon, Geoffrey J.; VARAKANTHAM, Pradeep; YEOH, William; LAU, Hoong Chuin; Aravamudhan, Ajay Srinivasan; and CHENG, Shih-Fen. Lagrangian Relaxation for Large-Scale Multi-Agent Planning. (2012). 1-5.
Available at: https://ink.library.smu.edu.sg/larc/3

Copyright Owner and License

Authors / LARC

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.