5.3 경로 계획(Route Planning)

5.3 경로 계획(Route Planning)

1. 정의

경로 계획(Route Planning)은 판단 모듈의 최상위 계층으로, 출발지에서 목적지까지의 최적 경로를 도로 네트워크 수준에서 탐색하는 과업이다. 경로 계획의 결과는 차량이 통과해야 할 도로 세그먼트(Road Segment)의 순서화된 시퀀스이며, 이는 하위 계층인 행동 계획과 동작 계획의 전략적 방향을 설정한다.

2. 도로 네트워크의 그래프 모델링

경로 계획은 도로 네트워크를 가중 방향 그래프(Weighted Directed Graph) G = (V, E, w)로 모델링한다. 여기서 V는 교차로 등의 노드 집합, E는 도로 세그먼트에 해당하는 간선 집합, w: E \rightarrow \mathbb{R}^+는 각 간선의 비용(가중치)을 나타내는 함수이다.

간선의 비용 w(e)는 다음의 요소를 반영하여 설계된다.

  • 거리: 도로 세그먼트의 물리적 길이
  • 소요 시간: 속도 제한과 교통 상황을 반영한 예상 통과 시간
  • 도로 유형: 고속도로, 일반 도로, 주거 도로 등의 선호도
  • 회전 비용: 좌회전, 유턴 등 복잡한 기동에 대한 추가 비용
  • 통행료: 유료 도로의 통행 비용

3. 경로 탐색 알고리즘

3.1 Dijkstra 알고리즘

Dijkstra 알고리즘은 단일 출발지에서 모든 노드까지의 최단 경로를 구하는 알고리즘이다(Dijkstra, 1959). 우선순위 큐(Priority Queue)를 사용하여 비용이 가장 작은 노드부터 탐색을 확장하며, 비용 함수가 음이 아닌 경우 최적 해를 보장한다. 시간 복잡도는 O((|V| + |E|) \log |V|)이다.

3.2 A* 알고리즘

A* 알고리즘은 Dijkstra 알고리즘에 휴리스틱 함수(Heuristic Function) h(n)을 추가하여 탐색 효율을 향상시킨 알고리즘이다(Hart et al., 1968). 평가 함수 f(n) = g(n) + h(n)을 사용하며, 여기서 g(n)은 출발지에서 노드 n까지의 실제 비용, h(n)은 노드 n에서 목적지까지의 추정 비용이다. 휴리스틱 함수가 실제 비용을 초과하지 않는 허용적(Admissible) 조건을 만족하면 최적 해를 보장한다.

도로 네트워크에서 일반적으로 사용되는 휴리스틱은 유클리드 거리(Euclidean Distance) 또는 하버사인 거리(Haversine Distance)이다.

3.3 계층적 경로 탐색

대규모 도로 네트워크에서의 경로 탐색 효율을 향상시키기 위해 계층적 접근법이 사용된다. 도로 네트워크를 여러 수준의 계층으로 분할하고, 상위 계층(고속도로 수준)에서 대략적 경로를 탐색한 후 하위 계층(일반 도로 수준)에서 세부 경로를 결정한다. Contraction Hierarchies(Geisberger et al., 2008)는 대표적인 계층적 경로 탐색 기법으로, 전처리를 통해 실시간 질의 시간을 마이크로초 수준으로 단축한다.

4. 동적 경로 재계획

실시간 교통 상황의 변화에 대응하기 위해 동적 경로 재계획(Dynamic Re-Routing)이 필요하다. 다음의 상황에서 경로 재계획이 수행된다.

  • 실시간 교통 정보에 의한 예상 소요 시간 변화
  • 도로 폐쇄, 사고, 공사로 인한 경로 차단
  • 차량의 의도치 않은 경로 이탈
  • 탑승자에 의한 목적지 변경

V2X 통신을 통해 수신되는 실시간 교통 정보, 도로 상태 정보 등이 동적 경로 재계획의 입력으로 활용된다.

5. 자율주행에서의 경로 계획 특성

자율주행의 경로 계획은 일반 내비게이션 경로 탐색과 비교하여 다음의 추가적 고려 사항을 가진다.

  • ODD 적합성: 자율주행 시스템의 ODD에 포함되는 도로만을 경로에 포함하여야 한다. ODD 외부의 도로는 자율주행이 불가능하므로 경로 탐색에서 제외하거나 인간 운전자에의 제어권 전환 구간으로 표시한다.
  • 차선 수준 경로: 일반 내비게이션이 도로 수준의 경로를 제공하는 것과 달리, 자율주행의 경로 계획은 차선 수준의 세부 경로를 포함할 수 있다. HD Map의 차선 연결 정보를 활용하여 교차로에서의 차선 배정, 회전 차선의 선택 등을 사전에 계획한다.

6. 참고 문헌

  • Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
  • Geisberger, R., Sanders, P., Schultes, D., & Delling, D. (2008). Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Proceedings of the 7th International Workshop on Experimental Algorithms (WEA), 319–333.
  • Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.

v1.0