기술 요약: PRISM - 도달 가능성 보장을 갖춘 효율적이고 국소적으로 최적인 확률론적 계획법

문제 정의

본 논문은 운동 불확실성, 상태 제약 및 제어 제약 조건 하에서 작동하는 로봇 시스템을 위한 신념 공간(belief-space) 계획의 근본적인 과제를 다룹니다. 구체적으로, 이 문제는 초기 가우시안 분포 $I = \mathcal{N}(\mu_I, \Sigma_I)$로부터 목표 가우시안 분포 $G = \mathcal{N}(\mu_G, \Sigma_G)$로 시스템을 유도하면서, 상태 및 제어에 대한 확률적(찬스) 제약을 만족시키는 문제를 포함합니다.

기존 접근 방식들은 다음과 같은 상당한 한계에 직면해 있습니다:

• 샘플링 기반 방법(예: FIRM, CS-BRM, RRT*)은 비현실적으로 많은 수의 노드를 요구하지 않고도 고차원 신념 공간에서 높은 커버리지를 달고 달성하는 데 어려움을 겪는 경우가 많습니다. 이들은 종종 유한 시간 완결성(finite-time completeness) 보장이 부족하며, 강건 제어 기술에 의존하여 비용을 부풀림으로써 제약을 위반하거나 최적성을 놓치는 궤적을 생성할 수 있습니다.
• 집합 기반 방법(예: Graphs of Convex Sets)은 결정론적 계획에 대해서는 완결성 보장을 제공하지만, 신념 공간의 볼록 집합 내에서 도달 가능성을 확립하는 데 어려움을 겪습니다.
• 공분산 조향(Covariance steering) 방법은 일반적으로 평균과 공분산 궤적을 공동으로 최적화하므로, 도달 가능성을 별도로 분석하기 어렵고 멀티 쿼리 계획을 위한 계산 비용이 높게 나타나는 경우가 많습니다.

핵심적인 어려움은 제약된 신념 공간에서의 도달 가능성 보장, 특히 상태 공분산을 축소하거나 액추에이터 제한을 준수하면서 목표치로 조향할 수 있는지 여부를 결정하는 데 있습니다.

방법론: PRISM 알고리즘

저자들은 PRISM(Precomputed Regions for Inflation-based Stochastic Motion planning)을 제안합니다. 이는 신념 공간 계획 문제를 **공분산 축소(covariance shrinking)**와 **결정론적 평균 조향(deterministic mean steering)**이라는 두 가지 별개의 단계로 분해하는 멀티 쿼리 계획 알고리즘입니다.

1. 이론적 토대: 상태 공분산의 도달 가능성

본 논문의 핵심적인 이론적 기여는 장애물 및 액추에이터 제약 조건 하에서 상태 공분산의 도달 가능성에 대한 새로운 충분 조건을 도출한 것입니다.

• 축소 가능성(Shrinkability): 논문은 "$\delta$-엄격하게 축소 가능한($\delta$-strictly shrinkable)" 공분산 개념을 도입합니다. 저자들은 초기 공분산 $\Sigma_1$이 매개변수 $\delta$와 시간 지평 $N$에 의해 정의된 특정 경계 내에 있다면, 모든 제약을 만족하면서 유한한 시간 내에 더 작은 등방성 공분산 $cI$로 축소될 수 있음을 증명합니다.
• 디커플링(Decoupling): 이러한 조건들은 PRISM이 계획 문제를 분리할 수 있게 해줍니다. PRISM은 먼저 시스템의 불확실성을 사전 계산된 상수 형태의 등방성 공분산($c^{(N)}_{1,\delta}I$)으로 축소합니다. 공분산이 이 "안전한" 수준으로 감소하면, 문제는 제약 조건이 엄격해지고(tightened) 장애물이 팽창된(inflated) 결정론적 평균 조향 문제로 변환됩니다.

2. 오프라인 그래프 구축

PRISM은 결정론적 공간에서 오프라인으로 로드맵을 구축합니다:

• 제약 조건 엄격화(Constraint Tightening): 사전 계산된 공분산 궤적을 사용하여 상태 및 제어 제약을 엄격하게 만들고 장애물을 팽창시켜, 결정론적 제약을 만족하는 모든 궤적이 원래의 확률적 찬스 제약을 만족하도록 보장합니다.
• 공간 분할: 엄격해진 제약 조건이 적용된 안전한 상태 공간을 중첩되는 볼록 다면체(convex polytopes)의 합집합으로 분할합니다.
• 그래프 생성: 노드는 이러한 다면체의 중심점(centroids)에 배치됩니다. 에지는 교차하는 다면체 사이에서 결정론적 평균 조향 문제(Problem V.3)를 풀어 중심점 간의 실행 가능한 경로를 찾음으로써 계산됩니다.
• 리프팅(Lifting): 이러한 결정론적 에지들은 평균 궤적을 사전 계산된 공분산 궤적과 결합함으로써 신념 공간으로 다시 "리프팅"됩니다.

3. 온라인 계획 및 국소 최적화

• 온라인 단계: 특정 시작 및 목표 분포가 주어지면, PRISM은 먼저 (초기 상태가 축소 가능 조건을 만족하지 않는 경우) 공분산을 축소할 수 있는 안전한 다면체 내의 정지된 평균(stationary mean)으로 시스템을 유도하려고 시도합니다. 그 후 시작 및 목표 분포를 사전 계산된 그래프에 연결하고 그래프 탐색을 수행하여 실행 가능한 경로를 찾습니다.
• 국소 최적화: 실행 가능한 경로가 발견되면, PRISM은 새로운 온라인 국소 최적화 모듈을 사용합니다. 이 모듈은 다음을 교대로 수행합니다:
  1. 에지 단축(Edge Shortening): 개별 에지에 대한 시간 할당을 줄입니다.
  2. 숏커팅(Shortcutting): 불필요한 에지를 제거하기 위해 인접하지 않은 노드 간의 직접적인 연결을 찾습니다.
  3. 볼록 최적화(Convex Optimization): 고정된 시간 할당 및 에지 시퀀스에 대해 평균 및 공분산 궤적을 최적화하기 위해 볼록 준정부호 프로그램(SDP)을 해결합니다.
     이 과정은 anytime(항상 실행 가능한 솔루션을 반환함) 특성을 가지며 비용을 크게 개선합니다.

주요 기여

1. 새로운 도달 가능성 조건: 장애물 및 액추에이터 제약 조건 하에서 상태 공분산의 도달 가능성에 대한 새로운 충분 조건을 확립하여, 평균 계획과 공분산 계획의 분리를 가능하게 했습니다.
2. PRISM 알고리즘: 신념 공간을 직접 샘플링하는 비효리적인 고차원 샘플링을 피하면서 높은 커버리지를 달성하기 위해 이러한 조건들을 활용하는 멀티 쿼리 플래너입니다.
3. 국소 최적화 서브모듈: 평균과 공분산 궤적을 공동 최적화하는 온라인 방법을 통해 기존 방식 대비 2.5배 이상의 성능 향상을 입증했습니다.
4. 이론적 보장: 시작 및 목표 분포(예: 정지된 평균, 유계된 공분산)에 대한 완만한 가정 하에 건전성(soundness)(모든 궤적이 찬스 제약을 만족함)과 완결성(completeness)(유한 시간 내에 경로를 찾는 것이 보장됨)에 대한 증명을 제공합니다.
5. 실험적 검증: 다양한 복도 너비와 복잡한 장애물 환경에서의 6-DoF 쿼드로터를 대상으로 광범위한 시뮬레이션을 수행했습니다.

실험 결과

저자들은 다양한 복도 너비와 장애물이 배치된 2D 환경의 6-DoF 쿼드로터에 대해 PRISM을 평가했습니다.

• 커버리지:
  • 좁은 통로가 있는 밀집된 사무실 환경에서, RRT, RRT*, MAX-COV-BALL과 같은 샘플링 기반 방법들은 통로가 좁아짐에 따라 커버리지가 크게 감소한 반면, PRISM은 모든 복도 너비에 대해 100% 커버리지를 달성했습니다.
  • 다양한 액추에이터 노이즈가 있는 복잡한 환경에서, PRISM은 다른 모든 방법이 45% 미만의 커버리지를 기록한 "어려운" 시나리오(비정지 평균, 큰 초기 공분산)에서도 97~100% 커버리지를 유지했습니다.
• 비용:
  • 국소 최적화 후, PRISM은 훨씬 낮은 평균 비용과 비용 분산을 가진 궤적을 생성했습니다.
  • 복잡한 환경에서 PRISM의 중앙값 경로 비용은 97.9였으며, 이는 CS-BRM(110.8) 및 RRT* (114.5)의 결과(자체 국소 최적화 후)와 비교됩니다.
  • PRISM의 국소 최적화는 (글로벌 플래너가 적은 수의 에지를 가진 경로를 생성하기 때문에) 다른 방법들보다 빠르게 수렴했습니다(중앙값 5.93초).
• 계산 시간:
  • PRISM의 오프라인 그래프 구축은 매우 효율적이었습니다(사무실 환경의 경우 1분 미만, 복잡한 환경의 경우 약 4~5분). 이는 수천 개의 에지에 대한 충돌 검사를 수행하느라 몇 시간이 걸리는 CS-BRM보다 훨씬 뛰어난 성능입니다.
  • 온라인 경로 탐색 시간은 가장 빠른 베이스라인들과 유사했습니다(평균 ~0.65초).

의의 및 주장

본 논문은 PRISM이 기존 방법들을 괴롭히는 커버리지와 비용 사이의 트레이드오프 문제를 해결함으로써 제약된 신념 공간 계획의 중요한 진전을 이루었다고 주장합니다. 공분산 축소를 평균 조향으로부터 분리함으로써, PRISM은 "역사의 저주(curse of history)"와 고차원 샘플링의 비효율성을 피합니다.

저자들은 PRISM이 샘플링 기반 접근 방식에서 흔히 결여되는 속성인, 넓은 범위의 신념 공간에 대한 유한 시간 완결성 보장을 제공한다는 점을 강조합니다. 또한, 효율적인 국소 최적화 모듈의 포함은 결과 궤적이 실행 가능할 뿐만 아니라 제어 비용 측면에서 국소적으로 최적임을 보장합니다. 결과적으로 PRISM은 전통적인 샘플링 방법이 실행 가능한 경로를 찾지 못하거나 지나치게 비용이 많이 드는 궤적을 생성하는 복잡하고 제약이 많은 환경에 특히 적합함을 보여줍니다.