Multi-robot adversarial patrolling strategies via lattice paths

Jan Buermann, Jie Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

In full-knowledge multi-robot adversarial patrolling, a group of robots has to detect an adversary who knows the robots' strategy. The adversary can easily take advantage of any deterministic patrolling strategy, which necessitates the employment of a randomised strategy. While the Markov decision process has been the dominant methodology in computing the penetration detection probabilities on polylines, we apply enumerative combinatorics to characterise the penetration detection probabilities for four penetration configurations. It allows us to provide the closed formulae of these probabilities and facilitates characterising optimal random defence strategies. Comparing to iteratively updating the Markov transition matrices, we empirically show that our method reduces the runtime by up to several hours. This allows us extensive simulations on the two dominant robot movement types for patrolling a perimeter showing that a movement with direction is up to 0.4 more likely to detect an adversary. Therefore, our approach greatly benefits the theoretical and empirical analysis of optimal patrolling strategies with extendability to more complicated attacks and other structured environments.
Original languageEnglish
Article number103769
JournalArtificial Intelligence
Volume311
Early online date11 Aug 2022
DOIs
Publication statusPublished - 31 Oct 2022

Keywords

  • Multi-robot systems
  • Robots in adversarial settings

Fingerprint

Dive into the research topics of 'Multi-robot adversarial patrolling strategies via lattice paths'. Together they form a unique fingerprint.

Cite this