Dynamics based control with an application to area-sweeping problems

ABSTRACT

In this paper we introduce Dynamics Based Control (DBC), an approach to planning and control of an agent in stochastic environments. Unlike existing approaches, which seek to optimize expected rewards (e.g., in Partially Observable Markov Decision Problems (POMDPs)), DBC optimizes system behavior towards specified system dynamics. We show that a recently developed planning and control approach, Extended Markov Tracking (EMT) is an instantiation of DBC. EMT employs greedy action selection to provide an efficient control algorithm in Markovian environments. We exploit this efficiency in a set of experiments that applied multi-target EMT to a class of area-sweeping problems (searching for moving targets). We show that such problems can be naturally defined and efficiently solved using the DBC framework, and its EMT instantiation.

REFERENCES

• 1: Ronald C. Arkin, An Behavior-based Robotics, MIT Press, Cambridge, MA, 1998
• 2: J. A. Bilmes. A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and Hidden Markov Models. Technical Report TR-97-021, Department of Electrical Engeineering and Computer Science, University of California at Berkeley, 1998.
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: M. E. desJardins, E. H. Durfee, C. L. Ortiz, and M. J. Wolverton. A survey of research in distributed, continual planning. AI Magazine, 4:13--22, 1999.
• 5: Vijay R. Konda , John N. Tsitsiklis, On Actor-Critic Algorithms, SIAM Journal on Control and Optimization, v.42 n.4, p.1143-1166, 2003 [doi>10.1137/S0363012901385691]
• 6: W. S. Lim. A rendezvous-evasion game on discrete locations with joint randomization. Advances in Applied Probability, 29(4):1004--1017, December 1997.
• 7: M. L. Littman, T. L. Dean, and L. P. Kaelbling. On the complexity of solving Markov decision problems. In Proceedings of the 11th Annual Conference on Uncertainty in Artificial Intelligence (UAI-95), pages 394--402, 1995.
• 8: 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]
• 9: Radford M. Neal , Geoffrey E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 10: Praveen Paruchuri , Milind Tambe , Fernando Ordóñez , Sarit Kraus, Security in multiagent systems by policy randomization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160681]
• 11: J. Pineau, G. Gordon, and S. Thrun. Point-based value iteration: An anytime algorithm for pomdps. In International Joint Conference on Artificial Intelligence (IJCAI), pages 1025--1032, August 2003.
• 12: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 13: Z. Rabinovich and J. S. Rosenschein. Extended Markov Tracking with an application to control. In The Workshop on Agent Tracking: Modeling Other Agents from Observations, at the Third International Joint Conference on Autonomous Agents and Multiagent Systems, pages 95--100, New York, July 2004.
• 14: Zinovi Rabinovich , Jeffrey S. Rosenschein, Multiagent coordination by Extended Markov Tracking, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082539]
• 15: Zinovi Rabinovich , Jeffrey S. Rosenschein, On the response of EMT-based control to interacting targets and models, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160718]
• 16: R. F. Stengel. Optimal Control and Estimation. Dover Publications, 1994.
• 17: M. Tambe , E. Bowring , H. Jung , G. Kaminka , R. Maheswaran , J. Marecki , P. J. Modi , R. Nair , S. Okamoto , J. P. Pearce , P. Paruchuri , D. Pynadath , P. Scerri , N. Schurr , P. Varakantham, Conflicts in teamwork: hybrids to the rescue, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, p.3-10, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082474]

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
      I.2.9 Robotics

General Terms:
Algorithms, Theory

Keywords:
control, dynamics based control, multiagent systems, robotics, target dynamics