Research map / Learning theory and algorithms / Combinatorial and search optimization
Improving Community-Participated Patrol for Anti-Poaching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a Stackelberg game model (RACPP) for anti-poaching patrols combining flexible professional rangers with fixed-target community villagers, and gives a MILP, an approximate two-dimensional binary search, and an exact Hybrid Waterfilling algorithm.
Problem
Optimizing anti-poaching patrol allocation when community members (villagers) act as patrollers who are inflexible (fixed to one target) alongside flexible professional rangers, against a best-responding poacher.
Approach
Extends security-game (SSG) water-filling to handle deterministic, indivisible villager allocations by combining greedy villager assignment, water-filling for rangers, and swaps triggered at critical points, yielding polynomial-time exact and approximate solvers.
Key results
- TDBS runtime is significantly lower than MILP and HW across n up to 1000 in synthetic experiments, with MILP hitting the 7200 s limit in some settings.
- Case study reports defender utility improvement of 25.9% to 152.6% (average 83.1%) over current patrol strategy across 45 (ep, ev) settings.
- Case study suggests prioritizing rangers when ep=0.8, ev=0.2, and villagers when ep=0.6, ev=0.4 for extra budget.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the current patrol allocation with the RACPP optimized allocation | current patrol strategy in the Northeast China protected tiger habitat · Northeast China protected tiger habitat | defender utility: 25. 9\% - 152. 6\%; average 83. 1\% | Helped |
Surprising findings
- Villager-specific effectiveness makes the problem NP-hard, whereas target-specific effectiveness remains polynomial-time solvable.
Limitations
- Real-world case study relies on unknown effectiveness parameters ep and ev, enumerated over a grid rather than estimated.
- Real patrol and animal density data are not public, limiting reproducibility of the case study.
- Model assumes villagers are fixed to one target for the whole season and attacker is perfectly rational best responder.
Experimental setup
Datasets: synthetic instances real-world patrol records and animal density data from a Northeast China tiger reserve
Benchmarks: synthetic RACPP instances varying n, rangers and villagers Northeast China protected tiger habitat case study
Metrics: runtime defender expected utility
Baselines: Gurobi MILP solver
Builds on: Stackelberg Security Game water-filling for security games
Closest papers by meaning
- Preventing Illegal Logging: Simultaneous Optimization of Resource Teams and Tactics for Security (AAAI 2016 · similarity 0.86)
- GUARD: Constructing Realistic Two-Player Matrix and Security Games for Benchmarking Game-Theoretic Algorithms (NeurIPS 2025 · similarity 0.86)
- Decision-Making for Land Conservation: A Derivative-Free Optimization Framework with Nonlinear Inputs (AAAI 2024 · similarity 0.81)
- Deep Reinforcement Learning for Green Security Games with Real-Time Information (AAAI 2019 · similarity 0.81)
- Safe Search for Stackelberg Equilibria in Extensive-Form Games (AAAI 2021 · similarity 0.80)
- Parameter-Dependent Competitive Analysis for Online Capacitated Coverage Maximization through Boostings and Attenuations (ICML 2024 · similarity 0.78)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.