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...
Saved in:
Main Authors: | , , , , , |
---|---|
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 |
id |
sg-smu-ink.larc-1002 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.larc-10022022-02-08T08:17:08Z Lagrangian Relaxation for Large-Scale Multi-Agent Planning Gordon, Geoffrey J. VARAKANTHAM, Pradeep YEOH, William LAU, Hoong Chuin Aravamudhan, Ajay Srinivasan CHENG, Shih-Fen 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. 2012-06-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/larc/3 https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1002&context=larc http://creativecommons.org/licenses/by-nc-nd/4.0/ LARC Research Publications eng Institutional Knowledge at Singapore Management University Multi-agent Planning Lagrangian Relaxation Artificial Intelligence and Robotics Theory and Algorithms |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Multi-agent Planning Lagrangian Relaxation Artificial Intelligence and Robotics Theory and Algorithms |
spellingShingle |
Multi-agent Planning Lagrangian Relaxation Artificial Intelligence and Robotics Theory and Algorithms Gordon, Geoffrey J. VARAKANTHAM, Pradeep YEOH, William LAU, Hoong Chuin Aravamudhan, Ajay Srinivasan CHENG, Shih-Fen Lagrangian Relaxation for Large-Scale Multi-Agent Planning |
description |
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. |
format |
text |
author |
Gordon, Geoffrey J. VARAKANTHAM, Pradeep YEOH, William LAU, Hoong Chuin Aravamudhan, Ajay Srinivasan CHENG, Shih-Fen |
author_facet |
Gordon, Geoffrey J. VARAKANTHAM, Pradeep YEOH, William LAU, Hoong Chuin Aravamudhan, Ajay Srinivasan CHENG, Shih-Fen |
author_sort |
Gordon, Geoffrey J. |
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/larc/3 https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1002&context=larc |
_version_ |
1745574975609241600 |