A heuristic approach for solving decentralized-POMDP: assessment on the pursuit problem

ABSTRACT

Defining the behaviour of a set of situated agents, such that a collaborative problem can be solved is a key issue in multi-agent systems. In this paper, we formulate this problem from the decision theoretic perspective using the framework of Decentralized Partially Observable Markov Decision Processes (DEC-POMDP). Formulating the coordination problem in this way provides a formal foundation for study of cooperation activities. But, as it has been recently shown solving DEC-POMDP is NEXP-complete and thus it is not a realistic approach for the design of agent cooperation policies. However, we demonstrate in this paper that it is not completely desperate. Indeed, we propose an heuristic approach for solving DEC-POMDP when agents are memory-less and when the global reward function can be broken up into a sum of local reward functions. We demonstrate experimentally on an example (the so-called pursuit problem) that this heuristic is efficient within a few iteration steps.

REFERENCES

• 1: Daniel S. Bernstein , Shlomo Zilberstein , Neil Immerman, The Complexity of Decentralized Control of Markov Decision Processes, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.32-37, June 30-July 03, 2000
• 2: E. Bonabeau, M. Dorigo, and G. Theraulaz. Inspiration for optimization from social insect behaviour, 2000.
• 3: Craig Boutilier, Sequential Optimality and Coordination in Multiagent Systems, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.478-485, July 31-August 06, 1999
• 4: Michael Lederman Littman, Algorithms for sequential decision-making, 1996
• 5: M. Puterman. Markov decision processes, 1994.
• 6: Peter Stone , Manuela Veloso, Multiagent Systems: A Survey from a Machine Learning Perspective, Autonomous Robots, v.8 n.3, p.345-383, June 2000 [doi>10.1023/A:1008942012299]
• 7: P. Xuan, V. Lesser, and S. Zilberstein. Formal modeling of communication decisions in cooperative multi-agent systems. In The Second Workshop on Game Theoric and Decision Theoric Agents, 2000.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
decision theoretic agents, multiagent systems