Lagrangian relaxation for large-scale multi-agent planning

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

Full description

Saved in:
Bibliographic Details
Main Authors: GORDON, Geoff, VARAKANTHAM, Pradeep, YEOH, William, LAU, Hoong Chuin, CHENG, Shih-Fen
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2012
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/1609
https://ink.library.smu.edu.sg/context/sis_research/article/2608/viewcontent/LR_IAT.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-2608
record_format dspace
spelling sg-smu-ink.sis_research-26082020-03-24T03:28:37Z Lagrangian relaxation for large-scale multi-agent planning GORDON, Geoff VARAKANTHAM, Pradeep YEOH, William LAU, Hoong Chuin CHENG, Shih-Fen 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. 2012-12-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/1609 info:doi/10.1109/WI-IAT.2012.252 https://ink.library.smu.edu.sg/context/sis_research/article/2608/viewcontent/LR_IAT.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Artificial Intelligence and Robotics Operations Research, Systems Engineering and Industrial Engineering
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Artificial Intelligence and Robotics
Operations Research, Systems Engineering and Industrial Engineering
spellingShingle Artificial Intelligence and Robotics
Operations Research, Systems Engineering and Industrial Engineering
GORDON, Geoff
VARAKANTHAM, Pradeep
YEOH, William
LAU, Hoong Chuin
CHENG, Shih-Fen
Lagrangian relaxation for large-scale multi-agent planning
description 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.
format text
author GORDON, Geoff
VARAKANTHAM, Pradeep
YEOH, William
LAU, Hoong Chuin
CHENG, Shih-Fen
author_facet GORDON, Geoff
VARAKANTHAM, Pradeep
YEOH, William
LAU, Hoong Chuin
CHENG, Shih-Fen
author_sort GORDON, Geoff
title Lagrangian relaxation for large-scale multi-agent planning
title_short Lagrangian relaxation for large-scale multi-agent planning
title_full Lagrangian relaxation for large-scale multi-agent planning
title_fullStr Lagrangian relaxation for large-scale multi-agent planning
title_full_unstemmed Lagrangian relaxation for large-scale multi-agent planning
title_sort lagrangian relaxation for large-scale multi-agent planning
publisher Institutional Knowledge at Singapore Management University
publishDate 2012
url https://ink.library.smu.edu.sg/sis_research/1609
https://ink.library.smu.edu.sg/context/sis_research/article/2608/viewcontent/LR_IAT.pdf
_version_ 1770571348318355456