MiniMax equilibrium of networked differential games

ABSTRACT

Surveillance systems based on wireless sensor network technology have been shown to successfully detect, classify and track evaders over a large area. State information collected via the sensor network also enables these systems to actuate mobile agents so as to achieve surveillance goals, such as target capture and asset protection. But satisfying these goals is complicated by the fact that the track information in a sensor network is routed to mobile agents through multihop wireless communication links and is thus subject to message delays and losses. Stabilization must also be considered in designing pursuer strategies so as to deal with state corruption as well as suboptimal evader strategies.

In this article, we formulate optimal pursuit control strategies in the presence of network effects, assuming that target track information has been established locally in the sensor network. We adapt ideas from the theory of differential games to networked games—including ones involving nonperiodic track updates, message losses and message delays—to derive optimal strategies, bounds on the information requirements, and scaling properties of these bounds. We show the inherent stabilization features of our pursuit strategies, both in terms of implementation as well as the strategies themselves.

REFERENCES

• 1: A. Arora , P. Dutta , S. Bapat , V. Kulathumani , H. Zhang , V. Naik , V. Mittal , H. Cao , M. Demirbas , M. Gouda , Y. Choi , T. Herman , S. Kulkarni , U. Arumugam , M. Nesterenko , A. Vora , M. Miyashita, A line in the sand: a wireless sensor network for target detection, classification, and tracking, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.5, p.605-634, 5 December 2004 [doi>10.1016/j.comnet.2004.06.007]
• 2: Anish Arora , Emre Ertin , Rajiv Ramnath , Mikhail Nesterenko , William Leal, Kansei: A High-Fidelity Sensing Testbed, IEEE Internet Computing, v.10 n.2, p.35-47, March 2006 [doi>10.1109/MIC.2006.37]
• 3: Anish Arora , Rajiv Ramnath , Emre Ertin , Prasun Sinha , Sandip Bapat , Vinayak Naik , Vinod Kulathumani , Hongwei Zhang , Hui Cao , Mukundan Sridharan , Santosh Kumar , Nick Seddon , Chris Anderson , Ted Herman , Nishank Trivedi , Chen Zhang , Mikhail Nesterenko , Romil Shah , Sandeep Kulkarni , Mahesh Aramugam , Limin Wang , Mohamed Gouda , Young-ri Choi , David Culler , Prabal Dutta , Cory Sharp , Gilman Tolle , Mike Grimmer , Bill Ferriera , Ken Parker, ExScal: Elements of an Extreme Scale Wireless Sensor Network, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.102-108, August 17-19, 2005 [doi>10.1109/RTCSA.2005.47]
• 4: Basar, T. and Olsder, G. J. 1999. Dynamic Noncooperative Game Theory. SIAM.
• 5: Hui Cao , Emre Ertin , Vinodkrishnan Kulathumani , Mukundan Sridharan , Anish Arora, Differential games in large-scale sensor-actuator networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127792]
• 6: Chen, P. and Sastry, S. 2006. Pursuit controller performance guarantees for a lifeline pursuit-evasion game over a wireless sensor network. In Proceedings of the 45th IEEE Conference on Decision and Control. IEEE Computer Society, Los Alamitos, CA.
• 7: Isaacs, R. 1975. Differential Games. Kruger Publishing Company, Huntington, NY.
• 8: Kulathumani, V., Arora, A., Demirbas, M., and Sridharan, M. 2007. Trail: a distance sensitive network protocol for distributed object tracking. In Proceedings of European Conference on Wireless Sensor Networks (EWSN).
• 9: Nash, J. 1951. Noncooperative games. Annals Math. 54, 286--295.
• 10: Oh, S., Russell, S., and Sastry, S. 2004. Markov chain monte carlo data association for general multiple-target tracking problems. In Proceedings of the IEEE International Conference on Decision and Control.
• 11: Schenato, L., Oh, S., and Sastry, S. 2005. Swarm coordination for pursuit evasion games using sensor networks. In Proceedings of the International Conference on Robotics and Automation.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms, Design, Reliability, Theory

Keywords:
Differential games, delay, equilibrium, sensor networks