Data-Driven Reachability of Nonlinear Lipschitz Systems via Koopman Operator Embeddings

이 논문은 비선형 리프시츠 시스템의 데이터 기반 도달 가능성 분석을 위해 코프만 연산자 임베딩과 존토크 집합 표현을 결합하여 기존 방법보다 긴 예측 구간에서 보수성을 줄이면서도 형식적 안전 보장을 유지하는 새로운 프레임워크를 제안하고 있습니다.

핵심

이 논문은 **"로봇이나 자율주행차가 미지의 환경에서 안전하게 움직일 수 있는지, 앞으로 어디로 갈지 예측하는 새로운 방법"**을 소개합니다.

기존의 방법들은 너무 보수적이라서 "아마도 여기까지 갈 거야"라고 말하면, 실제로는 훨씬 더 좁은 범위만 갈 수 있음에도 불구하고 "아마도 저기까지 갈 거야"라고 너무 넓게 예측하는 문제가 있었습니다. 이 논문은 그 문제를 해결하는 지능적인 예측 도구를 개발했습니다.

이 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

🎈 비유: 구름 속을 날아다니는 풍선

상상해 보세요. 여러분이 **풍선 (로봇)**을 들고 있고, 바람 (불확실성) 이 불고 있습니다. 풍선이 어디로 날아갈지 정확히 알 수 없기 때문에, 우리는 풍선이 닿을 수 있는 **최대 범위 (안전 영역)**를 그려야 합니다.

1. 기존 방법의 문제점: "너무 큰 상자"

기존의 데이터 기반 방법들은 풍선의 움직임을 예측할 때, 너무 큰 상자를 씌웠습니다.

• 왜? 풍선이 구불구불한 길 (비선형 시스템) 을 따라 움직일 때, 이를 단순한 직선으로만 생각하려고 했기 때문입니다.
• 결과: "풍선이 이 상자에 들어갈 거야"라고 말하지만, 실제 풍선은 상자 구석구석까지 가지도 못합니다. 이렇게 되면 "안전하다"고 판단하기 위해 불필요하게 넓은 영역을 피해야 하므로, 로봇이 움직일 수 있는 공간이 너무 좁아져서 비효율적입니다.

2. 이 논문의 해결책: "공중으로 올라가는 사다리" (쿠퍼만 연산자)

이 논문은 **"쿠퍼만 (Koopman) 연산자"**라는 마법 같은 사다리를 사용합니다.

• 비유: 풍선이 2 차원 평면에서 구불구불하게 날아다니는 것을 예측하기 어렵다면, **3 차원 공간 (하늘)**으로 풍선을 올려다보는 것입니다.
• 원리: 3 차원 공간 (고차원 공간) 으로 올라가서 보면, 풍선의 복잡한 구불구불한 움직임이 매우 단순하고 직선적인 선으로 보일 수 있습니다.
• 효과: 복잡한 비선형 운동을, 하늘에서는 단순한 직선 운동처럼 예측할 수 있게 됩니다. 이렇게 하면 훨씬 더 정확한 범위를 그릴 수 있습니다.

3. 데이터로 배우기: "지도 없이 길을 찾는 법"

이 방법은 로봇의 정확한 물리 법칙 (수식) 을 몰라도 됩니다. 대신, **과거에 로봇이 실제로 움직인 데이터 (노이즈가 섞인 기록)**만 있으면 됩니다.

• 학습: 로봇이 과거에 어떻게 움직였는지 데이터를 모아, "아, 이 데이터 패턴을 보면 하늘에서는 이렇게 직선으로 움직이는구나"라고 학습합니다.
• 오차 보정: 물론 하늘에서 본다고 해서 100% 완벽하지는 않습니다. 그래서 **잔여 오차 (Residual Set)**라는 "안전망"을 추가로 씌웁니다. "우리가 예측한 직선 경로에서 조금 벗어날 수도 있으니, 이 작은 오차 범위까지 포함하자"라고 계산합니다.

4. 최종 결과: "정확한 안전지대"

이 모든 과정을 거쳐서 다시 지면 (원래 상태 공간) 으로 내려오면, 우리는 기존 방법보다 훨씬 작고 정확한 안전 영역을 얻게 됩니다.

• 기존: "이 넓은 상자 안에 있을 거야." (너무 넓어서 쓸모없음)
• 이 논문: "이 좁고 정확한 영역 안에 있을 거야." (정확해서 로봇이 더 자유롭게 움직일 수 있음)

---

🚗 실제 실험 결과

연구진은 이 방법을 자율주행 자동차에 적용해 보았습니다.

• 결과: 기존 방법들은 시간이 지날수록 예측 범위가 너무 넓어져서 "차량이 이 넓은 도로 전체를 다 덮을 수 있어!"라고 말했지만, 이 새로운 방법은 **"차량은 이 좁은 차선 안에만 있을 거야"**라고 훨씬 정확하게 예측했습니다.
• 의미: 더 정확한 예측은 로봇이 장애물을 피할 때 불필요하게 멈추지 않고, 더 빠르고 안전하게 주행할 수 있게 해줍니다.

💡 한 줄 요약

"복잡한 로봇의 움직임을 예측할 때, 기존에는 너무 큰 상자로 막았지만, 이 논문은 데이터를 이용해 '하늘에서 내려다보는 시점'으로 바꾸어 훨씬 작고 정확한 안전 영역을 찾아냈습니다."

이 기술은 로봇이 더 똑똑하고 안전하게 우리 생활 속으로 들어올 수 있는 중요한 디딤돌이 될 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

• 배경: 로봇 제어 및 안전성 검증에서 시스템이 불확실한 환경에서 작동할 때, 모든 가능한 미래 상태를 포함하는 '도달 가능 집합 (Reachable Set)'을 계산하는 것은 필수적입니다. 기존의 데이터 기반 방법은 주로 존토포 (Zonotope) 표현을 사용하여 계산 효율성을 확보합니다.
• 한계점:
  • 비선형성: 비선형 시스템의 경우, 기존 데이터 기반 방법 (예: 선형 회귀 모델) 은 예측 구간이 길어지거나 측정 노이즈가 있을 때 과도하게 보수적인 (overly conservative) 결과를 초래합니다. 즉, 실제 도달 가능한 영역보다 훨씬 넓은 영역을 안전 영역으로 가정하여 제어 성능을 저하시킵니다.
  • 모델 불확실성: 정확한 물리 모델이 없는 경우, 학습된 모델의 오차와 프로세스 노이즈를 동시에 고려하여 엄격한 안전 보장을 제공하는 것이 어렵습니다.
• 목표: 측정된 상태 - 입력 데이터만을 사용하여 비선형 시스템의 도달 가능 집합을 계산하되, 기존 방법보다 더 정밀한 (tighter) 과대 근사 (over-approximation) 를 제공하면서도 형식적인 안전 보장을 유지하는 프레임워크를 개발하는 것입니다.

2. 제안된 방법론 (Methodology)

저자들은 Koopman 연산자 (Koopman Operator) 이론을 데이터 기반 접근법과 결합한 새로운 프레임워크를 제안합니다.

A. Koopman 연산자 기반 리프팅 (Lifting)

• 핵심 아이디어: 비선형 동역학을 고차원의 관측 가능 변수 (observable) 공간으로 '리프팅 (lifting)'하여, 원래의 비선형 시스템을 유한 차원의 선형 시스템으로 근사화합니다.
• 상태 - 입력 의존성 (State-Input Dependent): 기존 Koopman 방법들이 주로 선형 시간 불변 (LTI) 모델에 의존하는 것과 달리, 이 논문은 상태와 입력에 모두 의존하는 리프팅 함수를 사용합니다. 이는 비선형 제어 입력의 영향을 더 정확하게 포착하여 모델 정확도를 높입니다.
• 데이터 학습: 최소 제곱법 (Least-Squares Regression) 을 사용하여 측정된 상태 - 입력 시계열 데이터로부터 Koopman 행렬을 직접 학습합니다.

B. 불확실성 모델링 및 잔차 보정

학습된 선형 모델은 완벽한 근사가 아니므로, 다음과 같은 오차 원인을 명시적으로 모델링하여 도달 가능 집합에 포함시킵니다:

1. 선형화 오차 (Linearization Error): 리프팅된 공간에서의 비선형 동역학을 선형화할 때 발생하는 잔차 ($\bar{L}_k$).
2. Koopman 모델링 잔차 (Modeling Residual): 학습된 Koopman 모델과 실제 데이터 간의 다단계 예측 오차 ($L_k$). 이는 모든 사용 가능한 궤적에 대한 오차를 집계하여 구간 (interval) 으로 추정합니다.
3. 프로세스 노이즈 (Process Noise): 측정 및 시스템 노이즈 ($w_k$) 를 리프팅 공간에서 Lipschitz 연속성을 이용해 상한을 구합니다.
4. 데이터 커버링 오차 (Covering Error): 학습 데이터가 도달 가능한 전체 영역을 완전히 커버하지 못할 때 발생하는 오차 ($\epsilon$) 를 Lipschitz 상수와 데이터 커버링 반경을 통해 추정합니다.

C. 도달 가능성 분석 알고리즘

1. 리프팅 공간에서의 전파: 학습된 선형 Koopman 모델을 사용하여 초기 집합 (존토포) 을 리프팅 공간에서 시간 단계별로 전파합니다.
2. 오차 집합 합산: 전파된 집합에 위의 4 가지 불확실성 집합 (선형화 오차, 모델링 잔차, 노이즈, 커버링 오차) 을 Minkowski 합으로 추가하여 보수적인 상한을 형성합니다.
3. 원래 공간으로 투영: 리프팅 공간에서 계산된 도달 가능 집합을 원래의 상태 공간으로 투영하여 최종적인 도달 가능 집합을 얻습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 데이터 기반 프레임워크: Lipschitz 연속성을 가진 비선형, 비아핀 (non-affine) 시스템을 위한 Koopman 연산자 기반 도달 가능성 분석 프레임워크를 제안했습니다. 이는 노이즈가 포함된 측정 데이터에서 직접 학습됩니다.
2. 고급 리프팅 기법: 상태와 입력에 의존하는 관측 가능 변수를 도입하여, 기존 LTI 기반 Koopman 모델보다 비선형 동역학을 더 정확하게 근사화합니다.
3. 엄격한 안전 보장 (Formal Guarantees): 학습 오차, 노이즈, 선형화 오차, 데이터 커버링 오차를 모두 고려하여, 계산된 도달 가능 집합이 실제 시스템의 모든 가능한 궤적을 포함함 (over-approximation) 을 수학적으로 증명했습니다.
4. 확장성 및 효율성: 존토포 (Zonotope) 의 선형 변환 및 Minkowski 합 연산을 활용하여 계산 효율성을 유지하면서도 긴 예측 구간에서도 보수성을 크게 줄였습니다.

4. 실험 결과 (Results)

논문은 세 가지 시나리오를 통해 제안된 방법의 유효성을 검증했습니다:

• 시나리오 1: 아핀 (Affine) Lipschitz 시스템 (CSTR):
  • 연속 교반 탱크 반응기 (CSTR) 시뮬레이션에서 제안된 방법이 CORA (기존 모델 기반 도구) 및 기존 데이터 기반 선형 회귀 (LS) 방법보다 훨씬 좁고 정확한 도달 가능 집합을 제공함을 보였습니다. 특히 긴 예측 구간에서 보수성이 현저히 감소했습니다.
• 시나리오 2: 비아핀 (Non-affine) 비선형 시스템:
  • 입력과 상태가 곱셈 형태로 결합된 복잡한 비선형 시스템에서 제안된 방법이 다른 방법들보다 더 적은 보수성 (less conservative) 을 보이며 실제 궤적을 더 잘 포착했습니다.
• 시나리오 3: 실제 자율 주행 차량 (JetRacer):
  • NVIDIA Jetson Nano 기반의 실제 자율 주행 로봇 (JetRacer) 을 사용하여 실험했습니다. 제안된 방법은 기존 데이터 기반 방법보다 긴 예측 구간에서 훨씬 정밀한 도달 가능 영역을 산출하여, 실제 환경에서의 안전성 검증에 유리함을 입증했습니다.

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

• 안전성과 성능의 균형: 이 연구는 데이터 기반 접근법의 확장성 (scalability) 과 형식적 검증 (formal verification) 의 엄격함을 동시에 달성했습니다.
• 비선형성 처리: Koopman 연산자를 통해 비선형 시스템을 선형적으로 다룰 수 있게 함으로써, 기존 선형 모델의 한계를 극복하고 복잡한 비선형 동역학에서도 정확한 예측을 가능하게 했습니다.
• 실용성: 물리 모델이 불완전하거나 존재하지 않는 실제 로봇 시스템에서도 측정 데이터만으로 안전성을 검증할 수 있는 강력한 도구를 제공합니다.

결론적으로, 이 논문은 Koopman 연산자 임베딩과 존토포 기반 도달 가능성 분석을 결합하여, 노이즈가 있는 비선형 시스템에 대해 기존 방법보다 더 정밀하고 보수성이 적은 안전성 검증을 가능하게 하는 획기적인 방법론을 제시했습니다.