Multiagent coordination by Extended Markov Tracking

ABSTRACT

We present here Extended Markov Tracking (EMT), a computationally tractable method for the online estimation of Markovian system dynamics, along with experimental support for its successful contribution to a specific control architecture. The control architecture leverages EMT to simultaneously track and correct system dynamics.Using a widespread extension of the Markovian environment model to multiagent systems, we provide an application of EMT-based control to multiagent coordination. The resulting coordinated action algorithm, in contrast to alternative approaches, does not eliminate interference among agents, but rather exploits it for purposes of synchronization and implicit information transfer. This information transfer enables the algorithm to be computationally tractable. Experiments are presented that demonstrate the effectiveness of EMT-based control for multiagent coordination in stochastic environments.

REFERENCES

• 1: Daniel S. Bernstein , Robert Givan , Neil Immerman , Shlomo Zilberstein, The Complexity of Decentralized Control of Markov Decision Processes, Mathematics of Operations Research, v.27 n.4, p.819-840, November 2002 [doi>10.1287/moor.27.4.819.297]
• 2: Vincent D. Blondel and John N. Tsitsiklis. A survey of computational complexity results in systems and control. Automatica, 36(9):1249--1274, September 2000.
• 3: Frederic Bourgault, Alexei A. Makarenko, Stephan B. Williams, Ben Grocholsky, and Hugh Durrant-Whyte. Information based adaptive robotic exploration. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2002.
• 4: Craig Boutilier, Thomas Dean, and Steve Hanks. Decision-theoretic planning: structural assumptions and computational leverage. Journal of Artificial Intelligence Research (JAIR), 11:1--94, 1999.
• 5: Hung H. Bui. A general model for online probabilistic plan recognition. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), pages 1309--1315, 2003.
• 6: Anthony R. Cassandra. POMDP solver software. http://www.cassandra.org/pomdp/code/index.shtml, 2003.
• 7: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 8: Richard E. Fikes and Nils J. Nilsson. STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189--208, 1971.
• 9: Claudia V. Goldman and Shlomo Zilberstein. Decentralized control of cooperative systems: Categorization and complexity analysis. Journal of Artificial Intelligence Research (JAIR), 22:143--174, November 2004.
• 10: Ben Grocholsky, Alexei Makarenko, and Hugh Durrant-Whyte. Information-theoretic coordinated control of multiple sensor platforms. In IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, 2003.
• 11: Michael L. Littman. Value-function reinforcement learning in Markov games. Journal of Cognitive Research, 2:55--66, 2001.
• 12: Omid Madani , Steve Hanks , Anne Condon, On the undecidability of probabilistic planning and related stochastic optimization problems, Artificial Intelligence, v.147 n.1-2, p.5-34, July 2003 [doi>10.1016/S0004-3702(02)00378-8]
• 13: Dana S. Nau , Stephen J. J. Smith , Kutluhan Erol, Control strategies in HTN planning: theory versus practice, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.1127-1133, July 1998, Madison, Wisconsin, United States
• 14: Martin L. Puterman. Markov Decision Processes. Wiley-Interscience Publication, 1994.
• 15: David V. Pynadath and Milind Tambe. The communicative multiagent team decision problem: Analyzing teamwork theories and models. Journal of Artificial Intelligence Research (JAIR), 16:389--423, 2002.
• 16: David V. Pynadath , Michael P. Wellman, Probabilistic State-Dependent Grammars for Plan Recognition, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.507-514, June 30-July 03, 2000
• 17: Zinovi Rabinovich. Non-approximability of centralized control in distributed systems. Master's thesis, Computer Science, Hebrew University, Jerusalem, Israel, January 2002.
• 18: Patrick Riley , Manuela M. Veloso, Recognizing Probabilistic Opponent Movement Models, RoboCup 2001: Robot Soccer World Cup V, p.453-458, January 2002
• 19: Noam Slonim and Naftali Tishby. Agglomerative information bottlenecks. In Advances in Neural Information Processing Systems (NIPS-12), pages 617--623. MIT Press, 2000.
• 20: Naftali Tishby, Fernando C. Pereira, and William Bialek. The information bottleneck method. In The 37th Annual Allerton Conference on Computation, Control and Computing, pages 368--377, 1999.
• 21: Manuela M. Veloso, Jaime Carbonell, Alicia Prez, Daniel Borrajo, Eugene Fink, and Jim Blythe. Integrating planning and learning: The PRODIGY architecture. Journal of Experimental and Theoretical Artificial Intelligence (JETAI), 7(1):81--120, 1995.
• 22: Richard Washington, Markov tracking for agent coordination, Proceedings of the second international conference on Autonomous agents, p.70-77, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280777]
• 23: D. H. Wolpert. Product distribution field theory, 2003.
• 24: D. H. Wolpert, K. R. Wheeler, and K. Tumer. Collective intelligence for control of distributed dynamical systems. Europhysics Letters, 49(6):708--714, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

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

General Terms:
Algorithms

Keywords:
control, coordination, markovian environment, multiagent systems, planning