Dec-POMDP problem domains
On this page we are collecting a number of Dec-POMDP problem
descriptions, to create a repository containing several standard
problem domains that can be used for benchmarking. Contributions are
welcome. The models are provided in the .dpomdp file format, which is
an extension of Tony's POMDP file
format. The file format is explained in example.dpomdp, and can be used in the Multiagent
decision process (MADP) Toolbox, which contains a parser for
it. More information about this software toolbox can be found on its
homepage
or in this MSDM
2008 paper.
Below we also provide a list of known
optimal values.
General Dec-POMDPs
-
dectiger.dpomdp, the Decentralized Tiger
problem, introduced in (Nair, Tambe, Yokoo, Pynadath &
Marsella, IJCAI 2003).
-
broadcastChannel.dpomdp, the
Broadcast Channel
problem, introduced in (Hansen, Bernstein &
Zilberstein, AAAI 2004).
-
GridSmall.dpomdp, the Meeting in a 2x2
Grid problem, originally from (Bernstein, Hansen & Zilberstein, IJCAI
2005), this is the two observations per agent version of (Amato,
Bernstein & Zilberstein, AAMAS Workshop on Multi-Agent Sequential
Decision Making in Uncertain Domains (MSDM) 2006).
-
oneDoor_2_7_0.20_0.00_0_2.dpomdp,
the One Door problem, introduced in (Oliehoek, Spaan & Vlassis, AAMAS
Workshop on Multi-Agent Sequential Decision Making in Uncertain
Domains (MSDM) 2007). Other versions of this problem are available
upon request.
-
boxPushingUAI07.dpomdp, the
Cooperative Box Pushing problem, introduced in (Seuken &
Zilberstein, UAI 2007).
-
recycling.dpomdp, the
Recycling Robots problem, introduced in (Amato, Bernstein &
Zilberstein, UAI 2007).
-
fireFighting_2_3_3.dpomdp.gz,
the Fire Fighting problem with 3 houses and 3 fire levels, introduced
in (Oliehoek, Spaan & Vlassis, JAIR 2008).
-
fireFighting_2_4_3.dpomdp.gz,
the Fire Fighting problem with 4 houses and 3 fire levels, introduced
in (Oliehoek, Spaan & Vlassis, JAIR 2008).
-
Mars.dpomdp,
the Mars rover problem, introduced in (Amato & Zilberstein, AAMAS 2009).
-
Grid3x3corners.dpomdp,
the Meeting in a 3x3 grid problem, introduced
in (Amato, Dibangoye & Zilberstein, ICAPS 2009).
Transition and observation independent Dec-POMDPs
-
hotel1.tar.gz, hotel2.tar.gz, the two Hotel
problems introduced in (Spaan & Melo, AAMAS 2008).
-
ISR_2.tar.gz, Pent_2.tar.gz, MIT_2.tar.gz, SUNY_2.tar.gz, CIT_2.tar.gz, CMU_2.tar.gz,
the two-robot navigation problems introduced in (Spaan & Melo, AAMAS
2008), inspired by Tony Cassandra's single-agent navigation domains.
Optimal values
Here we provide the value of an optimal solution for some
of above problems for several horizons, which can for
instance be used to benchmark approximate solutions. The
table also notes in which papers the problem had been
first solved optimally for a given horizon. Note that
values reported are for the undiscounted setting, i.e.,
the discount factor (often denoted by gamma) was set to
1.0, overriding sometimes the discount factor specified in
the .dpomdp files. This explains discrepancies with some
of the cited papers. In most cases the reported values
have been computed using GMAA*-Cluster (OWS2009), otherwise they have been
copied from the referred paper.
For the highest known values for the infinite-horizon
case, see the Problem
description page at UMass.
To report errors, mistakes, additions, omissions, "prior art" with respect to
the "first solved by" column, please send an email to
Matthijs Spaan.
Notes:
1) In (NTYPM2003) an incorrect optimal value for DecTiger h=3 was presented.
2) The (ADZ2009) paper included new results obtained using the algorithm presented in (OWS2009).
3) In these cases the results reported in the referred paper concern a different discount factor (usually as stated in the problem definition).
4) In (OWS2009) a typo in the third decimal was published for Fire
Fighting h=2 (-4.3825 instead of the correct -4.3835).
References
NTYPM2003 (Nair, Tambe, Yokoo, Pynadath & Marsella, IJCAI 2003)
HBZ2004 (Hansen, Bernstein & Zilberstein, AAAI 2004)
SCZ2005 (Szer, Charpillet & Zilberstein, UAI 2005)
SC2006 (Szer & Charpillet, AAAI 2006)
OSV2008 (Oliehoek, Spaan & Vlassis, JAIR 2008)
OWS2009 (Oliehoek, Whiteson & Spaan, AAMAS 2009)
ADZ2009 (Amato, Dibangoye & Zilberstein, ICAPS 2009)
SOA2011 (Spaan, Oliehoek & Amato, IJCAI 2011)
|
