Publication Type

Conference Proceeding Article

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

Research Areas

Intelligent Systems and Decision Analytics

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

Publisher

ACM

City or Country

Valencia, Spain

Creative Commons License

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

Additional URL

http://dl.acm.org/citation.cfm?id=2343896.2343935