Strategic Coordination of Human Patrollers and Mobile Sensors With Signaling for Security Games

Haifeng Xu, Kai Wang, Phebe Vayanos, Milind Tambe

Introduction

In modern security environments, defenders must effectively allocate a heterogeneous mix of resources to protect critical targets. While traditional Stackelberg Security Games (SSGs) focus on human patrollers ("boots on the ground"), the proliferation of low-cost mobile sensors, such as Unmanned Aerial Vehicles (UAVs), presents new opportunities and challenges. This paper, presented at AAAI-18, introduces Sensor-Empowered security Games (SEG), a formal framework designed to jointly optimize the deployment of human patrollers and mobile sensors while leveraging strategic signaling to deter potential attackers.

The Problem: Sensors as "Half-Resources"

The primary challenge in integrating sensors into security games is that they are essentially "half-resources." Unlike human patrollers, sensors can detect an intrusion but cannot perform an intervention. Their effectiveness is contingent upon the proximity of a human patroller who can respond to a sensor-detected alert.

Furthermore, sensors enable strategic signaling (a form of Bayesian Persuasion). A sensor can emit a signal (e.g., flashing lights or sirens) to indicate an alert. If the defender uses a clever signaling policy, they can "bluff" the attacker into believing a patroller is nearby even when one is not, thereby maximizing deterrence.

A conceptual diagram of the SEG model on a cycle graph, featuring human patrollers and mobile sensors (UAVs).

The SEG Model and Strategic Signaling

The authors model the environment as a graph where edges represent the "intervention distance"—the maximum range a patroller can cover within the time required to intercept an attack after a sensor alert.

The SEG model categorizes target states into four types: covered by a patroller, uncovered, covered by a sensor with a patroller nearby, or covered by a sensor with no patroller nearby. In the latter two cases, the defender employs a signaling scheme. By sending "Alert" or "Quiet" signals, the defender aims to influence the attacker's beliefs. A successful "Alert" signal must be sufficiently credible to deter a rational attacker, even if it is occasionally a bluff.

Algorithmic Framework: SEGer and TailoredGreedy

Solving the SEG problem is NP-hard. To address this, the authors developed SEGer, a branch-and-price algorithm. SEGer utilizes column generation, where a Master Problem selects the optimal mix of strategies and a Slave Problem (formulated as a Mixed-Integer Linear Program) generates new high-utility strategies.

For large-scale deployments, the authors introduced TailoredGreedy. Although the defender's utility function is not strictly submodular, the researchers identified a submodular "proxy" function. This allows for a polynomial-time approximation with a provable $1/2(1-1/e)$ bound in zero-sum scenarios.

Experimental Results

The framework was evaluated using synthetic covariant games and various graph structures, including Erdős–Rényi random graphs and cycle graphs.

Utility and Signaling Effectiveness

The results demonstrate that the SEG model with signaling consistently outperforms baselines. A key finding is the relationship between payoff correlation and signaling utility. In strictly zero-sum games (correlation -1), signaling offers no advantage because the attacker's and defender's interests are diametrically opposed. However, in general-sum games (correlation approaching 0), strategic signaling becomes a powerful tool for increasing defender utility.

Comparison of defender utility across different levels of payoff correlation, highlighting the advantages of strategic signaling.

Scalability and Heuristics

The exact SEGer algorithm can handle up to 100 targets within a reasonable timeframe. In contrast, the TailoredGreedy heuristic scales to over 340 targets. Remarkably, TailoredGreedy achieved objective values nearly identical to the exact MILP solver while being approximately six times faster, proving its viability for real-world applications.

Conclusion and Future Work

This research quantifies the value of sensors as force multipliers in security games. By coordinating humans and sensors through strategic signaling, defenders can achieve higher security levels with fewer human resources.

Future research directions include relaxing the assumption of perfect sensor detection to account for false alarms, and integrating dynamic patrol path planning to move beyond static resource allocation.

Summary updated

Abstract

Traditional security games concern the optimal randomized allocation of human patrollers, who can directly catch attackers or interdict attacks. Motivated by the emerging application of utilizing mobile sensors (e.g., UAVs) for patrolling, in this paper we propose the novel Sensor-Empowered security Game (SEG) model which captures the joint allocation of human patrollers and mobile sensors. Sensors differ from patrollers in that they cannot directly interdict attacks, but they can notify nearby patrollers (if any). Moreover, SEGs incorporate mobile sensors' natural functionality of strategic signaling. On the technical side, we first prove that solving SEGs is NP-hard even in zero-sum cases. We then develop a scalable algorithm SEGer based on the branch-and-price framework with two key novelties: (1) a novel MILP formulation for the slave; (2) an efficient relaxation of the problem for pruning. To further accelerate SEGer, we design a faster combinatorial algorithm for the slave problem, which is provably a constant-approximation to the slave problem in zero-sum cases and serves as a useful heuristic for general-sum SEGs. Our experiments demonstrate the significant benefit of utilizing mobile sensors.
BibTeX
@inproceedings{xu2018strategic,
  author = {Haifeng Xu and Kai Wang and Phebe Vayanos and Milind Tambe},
  title = {{Strategic Coordination of Human Patrollers and Mobile Sensors With Signaling for Security Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11447},
}
Figure