Approximating state estimation in multiagent settings using particle filters

ABSTRACT

State estimation consists of updating an agent's belief given executed actions and observed evidence to date. In single agent environments, the state estimation can be formalized using the Bayes filter. Exact estimation can be performed in simple cases, but approximate techniques, like particle filtering, have been used in more realistic cases. This paper extends the particle filter to multiagent settings resulting in the interactive particle filter. The main difficulty we tackle is that to fully represent an agent's beliefs in such environments, one has to specify probability distributions over the physical state and over the beliefs of other agents. This leads to interactive hierarchical belief systems first developed in game theory. Since the update of such beliefs proceeds recursively, the interactive particle filter samples and propagates on all levels of the belief hierarchy. We present algorithms, discuss some of their properties, and illustrate the performance of our implementation using simple examples.

REFERENCES

• 1: R. J. Aumann and A. Heifetz. Handbook of Game Theory with Economic Applications, volume 3. Elsevier Science, 2002.
• 2: P. Battigalli and G. Bonanno. Recent results on belief, knowledge, and the epistemic foundations of game theory. Research in Economics, 53:149--225, 1999.
• 3: A. Brandenburger and E. Dekel. Hierarchies of beliefs and common knowledge. Journal of Economic Theory, 59:189--198, 1993.
• 4: A. Doucet, N. D. Freitas, and N. Gordon. Sequential Monte Carlo Methods in Practice. Springer Verlag, 2001.
• 5: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 6: Dieter Fox , Wolfram Burgard , Hannes Kruppa , Sebastian Thrun, A Probabilistic Approach to Collaborative Multi-Robot Localization, Autonomous Robots, v.8 n.3, p.325-344, June 2000 [doi>10.1023/A:1008937911390]
• 7: Piotr J. Gmytrasiewicz , Prashant Doshi, Interactive POMDPs: Properties and Preliminary Results, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1374-1375, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.154]
• 8: P. Gmytrasiewicz and P. Doshi. A framework for sequential planning in multiagent settings. Journal of AI Research, 23, 2005.
• 9: N. Gordon, D. Salmond, and A. Smith. Novel approach to non-linear/non-gaussian bayesian state estimation. IEEE Proceedings-F, 140(2):107--113, 1993.
• 10: J. C. Harsanyi. Games with incomplete information played by 'bayesian' players. Mgmt. Science, 14(3):159--182, 1967.
• 11: A. Heifetz and D. Samet. Topology-free typology of beliefs. Journal of Economic Theory, 82:324--341, 1998.
• 12: Leslie Pack Kaelbling , Michael L. Littman , Anthony R. Cassandra, Planning and acting in partially observable stochastic domains, Artificial Intelligence, v.101 n.1-2, p.99-134, May 1998 [doi>10.1016/S0004-3702(98)00023-X]
• 13: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 14: J. Mertens and S. Zamir. Formulation of bayesian analysis for games with incomplete information. International Journal of Game Theory, 14:1--29, 1985.
• 15: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 16: R. Smallwood and E. Sondik. The optimal control of partially observable markov decision processes over a finite horizon. Operations Research, 21:1071--1088, 1973.
• 17: S. Thrun. Monte carlo pomdps. In NIPS 12, pages 1064--1070, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Performance

Keywords:
approximation, bayesian learning, multiagent state estimation, particle filters