Uncertainties in adversarial patrol

ABSTRACT

In this work, we study the problem of multi-robot perimeter patrol in adversarial environments, under uncertainty. In this problem, the robots patrol around a closed area, where their goal is to patrol in a way that maximizes their chances of detecting an adversary trying to penetrate into the area. Uncertainties may rise in different aspects in this domain, and herein our focus is twofold. First, uncertainty in the robots' sensing capabilities, and second uncertainty of the adversary's knowledge of the patrol's weak points. In this work we provide an initial discussion and initial results concerning these two aspects of uncertainty in the multi-robot perimeter patrol problem. Specifically, we first consider the case in which the robots have realistic sensors, and thus they are imperfect. These sensors cannot always detect the adversary even if it close to the robot, and their detection capability changes with their range. We then deal with different possible choices of penetration spots by the adversary, and discuss possible optimal solutions for the patrolling robots in each such case.

REFERENCES

• 1: N. Agmon, G. A. Kaminka, and S. Kraus. Multi-robot fence patrol in adversarial domains. In IAS-10, pages 193--201. IOS Press, 2008.
• 2: N. Agmon, S. Kraus, and G. A. Kaminka. Multi-robot perimeter patrol in adversarial settings. In ICRA, 2008.
• 3: Noa Agmon , Vladimir Sadov , Gal A. Kaminka , Sarit Kraus, The impact of adversarial knowledge on adversarial planning in perimeter patrol, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 4: M. Ahmadi and P. Stone. A multi-robot system for continuous area sweeping tasks. In ICRA, 2006.
• 5: Yann Chevaleyre, Theoretical Analysis of the Multi-agent Patrolling Problem, Proceedings of the Intelligent Agent Technology, IEEE/WIC/ACM International Conference, p.302-308, September 20-24, 2004 [doi>10.1109/IAT.2004.109]
• 6: Y. Elmaliach, N. Agmon, and G. A. Kaminka. Multi-robot area patrol under frequency constraints. Annals of Math and AI, to appear, 2008.
• 7: Yehuda Elmaliach , Asaf Shiloni , Gal A. Kaminka, A realistic model of frequency-based multi-robot polyline patrolling, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 8: 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]
• 9: 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]
• 10: James Pita , Manish Jain , Fernando Ordóñez , Milind Tambe , Sarit Kraus , Reuma Magori-Cohen, Effective solutions for real-world Stackelberg games: when agents must deal with human uncertainties, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
• 11: S. Thrun. Probabilistic algorithms in robotics. AI Magazine, 21:93--109, 2000.
• 12: Sebastian Thrun , Wolfram Burgard , Dieter Fox, A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots, Autonomous Robots, v.5 n.3-4, p.253-271, July-August 1998 [doi>10.1023/A:1008806205438]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

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

General Terms:
Algorithms, Security

Keywords:
adversarial/game domains, formal models of multi-robot plans, multi-robotics