Forecast-Aware Cooperative Planning on Temporal Graphs under Stochastic Adversarial Risk

1. 문제 정의 (Problem Definition)

이 논문은 적대적 감시나 이동하는 위험 요소가 존재하는 환경에서 다중 로봇 팀이 협력하여 임무를 수행할 때 발생하는 문제를 다룹니다.

• 동적 위험 환경: 기존 연구들은 대부분 정적 (static) 인 위험 지형을 가정했으나, 실제 환경에서는 적 (Adversary) 이 확률적 (stochastic) 인 동역학 (예: 체류 또는 이동) 을 따라 움직이며 위험 지역이 시간에 따라 변화합니다.
• 협력 지원 (Support Coordination) 의 한계: 로봇 팀은 위험한 구간을 통과할 때 동료의 '지원 (support)'을 받으면 비용을 줄일 수 있습니다. 그러나 기존 지원 기반 프레임워크는 현재 위험만 고려하여 미래의 위험 변화를 예측하지 못하므로, 지원이 너무 일찍, 너무 늦게, 혹은 더 이상 위험하지 않은 곳에 배치되는 비효율이 발생합니다.
• 목표: 시간에 따라 변화하는 확률적 적대적 위험을 예측 (Forecast) 하고, 이를 바탕으로 선제적 (Proactive) 으로 지원 위치를 할당하여 전체 팀의 기대 이동 비용 (Expected Team Cost) 을 최소화하는 협력 계획 프레임워크를 구축하는 것입니다.

2. 방법론 (Methodology)

제안된 프레임워크는 예측 인식 협력 계획 (Forecast-Aware Cooperative Planning) 으로, 세 가지 주요 단계로 구성됩니다.

A. 적대적 위험 예측 (Adversary-Induced Edge Risk Forecast)

• 모델링: 적대자의 움직임을 그래프의 간선 (Edge) 상에서 1 차 마르코프 체인 (First-order Markov stay-move process) 으로 모델링합니다. 적대자는 현재 간선에 머무르거나 인접한 간선으로 이동할 확률을 가집니다.
• 예측: 초기 적대자 분포를 기반으로 전이 행렬 (Transition Matrix) 을 사용하여 미래 시간 단계 ($t$) 에서의 간선 점유 확률 (Edge-occupancy probability) 을 전파합니다.
• 결과: 각 간선 $(u, v)$ 와 시간 $t$ 에 대한 위험 확률 $\rho_{uv}(t)$ 를 생성합니다. 이는 적대자가 하나 이상 존재할 확률로 계산됩니다.

B. 예측 인식 지원 할당 (Forecast-Aware Support Allocation)

예측된 위험 정보를 바탕으로 지원 노드 (Support Nodes) 를 최적의 위치에 할당합니다.

• 후보 노드 선정: 계획 기간 ($T$) 동안 위험이 발생할 것으로 예측된 간선에 대해, 해당 간선을 커버할 수 있는 지원 가능 노드 ($V_{sup}$) 중 $k$-hop 이내의 노드를 후보로 선정합니다.
• 스코어링 (Scoring): 각 후보 노드에 점수를 부여하여 최적의 위치를 선정합니다. 점수 함수는 다음 두 요소를 균형 있게 고려합니다:
  1. 경로 중첩 (Path Overlap): 로봇들이 자주 통과하는 주요 경로에 위치하는지 ($\hat{P}(x)$).
  2. 위험 잠재력 (Risk Potential): 예측된 누적 위험이 높은 간선을 커버할 수 있는 지리적 최적성 ($\hat{R}(x)$).
  • 점수 공식: $Score(x) = \alpha \hat{P}(x) (1 + \beta \hat{R}(x))$
• 할당: 각 위험 간선에 대해 점수가 높은 상위 $s$ 개의 노드를 지원 위치로 할당합니다.

C. 위험 인식 공동 경로 계획 (Risk-Aware Joint Path Planning)

• 시간 확장 그래프 (Temporal Graph): 예측된 위험 확률 $\rho_{uv}(t)$ 를 기반으로 시간 의존적 간선 비용 (Time-dependent edge costs) 을 정의합니다. 지원이 활성화되면 위험 비용이 감소합니다.
• 계획 알고리즘: Lazy A* (Lazily-Expanded A*) 알고리즘을 사용하여 기대 비용을 최소화하는 로봇들의 경로를 탐색합니다. 이는 모든 확률적 시나리오를 고려하는 대신 예측된 기대값을 사용하여 계산 복잡도를 줄이면서도 최적성을 유지합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 문제 공식화: 확률적 적대적 동역학 하에서 시간 의존적 비용이 발생하는 시계열 그래프 (Temporal Graphs) 상의 협력 다중 로봇 이동 문제를 공식화했습니다.
2. 예측 인식 지원 할당 메커니즘: 적대자의 '체류 - 이동 (Stay-Move)' 전이를 활용하여 미래 위험을 예측하고, 이를 바탕으로 지원 노드를 선제적으로 할당하는 새로운 메커니즘을 제안했습니다. 이는 기존 정적 접근법과 차별화됩니다.
3. 성능 검증: 비예측적 (Non-anticipatory) 베이스라인 (랜덤 할당, 초기 위험만 고려한 할당 등) 과 비교하여 제안된 방법이 예상 팀 비용을 일관되게 감소시키며, 이상적인 오라클 (Oracle) 계획자에 근접한 성능을 달성함을 실험을 통해 입증했습니다.

4. 실험 결과 (Experimental Results)

• 실험 설정: 다양한 크기의 그래프 (520 노드), 로봇 수 (24 대), 적대자 수 (4 명), 그리고 적대자의 체류 확률 (0.2~1.0) 을 변화시켜 평가했습니다.
• 성능 비교:
  • 제안된 Forecast-aware 방법은 모든 시나리오에서 No Support(지원 없음), Random(무작위 할당), TCGRE(초기 위험만 고려) 보다 낮은 기대 팀 비용을 기록했습니다.
  • 특히 적대자의 이동성이 높은 경우 (체류 확률 0.2~0.8) 성능 차이가 두드러졌습니다.
  • 체류 확률이 1.0 인 정적 환경에서는 기존 TCGRE 와 유사한 성능을 보여 방법론의 타당성을 확인했습니다.
• 비용 보정 (Calibration): 예측된 기대 비용 ($J_{exp}$) 과 몬테카를로 시뮬레이션으로 측정한 실제 발생 비용 ($J_{real}$) 간의 오차가 매우 작음을 확인하여 예측 모델의 정확성을 입증했습니다.
• 계산 효율성: 제안된 방법은 지원 노드를 전략적으로 선별하여 탐색 공간을 축소하므로, 복잡한 환경에서도 90 초 내의 시간 제한 안에 해를 찾을 수 있었습니다. 반면, 지원이 없는 경우나 비효율적인 할당은 시간 초과 (Timeout) 가 발생했습니다.
• 사례 연구: 5 노드 그래프 예시에서 지원 없이 대기하는 경우보다, 예측을 통해 지원을 배치한 경우 팀 비용이 약 42% 감소하고 임무 완료 시간이 단축됨을 시각적으로 보여주었습니다.

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

• 동적 환경 대응: 정적 위험 가정을 넘어, 시간에 따라 진화하는 확률적 위험을 고려한 협력 계획의 새로운 패러다임을 제시했습니다.
• 선제적 협력: 로봇들이 위험이 발생하기 전에 미리 지원 위치를 확보함으로써, 불필요한 대기나 우회를 줄이고 임무 효율성을 극대화합니다.
• 실용성: 구조 활동 (Search-and-Rescue) 이나 호송 보호 (Convoy Protection) 등 실제 다중 로봇 임무에서 적대적 요소가 존재하는 환경에 적용 가능한 강력한 프레임워크를 제공합니다.
• 한계 및 향후 과제: 현재는 적대자의 동역학 모델을 알고 있다는 가정과 중앙 집중식 계획에 의존합니다. 향후에는 부분 관측 가능성 하에서의 온라인 위험 추정 및 분산형 협력으로 확장할 계획입니다.

이 논문은 불확실성이 내재된 동적 환경에서 로봇 팀의 생존성과 효율성을 높이기 위해 예측 (Forecasting) 과 협력 (Cooperation) 을 통합한 획기적인 접근법을 제시했다는 점에서 중요한 의의를 가집니다.