Stochastic Strategies for Robotic Surveillance as Stackelberg Games

Xiaoming Duan, Dario Paccagnan, Francesco Bullo

Abstract

This research explores stochastic robotic surveillance modeled as a Stackelberg game. A mobile agent moves randomly on a graph to capture an omniscient intruder who knows the robot's strategy and current location. The study derives universal performance limits and identifies optimal Markov chain-based strategies for specific graph topologies, including star, complete, and line graphs.

Introduction: The Surveillance Challenge

In robotic surveillance, a mobile agent (the robot) patrols a set of locations to detect or capture an intruder. A significant challenge arises when the intruder is strategic: if the robot follows a deterministic, repeating path, the intruder can learn the pattern and attack a location when the robot is far away.

Figure 1: Illustration of a robotic surveillance scenario where a mobile agent (drone) patrols a graph to detect an intruder.

To counter this, researchers employ stochastic (randomized) strategies, typically modeled as Markov chains. This paper addresses the "worst-case" scenario involving an omniscient intruder. This adversary knows the robot's current position and has perfectly learned the robot's transition probabilities. The objective is to design a transition matrix that maximizes the probability of capture despite the opponent's perfect information.

Methodology

The problem is framed as a Stackelberg game, where the "leader" (the robot) commits to a strategy first, and the "follower" (the intruder) responds optimally.

  1. Movement Modeling: The robot's movement is a first-order discrete-time Markov chain on a graph. The strategy is defined by a transition matrix $P$, where $p_{ij}$ represents the probability of moving from node $i$ to node $j$.
  2. Capture Mechanics: Capture occurs if the robot visits the intruder's chosen node within an attack duration $\tau$. This is modeled using hitting times—the time required for a Markov chain to reach a specific state.
  3. Optimization Goal: The robot seeks to maximize the minimum capture probability across all possible starting locations and attack targets: $\max_P \min_{i,j} \mathbb{P}(T_{ij} \leq \tau)$.
  4. Topological Analysis: The study focuses on three prototypical structures: Complete Graphs (all-to-all connectivity), Star Graphs (central hub with leaves), and Line Graphs (sequential chain).

Key Insights and Theoretical Bounds

  • Universal Performance Limit: The authors establish that for any graph with $n$ nodes and an attack duration $\tau$, the capture probability cannot exceed $\tau/n$. This represents a fundamental "speed limit" for surveillance efficiency.
  • The "No-Stay" Rule: For star and line graphs, the optimal strategy involves zero self-loops. Spending time at a current node is mathematically shown to be a wasted opportunity when the goal is to maximize coverage against a strategic opponent.
  • Effectiveness of Random Walks: In complete graphs, a uniform random walk is surprisingly robust, achieving performance within approximately 63% ($(1 - 1/e)$) of the theoretical optimum.
  • Symmetry in Linear Topologies: For line graphs, the optimal strategy is symmetric, balancing the risk of attacks at either end of the chain by moving toward the boundaries with specific calculated probabilities.

Results and Proofs

The paper provides rigorous mathematical proofs for several key configurations:

  • Star Graph Optimality: The optimal strategy involves moving from the center to any leaf node with probability $1/(n-1)$, and always returning from a leaf to the center.
  • Line Graph Optimality: A specific tridiagonal transition matrix is identified as the optimal strategy, supported by both proof and extensive Monte Carlo simulations (27,000 trials).
  • Suboptimality Guarantees: For complete graphs where $\tau$ is not a multiple of $n$, the authors provide exact formulas for the performance gap of standard random walks.

Limitations and Future Directions

While providing exact solutions for specific topologies, the research notes that finding optimal strategies for arbitrary graph structures remains computationally difficult. Furthermore, the current model assumes homogeneous attack durations ($\tau$ is constant across all nodes) and focuses on a single agent. Future work may extend these Stackelberg guarantees to multi-robot coordination and heterogeneous environments where different targets have varying levels of vulnerability.

Summary updated

Abstract

This article studies a stochastic robotic surveillance problem where a mobile robot moves randomly on a graph to capture a potential intruder that strategically attacks a location on the graph. The intruder is assumed to be omniscient: It knows the current location of the mobile agent and can learn the surveillance strategy. The goal for the mobile robot is to design a stochastic strategy so as to maximize the probability of capturing the intruder. We model the strategic interactions between the surveillance robot and the intruder as a Stackelberg game; and optimal and suboptimal Markov chain based surveillance strategies in star, complete, and line graphs are studied. We first derive a universal upper bound on the capture probability, i.e., the performance limit for the surveillance agent. We show that this upper bound is tight in the complete graph and further provide suboptimality guarantees for the random walk. For the star and line graphs, we first characterize dominant strategies for the surveillance agent and the intruder. Then, we rigorously prove the optimal strategy for the surveillance agent.
BibTeX
@article{duan2021stochastic,
  author = {Xiaoming Duan and Dario Paccagnan and Francesco Bullo},
  title = {{Stochastic Strategies for Robotic Surveillance as Stackelberg Games}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2021},
  doi = {10.1109/tcns.2021.3058932},
}
Figure