Winning back the CUP for Distributed POMDPs: Planning over continuous belief spaces

Distributed Partially Observable Markov Decision Problems (Distributed POMDPs) are evolving as a popular approach for modeling multiagent systems, and many different algorithms have been proposed to obtain locally or globally optimal policies. Unfortunately, most of these algorithms have either been...

Full description

Saved in:
Bibliographic Details
Main Authors: VARAKANTHAM, Pradeep, Nair, Ranjit, Tambe, Milind, Yokoo, Makoto
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2006
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/940
https://ink.library.smu.edu.sg/context/sis_research/article/1939/viewcontent/AAMAS2006.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-1939
record_format dspace
spelling sg-smu-ink.sis_research-19392016-05-17T07:21:11Z Winning back the CUP for Distributed POMDPs: Planning over continuous belief spaces VARAKANTHAM, Pradeep Nair, Ranjit Tambe, Milind Yokoo, Makoto Distributed Partially Observable Markov Decision Problems (Distributed POMDPs) are evolving as a popular approach for modeling multiagent systems, and many different algorithms have been proposed to obtain locally or globally optimal policies. Unfortunately, most of these algorithms have either been explicitly designed or experimentally evaluated assuming knowledge of a starting belief point, an assumption that often does not hold in complex, uncertain domains. Instead, in such domains, it is important for agents to explicitly plan over continuous belief spaces. This paper provides a novel algorithm to explicitly compute finite horizon policies over continuous belief spaces, without restricting the space of policies. By marrying an efficient single-agent POMDP solver with a heuristic distributed POMDP policy-generation algorithm, locally optimal joint policies are obtained, each of which dominates within a different part of the belief region. We provide heuristics that significantly improve the efficiency of the resulting algorithm and provide detailed experimental results. To the best of our knowledge, these are the first run-time results for analytically generating policies over continuous belief spaces in distributed POMDPs. 2006-05-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/940 info:doi/10.1145/1160633.1160683 https://ink.library.smu.edu.sg/context/sis_research/article/1939/viewcontent/AAMAS2006.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 Business 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
Business
Operations Research, Systems Engineering and Industrial Engineering
spellingShingle Artificial Intelligence and Robotics
Business
Operations Research, Systems Engineering and Industrial Engineering
VARAKANTHAM, Pradeep
Nair, Ranjit
Tambe, Milind
Yokoo, Makoto
Winning back the CUP for Distributed POMDPs: Planning over continuous belief spaces
description Distributed Partially Observable Markov Decision Problems (Distributed POMDPs) are evolving as a popular approach for modeling multiagent systems, and many different algorithms have been proposed to obtain locally or globally optimal policies. Unfortunately, most of these algorithms have either been explicitly designed or experimentally evaluated assuming knowledge of a starting belief point, an assumption that often does not hold in complex, uncertain domains. Instead, in such domains, it is important for agents to explicitly plan over continuous belief spaces. This paper provides a novel algorithm to explicitly compute finite horizon policies over continuous belief spaces, without restricting the space of policies. By marrying an efficient single-agent POMDP solver with a heuristic distributed POMDP policy-generation algorithm, locally optimal joint policies are obtained, each of which dominates within a different part of the belief region. We provide heuristics that significantly improve the efficiency of the resulting algorithm and provide detailed experimental results. To the best of our knowledge, these are the first run-time results for analytically generating policies over continuous belief spaces in distributed POMDPs.
format text
author VARAKANTHAM, Pradeep
Nair, Ranjit
Tambe, Milind
Yokoo, Makoto
author_facet VARAKANTHAM, Pradeep
Nair, Ranjit
Tambe, Milind
Yokoo, Makoto
author_sort VARAKANTHAM, Pradeep
title Winning back the CUP for Distributed POMDPs: Planning over continuous belief spaces
title_short Winning back the CUP for Distributed POMDPs: Planning over continuous belief spaces
title_full Winning back the CUP for Distributed POMDPs: Planning over continuous belief spaces
title_fullStr Winning back the CUP for Distributed POMDPs: Planning over continuous belief spaces
title_full_unstemmed Winning back the CUP for Distributed POMDPs: Planning over continuous belief spaces
title_sort winning back the cup for distributed pomdps: planning over continuous belief spaces
publisher Institutional Knowledge at Singapore Management University
publishDate 2006
url https://ink.library.smu.edu.sg/sis_research/940
https://ink.library.smu.edu.sg/context/sis_research/article/1939/viewcontent/AAMAS2006.pdf
_version_ 1770570777972703232