Coevolutive planning in markov decision processes

ABSTRACT

We investigate the idea of having groups of agents coevolving in order to iteratively refine multi-agent plans. This idea we called coevolution is formalized and analyzed in a general purpose and applied to the stochastic control frameworks that use an explicit model of the world,: coevolution can directly be adapted to the frameworks of Multi-Agent Markov Decision Processes (MMDP) and Multi-Agent Partially Observable MDP (MPOMDP). We also consider the decentralized version of MPOMDP (DEC-POMDP) which is known to be a difficult problem,: we show that the coevolution approach can be applied if we restrict the search to memoryless policies. We evaluate our coevolutive approach experimentally on a typical multi-agent problem.

REFERENCES

• 1: J. Baxter and P. Bartlett. Direct gradient-based reinforcement learning. Technical report, Research School of Information Sciences and Engineering, Australian National University, July 1999
• 2: 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
• 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: Iadine Chades , Bruno Scherrer , François Charpillet, A heuristic approach for solving decentralized-POMDP: assessment on the pursuit problem, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508804]
• 5: Leonid Peshkin , Kee-Eung Kim , Nicolas Meuleau , Leslie Pack Kaelbling, Learning to Cooperate via Policy Search, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.489-496, June 30-July 03, 2000
• 6: M. Puterman. Markov decision processes, 1994
• 7: E. J. Sondik. The Optimal Control of Partially Observable Markov Decision Processes. PhD thesis, Stanford University, California, 1971
• 8: C. Watkins and P. Dayan. Machine learning, 1992

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
action selection and planning, coordinating multi-agent & activites, evolution adaptation and learning, markov decision processes