8.97 확률론적 경로 계획과 불확실성 처리

1. 확률론적 경로 계획의 필요성

고전적 경로 계획은 결정론적 환경을 가정하고 충돌 없는 경로를 찾는다. 그러나 실제 로봇 시스템은 다음의 불확실성에 직면한다.

• 환경의 불확실성: 지도 오차, 미지 장애물
• 로봇 상태의 불확실성: 위치 추정 오차
• 제어의 불확실성: 모터 잡음, 슬립, 오도메트리 드리프트
• 동적 장애물의 불확실성: 다른 에이전트의 미래 위치 예측

확률론적 경로 계획은 이러한 불확실성을 명시적으로 모델링하여 안전하고 효율적인 궤적을 생성한다.

2. 불확실성 전파

2.1 선형 시스템에서의 공분산 전파

로봇 상태의 공분산 \boldsymbol{\Sigma}_t는 선형화된 동역학을 통해 시간에 따라 전파된다.

\boldsymbol{\Sigma}_{t+1} = \mathbf{A}_t\boldsymbol{\Sigma}_t\mathbf{A}_t^T + \mathbf{Q}_t

여기서 \mathbf{A}_t는 동역학의 야코비안, \mathbf{Q}_t는 프로세스 잡음 공분산이다. 관측이 있으면 칼만 필터의 갱신에 의해 공분산이 감소한다.

2.2 비선형 시스템

무향 변환(UT)이나 몬테카를로 샘플링으로 비선형 시스템의 불확실성을 전파한다.

3. 기회 제약(Chance Constraint) 기반 계획

3.1 정식화

안전 제약(예: 충돌 회피)을 확률적 제약으로 표현한다.

\min_u J(u), \quad \text{s.t.} \quad P(\mathbf{x} \in \mathcal{X}_{\text{safe}}) \geq 1 - \delta

여기서 \delta는 허용 위반 확률이다. 이는 결정론적 제약의 소프트 확장으로, 불확실성하에서 보수적이지 않으면서도 안전을 보장한다.

3.2 결정론적 변환

기회 제약을 결정론적 제약으로 변환하는 기법이 다수 존재한다.

가우시안 가정: 상태가 가우시안이면 분위수를 이용한 등가 제약이 도출된다.

\mathbf{a}^T\boldsymbol{\mu} + \Phi^{-1}(1 - \delta)\sqrt{\mathbf{a}^T\boldsymbol{\Sigma}\mathbf{a}} \leq b

본페로니 근사: 다수의 기회 제약을 유니온 바운드로 결합한다.

시나리오 기반 근사: 샘플링된 시나리오에 대해 결정론적 제약을 부과한다.

4. LQG-MP(LQG 기반 모션 계획)

Van den Berg 등이 제안한 방법으로, 칼만 필터-LQG 제어의 폐루프 시뮬레이션을 통해 불확실성을 예측한다. 계획 단계에서 실행 시의 예상 오차를 고려하여 경로의 “품질“을 평가한다.

5. 믿음 공간 계획(Belief Space Planning)

POMDP의 근사 해법으로, 로봇의 믿음 상태 공간에서 계획을 수행한다. 믿음 상태는 상태 평균과 공분산(가우시안 가정)으로 매개변수화된다.

5.1 믿음 roadmap

로드맵의 각 노드가 믿음 상태이며, 에지는 한 믿음에서 다른 믿음으로의 전이이다. 정보 이득과 이동 비용을 균형 있게 고려한다.

5.2 믿음 RRT

RRT를 믿음 공간으로 확장한다. 샘플링 기반 탐색이 상태 불확실성을 고려한 경로를 생성한다.

6. 강건한 경로 계획(Robust Path Planning)

불확실성이 유계 집합(bounded set)으로 모델링되는 강건 최적화 접근이다. 최악 경우에도 안전한 경로를 보장한다.

\min_u J(u), \quad \text{s.t.} \quad \forall \delta \in \Delta: \mathbf{x}(u, \delta) \in \mathcal{X}_{\text{safe}}

보수적이지만 확률 분포의 가정 없이 엄격한 안전 보장을 제공한다.

7. 도달 가능 집합 분석

로봇의 가능한 미래 상태의 집합을 시간에 따라 전파한다. 도달 가능 집합이 위험 영역과 교차하지 않도록 제어 입력을 설계한다.

7.1 해밀턴-야코비 도달 가능성

연속 시간 시스템의 도달 가능 집합을 해밀턴-야코비 방정식의 수치 해로 계산한다.

8. 동적 환경의 처리

8.1 예측 분포

이동 장애물의 미래 궤적을 확률 분포로 예측한다. 등속 모델, 사회적 힘 모델, 학습 기반 예측기 등이 사용된다.

8.2 시공간(Space-Time) 계획

장애물의 시간에 따른 예측 분포를 시공간에 투영하여 4차원 계획 문제로 정식화한다.

9. 모델 예측 제어(MPC)에서의 확률 처리

9.1 확률론적 MPC

예측 지평 내의 상태 분포 전파를 고려하여 기회 제약을 포함하는 MPC이다.

9.2 관 기반 MPC(Tube MPC)

불확실성 유계 관(tube)을 따라 공칭 궤적이 놓이도록 피드백 제어를 설계한다.

10. 로봇 공학에서의 응용

자율 주행: 다른 차량과 보행자의 예측 불확실성을 고려한 경로 계획.

드론 비행: 바람, 통신 지연 등의 불확실성을 고려한 경로 생성.

매니퓰레이션: 물체 자세와 모델 불확실성을 고려한 파지 계획.

SLAM과 결합: 위치 불확실성과 지도 불확실성을 동시에 고려한 탐험 경로 계획.

11. 참고 문헌

• Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.
• Van Den Berg, J., Abbeel, P., & Goldberg, K. (2011). “LQG-MP: Optimized Path Planning for Robots with Motion Uncertainty and Imperfect State Information.” IJRR, 30(7), 895–913.
• Blackmore, L., Ono, M., & Williams, B. C. (2011). “Chance-Constrained Optimal Path Planning with Obstacles.” IEEE Transactions on Robotics, 27(6), 1080–1094.
• LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.

version: 1.0