안녕하세요. K-road 5기 조아진 입니다.
저는 Planning 파트에서 가장 핵심적인 역할인 경로 생성에서 쓰이는 한 가지 알고리즘과 관련하여 글을 작성하려 합니다.
자율 주행에서 경로생성 알고리즘은 정말 다양합니다. 이러한 경로 생성 알고리즘 중 특히 최적화 기반의 알고리즘인 Bit* (Batch Informed Trees star)가 매우 흥미로워 소개해보고자 합니다.
Bit* (Batch Informed Trees star)
자율주행에서의 그래프는 샘플링 기반 알고리즘을 사용하여 랜덤하게 샘플링된 상태공간의 점을 연결하여 구성됩니다. 이 때 그래프란 자율 주행 자동차, 로봇 조작 등에서 활용되는 공간의 추상화된 표현인데, 이는 상태공간 내에서 덤하게 생성된 점들을 연결하여 구성되며, 각 점은 로봇이나 자동차가 도달할 수 있는 특정위치를 나타냅니다.
그래프에서는 각 점(또는 노드)들이 엣지로 연결되어 있고, 이 엣지들은 가능한 이동 경로를 나타냅니다. 이동 경로는 충돌이 없어야 하며, 즉 장애물에 부딪히지 않고 안전하게 이동할 수 있는 경로를 의미합니다. BIT* 알고리즘은 이러한 그래프를 통해 시작 상태에서 목표 상태로의 최적의 경로를 찾아내는 데 사용됩니다.
BIT* 알고리즘의 기본 구조
BIT* 알고리즘의 구조는 다음과 같은 네단계로 나타낼 수 있습니다.
- 그래프 생성: BIT는 공간을 여러 개의 셀로 분할하여 각 셀의 중심점을 노드로 사용하는 그래프를 생성합니다. 이 그래프에서 노드들은 가능한 경로의 지점들을 나타내며, 이 노드들을 연결하는 경로(엣지)는 물리적 장애물을 회피하면서 이동할 수 있는 경로를 의미합니다.
- 메트릭 모션 계획: 각 노드에는 메트릭 모션 계획이 적용되어, 즉 각 노드에서 다른 노드로 이동할 때의 최적 경로가 계산됩니다. 이는 구조화된 RRT(Randomized Rapidly-exploring Random Trees) 방식을 사용하여 구현됩니다.
- 휴리스틱 사용: BIT는 특정 휴리스틱을 사용하여 점점 더 밀집된 내재 무작위 기하 그래프(RGG)의 시퀀스를 효과적으로 탐색합니다. 이 휴리스틱은 최적의 경로를 더 빠르게 찾기 위해 이전 정보를 재활용합니다.
- 경로 계획: 알고리즘은 시작 상태에서 목표 상태로의 경로를 계획합니다. 이 과정에서 최소 경로 길이를 찾기 위해 특정 샘플링 영역을 경험적으로 사용합니다.
BIT* 알고리즘의 작동원리
작동원리는 좀 더 쉬운 이해를 위해 그림을 가져와보았습니다.
이 그림은 BIT* 휴리스틱을 사용하여 경로의 최소 길이를 검색하는 것을 나타냅니다.
그림에서 보여지는 타원은 시작 상태(x_start)와 목표 상태(x_goal) 사이의 최적 경로를 찾는 데 사용되는 검색 영역입니다. c_min은 x_start와 x_goal 사이의 최소 예상 비용을, c_best는 현재까지 발견된 최적 경로의 비용을 나타냅니다. 타원의 모양은 이 두 비용을 기반으로 하여 결정되며, 타원 내부의 경로들은 가능한 최적 경로 후보들입니다.
BIT* 의 특징
BIT의 특징은 다른 알고리즘과 비교하며 알아보려고 합니다. 경로 생성 알고리즘 중 RRT알고리즘의 특징에서 좀 더 발전 시키면 BIT*알고리즘과 유사합니다.
- RRT*
rrt*는 무작위 샘플링을 기반으로 하여 한 노드 확장을 통해 경로를 탐색합니다. 즉, 한 노드에서 시작하여 무작위 방향으로 확장하면서 최적의 경로를 찾아가는 방식입니다. 점진적으로 최적 경로에 수렴하며 추가적인 노드를 반복적으로 검토하여 경로를 개선합니다. 이 과정에서 노드의 확장이 지속적으로 이루어지기 때문에 대규모 노드 확장이 필요하며, 결과적으로 계산 비용이 높아질 수 있습니다.
- BIT* 에서의 적용
위에서 설명한 RRT*의 무작위 샘플링과 최적화 방법은 BIT에서 중요하게 활용됩니다. BIT*는 이를 기반으로 더 효율적인 휴리스틱 기반 탐색을 추가하여 더 적은 노드로 더 빠른 최적화를 달성합니다.
BIT* 알고리즘을 사용한 경로생성예시
BIT* 알고리즘의 샘플 배치와 탐색 확장 과정을 알아보겠습니다.
첫 번째 그림은 BIT* 알고리즘에서 사용된 샘플들의 초기 배치를 보여줍니다. 이 그림에서는 다양한 샘플들이 장애물과 자유 공간에 걸쳐 균일하게 분포되어 있습니다. 샘플들은 삼각형으로 표시되며, 이는 탐색 공간 내에서 잠재적 경로의 노드를 나타냅니다. 이러한 샘플들은 암시적인 무작위 기하 그래프를 형성합니다. 두 번째 그림은 배치 처리 과정 중 하나를 보여줍니다. 여기서 중요한 특징은 선택된 샘플 주변에서 탐색이 확장되는 방식입니다. 이 과정에서, 휴리스틱 검색이 적용되어 목표 지점을 향해 가장 유망한 경로를 중심으로 확장이 이루어집니다. 그림에서는 특정 샘플 주변에 시안색 원이 그려져 있는데, 이는 해당 샘플을 중심으로 탐색이 집중되고 있음을 나타냅니다. 이 원 안의 샘플들은 더 적합한 해를 찾기 위한 하위 문제로 제한되어 추가적인 탐색이 수행됩니다.
이러한 과정을 통해 출발지와 목적지가 정해진 상태에서 경로계획이 잘 되는지 나타낸 실험한 결과를 가져와봤습니다.
이 상황은 좁은 경로를 가진 몇 가지 장애물을 배치한 상황입니다. 시작점은 (-1,0), 목적지는 (3.8) 입니다. 이러한 상황을 가정하고 BIT*알고리즘을 통해 경로를 생성하였습니다.
아까 설명드렸던 타원 그림에서의 원리를 적용하여 way points들을 찍고 이를 연결 장애물을 피한 경로가 생성됩니다. 지금 경로는 Bit*만 적용하여 경로를 생성하였는데, 이 길은 미분 불가능한 점이 많아 이 상태로 차량이 추적하기는 어렵습니다. 이를 해결하기 위해선 보간법을 사용하는데, 그러면 경로가 부드러운 곡선이 되면서 차량 추종하기 쉬운 경로가 완성됩니다.
이 상황에선 B-Spline 보간법이 쓰였습니다. 이렇게 해서 경로가 생성되는 과정을 살펴보았습니다.
BIT* 의 최적 성능 조건
마지막으로 이러한 BIT* 알고리즘은 어떠한 조건에서 최대의 성능을 발휘할 수 있는지에 대해 설명하고 글을 마무리하고자 합니다.
- 고차원의 탐색공간: 배치 처리와 정보가 풍부한 샘플링을 사용하는 BIT는 자율주행차량이 복잡한 도시 환경이나 다양한 장애물이 있는 오프로드 환경을 탐색할 때, BIT는 고차원 공간에서의 효율적인 경로 탐색 능력을 발휘할 수 있습니다.
- 실시간 경로 재계산이 중요한 상황: 환경 변화나 새로운 장애물이 감지될 때, Bit*는 이미 계산된 데이터와 트리 구조를 재사용하여 빠르게 새로운 경로를 계획 가능합니다.
- 다양한 경로 선택지가 필요한 경우: 다양한 경로 선택지를 고려해야 할 때, 예를 들어 교통 상황이나 도로 상태에 따라 동적으로 최적의 경로를 재계산해야 하는 상황에서 BIT*는 배치 처리를 통해 빠르게 다수의 경로를 평가하고 최적의 경로를 도출할 수 있습니다.
*참고문헌
Supporting BIT*-Based Path Planning with MPC-Based Motion Planning of the Self-Driving Car
Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graph