A Surveillance Evasion Game with Continuous Sensor Redeployment via Bilevel Optimization

기술 요약: 이계 최적화를 통한 연속 센서 재배치를 활용한 감시 회피 게임

문제 공식화
본 논문은 무인 항공 시스템 (UAS) 이 센서 외곽의 시공간적 공백을 악용하여 통제된 공역에 탐지되지 않고 침투한다는 중대한 보안 문제를 다룬다. 저자들은 이 상호작용을 방향성 센서와 전방향성 센서로 구성된 이종 센서 네트워크 (수비자) 와 적대적 UAS (공격자) 간의 2 인 제로섬 미분 게임으로 모델링한다.

이전 연구들이 종종 수비자를 이산적 배치 그래프, 고정된 구성, 또는 정적 전방향성 커버리지를 가정하는 데 국한시켰던 것과 달리, 본 연구는 연속 전략 공간에 기반하여 문제를 공식화한다. 공격자는 탐지 확률의 누적 값을 최소화하는 충돌 없는 시공간 궤적을 시작점에서 목표점까지 찾기를 추구하는 반면, 수비자는 센서의 공간적 배치를 최적화하여 이 확률을 극대화하려 한다. 주요 복잡성은 회전하는 방향성 센서의 사용에서 비롯되는데, 이는 시간에 따라 변하는 비볼록 커버리지 영역과 예측 가능한 공백을 생성하여 지능적인 적대자가 이를 악용할 수 있게 만든다. 저자들은 고차원적이고 비볼록한 결합 전략 공간과 회전하는 센서의 시야각 (FOV) 으로 인해 발생하는 불연속성 때문에 전역 안장점 (global saddle point) 을 찾는 것은 계산적으로 불가능하다고 지적한다. 따라서 목적은 무한소 단방향 편차로도 어느 플레이어도 보상을 개선할 수 없는 상태인 국소 내시 균형 (LNE) 을 계산하는 것이다.

방법론
제안된 솔루션은 LNE 에 수렴할 때까지 공격자와 수비자의 최적 대응 하문제를 번갈아 해결하는 반복적 이계 최적화 프레임워크를 사용한다.

1. 공격자의 최적 대응:
   고정된 센서 배치가 주어지면, 공격자는 탐지 확률을 최소화하기 위해 비선형 프로그래밍 (NLP) 문제를 해결한다. 비볼록한 탐지 지형을 처리하기 위해 저자들은 두 단계 접근법을 활용한다:

   • 초기화: 시공간 확률적 급속 탐색 랜덤 트리 (STP-RRT*) 알고리즘이 동적 센서 커버리지 영역을 우회하는 실현 가능하고 충돌 없는 초기 궤적을 생성한다.
   • 정제: 기울기 기반 NLP 솔버 (IPOPT) 가 누적 탐지 확률을 최소화하도록 이 궤적을 정제한다. 탐지 모델은 미분 가능성을 보장하여 기울기 기반 최적화를 가능하게 하는 부드러운 시그모이드 함수를 사용하여 가시성을 근사화한다.

2. 수비자의 최적 대응:
   공격자의 최적화된 궤적이 주어지면, 수비자는 탐지 확률을 극대화하기 위해 연속 센서 재배치 문제를 해결한다.

   • 연속 재배치: 이산적 그래프 기반 방법과 달리, 센서는 볼록 다각형 건물의 경계를 따라 자유롭게 미끄러지도록 허용된다.
   • 부드러운 제약 조건: 이러한 경계에서 기울기 기반 최적화를 가능하게 하기 위해, 저자들은 가장 가까운 건물 가장자리에 대한 부호付き 거리의 로그 - 합 - 지수 (log-sum-exp) 부드러운 근사를 사용하여 배치 제약 조건을 부과한다. 이 기법은 다각형 꼭짓점에서의 미분 가능성을 유지하여 경성 (hard) 경계 제약의 비미분 가능성을 극복한다.

3. 반복 체계:
   프레임워크는 공격자의 최소화 과정과 수비자의 극대화 과정을 번갈아 수행한다. 이 과정은 두 플레이어의 기울기 잔차가 지정된 허용 오차 이하로 떨어지고 LNE 의 1 차 정류 조건을 만족할 때 종료된다. 알고리즘이 한계 주기 (감쇠하지 않는 진동) 에 진입하면, 수비자가 새로운 무작위 배치에서 재초기화하여 수렴을 회복한다.

주요 기여
본 논문은 세 가지 주요 기여를 한다:

• 게임 공식화: 회전하는 방향성 센서의 시간에 따라 변하는 비볼록 탐지 영역을 연속 전략 공간에서 모델링하는 2 인 제로섬 미분 게임 공식화.
• 연속 재배치: 미분 가능한 로그 - 합 - 지수 제약 조건을 통해 물리적 건물 경계를 따라 센서가 연속적으로 미끄러지도록 허용하는 새로운 수비자 공식화, 이를 통해 기울기 기반 최적화를 가능하게 함.
• 반복적 이계 최적화: 센서 배치와 공격자 궤적을 번갈아 최적화하여 국소 내시 균형에 수렴하는 알고리즘적 프레임워크이며, 두 플레이어 모두에 대해 유도된 분석적 1 차 정류 조건을 포함함.

결과 및 검증
본 프레임워크는 수치 시뮬레이션과 물리적 실험 실증을 통해 평가되었다:

• 몬테카를로 시뮬레이션: 500 회 시뮬레이션에서 제안된 프레임워크가 무작위 센서 배치 (자연스러운 기준선) 에 비해 수비자의 탐지 확률에서 4 배 향상을 달성함을 보였다. 이 방법은 96.8% 의 수렴률로 국소 내시 균형에 도달했다. 수렴 상태에서 수비자의 탐지 확률은 평균 약 0.103 에서 약 0.419 로 크게 증가한 반면, 공격자의 성공률은 감소했다.
• 수렴 행동: 교대 최적화는 일반적으로 플래토 (plateau) 로 안정화되었으며, 수치 잔차는 $10^{-6}$ 근처로 감소했다. 500 회 시뮬레이션 중 1 회 (2%) 에서만 한계 주기 행동이 관찰되었으며, 재초기화를 통해 성공적으로 해결되었다.
• 실험 실증: 본 프레임워크는 도시 협곡이 있는 공항 방어 시나리오를 시뮬레이션한 축소된 물리적 환경에서 테스트되었다. 공격자로 Crazyflie 2.1 을, 수비자로 PTZ 카메라를 사용하여 실험한 결과, 이계 최적화가 일관된 전략 개선을 산출함을 검증했다. LNE 전략 ($a^*, d^*$) 은 탐지 비용 ($J$) 을 0.9451 로 만들어, 초기 휴리스틱 배치 ($J=0.6847$) 보다 훨씬 높았으며, 한 플레이어만 전략을 최적화한 시나리오보다 우월했다.

의의 및 주장
저자들은 이 작업을 Counter-UAS (CUAS) 임무에서 이종 센서 배치를 위한 배포 가능한 기준선으로 위치시킨다. 그들은 기존 문헌의 세 가지 격차를 해소하는 데 의의가 있다고 주장한다: 건물 경계를 따른 연속 센서 재배치의 부재, 게임 이론적 맥락에서 확률적 방향성 FOV 모델링의 부재, 그리고 이산 전략 공간에서 기울기 기반 이계 최적화로 이동한 점이다.

본 논문은 배포 토폴로지의 기여를 분리함으로써 필수적인 첫걸음을 마련하는 것으로 겸손하게 자신의 기여를 규정하며, 더 복잡한 결합 일정 - 배치 문제는 향후 과제로 남아 있음을 인정한다. 결과는 방향성 센서의 역동적 특성을 고려하여 연속 공간에서 센서 배치를 최적화하는 것이 정적 또는 무작위 기준선에 비해 지능적인 적대자에 대한 외곽 보안을 크게 강화한다는 것을 확인시켜 준다.