Provably Safe Motion Planning Under Unknown Disturbances

문제 정의
본 논문은 알려지지 않은 분포를 가진 무작위 섭동에 노출된 로봇 시스템의 운동 계획 문제 해결을 다룹니다. 전통적인 샘플링 기반 계획기들은 종종 결정론적 모델을 가정하거나 강한 분포 가정 (예: 가우시안 잡음) 과 경계 섭동 모델에 의존합니다. 이러한 접근 방식은 종종 과도하게 보수적인 계획을 초래하여 복잡한 환경에서 실패하거나 섭동 분포에 대한 비현실적인 지식을 요구합니다. 저자들은 초기 상태와 과정 잡음의 분포가 알려지지 않았음에도 불구하고, 충돌 회피와 목표 도달에 대한 확률적 제약을 높은 신뢰도로 만족시키는 선형 (또는 피드백 선형화 가능) 시스템에 대한 운동 계획을 생성하는 문제로 문제를 공식화했습니다. 시스템은 임의의 모양을 가진 장애물이 포함된 작업 공간에서 상태 및 제어 제약 내에서 작동해야 합니다.

방법론
제안된 접근 방식인 WDR-X(Wasserstein 분포 강건-X) 는 데이터 기반 불확실성 정량화와 트리 기반 탐색을 통합한 샘플링 기반 운동 계획 프레임워크입니다. 방법론은 두 가지 주요 단계로 진행됩니다:

1. 모호성 튜브 구성 (오프라인):
   특정 잡음 분포를 가정하는 대신, 알고리즘은 $N$개의 독립 동일 분포 (i.i.d.) 궤적 샘플 세트로부터 Wasserstein 모호성 튜브를 학습합니다. 이 튜브는 사용자 정의 신뢰 수준으로 모든 시간 단계에서 실제 상태 분포를 포함하는 모호성 집합 (Wasserstein 공) 의 시퀀스입니다.

   • 오차 역학: 저자들은 기준 궤적에 대한 오차 역학을 분석함으로써 계획 문제를 불확실성 전파와 분리합니다. 그들은 상태에 대한 모호성 집합이 오차의 모호성 집합과 기준 상태로부터 유도될 수 있음을 증명합니다.
   • 무한 시간 범위: 이전 방법들에서 모호성 경계가 시간이 지남에 따라 무한히 증가하는 것과 달리, 이 접근 방식은 유한한 신뢰도로 무한한 시간 길이의 튜브를 구성합니다. 이는 특정 시간 단계에서 데이터 기반 모호성 집합을 학습하고 시스템 역학을 사용하여 중간 단계에 대한 집합을 유도함으로써 달성되며, 결과적으로 유계로 유지되는 "톱니형" 반지름 프로파일이 생성됩니다.
   • 저차원 분해: 차원의 저주를 해결하기 위해, 프레임워크는 저차원 모호성 튜브를 활용합니다. 상태 분포를 특정 제약과 관련된 부분 공간 (예: 장애물에 대한 작업 공간 위치, 한계에 대한 제어 노력) 으로 투영함으로써, 이 방법은 안전 보장을 유지하면서 샘플 복잡성과 계산 비용을 크게 줄입니다.

2. 확률적 완전성 계획 (온라인):
   계획기는 명목 (결정론적) 기준 궤적 위에 샘플링 기반 트리 (예: RRT) 를 성장시킵니다.

   • 유효성 검사: 각 노드에서 알고리즘은 상태가 확률적 제약을 만족하는지 확인합니다. 이는 학습된 모호성 집합에 대한 최악의 경우 충돌 확률을 평가함으로써 수행됩니다.
   • 효율적인 검사기: 논문은 세 가지 유효성 검사 전략을 도입합니다:
     • 정확한 검사기 (Exact Checker): 이산 분포에 대한 정확한 최악의 경우 충돌 확률을 계산하는 확률 질량 수송에 기반한 최적화 없는 알고리즘입니다.
     • 지연 검사기 (Lazy Checker): 상세한 질량 수송 계산을 피하기 위해 사전 계산된 신뢰 튜브 (공) 를 사용하는 더 빠르고 보수적인 방법입니다.
     • 밴딧 기반 검사기 (Bandit-Based Checker): 다중 암 밴딧 프레임워크를 사용하여 정확하고 지연 검사기 사이를 적응적으로 선택하는 하이브리드 접근 방식입니다. 이는 특히 좁은 통로와 같은 복잡한 환경에서 효율성과 보수성 사이의 균형을 맞춥니다.

주요 기여
본 논문은 다음과 같은 구체적인 기여를 합니다:

• 알고리즘: 궤적 관찰 데이터를 활용하는 알려지지 않은 가법 섭동을 가진 선형 시스템을 위한 샘플링 기반 운동 계획 알고리즘.
• 이론적 보장: 섭동 분포에 대한 완화된 가정 하에서 계획기의 건전성과 확률적 완전성에 대한 증명.
• 모호성 전파: 선형 시스템의 경우 모호성 전파가 계획과 분리될 수 있음을 보여주어 단일 오프라인 학습 튜브를 가능하게 하는 분포 모호성 전파에 대한 새로운 이론적 결과.
• 더 엄격한 경계: 한쪽 면 McDiarmid 부등식과 모멘트 정보를 활용하여 기존 문헌에 비해 1-Wasserstein 거리로 정의된 데이터 기반 모호성 집합의 크기에 대한 더 엄격한 특성화.
• 유효성 검사: 효율성과 보수성 사이의 절충을 이루는 세 가지 유효성 검사 방법이며, 모두 기존 작업보다 덜 보수적이며 적응적으로 적절한 검사기를 선택하는 다중 암 밴딧 체계로 통합됨.
• 차원 축소: 안전성을 희생하지 않고 데이터 및 계산 요구 사항을 줄이기 위해 여러 저차원 모호성 튜브를 사용하는 것에 대한 공식화.

실험 결과
저자들은 4 차 선형 시스템과 2 차원 작업 공간을 항해하는 8 차 드론 시스템의 두 가지 시스템에 대해 접근 방식을 평가했습니다.

• 기준선: 이 방법은 모멘트 기반 분포 강건 접근 방식 (TS 및 Risk-Assigned) 과 기타 Wasserstein 기반 변형 (Particle, Confidence, Hybrid) 과 비교되었습니다.
• 성능:
  • 복잡하고 좁은 통로 환경에서 제안된 Bandit-WDR-RRT는 과도한 보수성으로 인해 경로를 찾지 못한 모멘트 기반 기준선보다 크게 우월했습니다. 예를 들어, 비가우시안 잡음이 있는 좁은 통로에서 기준선은 0~9% 의 성공률을 보인 반면, Bandit-WDR-RRT 는 최대 100% 의 성공률을 달성했습니다.
  • 밴딧 기반 검사기는 다른 변형들의 성공률을 맞먹거나 초과하면서 Hybrid 접근 방식보다 1.5~3 배 빠른 최고의 균형을 보여주었습니다.
  • 저차원 접근 방식은 위치 및 제어 제약에 대해 별도의 튜브를 학습함으로써 8 차 드론 시스템에 대한 계획을 성공적으로 가능하게 하여 확장성을 입증했습니다.
• 안전성: 몬테카를로 시뮬레이션은 생성된 계획이 충돌 회피에서 99~100% 의 성공률을 달성하여 모호성 튜브 제약의 건전성을 검증했습니다.

의의
본 논문은 알려지지 않은 섭동 분포를 가진 시스템을 위한 검증 가능한 안전성과 확장성을 갖춘 운동 계획 프레임워크를 제공한다는 점에 주요 의의가 있다고 주장합니다. Wasserstein 모호성 집합과 데이터 기반 학습을 활용함으로써, 이 접근 방식은 모멘트 기반 방법의 기하학적 과대 근사와 가우시안 기반 방법의 분포 가정을 피합니다. 확률적 완전성을 희생하지 않고 임의의 모양을 가진 장애물과 비볼록 제약을 처리할 수 있는 능력은 안전이 중요하고 섭동 모델이 불확실한 복잡하고 실제적인 로봇 응용 분야에 이 방법을 적합하게 만듭니다. 밴딧 기반 유효성 검사기의 도입은 계산 속도와 솔루션 보수성 사이의 균형을 동적으로 관리함으로써 실용적 유용성을 더욱 향상시킵니다.