Encirclement Guaranteed Finite-Time Capture against Unknown Evader Strategies

논문 개요

이 논문은 2 차원 무한 평면 환경에서 한 명의 추격 대상 (Evader) 을 포위하고 일정 시간 내에 포획하는 문제를 다룹니다. 핵심적인 특징은 추격자 (Pursuers) 가 추격 대상의 이동 전략 (속도와 방향) 을 전혀 알지 못하는 상황에서도, 추격 대상이 항상 추격자들의 볼록 껍질 (Convex Hull) 내부에 머물도록 보장하면서 (포위), 유한 시간 내에 포획을 달성하는 분산 제어 전략을 제안한다는 점입니다.

1. 문제 정의 (Problem Statement)

• 환경: 2 차원 무한 평면 ($\mathbb{R}^2$).
• 주체: $n$명의 추격자 ($n \ge 3$) 와 1 명의 추격 대상.
• 목표:
  1. 포위 (Encirclement): 모든 시간 $t$에서 추격 대상이 추격자들의 위치로 이루어진 볼록 껍질 $H(p_1, \dots, p_n)$ 내부에 있어야 함.
  2. 유한 시간 포획 (Finite-Time Capture): 유한 시간 $t_c$ 내에 최소 한 명의 추격자가 대상과 $r_c$ (포획 반경) 이내의 거리가 되어야 함.
• 제약 조건:
  • 추격 대상의 현재 속도 ($\mu$) 와 heading angle ($\psi$) 은 추격자에게 알려지지 않음 (불확실성).
  • 단, 대상의 최대 속도 ($\mu_m$) 는 추격자에게 알려져 있다고 가정.
  • 모든 추격자의 속도는 단위 속도 ($v_i = 1$) 로 정규화되며, $\mu_m < 1$ (추격자가 대상보다 빠름) 을 가정.
• 초기 조건: $t=0$ 시점에 대상은 이미 추격자들의 볼록 껍질 내부에 위치해 있음.

2. 방법론 (Methodology)

가. 면적 기반 포위 전략 (Area-Based Encirclement)

• 삼각분할 (Triangulation): 추격 대상과 인접한 두 추격자로 이루어진 삼각형 ($\triangle e p_j p_k$) 의 면적 $A_{jk}$를 정의합니다.
• 포위 조건: 대상이 볼록 껍질 내부에 있을 때 $A_{jk} > 0$, 경계선 위에 있을 때 $A_{jk} = 0$, 외부로 나갔을 때 $A_{jk} < 0$이 되도록 부호를 정의합니다.
• 핵심 원리: 포위가 유지되려면, 대상이 볼록 껍질의 한 변 (Edge) 위에 있을 때 ($A_{jk}=0$), 해당 면적의 시간 미분 $\dot{A}_{jk}$가 항상 0 이상 ($\dot{A}_{jk} \ge 0$) 이어야 합니다.
• 활성 추격자 (Active Pursuers): 대상이 특정 변 ($p_j p_k$) 위에 있을 때, 해당 변을 구성하는 두 추격자만 전략을 변경합니다.
• 전략 (Theorem 1): 활성 추격자들은 대상의 위치를 기준으로 특정 각도 범위 ($\phi$) 내에서 이동합니다. 이 각도 범위는 대상의 최대 속도 $\mu_m$에 따라 결정되며, 대상이 어떤 방향으로 도망치더라도 면적이 감소하지 않도록 보장합니다.
  • 조건: $v_j d_{ek} \sin \phi_j + v_k d_{ej} \sin \phi_k \ge d_{jk} \mu_m$

나. 유한 시간 포획 전략 (Finite-Time Capture Strategy)

• 라이아푸노프 함수 (Lyapunov Function): $V = \sum_{i=1}^n \|p_i - e\|$ (모든 추격자와 대상 간의 거리 합) 를 정의합니다.
• 두 단계 전략 (Theorem 2):
  1. 내부 단계 (Interior Phase): 대상이 볼록 껍질 내부에 있을 때, 모든 추격자는 순수 추적 (Pure Pursuit) 전략을 따릅니다 (대상 방향으로 직진).
  2. 경계 단계 (Edge Phase): 대상이 볼록 껍질의 변 위에 있을 때, 해당 변을 구성하는 활성 추격자들은 포위 보장 전략 (위에서 정의된 각도 범위 내) 을 따르고, 나머지 추격자는 순수 추적을 계속합니다.
• 수렴성 증명: 두 단계 모두에서 라이아푸노프 함수의 시간 미분 $\dot{V}$가 음수 상수 ($\dot{V} \le -n(1-\mu_m)$) 로 하한이 잡혀 있음을 증명하여, 유한 시간 내에 $V$가 포획 조건 ($r_c$) 에 도달함을 보였습니다.
• 포획 시간 상한선: $t_c \le \frac{V_0 - n r_c}{n(1 - \mu_m)}$으로 명시적인 상한식을 유도했습니다.

3. 주요 기여 (Key Contributions)

1. 동시 보장 (Simultaneous Guarantees): 기존 연구들은 포위 또는 포획 중 하나만 보장하거나 특정 가정 하에서만 해결했으나, 본 논문은 알 수 없는 추격 대상의 전략에 대해 포위 유지와 유한 시간 포획을 동시에 보장하는 첫 번째 분산 전략을 제시했습니다.
2. 삼각형 면적 기반 접근법: 볼록 껍질 내 포위 상태를 정량화하기 위해 삼각형 면적의 부호와 변화율을 활용하는 새로운 기하학적 접근법을 도입했습니다.
3. 명시적 포획 시간 상한선: 라이아푸노프 분석을 통해 포획에 필요한 최대 시간을 수학적으로 유도했습니다.
4. 완전 분산 제어 (Decentralized Control): 각 추격자는 다른 추격자와의 통신 없이, 자신의 위치와 대상 및 인접 추격자의 위치 정보만으로 전략을 결정할 수 있습니다.

4. 실험 결과 (Numerical Results)

• 시나리오: 3 명의 추격자와 1 명의 대상 ($\mu_m = 0.7$) 을 사용하여 다양한 대상 전략에 대한 시뮬레이션 수행.
  • Greedy Policy: 가장 가까운 추격자에서 도망치는 전략.
  • Switching Policy: 경계선과 내부 사이를 오가는 전략.
  • Random Policy: 인간과 같은 예측 불가능한 이동.
  • Closest Link Policy: 가장 가까운 경계선으로 이동하여 그 위에 머무는 전략.
• 성능:
  • 모든 전략에서 대상은 항상 볼록 껍질 내부에 유지되었으며, 약 1.15 초 ~ 1.25 초 내에 포획되었습니다.
  • 이론적으로 계산된 포획 시간 상한선 (약 3.10 초) 보다 훨씬 빠른 시간에 포획이 이루어졌습니다.
• 비교 분석: 기존 연구 [12] 의 'Sector Set based Robust MPC' 접근법과 비교.
  • MPC 방식은 포위 유지에는 성공했으나, 포획까지 약 42 초가 소요됨.
  • 제안된 방식은 약 1.15 초로 약 36 배 이상 빠른 포획을 달성했습니다. 이는 MPC 의 경직된 제약 조건이 추격자의 직접적인 접근을 방해했기 때문입니다.

5. 의의 및 결론 (Significance & Conclusion)

• 실용성: 군사적 감시, 보안 구역 내 침입자 제압 등, 적의 의도를 알 수 없는 상황에서 신속하고 안전하게 위협을 제거해야 하는 실제 응용 분야에 매우 유용합니다.
• 이론적 가치: 불확실성 하의 게임 이론적 접근과 제어 이론 (Lyapunov) 을 결합하여, 복잡한 다중 에이전트 시스템에서 '포위'와 '포획'이라는 두 가지 상충될 수 있는 목표를 동시에 달성하는 엄밀한 수학적 증명을 제시했습니다.
• 향후 과제: 3 차원 공간으로의 확장, 다수 대상 처리, 포획 시간 상한선의 개선 등이 향후 연구 과제로 제시되었습니다.

이 논문은 불확실한 환경에서 다수 에이전트 시스템이 어떻게 협력하여 목표를 달성할 수 있는지에 대한 강력한 이론적 틀과 실용적인 알고리즘을 제공합니다.