The impact of adversarial knowledge on adversarial planning in perimeter patrol

ABSTRACT

This paper considers the problem of multi-robot patrolling around a closed area, in the presence of an adversary trying to penetrate the area. Previous work on planning in similar adversarial environments addressed worst-case settings, in which the adversary has full knowledge of the defending robots. It was shown that non deterministic algorithms may be effectively used to maximize the chances of blocking such a full-knowledge opponent, and such algorithms guarantee a "lower bound" to the performance of the team. However, an open question remains as to the impact of the knowledge of the opponent on the performance of the robots. This paper explores this question in depth and provides theoretical results, supported by extensive experiments with 68 human subjects concerning the compatibility of algorithms to the extent of information possessed by the subjects. First, we analytically examine the case of a zero-knowledge opponent---a different extreme---and show that surprisingly, this seemingly best-case scenario (from the point of view of defending robots) is optimally addressed by a deterministic, non-randomizing patrol. Moreover, we show empirically that an optimal algorithm for the full-knowledge opponent fails miserably in this case. We then address the case in which the adversary gained partial information, propose the Combine algorithm that maximizes the expected probability of penetration detection along with minimizing the deviation between the probabilities of penetration detection along the perimeter, and support the performance of this algorithm in the experiments.

REFERENCES

• 1: N. Agmon, S. Kraus, and G. A. Kaminka. Multi-robot perimeter patrol in adversarial settings. In ICRA, 2008.
• 2: M. Ahmadi and P. Stone. A multi-robot system for continuous area sweeping tasks. In ICRA, 2006.
• 3: A. Almeida, G. Ramalho, H. Santana, P. Tedesco, T. Menezes, V. Corruble, and Y. Chevaleyr. Recent advances on multi-agent patrolling. Lecture Notes in Computer Science, 3171:474--483, 2004.
• 4: D. Carmel and S. Markovitch. Incorporating opponent models into adversary search. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 120--125, 1996.
• 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. In ICRA, 2007.
• 7: T. Haynes and S. Sen. Evolving behavioral strategies in predators and prey. In IJCAI-95 Workshop on Adaptation and Learning in Multiagent Systems, pages 32--37, 1995.
• 8: Hiroaki Kitano , Minoru Asada , Yasuo Kuniyoshi , Itsuki Noda , Eiichi Osawa , Hitoshi Matsubara, RoboCup: A Challenge Problem for AI and Robotics, RoboCup-97: Robot Soccer World Cup I, p.1-19, January 1998
• 9: Sarit Kraus , Jeffrey S. Rosenschein , Maier Fenster, Exploiting focal points among alternative solutions: Two approaches, Annals of Mathematics and Artificial Intelligence, v.28 n.1-4, p.187-258, 2000 [doi>10.1023/A:1018908306970]
• 10: 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]
• 11: 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]
• 12: Hugo Santana , Geber Ramalho , Vincent Corruble , Bohdana Ratitch, Multi-Agent Patrolling with Reinforcement Learning, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1122-1129, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.180]
• 13: R. Vidal, O. Shakernia, H. J. Kim, D. H. Shim, and S. Sastry. Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation. Robotics and Automation, IEEE Transactions on, 18(5):662--669, 2002.

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, Experimentation, Security

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