7.120 볼록 최적화의 로봇 모션 계획 응용

7.120 볼록 최적화의 로봇 모션 계획 응용

1. 모션 계획에서 볼록 최적화의 역할

로봇 모션 계획(motion planning)은 본질적으로 비볼록 문제이다. 장애물 회피 제약의 허용 영역이 비볼록이고, 비선형 동역학 제약이 존재하기 때문이다. 그러나 문제의 특정 구성 요소를 볼록 최적화로 정식화하거나, 전체 문제를 순차적 볼록 근사(sequential convex approximation)로 풀어 전역 최적 또는 고품질 국소 해를 효율적으로 산출하는 접근법이 활발히 연구되고 있다.

2. 안전 복도 기반 궤적 최적화

2.1 볼록 자유 공간의 구성

장애물이 있는 환경에서 자유 공간(free space)은 비볼록이지만, 이를 볼록 영역의 합집합으로 분해할 수 있다. 각 궤적 구간이 하나의 볼록 영역 내에 머물도록 할당하면, 각 구간의 장애물 회피 제약이 볼록 제약이 된다.

볼록 다면체 복도(convex polytope corridor): 자유 공간을 경유점 주위의 축 정렬 상자(axis-aligned box) 또는 일반 다면체의 연쇄로 표현한다. 각 다면체 \mathcal{P}_k = \{\mathbf{x} : \mathbf{A}_k\mathbf{x} \leq \mathbf{b}_k\} 내의 궤적 구간은 선형 부등식 제약으로 표현된다.

타원체 복도: 장애물로부터의 안전 거리를 타원체로 모델링하는 경우, 2차 원뿔 제약으로 표현 가능하다.

2.2 최소 스냅 궤적 생성

안전 복도 내에서 다항식 궤적의 스냅(snap) 적분을 최소화하는 문제는 볼록 QP로 정식화된다.

\min \int_{t_0}^{t_f} \lVert \mathbf{r}^{(4)}(t) \rVert^2 dt

\text{s.t.} \quad \mathbf{r}(t) \in \mathcal{P}_k, \quad t \in [t_k, t_{k+1}]

\text{경유점 및 연속성 조건}

다항식 기저 함수의 계수가 결정 변수이며, 연속성 조건과 다면체 제약이 모두 선형이므로 볼록 QP가 된다. 이 접근법은 멀티로터 궤적 생성에서 표준으로 사용된다.

3. 순차적 볼록 계획법(Sequential Convex Programming, SCP)

비볼록 제약을 포함하는 모션 계획 문제를 반복적으로 볼록 근사하여 푸는 방법이다.

3.1 기본 절차

  1. 초기 궤적 \boldsymbol{\xi}_0를 설정한다.
  2. k번째 반복에서:
  • 비볼록 제약을 현재 궤적 \boldsymbol{\xi}_k 주위에서 볼록 근사(1차 테일러 전개)한다.
  • 근사된 볼록 문제를 풀어 갱신 방향을 결정한다.
  • 신뢰 영역 제약에 의해 갱신 크기를 제한한다.
  1. 수렴할 때까지 반복한다.

3.2 장애물 회피의 볼록 근사

장애물과의 거리 제약 d(\mathbf{q}) \geq d_{safe}는 비볼록이다. 현재 자세 \mathbf{q}_k에서의 최근접점과 법선 방향 \hat{\mathbf{n}}_k를 이용하여 다음과 같이 선형화한다.

\hat{\mathbf{n}}_k^T \mathbf{J}_{p}(\mathbf{q}_k)(\mathbf{q} - \mathbf{q}_k) + d(\mathbf{q}_k) \geq d_{safe}

이 선형화된 제약은 원래 비볼록 제약의 보수적 근사(conservative approximation)를 제공한다.

4. 혼합 정수 볼록 계획

접촉 모드(접촉/비접촉)의 이진 선택과 연속 궤적 변수를 동시에 최적화하는 문제는 혼합 정수 볼록 계획(Mixed-Integer Convex Programming)으로 정식화된다.

\min \quad \text{연속 비용} \quad \text{s.t.} \quad \text{볼록 제약}, \quad \text{이진 논리 제약}

장애물 회피에서 “로봇이 장애물의 어느 쪽을 통과하는가“라는 이산 선택이 이진 변수로 모델링된다. 분기 한정법(branch and bound)에 의해 풀리며, 각 노드에서의 이완 문제가 볼록이므로 효율적 하한이 제공된다.

5. 볼록 재정식화의 사례

5.1 경로를 따른 시간 최적 궤적

사전에 결정된 경로 \mathbf{q}(s)를 따르는 시간 최적 궤적 문제는, 변수 치환 b(s) = \dot{s}^2에 의해 볼록 문제로 변환된다. 토크 제약이 (b, \dot{b}) 공간에서 선형이 되므로, 전체 문제가 LP 또는 볼록 QP가 된다.

5.2 추력 제한 착륙 궤적

자유 비행 단계의 동역학이 선형(질점 모델)이고, 추력 크기 제약이 2차 원뿔인 경우, 착륙 궤적 문제가 SOCP로 정식화된다. 무손실 볼록화(lossless convexification)에 의해 추력 방향의 비볼록 제약이 제거되어도 최적해가 보존됨이 증명되어 있다.

6. 실시간 볼록 최적화

로봇 제어에서 볼록 최적화의 실시간 해법이 핵심이다.

코드 생성: CVXGEN, FORCES Pro 등의 도구가 특정 문제 구조에 맞춘 최적화된 C 코드를 자동 생성하여, 임베디드 시스템에서의 실시간 해법을 가능하게 한다.

연산자 분할법: OSQP와 같은 ADMM 기반 해법기가 행렬 분해를 사전에 수행하고 온라인에서는 반복적 연산만을 수행하여 실시간 성능을 확보한다.

웜 스타트: 이전 해를 초기점으로 활용하여 수렴에 필요한 반복 횟수를 최소화한다.

7. 참고 문헌

  • Schulman, J., Duan, Y., Ho, J., Lee, A., Awwal, I., Bradlow, H., Pan, J., Patil, S., Goldberg, K., & Abbeel, P. (2014). “Motion Planning with Sequential Convex Optimization and Convex Collision Checking.” The International Journal of Robotics Research, 33(9), 1251–1270.
  • Mellinger, D., & Kumar, V. (2011). “Minimum Snap Trajectory Generation and Control for Quadrotors.” Proceedings of ICRA, 2520–2525.
  • Deits, R., & Tedrake, R. (2015). “Computing Large Convex Regions of Obstacle-Free Space through Semidefinite Programming.” Proceedings of the Workshop on the Algorithmic Foundations of Robotics (WAFR), 109–124.
  • Acikmese, B., & Ploen, S. R. (2007). “Convex Programming Approach to Powered Descent Guidance for Mars Landing.” Journal of Guidance, Control, and Dynamics, 30(5), 1353–1366.
  • Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.

version: 1.0