A Surveillance Evasion Game with Continuous Sensor Redeployment via Bilevel Optimization

Résumé Technique : Un Jeu d'Évitement de Surveillance avec Redéploiement Continu de Capteurs via une Optimisation Bi-niveau

Formulation du Problème
L'article aborde le défi sécuritaire critique des Systèmes Aériens sans Équipage (UAS) exploitant les lacunes spatio-temporelles dans les périmètres de capteurs pour pénétrer dans un espace aérien restreint sans être détectés. Les auteurs modélisent cette interaction comme un jeu différentiel à deux joueurs et à somme nulle entre un UAS adversaire (attaquant) et un réseau de capteurs hétérogène (défenseur) composé à la fois de capteurs directionnels et omnidirectionnels.

Contrairement aux approches antérieures qui restreignent souvent les défenseurs à des graphes de placement discrets, des configurations fixes, ou supposent une couverture omnidirectionnelle statique, ce travail formule le problème sur des espaces de stratégies continus. L'attaquant cherche une trajectoire spatio-temporelle sans collision d'un point de départ à un point d'arrivée minimisant la probabilité cumulative de détection. Inversement, le défenseur vise à maximiser cette probabilité en optimisant le placement spatial des capteurs. Une complexité clé découle de l'utilisation par le défenseur de capteurs directionnels rotatifs, qui créent des régions de couverture non convexes variant dans le temps et des lacunes prévisibles qu'un adversaire intelligent peut exploiter. Les auteurs notent que la recherche d'un point de selle global est intraitable en raison de la nature non convexe et de haute dimension des espaces de stratégies conjoints et des discontinuités introduites par les champs de vision (FOV) rotatifs des capteurs. Par conséquent, l'objectif est de calculer un Équilibre de Nash Local (LNE), un état où aucun joueur ne peut améliorer son gain par des déviations unilatérales infinitésimales.

Méthodologie
La solution proposée emploie un cadre d'optimisation bi-niveau itératif qui alterne entre la résolution des sous-problèmes de meilleure réponse de l'attaquant et du défenseur jusqu'à convergence vers un LNE.

1. Meilleure Réponse de l'Attaquant :
   Étant donné un placement fixe des capteurs, l'attaquant résout un problème de programmation non linéaire (NLP) pour minimiser la probabilité de détection. Pour gérer le paysage de détection non convexe, les auteurs utilisent une approche en deux étapes :

   • Initialisation : L'algorithme Space-Time Probabilistic Rapidly-exploring Random Tree (STP-RRT*) génère une trajectoire initiale faisable et sans collision naviguant autour des régions de couverture dynamiques des capteurs.
   • Raffinement : Un solveur NLP basé sur le gradient (IPOPT) affine cette trajectoire pour minimiser la probabilité cumulative de détection. Le modèle de détection utilise une fonction sigmoïde lisse pour approximer la visibilité, assurant la différentiabilité pour l'optimisation basée sur le gradient.

2. Meilleure Réponse du Défenseur :
   Étant donnée la trajectoire optimisée de l'attaquant, le défenseur résout un problème de redéploiement continu de capteurs pour maximiser la probabilité de détection.

   • Redéploiement Continu : Contrairement aux méthodes discrètes basées sur des graphes, les capteurs sont autorisés à glisser librement le long des limites de bâtiments polygonales convexes.
   • Contraintes Lisses : Pour permettre l'optimisation basée sur le gradient sur ces limites, les auteurs imposent des contraintes de placement en utilisant une approximation lisse log-sum-exp de la distance signée au bord de bâtiment le plus proche. Cette technique préserve la différentiabilité aux sommets du polygone, surmontant la non-différentiabilité des contraintes de limites rigides.

3. Schéma Itératif :
   Le cadre alterne entre la minimisation de l'attaquant et la maximisation du défenseur. Le processus se termine lorsque les résidus de gradient pour les deux joueurs tombent en dessous d'une tolérance prescrite, satisfaisant les conditions de stationnarité du premier ordre pour un LNE. Si l'algorithme entre dans un cycle limite (oscillation non décroissante), le défenseur réinitialise depuis un nouveau placement aléatoire pour retrouver la convergence.

Contributions Clés
L'article apporte trois contributions principales :

• Formulation du Jeu : Une formulation de jeu différentiel à deux joueurs et à somme nulle modélisant des régions de détection non convexes variant dans le temps pour des capteurs directionnels rotatifs sur des espaces de stratégies continus.
• Redéploiement Continu : Une nouvelle formulation pour le défenseur permettant aux capteurs de glisser continûment le long des limites physiques des bâtiments, imposée via une contrainte log-sum-exp différentiable, permettant une optimisation basée sur le gradient.
• Optimisation Bi-niveau Itérative : Un cadre algorithmique qui converge vers un Équilibre de Nash Local en optimisant alternativement le placement des capteurs et les trajectoires de l'attaquant, avec des conditions de stationnarité du premier ordre analytiques dérivées pour les deux joueurs.

Résultats et Validation
Le cadre a été évalué par le biais de simulations numériques et d'une démonstration expérimentale physique :

• Simulation de Monte Carlo : Une simulation de 500 essais a démontré que le cadre proposé réalise une amélioration de 4 fois de la probabilité de détection du défenseur par rapport à un placement aléatoire de capteurs (la ligne de base naturelle). La méthode a atteint un taux de convergence de 96,8 % vers un Équilibre de Nash Local. À l'état convergé, la probabilité de détection du défenseur a augmenté de manière significative (d'une moyenne d'environ 0,103 à environ 0,419), tandis que le taux de réussite de l'attaquant a diminué.
• Comportement de Convergence : L'optimisation alternée s'est généralement stabilisée en un plateau, avec des résidus numériques décroissant jusqu'à près de $10^{-6}$. Un comportement de cycle limite a été observé dans seulement 1 essai sur 500 (2 %), qui a été résolu avec succès par réinitialisation.
• Démonstration Expérimentale : Le cadre a été testé dans un environnement physique à échelle réduite simulant un scénario de défense d'aéroport avec un canyon urbain. En utilisant un Crazyflie 2.1 comme attaquant et des caméras PTZ comme défenseurs, les expériences ont validé que l'optimisation bi-niveau produit des améliorations de stratégie cohérentes. La stratégie LNE ($a^*, d^*$) a résulté en un coût de détection ($J$) de 0,9451, nettement supérieur au placement heuristique initial ($J=0,6847$) et supérieur aux scénarios où un seul joueur optimisait sa stratégie.

Signification et Revendications
Les auteurs positionnent ce travail comme une ligne de base déployable pour les placements de capteurs hétérogènes dans les missions de contre-UAS (CUAS). Ils affirment que la signification réside dans le comblement de trois lacunes dans la littérature existante : l'absence de redéploiement continu de capteurs le long des limites des bâtiments, l'absence de modélisation probabiliste du FOV directionnel dans les contextes théoriques des jeux, et le passage des espaces de stratégies discrets vers l'optimisation bi-niveau basée sur le gradient.

L'article présente modestement sa contribution comme établissant une première étape nécessaire en isolant la contribution de la topologie de déploiement, reconnaissant que le problème plus complexe de couplage entre calendrier et placement reste à traiter dans les travaux futurs. Les résultats confirment que l'optimisation du placement des capteurs dans un espace continu, tenant compte de la nature dynamique des capteurs directionnels, améliore considérablement la sécurité du périmètre contre des adversaires intelligents par rapport aux lignes de base statiques ou aléatoires.