Lagrangian Relaxation for Large-Scale Multi-Agent Planning

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Gordon, Geoffrey J., VARAKANTHAM, Pradeep, YEOH, William, LAU, Hoong Chuin, Aravamudhan, Ajay Srinivasan, CHENG, Shih-Fen
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2012
Subjects:
Online Access:https://ink.library.smu.edu.sg/larc/3
https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1002&context=larc
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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.