A multi-resolution pyramid for outdoor robot terrain perception.

R. Emery-Montemerlo, G. Gordon, J. Schneider, and S. Thrun.

Partially observable decentralized decision making in robot teams is fundamentally different from decision making in fully observable problems. Team members cannot simply apply single-agent solution techniques in parallel. Instead, we must turn to game theoretic frameworks to correctly model the problem. While partially observable stochastic games (POSGs) provide a solution model for decentralized robot teams, this model quickly becomes intractable. We propose an algorithm that approximates POSGs as a series of smaller, related Bayesian games, using heuristics such as QMDP to provide the future discounted value of actions. This algorithm trades off limited look-ahead in uncertainty for computational feasibility, and results in policies that are locally optimal with respect to the selected heuristic. Empirical results are provided for both a simple problem for which the full POSG can also be constructed, as well as more complex, robot-inspired, problems.

The full paper is available in PDF and gzipped Postscript

@INPROCEEDINGS{EmeryMontemerlo04a,
  AUTHOR	= {Emery-Montemerlo, R. and Gordon, G. and Schneider, J. and Thrun, S.},
  TITLE		= {Approximate Solutions For Partially Observable Stochastic Games With Common Payoffs},
  YEAR		= {2004},
  BOOKTITLE	= {Proceedings of Autonomous Agents and Multi-Agent Systems},
  ADDRESS	= {New York, NY}
}