I have moved to Delft University of Technology.

Home
Contact
Collaborators
Publications
Research
Projects
    MAIS-S
    DecPUCS
    PCMMC
    URUS
Resources
    Software
    Dec-POMDP
Activities
    Workshops
    Tutorials
    Events
    Reading group
Miscellaneous
    Personal

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

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.

DecTiger
Horizon Optimal value First solved by Notes
2-4.000000(NTYPM2003)
35.190812(SCZ2005)1)
44.802755(SCZ2005)
57.026451(OWS2009)
610.381625(SOA2011)
BroadcastChannel
Horizon Optimal value First solved by Notes
2 2.000000 (HBZ2004)
3 2.990000 (HBZ2004)
4 3.890000 (HBZ2004)
5 4.790000 (SC2006)
6 5.690000 (OWS2009)
7 6.590000 (OWS2009)
8 7.490000 (OWS2009)
9 8.390000 (OWS2009)
109.290000 (OWS2009)
1513.790000(OWS2009)
2018.313228(OWS2009)
2522.881523(OWS2009)
3027.421850(SOA2011)
5045.501604(SOA2011)
10090.760423(SOA2011)
250226.500545(SOA2011)
500452.738119(SOA2011)
600543.228071(SOA2011)
700633.724279(SOA2011)
900814.709393(SOA2011)
GridSmall
Horizon Optimal value First solved by Notes
2 0.910000 (OSV2008)
3 1.550444 (OSV2008)
4 2.241577 (OWS2009)
52.970496(SOA2011)
63.717168(SOA2011)
One Door
Horizon Optimal value First solved by Notes
2 0.000000 unpublished
3 -0.000395 unpublished
4 -0.001682unpublished
Cooperative Box Pushing
Horizon Optimal value First solved by Notes
2 17.600000 (OWS2009)
3 66.081000 (OWS2009)
4 98.593613 (ADZ2009)
Recycling Robots
Horizon Optimal value First solved by Notes
2 7.000000(OWS2009)3)
3 10.660125(OWS2009)3)
4 13.380000(OWS2009)3)
5 16.486000(OWS2009)3)
6 19.554200(OWS2009)3)
7 22.633740(OWS2009)3)
8 25.709878(OWS2009)3)
9 28.787037(OWS2009)3)
10 31.863889(OWS2009)3)
11 34.940833(OWS2009)3)
12 38.017750(OWS2009)3)
13 41.094675(OWS2009)3)
14 44.171598(OWS2009)3)
15 47.248521(OWS2009)3)
2062.633136(SOA2011)
3093.402367(SOA2011)
40124.171598(SOA2011)
50154.940828(SOA2011)
60185.710059(SOA2011)
70216.479290(SOA2011)
Fire Fighting (3 houses, 3 fire levels)
Horizon Optimal value First solved by Notes
2-4.383496 (OSV2008)4)
3-5.736969 (OSV2008)
4-6.578834(OWS2009)
5-7.069874(SOA2011)
6-7.175591(SOA2011)
Mars Rovers
Horizon Optimal value First solved by Notes
2 5.800000 (ADZ2009) (OWS2009) 2)
3 9.380000 (ADZ2009) (OWS2009) 2)
410.180800 (OWS2009) 2)
Meeting in a 3x3 grid
Horizon Optimal value First solved by Notes
2 0.000000(ADZ2009) (OWS2009) 2)
3 0.133200 (ADZ2009) (OWS2009) 2)
4 0.433 (ADZ2009)
5 0.896 (ADZ2009)
Hotel 1
Horizon Optimal value First solved by Notes
2 10.000000 (OWS2009)3)
3 16.875000 (OWS2009)3)
4 22.187500 (OWS2009)3)
527.187500(SOA2011)
632.187500(SOA2011)
737.187500(SOA2011)
842.187500(SOA2011)
947.187500(SOA2011)
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)