Leader-follower strategies for robotic patrolling in environments with arbitrary topologies

ABSTRACT

Game theoretic approaches to patrolling have become a topic of increasing interest in the very last years. They mainly refer to a patrolling mobile robot that preserves an environment from intrusions. These approaches allow for the development of patrolling strategies that consider the possible actions of the intruder in deciding where the robot should move. Usually, it is supposed that the intruder can hide and observe the actions of the patroller before intervening. This leads to the adoption of a leader-follower solution concept. In this paper, mostly theoretical in its nature, we propose an approach to determine optimal leader-follower strategies for a mobile robot patrolling an environment. Differently from previous works in literature, our approach can be applied to environments with arbitrary topologies.

REFERENCES

• 1: N. Agmon, S. Kraus, and G. Kaminka. Multi-robot perimeter patrol in adversarial settings. In Proc. ICRA, pages 2339--2345, 2008.
• 2: Francesco Amigoni , Nicola Gatti , Antonio Ippedico, A Game-Theoretic Approach to Determining Efficient Patrolling Strategies for Mobile Robots, Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, p.500-503, December 09-12, 2008 [doi>10.1109/WIIAT.2008.324]
• 3: M. Bazaraa, H. Sherali, and C. Shetty. Nonlinear Programming: Theory and Algorithms. Wiley, 2006.
• 4: Vincent Conitzer , Tuomas Sandholm, Computing the optimal strategy to commit to, Proceedings of the 7th ACM conference on Electronic commerce, p.82-90, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134717]
• 5: R. Fourer , D. M. Gay , B. W. Kernighan, A modeling language for mathematical programming, Management Science, v.36 n.5, p.519-554, May 1990 [doi>10.1287/mnsc.36.5.519]
• 6: D. Fudenberg and J. Tirole. Game Theory. The MIT Press, Cambridge, USA, 1991.
• 7: Nicola Gatti, Game Theoretical Insights in Strategic Patrolling: Model and Algorithm in Normal-Form, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.403-407, June 27, 2008
• 8: V. Isler, S. Kannan, and S. Khanna. Randomized pursuit-evasion in a polygonal environment. IEEE T ROBOT, 5(21):864--875, 2005.
• 9: D. Koller, N. Megiddo, and B. von Stengel. Efficient computation of equilibria for extensive two-person games. GAME ECON BEHAV, 14(2):220--246, 1996.
• 10: D. Kreps and R. Wilson. Sequential equilibria. Econometrica, 50(4):863--894, 1982.
• 11: L. Martins-Filho and E. Macau. Patrol mobile robots and chaotic trajectories. In Mathematical Problems in Engineering. Hindawi, 2007.
• 12: Praveen Paruchuri , Jonathan P. Pearce , Janusz Marecki , Milind Tambe , Fernando Ordonez , Sarit Kraus, Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 13: Praveen Paruchuri , Jonathan P. Pearce , Milind Tambe , Fernando Ordonez , Sarit Kraus, An efficient heuristic approach for security against multiple adversaries, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329344]
• 14: 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]
• 15: James Pita , Manish Jain , Janusz Marecki , Fernando Ordóñez , Christopher Portway , Milind Tambe , Craig Western , Praveen Paruchuri , Sarit Kraus, Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track, May 12-16, 2008, Estoril, Portugal
• 16: A. Rubinstein. Perfect equilibrium in a bargaining model. Econometrica, 50(1):97--109, 1982.
• 17: Stanford Business Software Inc. http://www.sbsi-sol-optimize.com/.
• 18: R. Vidal, O. Shakernia, J. Kim, D. Shim, and S. Sastry. Probabilistic pursuit-evasion games: Theory, implementation and experimental results. IEEE T ROBOTIC AUTOM, 18(5):662--669, 2002.
• 19: B. von Stengel and S. Zamir. Leadership with commitment to mixed strategies. CDAM Research Report LSE-CDAM-2004-01, London School of Economics, 2004.
• 20: L. Wolsey. Integer programming. Wiley, 1998.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
leader-follower strategies, robotic patrolling