7.149 전역 경로 계획에서의 최적화 접근법

7.149 전역 경로 계획에서의 최적화 접근법

1. 전역 경로 계획의 개요

전역 경로 계획(global path planning)은 주어진 환경 지도에서 시작점부터 목표점까지의 충돌 없는 경로를 찾는 문제이다. 전통적으로 그래프 탐색(A*, 다익스트라)이나 샘플링 기반(RRT, PRM) 방법이 사용되지만, 이들은 경로의 최적성이나 매끄러움을 직접적으로 보장하지 않는다. 최적화 기반 접근법은 경로의 품질 기준(길이, 매끄러움, 안전성 등)을 명시적으로 최적화하여 고품질 경로를 산출한다.

2. 그래프 탐색 기반 최적 경로

2.1 A* 알고리즘과 최적성

A* 알고리즘은 허용 가능한(admissible) 휴리스틱 함수 h(\mathbf{x})를 사용하면 최단 경로를 보장한다. 이산화된 그리드나 그래프에서의 최적 경로를 찾지만, 이산화의 해상도에 의해 경로의 품질이 제한된다.

2.2 격자 기반 계획의 최적성

균일 격자에서 A*가 산출하는 경로는 격자 해상도에 의한 이산화 오차를 갖는다. 격자 해상도를 높이면 오차가 감소하지만 계산 비용이 지수적으로 증가한다.

3. 샘플링 기반 최적 계획

3.1 RRT*

RRT*(Rapidly-exploring Random Tree Star)는 RRT의 점근적 최적(asymptotically optimal) 확장으로, 새 노드 추가 시 근방의 기존 노드에 대한 재연결(rewiring)을 수행하여 비용을 점진적으로 개선한다. 샘플 수가 증가하면 최적 경로에 수렴함이 보장된다.

3.2 PRM*

PRM*(Probabilistic Roadmap Star)는 PRM의 점근적 최적 변형으로, 근방 반지름을 r_n = \gamma(\log n / n)^{1/d} (d는 차원)로 설정하여 연결 반지름이 샘플 밀도에 적응하도록 한다.

4. 최적화 기반 전역 경로 계획

4.1 CHOMP(Covariant Hamiltonian Optimization for Motion Planning)

CHOMP는 초기 궤적(통상 직선 경로)에서 출발하여 장애물 비용과 매끄러움 비용의 가중 합을 경사 하강법으로 최소화하는 방법이다.

\min_{\boldsymbol{\xi}} \quad f_{smooth}(\boldsymbol{\xi}) + \lambda f_{obs}(\boldsymbol{\xi})

f_{smooth}는 가속도 또는 저크의 적분이고, f_{obs}는 부호 거리 함수(SDF)에 기반한 장애물 비용이다. 공변 그래디언트(covariant gradient)를 사용하여 매끄러움 메트릭에 의한 사전 조건화를 수행한다.

4.2 TrajOpt(Sequential Convex Optimization)

Schulman 등(2014)이 제안한 방법으로, 순차적 볼록 계획(SCP)에 의해 비볼록 충돌 회피 제약을 처리한다. 각 반복에서 장애물 거리 제약을 선형화하고, 신뢰 영역 제약을 포함하는 볼록 QP를 풀어 궤적을 갱신한다.

4.3 GCS(Graphs of Convex Sets)

Marcucci 등(2024)이 제안한 프레임워크로, 자유 공간을 볼록 영역의 그래프로 분해하고, 그래프의 최단 경로와 영역 내의 궤적 최적화를 동시에 수행한다. 혼합 정수 볼록 계획으로 정식화되며, 이완 기법에 의해 효율적으로 풀 수 있다.

5. 전역 탐색과 국소 최적화의 결합

비볼록 환경에서 순수 경사 기반 최적화는 국소 최적해(예: 장애물의 잘못된 쪽으로 통과하는 경로)에 갇힐 수 있다. 이를 극복하기 위한 2단계 전략이 표준적으로 사용된다.

1단계: 전역 탐색: RRT*, A* 등의 조합적/샘플링 기반 방법으로 위상적으로 올바른(장애물의 올바른 쪽으로 통과하는) 초기 경로를 생성한다.

2단계: 국소 최적화: 1단계의 초기 경로를 CHOMP, TrajOpt, 또는 직접 배치법 기반 NLP로 정밀 최적화하여 매끄럽고 최적에 가까운 궤적을 산출한다.

이 결합은 전역 탐색의 완전성(completeness)과 경사 기반 최적화의 효율성을 동시에 확보한다.

6. 다중 해상도 최적화

경로 계획의 계산 비용을 줄이기 위해, 조밀하지 않은 초기 경로에서 시작하여 점진적으로 해상도를 높이는 다중 해상도(multi-resolution) 전략이 사용된다. 저해상도에서 전역 구조를 결정하고, 고해상도에서 국소 정밀화를 수행한다.

7. 로봇 공학에서의 응용 사례

매니퓰레이터 모션 계획: 고차원(6~7자유도) 관절 공간에서의 장애물 회피 경로 계획에 CHOMP, TrajOpt이 적용된다.

이동 로봇 경로 계획: 2차원 또는 3차원 작업 공간에서 A* + 경사 기반 경로 최적화의 결합이 자율 주행과 자율 비행에 사용된다.

보행 로봇 발디딤 계획: 이산적 발디딤 위치의 선택(조합 문제)과 연속적 무게 중심 궤적의 최적화를 결합하는 혼합 정수 최적화가 연구되고 있다.

8. 참고 문헌

  • LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
  • Ratliff, N., Zucker, M., Bagnell, J. A., & Srinivasa, S. (2009). “CHOMP: Gradient Optimization Techniques for Efficient Motion Planning.” Proceedings of ICRA, 489–494.
  • Schulman, J., et al. (2014). “Motion Planning with Sequential Convex Optimization and Convex Collision Checking.” IJRR, 33(9), 1251–1270.
  • Karaman, S., & Frazzoli, E. (2011). “Sampling-Based Algorithms for Optimal Motion Planning.” IJRR, 30(7), 846–894.
  • Marcucci, T., et al. (2024). “Motion Planning around Obstacles with Convex Optimization.” Science Robotics, 9(84).

version: 1.0