A Surveillance Evasion Game with Continuous Sensor Redeployment via Bilevel Optimization

Technische Samenvatting: Een Spel voor Surveillanceontduiking met Continue Herplaatsing van Sensoren via Bilevel-optimalisatie

Probleemformulering
Het artikel behandelt de kritieke veiligheidsuitdaging dat Onbemande Luchtvaartsystemen (UAS's) ruimtetijd-gaten in sensorperimeters benutten om ongemerkt in beperkt luchtruim binnen te dringen. De auteurs modelleren deze interactie als een tweespeler nul-som differentieelspel tussen een vijandige UAS (aanvaller) en een heterogeen sensornetwerk (verdediger) dat bestaat uit zowel directionele als omnidirectionele sensoren.

In tegenstelling tot eerdere benaderingen die verdedigers vaak beperken tot discrete plaatsingsgrafieken, vaste configuraties of uitgaan van statische omnidirectionele dekking, formuleert dit werk het probleem over continue strategieruimten. De aanvaller streeft naar een botsingsvrije ruimtetijd-traject van een startpunt naar een doelpunt dat de cumulatieve detectiekans minimaliseert. Omgekeerd beoogt de verdediger deze kans te maximaliseren door de ruimtelijke plaatsing van sensoren te optimaliseren. Een belangrijke complexiteit ontstaat door het gebruik van roterende directionele sensoren door de verdediger, die tijdsvariërende, niet-convexe dekkinggebieden en voorspelbare gaten creëren die een intelligente adversary kan benutten. De auteurs merken op dat het vinden van een globaal zadelpunt onberekenbaar is vanwege de hoge-dimensionaliteit en niet-convexe aard van de gezamenlijke strategieruimten en de discontinuïteiten die worden geïntroduceerd door roterende sensorzichtvelden (FOV). Bijgevolg is het doel het berekenen van een lokaal Nash-evenwicht (LNE), een toestand waarin geen enkele speler zijn uitbetaling kan verbeteren door infinitesimale eenzijdige afwijkingen.

Methodologie
De voorgestelde oplossing maakt gebruik van een iteratief bilevel-optimalisatiekader dat afwisselend de best-response deelvraagstukken van de aanvaller en de verdediger oplost totdat convergentie naar een LNE is bereikt.

1. Best Response van de Aanvaller:
   Gegeven een vaste sensorplaatsing lost de aanvaller een niet-lineair programmeringsprobleem (NLP) op om de detectiekans te minimaliseren. Om de niet-convexe detectielandschap te hanteren, gebruiken de auteurs een tweestapsbenadering:

   • Initialisatie: Het Space-Time Probabilistic Rapidly-exploring Random Tree (STP-RRT*) algoritme genereert een haalbaar, botsingsvrij initieel traject dat rond dynamische sensordekkinggebieden navigeert.
   • Verfijning: Een op gradiënten gebaseerde NLP-oplosser (IPOPT) verfijnt dit traject om de cumulatieve detectiekans te minimaliseren. Het detectiemodel maakt gebruik van een gladde sigmoidfunctie om zichtbaarheid te benaderen, waardoor differentieerbaarheid voor gradiëntgebaseerde optimalisatie wordt gewaarborgd.

2. Best Response van de Verdediger:
   Gegeven het geoptimaliseerde traject van de aanvaller lost de verdediger een probleem voor continue sensorherplaatsing op om de detectiekans te maximaliseren.

   • Continue Herplaatsing: In tegenstelling tot discrete grafgebaseerde methoden, mogen sensoren vrij glijden langs de grenzen van convexe veelhoekige gebouwen.
   • Gladde Constraints: Om gradiëntgebaseerde optimalisatie op deze grenzen mogelijk te maken, handhaven de auteurs plaatsingsconstraints met behulp van een log-sum-exp gladde benadering van de tekensignatuur van de afstand tot de dichtstbijzijnde rand van een gebouw. Deze techniek behoudt differentieerbaarheid op veelhoekhoekpunten en overwint de niet-differentieerbaarheid van harde randconstraints.

3. Iteratief Schema:
   Het kader wisselt af tussen minimalisatie door de aanvaller en maximalisatie door de verdediger. Het proces wordt beëindigd wanneer de gradiëntresiduen voor beide spelers onder een voorgeschreven tolerantie dalen, waarmee de eerste-orde stationariteitsvoorwaarden voor een LNE worden voldaan. Als het algoritme een limietcyclus ingaat (niet-afnemende oscillatie), initialiseert de verdediger opnieuw vanuit een nieuwe willekeurige plaatsing om convergentie te herstellen.

Belangrijkste Bijdragen
Het artikel levert drie primaire bijdragen:

• Spelformulering: Een tweespeler nul-som differentieelspelformulering die tijdsvariërende, niet-convexe detectiegebieden van roterende directionele sensoren over continue strategieruimten modelleert.
• Continue Herplaatsing: Een nieuwe verdedigerformulering die sensoren toestaat continu te glijden langs fysieke gebouwgrenzen, afgedwongen via een differentieerbare log-sum-exp constraint, waardoor gradiëntgebaseerde optimalisatie mogelijk wordt.
• Iteratief Bilevel-optimalisatie: Een algoritmisch kader dat convergeert naar een lokaal Nash-evenwicht door afwisselend sensorplaatsing en aanvallerstrajecten te optimaliseren, met analytische eerste-orde stationariteitsvoorwaarden die voor beide spelers zijn afgeleid.

Resultaten en Validatie
Het kader werd geëvalueerd via numerieke simulaties en een fysieke experimentele demonstratie:

• Monte Carlo Simulatie: Een simulatie met 500 proeven toonde aan dat het voorgestelde kader een 4-voudige verbetering bereikt in de detectiekans van de verdediger ten opzichte van willekeurige sensorplaatsing (de natuurlijke baseline). De methode bereikte een convergentiepercentage van 96,8% naar een lokaal Nash-evenwicht. In de geconvergeerde toestand nam de detectiekans van de verdediger significant toe (van een gemiddelde van ~0,103 naar ~0,419), terwijl het succespercentage van de aanvaller afnam.
• Convergentiegedrag: De afwisselende optimalisatie stabiliseerde doorgaans in een plateau, met numerieke residuen die afnamen tot bijna $10^{-6}$. Limietcykelgedrag werd waargenomen in slechts 1 van de 500 proeven (2%), wat succesvol werd opgelost door herinitialisatie.
• Experimentele Demonstratie: Het kader werd getest in een schaalverkleinde fysieke omgeving die een luchthavenverdedigingsscenario met een stedelijke canyon simuleerde. Met een Crazyflie 2.1 als aanvaller en PTZ-camera's als verdedigers, bevestigden de experimenten dat de bilevel-optimalisatie consistente strategische verbeteringen oplevert. De LNE-strategie ($a^*, d^*$) resulteerde in een detectiekost ($J$) van 0,9451, aanzienlijk hoger dan de initiële heuristische plaatsing ($J=0,6847$) en superieur aan scenario's waarin slechts één speler zijn strategie optimaliseerde.

Betekenis en Claims
De auteurs positioneren dit werk als een inzetbare baseline voor heterogene sensorplaatsingen in Counter-UAS (CUAS) missies. Zij claimen dat de betekenis ligt in het overbruggen van drie gaten in de bestaande literatuur: het gebrek aan continue sensorherplaatsing langs gebouwgrenzen, de afwezigheid van probabilistische directionele FOV-modellering in speltheoretische contexten, en de verschuiving weg van discrete strategieruimten naar gradiëntgebaseerde bilevel-optimalisatie.

Het artikel presenteert zijn bijdrage bescheiden als het zetten van een noodzakelijke eerste stap door de bijdrage van de plaatsingstopologie te isoleren, met erkenning dat het complexere gekoppelde planning- en plaatsingsprobleem voor toekomstig werk blijft. De resultaten bevestigen dat het optimaliseren van sensorplaatsing in een continue ruimte, rekening houdend met het dynamische karakter van directionele sensoren, de perimeterveiligheid tegen intelligente adversaries aanzienlijk verbetert in vergelijking met statische of willekeurige baselines.