하이브리드 A* (Hybrid A*)
한 줄 정의: 격자 탐색에 차량의 연속적인 위치·방향과 운동 제약을 결합해 실제로 주행 가능한 경로를 찾는 탐색 알고리즘입니다.
쉽게 풀면
보통 A* 알고리즘은 격자 칸의 중심을 이어서 경로를 만들기 때문에, 자동차처럼 제자리에서 돌 수 없는 차량은 그대로 따라갈 수 없습니다. 하이브리드 A*는 각 칸 안에 차량의 정확한 위치와 방향을 함께 기억하고, 핸들을 꺾어 실제로 갈 수 있는 움직임만으로 다음 상태를 만듭니다. 그래서 결과 경로를 차량이 곧바로 따라갈 수 있습니다.
왜 중요한가
자율주행 차량의 주차, 비정형 공간 주행, 자율 트랙터와 물류 차량의 경로 계획에서 기준 알고리즘으로 자주 비교됩니다. 2007년 DARPA 어번 챌린지에 참가한 스탠퍼드 팀의 차량에 쓰인 뒤 널리 알려졌습니다.
논문에서는 이렇게 쓰입니다
"주차장 환경에서 하이브리드 A*로 초기 경로를 생성한 뒤 수치 최적화로 곡률을 평활화하였다."
탐색 후 평활화로 이어지는 전형적 파이프라인입니다.
조금 더 깊게 보면
상태를 (x, y, θ)로 두고, 이를 격자로 이산화한 칸마다 연속 상태 하나를 보관합니다. 확장은 차량 기구학 모델에 따라 몇 가지 조향각으로 짧게 적분해 얻으며, 목표 근처에서는 리드-셰프(Reeds-Shepp) 곡선으로 직접 연결을 시도해 탐색을 줄입니다. 휴리스틱으로는 장애물을 무시한 비홀로노믹 거리와 운동 제약을 무시한 격자 거리 중 큰 값을 씁니다. 이산화 때문에 완전성과 최적성은 보장되지 않습니다.
주의할 점
A* 알고리즘은 이산 격자 위의 최단 경로를 보장하지만, 하이브리드 A*는 연속 상태와 비홀로노믹 제약을 반영하는 대신 최적성을 포기한다는 점이 다릅니다.