Abstract
Green Security Games have become a popular way to model scenarios involving the protection of natural resources, such as wildlife. Sensors (e.g. drones equipped with cameras) have also begun to play a role in these scenarios by providing real-time information. Incorporating both human and sensor defender resources strategically is the subject of recent work on Security Games with Signaling (SGS). However, current methods to solve SGS do not scale well in terms of time or memory. We therefore propose a novel approach to SGS, which, for the first time in this domain, employs an Evolutionary Computation paradigm: EASGS. EASGS effectively searches the huge SGS solution space via suitable solution encoding in a chromosome and a specially-designed set of operators. The operators include three types of mutations, each focusing on a particular aspect of the SGS solution, optimized crossover and a local coverage improvement scheme (a memetic aspect of EASGS). We also introduce a new set of benchmark games, based on dense or locally-dense graphs that reflect real-world SGS settings. In the majority of 342 test game instances, EASGS outperforms state-of-the-art methods, including a reinforcement learning method, in terms of time scalability, nearly constant memory utilization, and quality of the returned defender's strategies (expected payoffs).
Introduction: The Challenge of Green Security
In "Green Security Games," defenders such as park rangers protect vast areas from adversaries like poachers. Modern technology, particularly drones, has introduced a layer of "signaling" to these interactions. If a drone detects a poacher, it can send a signal—such as a light or a radio transmission—to warn them that a ranger is en route. Crucially, defenders can strategically use "bluffs," sending a signal even if a ranger is not immediately available, to deter attacks when resources are spread thin.
The mathematical objective is to find the Stackelberg Equilibrium, the optimal strategy for the defender assuming the adversary will observe and react to defensive patterns. Existing solutions typically rely on Linear Programming (LP) or Mixed Integer Linear Programming (MILP). While these methods are precise, they suffer from "state-space explosion." As the number of targets or the complexity of the patrol graph increases, these solvers often run out of memory or require prohibitive computation time, making them impractical for large-scale real-world applications.
The EASGS Framework
To address these scalability issues, we propose EASGS (Evolutionary Algorithm for Security Games with Signaling). Rather than treating the problem as a rigid set of equations, EASGS approaches it through the lens of evolutionary computation, maintaining a population of candidate strategies that improve over time.
Key Innovations in EASGS:
- Defender-Centered Chromosome: To avoid the computational cost of mapping every possible state of every vertex, the algorithm encodes a list of "actions" (sensor and patroller allocations) and their associated signaling probabilities directly into the chromosome.
- Specialized Operators:
- Crossover: This operator merges two parent strategies, favoring pure strategies that yielded higher payoffs in previous generations.
- Three-Tiered Mutation: The algorithm employs three distinct mutation types: one modifies signaling probabilities, one explores new resource allocations, and a third—Coverage Improvement—specifically targets vertices currently being exploited by the adversary.
- Memetic Local Optimization: A post-processing step ensures that generated strategies are feasible, such as verifying that a patroller can realistically reach a target from their current position within the game's constraints.
- Population Refreshing: To prevent the algorithm from getting stuck in "local optima" (sub-optimal solutions that appear good relative to their immediate neighbors), EASGS periodically replaces half the population with fresh, random individuals while preserving the best-performing strategy.
Experimental Setup and Datasets
We evaluated EASGS against 342 artificial game instances. A key contribution of this work is the introduction of a new set of benchmark games categorized by graph structure:
- Sparse, Moderate, and Dense Graphs: Random graphs generated using the Watts-Strogatz model to test general performance.
- Locally-Dense Graphs: A new benchmark reflecting real-world geography, where "cliques" (areas easy to patrol, like open fields) are connected by "links" (roads or trails).
EASGS was tested against several baselines, including exact solvers (SELP), heuristic branch-and-price methods (SBP), and a reinforcement learning baseline (m-CombSGPO).
Key Results and Insights
Our findings demonstrate that EASGS offers significant advantages over traditional methods:
- Density Independence: Unlike MILP solvers that struggle as the number of connections in a graph increases, the complexity of EASGS's operations is largely independent of graph density. This allows it to handle complex, highly connected maps with ease.
- Memory Efficiency: While the exact solver (SELP) exceeded 128 GB of RAM for games with more than 20 vertices, EASGS maintained a nearly constant memory footprint, never exceeding 150 MB even for 100-vertex games. This efficiency makes it suitable for deployment on field hardware with limited resources.
- Scalability and Quality: EASGS outperformed all competitive methods in time scalability on dense and locally-dense graphs. In the 342 test instances, it provided the best defender payoffs in the majority of cases. While it is a metaheuristic and does not guarantee a global optimum, it consistently found "near-optimal" solutions in scenarios where other heuristics failed to produce a result.
- Strategic Bluffs: The algorithm successfully learned to balance "strong" and "weak" signals to maximize deterrence, effectively utilizing limited ranger resources through strategic signaling.
Conclusion and Future Work
EASGS represents the first application of evolutionary computation to the domain of Security Games with Signaling. By prioritizing scalability and memory efficiency, it provides a viable path for deploying sophisticated defensive strategies in large-scale environmental protection efforts.
Future Work will focus on integrating EASGS with real-time computer vision sensors for field testing and extending the framework to handle multi-adversary scenarios involving poachers with diverse behavioral patterns.
Summary updated