Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees

1. 문제 정의 (Problem Definition)

이 논문은 미지의 이산 시간 동적 시스템 (unknown discrete-time dynamical systems) 에 대해 유한 시간 구간 (finite horizon) 내의 도달 가능 집합 (Reachable Set) 을 추정하는 문제를 다룹니다.

• 배경: 기존 도달 가능 집합 추정 방법은 잘 정의된 모델에 의존하거나, 데이터 기반 접근법에서는 관측된 궤적 (trajectories) 을 단순히 '절대적인 진실'로 간주하여 확률적 보장을 제공했습니다.
• 주요 과제: 실제 환경에서는 다음과 같은 세 가지 도전 과제가 동시에 존재합니다.
  1. 집합의 엄격함 (tightness) 과 신뢰성 (reliability) 간의 조정 가능한 트레이드오프: 너무 작은 집합은 위험을 과소평가하고, 너무 큰 집합은 제어 성능을 저하시킵니다.
  2. 교란된 궤적 데이터에 대한 강건성 (Robustness): 노이즈나 적대적 공격 (adversarial perturbations) 으로 인해 관측 데이터가 왜곡될 수 있습니다.
  3. 분포 이동 (Distribution Shift) 에 대한 보장: 학습 시의 데이터 분포와 배포 시의 분포가 달라질 때 (Wasserstein 거리 기준), 이론적 보장이 어떻게 저하되는지에 대한 명확한 한계가 필요합니다.

2. 방법론 (Methodology)

논문은 시나리오 최적화 (Scenario Optimization) 프레임워크를 기반으로 하되, 이를 도달 가능 집합 추정에 맞게 확장하고 강화했습니다.

A. 조정 가능한 완화 시나리오 프로그램 (Tunable Relaxed Scenario Program)

• 기존 연구들은 관측된 모든 궤적이 도달 가능 집합에 포함되어야 한다는 '경직된 제약 (hard constraints)'을 사용했습니다.
• 본 논문은 슬랙 변수 (slack variables, $\xi_i$) 를 도입하여 제약 조건을 완화했습니다.
  • 목적 함수: $\sum S(R_k) + \rho \sum \xi_i$
  • 여기서 $S(R_k)$는 집합의 크기 (부피 등) 를 나타내고, $\rho$는 조정 가능한 하이퍼파라미터입니다.
  • $\xi_i$는 특정 궤적이 집합에서 벗어날 수 있는 허용 오차를 의미합니다.
• 효과: $\rho$ 값을 조절함으로써 추정된 집합의 크기와 미래 궤적 포함에 대한 이론적 보장 사이의 균형을 사용자가 직접 조절할 수 있습니다.

B. 적대적 강건 도달 가능 집합 (Adversarially Robust Reachable Sets)

• 관측된 각 궤적 $x^{(i)}$가 반지름 $R$ 이내의 적대적 교란 (adversarial perturbations) 을 받을 수 있다고 가정합니다.
• 이를 위해 적대적 강건 시나리오 최적화 (Adversarially Robust Scenario Optimization) 기법을 적용하여, 교란된 모든 가능한 궤적 ($\tilde{x} \in A_{x^{(i)}}$) 에 대해 제약 조건이 만족되도록 문제를 재구성했습니다.
• 적대적 복잡도 (Adversarial Complexity, $s^*_A$): 도달 가능 집합을 구성하는 데 중요한 궤적의 수를 정의하고, 이를 기반으로 미래 궤적의 제외 확률 (violation probability) 에 대한 사후 확률적 보장 (a posteriori probabilistic guarantees) 을 유도했습니다.

C. Wasserstein 분포 이동에 대한 강건성

• 배포 시 데이터 분포가 학습 분포에서 1-Wasserstein 거리로 $\tilde{\mu}$만큼 이동할 경우, 도달 가능 집합의 보장이 어떻게 영향을 받는지 분석했습니다.
• 결과: Wasserstein 반지름 ($\tilde{\mu}$) 과 적대적 반지름 ($R$) 의 비율에 비례하여 이론적 위반 한계가 증가함을 보였습니다. 즉, 분포 이동이 발생하더라도 보장이 우아하게 저하 (degrade gracefully) 됨을 증명했습니다.

D. 계산 가능한 볼록 재형성 (Tractable Convex Reformulations)

• 다양한 기하학적 형태에 대해 문제를 볼록 최적화 (Convex Optimization) 문제로 재구성하여 수치적 계산을 가능하게 했습니다.
  • $p$-노름 볼 (p-norm balls): 부피 또는 반지름을 최소화.
  • 타원체 (Ellipsoids): 행렬 $C_k$와 벡터 $b_k$를 결정.
  • 존토프 (Zonotopes): 생성 행렬과 반폭을 결정.

3. 주요 기여 (Key Contributions)

1. 조정 가능한 트레이드오프 프레임워크: 기존 시나리오 최적화 기반 방법론의 경직된 제약을 완화하고, 슬랙 변수와 페널티 파라미터 ($\rho$) 를 통해 집합의 크기와 일반화 성능 사이의 균형을 조절할 수 있는 새로운 프레임워크를 제안했습니다.
2. 적대적 교란 하의 사후 보장: 관측 데이터가 노이즈나 적대적 공격으로 교란될 수 있음을 명시적으로 모델링하고, 이를 해결하는 강건한 도달 가능 집합 추정 방법과 이에 대한 확률적 보장을 제시했습니다.
3. 분포 이동에 대한 명시적 한계: Wasserstein 거리 기반의 분포 이동이 발생할 때, 이론적 보장이 얼마나 저하되는지에 대한 명시적인 상한선 (explicit bound) 을 유도했습니다.
4. 다양한 기하학적 구조의 적용: 볼, 타원체, 존토프 등 다양한 형태의 집합에 대해 계산적으로 효율적인 볼록 재형성 (convex reformulations) 을 도출했습니다.

4. 실험 결과 (Results)

• 시뮬레이션 설정: $T=25$ 시간 구간을 가진 비선형 확률적 동적 시스템을 사용했습니다. $N=1000$개의 궤적을 학습 데이터로 사용했으며, 각 궤적에 적대적 교란을 가했습니다.
• 기하학적 형태 비교: 볼 (Euclidean balls), 타원체 (ellipsoids), 존토프 (zonotopes) 세 가지 형태를 비교했습니다.
  • $\rho$의 영향: $\rho$가 증가할수록 슬랙 변수에 대한 페널티가 커져, 관측된 궤적을 더 잘 포함하는 더 큰 집합이 생성됨을 확인했습니다. 이는 집합 크기와 미래 궤적 포함률 간의 트레이드오프를 시각적으로 입증했습니다.
  • 이론적 vs 경험적 위반률: 다양한 샘플 수 ($N$) 와 $\rho$ 값에서 이론적 위반 한계 (dashed lines) 가 경험적 위반률 (solid lines) 보다 항상 높게 나타났습니다. 이는 제안된 방법론이 확률적 보장을 잘 유지함을 의미합니다.
  • 존토프의 특징: 존토프는 타원체나 볼보다 더 많은 샘플이 필요하지만, 더 엄밀한 (tighter) 도달 가능 영역을 제공합니다.
• 분포 이동 테스트: 학습 분포와 다른 분포 (평균과 분산이 약간 다른 가우시안) 에서 테스트한 결과, 제안된 Wasserstein 기반 상한선이 실제 위반률을 잘 예측하고 있음을 확인했습니다.

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

이 논문은 데이터 기반 도달 가능 집합 추정 분야에서 다음과 같은 중요한 진전을 이루었습니다:

• 실용성 증대: 이상치 (outliers) 나 데이터 오염에 민감하지 않도록 설계된 유연한 프레임워크를 제공하여, 실제 시스템의 불확실성과 데이터 품질 문제를 해결합니다.
• 이론적 엄밀성: 단순한 데이터 피팅을 넘어, 적대적 공격과 분포 변화라는 두 가지 주요 불확실성 요인에 대해 수학적으로 엄밀한 보장을 제공합니다.
• 확장성: 다양한 기하학적 형태에 적용 가능한 볼록 최적화 형식을 제공하여, 실제 제어 및 안전 검증 (safety verification) 문제에 바로 적용 가능한 계산적 도구를 마련했습니다.

결론적으로, 이 연구는 조정 가능한 매개변수를 통해 안전성과 효율성을 균형 있게 설계할 수 있으며, 적대적 환경과 분포 변화 하에서도 신뢰할 수 있는 안전 보장을 제공하는 강력한 데이터 기반 방법론을 제시합니다.