A Surveillance Evasion Game with Continuous Sensor Redeployment via Bilevel Optimization

Technical Summary: A Surveillance Evasion Game with Continuous Sensor Redeployment via Bilevel Optimization

Problem Formulation
The paper addresses the critical security challenge of Uncrewed Aerial Systems (UASs) exploiting spatiotemporal gaps in sensor perimeters to infiltrate restricted airspace undetected. The authors model this interaction as a two-player zero-sum differential game between an adversarial UAS (attacker) and a heterogeneous sensor network (defender) consisting of both directional and omnidirectional sensors.

Unlike prior approaches that often restrict defenders to discrete placement graphs, fixed configurations, or assume static omnidirectional coverage, this work formulates the problem over continuous strategy spaces. The attacker seeks a collision-free spatiotemporal trajectory from a start point to a goal point that minimizes the cumulative probability of detection. Conversely, the defender aims to maximize this probability by optimizing the spatial placement of sensors. A key complexity arises from the defender's use of rotating directional sensors, which create time-varying, non-convex coverage regions and predictable gaps that an intelligent adversary can exploit. The authors note that finding a global saddle point is intractable due to the high-dimensional, non-convex nature of the joint strategy spaces and the discontinuities introduced by rotating sensor fields of view (FOV). Consequently, the objective is to compute a Local Nash Equilibrium (LNE), a state where neither player can improve their payoff through infinitesimal unilateral deviations.

Methodology
The proposed solution employs an iterative bilevel optimization framework that alternates between solving the attacker's and defender's best-response subproblems until convergence to an LNE is achieved.

1. Attacker's Best Response:
   Given a fixed sensor placement, the attacker solves a nonlinear programming (NLP) problem to minimize detection probability. To handle the non-convex detection landscape, the authors utilize a two-step approach:

   • Initialization: The Space-Time Probabilistic Rapidly-exploring Random Tree (STP-RRT*) algorithm generates a feasible, collision-free initial trajectory navigating around dynamic sensor coverage regions.
   • Refinement: A gradient-based NLP solver (IPOPT) refines this trajectory to minimize the cumulative detection probability. The detection model uses a smooth sigmoid function to approximate visibility, ensuring differentiability for gradient-based optimization.

2. Defender's Best Response:
   Given the attacker's optimized trajectory, the defender solves a continuous sensor redeployment problem to maximize detection probability.

   • Continuous Redeployment: Unlike discrete graph-based methods, sensors are allowed to slide freely along the boundaries of convex polygonal buildings.
   • Smooth Constraints: To enable gradient-based optimization on these boundaries, the authors enforce placement constraints using a log-sum-exp smooth approximation of the signed distance to the nearest building edge. This technique preserves differentiability at polygon vertices, overcoming the non-differentiability of hard boundary constraints.

3. Iterative Scheme:
   The framework alternates between the attacker's minimization and the defender's maximization. The process terminates when the gradient residuals for both players fall below a prescribed tolerance, satisfying the first-order stationarity conditions for an LNE. If the algorithm enters a limit cycle (non-decaying oscillation), the defender reinitializes from a new random placement to recover convergence.

Key Contributions
The paper makes three primary contributions:

• Game Formulation: A two-player zero-sum differential game formulation that models time-varying, non-convex detection regions of rotating directional sensors over continuous strategy spaces.
• Continuous Redeployment: A novel defender formulation allowing sensors to slide continuously along physical building boundaries, enforced via a differentiable log-sum-exp constraint, enabling gradient-based optimization.
• Iterative Bilevel Optimization: An algorithmic framework that converges to a Local Nash Equilibrium by alternately optimizing sensor placement and attacker trajectories, with analytical first-order stationarity conditions derived for both players.

Results and Validation
The framework was evaluated through numerical simulations and a physical experimental demonstration:

• Monte Carlo Simulation: A 500-trial simulation demonstrated that the proposed framework achieves a 4× improvement in defender detection probability compared to randomized sensor placement (the natural baseline). The method achieved a 96.8% convergence rate to a Local Nash Equilibrium. In the converged state, the defender's detection probability increased significantly (from a mean of ~0.103 to ~0.419), while the attacker's success rate decreased.
• Convergence Behavior: The alternating optimization typically stabilized into a plateau, with numerical residuals decaying to near $10^{-6}$. Limit cycle behavior was observed in only 1 out of 500 trials (2%), which was successfully resolved by reinitialization.
• Experimental Demonstration: The framework was tested in a scaled-down physical environment simulating an airport defense scenario with an urban canyon. Using a Crazyflie 2.1 as the attacker and PTZ cameras as defenders, the experiments validated that the bilevel optimization produces consistent strategy improvements. The LNE strategy ($a^*, d^*$) resulted in a detection cost ($J$) of 0.9451, significantly higher than the initial heuristic placement ($J=0.6847$) and superior to scenarios where only one player optimized their strategy.

Significance and Claims
The authors position this work as a deployable baseline for heterogeneous sensor placements in Counter-UAS (CUAS) missions. They claim the significance lies in bridging three gaps in existing literature: the lack of continuous sensor redeployment along building boundaries, the absence of probabilistic directional FOV modeling in game-theoretic contexts, and the move away from discrete strategy spaces toward gradient-based bilevel optimization.

The paper modestly frames its contribution as establishing a necessary first step by isolating the contribution of deployment topology, acknowledging that the more complex coupled schedule-placement problem remains for future work. The results confirm that optimizing sensor placement in a continuous space, accounting for the dynamic nature of directional sensors, significantly enhances perimeter security against intelligent adversaries compared to static or randomized baselines.