PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent

Noa Agmon, Gal A. Kaminka, Sarit Kraus

arXiv:1401.3903v1cs.MAcs.RO

TL;DR

Frequency-based patrol does not capture the challenge posed by an adversary who knows the patrol strategy and seeks an undetected entry. This paper develops a polynomial-time Markovian framework to optimize detection at the weakest spot, and extends it across robot movement, sensing, and environment models.

  • Problem

    Frequency-based patrol criteria do not directly address how robots should maximize detection when an adversary can exploit knowledge of their patrol strategy.

    Source: §1 · pp. 1–2

  • Method

    The paper models nondeterministic patrol as a Markov chain and computes segment detection probabilities to find an optimal strategy against a full-knowledge adversary.

    Source: §1 · p. 2, §4 · p. 8, §4.2 · p. 13

  • Results

    The paper gives a polynomial-time optimal patrol algorithm that maximizes detection probability at the full-knowledge adversary's weakest spot and reports advantages for nondeterministic patrol.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework extends to open fences and to varied movement and sensing models, including directed or omnidirectional motion and perfect or imperfect sensing.

    Source: §1 · pp. 2–3

    The approach assumes a first-order Markovian robot strategy; higher-order strategies, heterogeneous robots, and non-linear environments remain future-work directions.

    Source: §6 · p. 28

Abstract

from arXiv · show

The problem of adversarial multi-robot patrol has gained interest in recent years, mainly due to its immediate relevance to various security applications. In this problem, robots are required to repeatedly visit a target area in a way that maximizes their chances of detecting an adversary trying to penetrate through the patrol path. When facing a strong adversary that knows the patrol strategy of the robots, if the robots use a deterministic patrol algorithm, then in many cases it is easy for the adversary to penetrate undetected (in fact, in some of those cases the adversary can guarantee penetration). Therefore this paper presents a non-deterministic patrol framework for the robots. Assuming that the strong adversary will take advantage of its knowledge and try to penetrate through the patrols weakest spot, hence an optimal algorithm is one that maximizes the chances of detection in that point. We therefore present a polynomial-time algorithm for determining an optimal patrol under the Markovian strategy assumption for the robots, such that the probability of detecting the adversary in the patrols weakest spot is maximized. We build upon this framework and describe an optimal patrol strategy for several robotic models based on their movement abilities (directed or undirected) and sensing abilities (perfect or imperfect), and in different environment models - either patrol around a perimeter (closed polygon) or an open fence (open polyline).

1. Introduction

Multi-robot patrol research has often optimized visit frequency, but this paper frames patrol as an adversarial detection problem in security settings. It develops a nondeterministic Markovian framework and optimal algorithms for full-knowledge adversaries, extending the framework to varied robot and environment models.

1. Introduction

  • Unlike frequency-based patrol, adversarial patrol seeks to maximize the chance of detecting an intruder, which matters in security applications.Prior work often optimized minimal or uniform point-visit frequency.Source: §1 · p. 1
  • Deterministic patrol can let a knowledgeable adversary guarantee penetration, motivating nondeterministic behavior when entry can occur at any time.The example contrasts deterministic patrol with robots that turn around probabilistically.Source: §1 · p. 2
  • A full-knowledge adversary targets the patrol's weakest spot, so the robots' objective is to maximize detection probability there with a polynomial-time optimal algorithm.The paper also reports that nondeterministic patrol is advantageous and guarantees lower-bound performance criteria.Source: §1 · p. 2
  • The framework extends beyond closed perimeters to open fences and supports directed or omnidirectional movement and varied sensing capabilities.The considered sensing models include perfect or imperfect, local or long-range sensing.Source: §1 · pp. 2–3

2. Related Work

Related work includes frequency-based patrol, adversarial patrol, stochastic pursuit-evasion, and game-theoretic approaches. This paper distinguishes itself by deriving tailored polynomial-time optimal patrol algorithms for specified robot and environment models.

2. Related Work

  • Frequency-based patrol optimizes visit frequency or idleness, whereas adversarial patrol evaluates how well a strategy detects intruders.Chevaleyre (2004) analyzed idleness and patrol schemes on graphs; Elmaliach et al. (2007, 2009) pursued maximal minimal and uniform frequency.Source: §2 · pp. 3–4
  • Sak et al. (2008) found no single non-deterministic graph-patrol method outperformed others in all tested domains, while this paper proves optimality for specified settings.Their empirical comparison considered different graph structures and adversary types.Source: §2 · p. 4
  • Rather than using game-theoretic equilibrium tools, the paper uses tailored minmax algorithms to find optimal multi-robot patrol strategies in polynomial time.Prior game-theoretic approaches often offered approximate or heuristic solutions to intractable optimal solutions.Source: §2 · pp. 4–5
  • Unlike cat-and-mouse models where the cat lacks knowledge of the mouse's movement, this work assumes a worst-case adversary and models patrol on open or closed polylines.The robot model can include directionality, turning costs, and sensing capabilities.Source: §2 · p. 5

3. Robot and Environment Model

The model discretizes patrol into uniform-time segments and considers synchronous, homogeneous robots moving around a closed polygon. It defines detection probability against an adversary that chooses when and where to penetrate, including a full-knowledge weakest-spot strategy.

3.1 The Environment

  • The environment is represented as a cycle of N segments, each taking one time cycle to traverse, with segment lengths reflecting local velocity constraints and sensing.Distance between robots is measured in travel-time segments.Source: §3.1 · pp. 5–6, Figure 1 · p. 6

3.2 Patrolling Robotic Model

  • Robots operate synchronously in compute-and-move cycles; the model focuses on how each robot computes its next goal point.The robots are homogeneous and there are k > 1 of them.Source: §3.2 · p. 6
  • In the basic directed-motion model, turning around costs τ time units on the current segment, with τ = 1 assumed unless otherwise stated.The robots must physically turn when their goal point is behind them.Source: §3.2 · p. 6
  • Optimal patrolling requires robots to maintain uniform spacing d = N/k, which requires coordinated movement; systems without reliable communication are left for future work.Centralized systems or systems with communication can achieve this coordination.Source: §3.2 · pp. 6–7

3.3 Adversarial Model

  • The adversary chooses an unknown time and segment for a non-instantaneous penetration lasting t time units; under full knowledge it targets the segment with minimum detection probability.The adversary knows the patrol scheme and may learn it by observing the robots.Source: §3.3 · pp. 7–8
  • For a segment si, ppdi is the probability that a penetrator is detected by a robot passing through that segment during the t-unit attempt.With perfect sensing, detection depends on the first robot visit during the attempt.Source: §3.3 · p. 7
  • When t < (d + τ + 1)/2, some segment may be unreachable during the attempt, allowing guaranteed penetration; when t ≥ d, deterministic patrol can give every segment ppdi = 1.The bounds follow from robot spacing and the time cost of turning around.Source: §3.3 · p. 7

4. A Framework for Adversarial Patrolling of Perimeters

The framework calculates segment-level probabilities of detecting penetration and selects patrol parameters to maximize the weakest segment’s detection probability against a full-knowledge adversary. For the basic perimeter model, it uses randomized patrols by uniformly spaced, coordinated robots and a polynomial-time Markov-chain method; examples illustrate how detection varies with patrol parameters and across segments.

4. A Framework for Adversarial Patrolling of Perimeters

  • Robots continue straight with probability p or turn around with probability 1 −p, while segment detection probability depends on a first visit within t time units under perfect detection.The framework evaluates detection independently of the adversary’s actions.Source: §4 · p. 8, §4.1 · p. 11
  • Uniform spacing and coordinated movement in the same direction maximize the minimum penetration-detection probability, and optimal full-knowledge patrols maintain uniform spacing throughout execution.The robots move at the same speed and turn around simultaneously; reducing the distance between consecutive robots raises detection probability in the intervening segments.Source: §4 · pp. 9–10

4.1 The Penetration Detection Problem

  • The penetration-detection problem first derives each segment’s detection-probability function for the robot, sensing, and environment models, then maximizes detection in the weakest segment.The stages are independent, allowing the framework to accommodate different models and alternative objectives such as maximizing expected detection probability.Source: §4.1 · p. 11

4.2 Determining the Probability of Penetration Detection

  • A polynomial-time algorithm computes each segment’s detection probability by summing Markov-chain paths of length at most t to an absorbing first-visit state.The basic calculation uses two directional states per segment and considers one section between consecutive robots because the perimeter is symmetric.Source: §4.2 · pp. 12–13
  • FindFunc computes the segment ppd functions in O(d^3); modeling turn time τ adds a complexity factor of τ, unchanged when τ is constant.For τ > 1, the Markov chain represents the additional time required to turn around.Source: §4.2 · p. 13, §4.2.1 · p. 14

4.3 An Optimal Adversarial Patrol Algorithm for Full-Knowledge Adversaries

  • FindP chooses p to maximize the minimum segment ppd across the perimeter and is proven to find the maximin value.The maximin point occurs at an intersection of curves or a local maximum; a point with maximin ppd greater than 0 exists.Source: §4.3 · pp. 15–16

4.4 Examples

  • With t=8, maximin ppd falls from 0.423 at d=9 to 0.05 at d=15; it rises as t/d approaches 1.The paper also reports that maximin ppd increases as t increases for fixed d.Source: §4.4 · p. 17, Figure 5 · p. 17
  • Across 16 segments, ppd usually falls with distance from the left robot to the maximin segment, then rises toward the right robot; p > 0.8 places it right of midpoint.This pattern reflects the stronger influence of the left robot on segments to the left of the maximin segment and the right robot on segments to its right.Source: §4.4 · p. 17, Figure 6 · p. 18

5. Accounting for Movement Constraints and Sensing Uncertainty

The framework extends multi-robot patrol to settings with varied movement and sensing capabilities, including patrol along an open fence. Its Markov-chain framework can be adapted to these models.

5. Accounting for Movement Constraints and Sensing Uncertainty

  • The section extends the patrol framework to movement models that are not necessarily directed.Source: §5 · p. 18
  • Perimeter patrol is considered with imperfect local sensing, perfect long-range sensing, and imperfect long-range sensing.Source: §5 · p. 18
  • The framework also addresses patrol along an open polyline rather than a perimeter.Source: §5 · p. 18

5.1 Different Movement Models

The framework handles three movement models by adapting the robots’ Markov chains. For d = 16 and t = 12, DCP yields ppd no greater than DNCP, while BMP has higher values near the right-hand robot and lower values around t.

5.1 Different Movement Models

  • The three models are BMP, DCP, and DNCP, distinguished by whether movement is directed and whether turning around costs time.BMP has undirected movement; DCP is directed with turning cost τ = 1; DNCP is directed with τ = 0.Source: §5.1 · pp. 18–19
  • The framework handles each movement model by adapting its Markov chain, changing only lines 5–6 of FindFunc.BMP moves right with probability p and left with 1 − p; DCP and DNCP continue in the current direction with probability p and turn around with probability 1 − p.Source: §5.1 · p. 19, Figure 7 · p. 19
  • BMP models movement as a random walk between adjacent segments, whereas DCP and DNCP model continuing forward or turning around.Source: §5.1 · p. 19
  • For d = 16 and t = 12, DCP ppd is no greater than DNCP ppd across segments, while BMP values are high near the right-hand robot and fall around t.BMP uses a rightward probability of 0.707; equal left-right probabilities would neglect segments farther away, lowering the minimal ppd.Source: §5.1 · p. 20, Figure 8 · p. 20

5.2 Perimeter Patrol with Imperfect Penetration Detection

With imperfect sensing, repeated visits can contribute to detection probability, which is not simply the probability of first reaching a segment. The section extends the framework and proves that optimal perimeter patrol requires uniform robot spacing and coordinated turns.

5.2 Perimeter Patrol with Imperfect Penetration Detection

  • With imperfect sensing, ppd for a segment includes detection during any visit, so revisiting can increase its detection probability.Detection probability is accumulated across visits, with a visit’s detection chance bounded by pd ≤ 1.Source: §5.2 · p. 21
  • The detection probability combines the chance of detection on the first visit with later detection after earlier visits fail.For a robot residing in a segment, the probability of no detection through t visits is represented by (1 − pd)^t.Source: §5.2 · p. 21
  • The section establishes that ppd decreases or stays constant as distance from a robot increases, supporting the uniform-spacing result.The theorem states the detection probability is at least as high at a segment as at the next segment farther away on either side.Source: §5.2 · p. 21
  • The theorem generalizes the perfect-sensing result: minimal and average ppd are maximized when robots remain uniformly spaced around the perimeter.The argument uses the nonincreasing ppd with distance from robots.Source: §5.2 · p. 22
  • In the ImpDetect model, optimal full-knowledge patrol requires uniform robot placement around the perimeter and simultaneous turns, preserving uniform spacing throughout execution.Source: §5.2 · p. 22
  • The algorithm represents imperfect detection with a changed Markov chain, splitting the robot’s current segment state and adding an absorbing detected state.It obtains ppd after t + 1 steps, and its time complexity remains O(d^4).Source: §5.2 · p. 22

5.3 Improving Sensing Capabilities in Perimeter Patrol

The section extends perimeter-patrol analysis to longer-range sensing, including a combined model with imperfect, distance-dependent detection. It describes how these sensing models change the detection-probability calculation.

5.3.1 Extending (Perfect) Sensing Range

  • With L>0, robots sense L segments beyond their current segment, and the shaded segments lie in the robot’s facing direction.The model distinguishes sensing range from sensing quality.Source: §5.3.1 · p. 23
  • Forcing L=0 by enlarging segments reduces analysis accuracy because the base time cycle should remain small enough to suit robot velocity and t.Source: §5.3.1 · p. 23
  • Extending sensing range permits consideration of shorter adversary penetration times than when L=0, assuming a turning robot senses only its current segment.The passage gives the allowable time values by equation, but the supplied text does not show that equation.Source: §5.3.1 · p. 23

5.3.2 Extending the Sensorial Range Along With Imperfect Detection

  • ImpDetLRange combines LRange and ImpDetect: L sets sensing reach, while VS gives segment-specific detection probabilities that do not increase with distance.The model treats vi as the probability of detecting a penetration in segment si when the robot is in s0.Source: §5.3.2 · p. 24
  • The imperfect long-range model changes Markov-chain transitions to reflect detection probabilities for sensed segments and computes ppdi from M^(t+1)Vi at s0.The added absorbing state takes an extra step to reach, so the calculation uses t+1 time steps.Source: §5.3.2 · p. 24

5.4 Multi-Robot Adversarial Patrolling Along Fences

Fence patrol differs from perimeter patrol because robots turn back along an open path and detection probabilities depend on their current location. The section adapts the Markov-chain calculation and maximin optimization to that setting.

5.4.1 Patrolling Along a Closed Polyline vs. an Open Polyline

  • In an open fence, even the best-case maximum interval between visits is 2l/4 −2, versus a circular patrol where an adversary taking more than l/4 cannot penetrate under uniform spacing.The comparison assumes equal total length l and four robots; the open path’s longer visit interval can leave room for penetration.Source: §5.4.1 · pp. 25–26, Figure 12 · p. 26
  • Open-path asymmetry makes ppd depend on robot location and direction, requiring a d × d matrix of ppd functions rather than the perimeter’s vector of d functions.Source: §5.4.1 · p. 26

5.4.2 Determining ppdi in an Open Polyline (Fence)

  • The fence model uses a Markov chain with two states per segment for travel direction; robots turn at section ends and otherwise turn with probability 1−p.They continue straight with probability p.Source: §5.4.2 · p. 26
  • Fence patrol requires d² ppd functions because detection probability depends on the robot’s current location, compared with d functions for perimeter patrol.Source: §5.4.2 · p. 26

5.4.3 Optimal Algorithm for Fence Patrol

  • MaximinFence finds the patrol probability p that maximizes the minimum ppd by finding the maximal point in the integral intersection of the ppdi curves.Only d optimal p values need calculation; the opposite direction is a reflective image of the first.Source: §5.4.3 · p. 27

6. Summary

The paper presents a polynomial-time framework for optimal patrol against a full-knowledge adversary, then extends it to open fences and varied robot movement and sensing models.

6. Summary

  • For closed-polygon patrol, the framework finds a polynomial-time optimal algorithm that strengthens the patrol’s weakest spot against a full-knowledge adversary.Source: §6 · p. 28
  • The computation assumes first-order Markovian robot strategies; evaluating higher-order strategies and their time complexity and performance remains future work.Source: §6 · p. 28
  • Non-uniform environments, heterogeneous robots, and nonlinear environments are also identified as directions for future work.Source: §6 · p. 28
Loading 1401.3903v1…