하이브리드 A* 및 딜로네 삼각분할 기반 자율주행 실시간 경로 계획 알고리즘 구조도

자율주행 판단 알고리즘: 하이브리드 A* 및 딜로네 삼각분할 기반의 실시간 경로 계획 메커니즘

작성자:

1. 서론: 자율주행 경로 계획(Path Planning)의 핵심과 복잡성

레벨 3 이상의 도심 자율주행이 구동하기 위해서는 센서(카메라, 라이다, 레이다)를 통해 주위 환경을 인지(Perception)하고, 이를 바탕으로 안전하며 실행 가능한 이동 궤적을 실시간으로 산출하는 경로 계획(Path Planning) 기술이 필수적입니다.

그러나 주행 경로를 설정하는 작업은 단순히 점과 점을 연결하는 그리드 검색에 그치지 않습니다.

  1. 비홀로노믹(Non-holonomic) 운동학 제약: 일반적인 로봇과 달리 자동차는 제자리 회전이나 측면 수직 이동이 불가능하며, 최소 회전 반경(Minimum Turning Radius)과 조향각(Steering Angle) 한계를 지닙니다.
  2. 동적 장애물과 좁은 주행 공간: 주차장, 복잡한 교차로, 공사 구간 등에서는 센티미터(cm) 단위의 정밀한 경로 탐색이 요구됩니다.
  3. 실시간 연산 능력(Real-Time Performance): 100ms 이내의 짧은 주기 안에 물리적으로 구동 가능한 최적의 경로를 연속적으로 도출해야 합니다.

이러한 한계를 극복하기 위해 최신 자율주행 시스템에서는 기하학적 공간 분할 기술인 딜로네 삼각분할(Delaunay Triangulation)과 차량의 운동학적 특성을 반영하는 하이브리드 A(Hybrid A) 알고리즘을 결합한 하이브리드 판단 메커니즘을 적극 채택하고 있습니다.

2. 딜로네 삼각분할(Delaunay Triangulation)을 활용한 주행 공간 재구성

2.1 딜로네 삼각분할의 수학적 정의

평면 상의 점 집합 $S$에 대해, 어떤 삼각형의 외접원(Circumcircle) 내부에도 $S$의 다른 어떤 점도 포함되지 않도록 점들을 연결하여 삼각형 패싯을 만드는 분할 기법을 딜로네 삼각분할이라고 합니다.

딜로네 삼각분할의 쌍대 그래프(Dual Graph)는 보로노이 다이어그램(Voronoi Diagram)을 형성합니다. 보로노이 영역의 경선은 장애물들로부터 동일한 거리에 위치한 ‘가장 안전한 중앙선’을 의미합니다.

2.2 자율주행 주행 가능 영역(Free Space) 획득

  1. 라이다 및 카메라 3D 포인트 클라우드 데이터를 통해 추출된 동적·정적 장애물 경계점들을 $S$ 좌표로 설정합니다.
  2. 장애물 점들을 기반으로 실시간 딜로네 삼각분할을 수행합니다.
  3. 생성된 삼각형 에지(Edge) 중 장애물을 관통하는 선분을 제거하여, 차량이 안전하게 통과할 수 있는 주행 가능 통로(Navigable Corridor)를 빠른 속도로 추출합니다.

이 과정은 무수한 그리드 전체를 검색해야 하는 기존 방식의 연산량을 획기적으로 줄여주는 1차 공간 필터링(Coarse Path Extraction) 역할을 수행합니다.

3. 하이브리드 A*(Hybrid A*) 알고리즘의 동작 원리

기존의 전통적인 A* 알고리즘은 2D 격자(Grid)의 중심만을 이동 마디(Node)로 취급하므로 지그재그 형태의 경로를 생성하며, 이는 실제 자동차가 조향할 수 없는 불가능한 궤적을 출력합니다. 이를 극복한 것이 하이브리드 A* 알고리즘입니다.

[딜로네 기반 통로 추출] ➔ [연속적 상태 공간 노드 확장] ➔ [Reed-Shepp 곡선 종단 결합] ➔ [최적화 (Smoothing)]

3.1 연속적 상태 공간(Continuous State Space)의 도입

하이브리드 A*는 2D 격자 셀(Cell)을 활용하여 방문 여부(Closed Set)를 관리하지만, 노드의 상태값은 3차원 연속 공간인 $(x, y, \theta)$로 표현합니다.

  • $x, y$: 차량의 2D 평면 위치
  • $\theta$: 차량의 헤딩각(Heading Angle)

노드가 확장될 때 격자의 중심으로 이동하는 것이 아니라, 실제 차량의 운동학 모델(Ackermann Steering Kinematics)을 반영하여 일정한 조향각 $\delta \in [-\delta_{max}, \delta_{max}]$을 적용했을 때의 연속적인 궤적 변위로 다음 노드를 생성합니다.

3.2 휴리스틱 함수(Heuristic Function)의 이중화 설계

하이브리드 A*의 빠른 탐색 속도와 수렴성은 휴리스틱 $h(n)$의 정밀도에 달려 있습니다. 다음 두 휴리스틱의 최댓값을 채택합니다.

$$h(n) = \max\left( h_{\text{non-holonomic-without-obstacles}}, \, h_{\text{holonomic-with-obstacles}} \right)$$

  1. Non-holonomic without obstacles ($h_{reed\_shepp}$): 장애물이 없다고 가정하고, 차량의 최소 회전 반경을 고려한 Reed-Shepp 곡선의 이론적 최단 거리를 산출합니다.
  2. Holonomic with obstacles ($h_{2D\_A^*}$): 차량의 운동학 제약은 무시하되 2D 장애물 지도를 고려한 일반 2D A*의 이동 비용을 동적 계획법(DP)으로 역방향 탐색하여 계산합니다.

4. 실시간 경로 생성 및 평활화(Optimization & Smoothing) 파이프라인

하이브리드 A*를 통해 도출된 초기 노드 궤적은 기하학적으로 구동 가능하지만, 조향각의 불연속 변화가 존재하여 승차감이 저하되고 급격한 제어를 유발할 수 있습니다. 따라서 2차 수학적 최적화(Optimization) 과정을 거칩니다.

4.1 경계 조건 및 최적화 목적 함수(Cost Function)

초기 경로의 좌표점들을 $P = {p_1, p_2, \dots, p_N}$라 할 때, 경량화된 경사 하강법(Gradient Descent) 또는 SQP(Sequential Quadratic Programming)를 통해 목적 함수 $J(P)$를 최소화합니다.

$$J(P) = w_s \sum (p_i – p_{i-1})^2 + w_{obs} \sum c_{obs}(p_i) + w_k \sum (\Delta \theta_i)^2$$

  • Smoothness Cost ($w_s$): 인접한 경로 점들 사이의 변위를 최소화하여 곡선 경로를 부드럽게 보정합니다.
  • Obstacle Cost ($w_{obs}$): 딜로네 삼각분할에서 추출된 장애물 거리 장(Distance Field)을 활용하여 장애물과 안전 거리를 유지시킵니다.
  • Curvature Cost ($w_k$): 곡률 변화율을 제한하여 차량의 최대 조향 속도(Steering Rate) 한계를 넘어가지 않도록 보정합니다.

5. 실무 구현 시의 한계점 및 최적화 대응 기법

  1. 고차원 탐색 공간으로 인한 연산 지연:$(x, y, \theta)$ 공간 검색은 차원이 증가함에 따라 메모리 소모가 극심해집니다. ➔ 목적지 근방에 도달했을 때 Analytics Expansion 기법을 적용하여 2D 탐색을 즉시 중단하고 Reed-Shepp 곡선으로 종단 결합(Analytic Shot)을 시도함으로써 탐색 시간을 70% 이상 단축합니다.
  2. 동적 장애물 대응의 한계:하이브리드 A는 정적 지형 탐색에 강점을 가지므로 움직이는 보행자나 다른 차량에 약합니다. ➔ 상위 판단 레이어에서 딜로네/하이브리드 A로 굵은 전역 경로(Global Path)를 고정한 후, 하위 레이어인 MPC(Model Predictive Control) 또는 DWA(Dynamic Window Approach)를 결합하여 국소 동적 회피(Local Avoidance)를 실시간 수행합니다.

6. 결론: 안전한 자율주행을 이끄는 판단 알고리즘의 미래

딜로네 삼각분할의 기하학적 공간 정제 능력과 하이브리드 A*의 차량 운동학 기반 궤적 생성 메커니즘의 결합은 자율주행차가 복잡한 환경에서도 사람처럼 부드럽고 안전하게 이동할 수 있도록 만드는 핵심 기술입니다.

향후 이러한 전통적 기하학/탐색 알고리즘은 강화학습(Reinforcement Learning) 및 BEV 딥러닝 인지 네트워크와 융합되어, 예외 상황(Edge Case) 대응 능력을 극대화하는 센서-판단 일체형 자율주행 프레임워크로 발전해 나갈 것입니다.

Dolgov, D., et al. “Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments.” International Journal of Robotics Research (2010).

De Berg, M., et al. “Computational Geometry: Algorithms and Applications.” Springer (2008).

댓글 남기기