5.5 동작 계획(Motion Planning)

1. 정의

동작 계획(Motion Planning)은 판단 모듈의 최하위 계층으로, 행동 계획의 전술적 지침을 구체적인 시공간 궤적(Spatiotemporal Trajectory)으로 변환하는 과업이다. 동작 계획은 차량의 동역학적 제약, 충돌 회피, 쾌적성, 교통 법규 등 다수의 제약 조건을 동시에 만족하는 궤적을 실시간으로 생성하여야 한다.

2. 구성 공간과 탐색 공간

동작 계획은 구성 공간(Configuration Space, C-Space)에서 장애물을 회피하며 목표 상태에 도달하는 경로를 탐색하는 문제로 정식화된다. 자율주행 차량의 구성은 일반적으로 (x, y, \theta)(위치와 방향)로 정의되며, 시간을 추가하여 (x, y, \theta, t)의 시공간 구성 공간에서 궤적을 탐색한다.

3. 주요 동작 계획 알고리즘

3.1 격자 기반 탐색 (Lattice-Based Search)

래티스 계획은 차량의 운동학적 모델을 반영한 사전 계산된 기본 기동(Motion Primitive)의 격자에서 최적 궤적을 탐색하는 방법이다. 각 기본 기동은 차량의 동역학적 제약을 만족하도록 설계되며, 이들을 연결하여 목표 궤적을 구성한다. A* 또는 동적 프로그래밍(Dynamic Programming)을 이용하여 최적 시퀀스를 탐색한다.

장점은 생성된 궤적이 차량 동역학 제약을 기본적으로 만족한다는 점이며, 한계는 기본 기동의 해상도에 의해 궤적의 세밀도가 제한된다는 점이다.

3.2 샘플링 기반 계획 (Sampling-Based Planning)

구성 공간에서 무작위 샘플링을 통해 경로를 탐색하는 방법이다.

• RRT(Rapidly-exploring Random Tree) (LaValle, 1998): 무작위로 샘플링한 점을 향해 트리를 확장하여 경로를 탐색한다. 고차원 공간에서도 효율적으로 동작한다.
• RRT*: RRT에 점근적 최적성(Asymptotic Optimality)을 추가한 변형이다. 새로운 노드 추가 시 기존 트리의 재연결(Rewiring)을 수행하여 경로 비용을 점진적으로 개선한다(Karaman & Frazzoli, 2011).

샘플링 기반 방법은 복잡한 장애물 환경에서도 경로를 탐색할 수 있으나, 확률적 특성으로 인해 동일 상황에서 서로 다른 궤적이 생성될 수 있다.

3.3 최적화 기반 계획 (Optimization-Based Planning)

궤적을 매개변수화하고, 비용 함수를 최소화하는 최적화 문제로 정식화하는 방법이다.

\boldsymbol{\tau}^* = \arg\min_{\boldsymbol{\tau}} J(\boldsymbol{\tau}) \quad \text{subject to} \quad g(\boldsymbol{\tau}) \leq 0, \quad h(\boldsymbol{\tau}) = 0

여기서 J(\boldsymbol{\tau})는 비용 함수(경로 길이, 가감속의 크기, 목표 경로와의 편차 등), g(\boldsymbol{\tau})는 부등식 제약(충돌 회피, 차량 동역학 한계 등), h(\boldsymbol{\tau})는 등식 제약(초기 상태, 목표 상태 등)이다.

비선형 최적화 기법(Sequential Quadratic Programming, Interior Point Method 등)이 사용되며, 초기 해의 품질이 최적화 결과에 영향을 미친다.

3.4 Frenet 좌표계 기반 계획

도로의 중심선(Reference Path)을 기준으로 종방향(s)과 횡방향(d)을 분리하여 궤적을 계획하는 방법이다. Frenet 좌표계에서는 차선 추종, 차선 변경 등의 기동을 직관적으로 표현할 수 있다.

종방향과 횡방향의 궤적을 독립적으로 다항식(예: 5차 다항식)으로 계획하고, 이를 조합하여 후보 궤적 집합을 생성한 후 비용 함수를 통해 최적 궤적을 선택하는 방식이 Werling et al.(2010)에 의해 제안되었다.

4. 동작 계획의 실시간 요구사항

동작 계획은 일반적으로 10~20 Hz의 주기로 실행되어야 하며, 이는 각 계획 주기가 50~100ms 이내에 완료되어야 함을 의미한다. 최적화 기반 방법의 경우 온라인 최적화의 계산 시간이 제약이 될 수 있으며, 이에 대한 대응으로 따뜻한 시작(Warm Start) 기법, 병렬 연산, 문제 규모의 축소 등이 활용된다.

5. 참고 문헌

• Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research, 30(7), 846–894.
• LaValle, S. M. (1998). Rapidly-exploring random trees: A new tool for path planning. Technical Report 98-11, Computer Science Department, Iowa State University.
• Werling, M., Ziegler, J., Kammel, S., & Thrun, S. (2010). Optimal trajectory generation for dynamic street scenarios in a Frenet frame. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 987–993.

v1.0