A*(astar) 알고리즘
오늘은 지난 포스팅에 이어서 A* 알고리즘에 대해 알아보겠습니다.
A* 알고리즘이란?
A* 알고리즘은 가장 많이 사용되는 경로 알고리즘 중 하나이며 최적의 경로를 찾아내는 그리드 기반 탐색 알고리즘입니다.
주어진 장애물 맵을 기반으로 출발점에서부터 목적지점까지의 장애물을 회피하는 최적의 경로를 생성합니다.
위의 알고리즘은 전역경로 계획(Global path planning)에 자주 사용됩니다.
이전 포스팅에서 설명했던 Dijkstra(다익스트라)알고리즘과의 차이점은 휴리스틱이라는 개념이 사용된다는 점입니다.
휴리스틱이란?
위의 설명에서 언급했던 휴리스틱에 대해 알아보겠습니다.
본인이 눈을 감은 상태로 처음가보는 장소에 서있다고 가정해 봅시다.
처음 가보는 장소이기때문에 주변 환경에 대해서 아는 정보가 전혀 없을 것이고, 눈을 가리고 있기 때문에 주변의 환경을 파악할 수도 없을 것입니다.
이제 눈을 뜨고 특정 지점까지 이동을 해 보겠습니다.
아마 대부분의 사람들이 아래와 같은 순서로 길을 찾을것입니다.
1. 본인의 현재 위치를 파악한다.
2. 목표 지점을 확인한다.
3. 현재 위치에서 목표지점까지의 방향을 확인한다.
4. 목표지점까지의 방향을 기반으로 앞으로 나아간다.
5. 앞으로 나아가다 장애물이 발견되면 옆으로 피한다.
6. 회피한 위치에서 목적지까지의 방향을 다시 확인하고 앞으로 나아간다.
7. 2~6번의 과정을 목적지에 도착할 때까지 반복한다.
위의 과정이 A* 알고리즘의 흐름입니다.
위의 과정 중 3번, 현재 위치에서 목표지점까지의 방향을 확인하는 부분이 휴리스틱의 과정이라고 볼 수 있습니다.
즉 휴리스틱이란, 현재 위치에서 목표지점까지 연결하는 직선을 생성하고 생성된 직선을 기반으로 경로를 탐색하는 것입니다.
휴리스틱을 사용함으로써 불필요한 경로 탐색이 줄어들게 되어 계산 시간, 연산량이 줄어들게 됩니다.
A* 알고리즘
이제 본격적으로 A* 알고리즘이 어떻게 동작되는지 알아보겠습니다.
우선 A* 알고리즘은 그리드 기반 경로 탐색 알고리즘이기 때문에 사전에 정의된 격자 지도(grid map)가 있어야 합니다.
격자지도는 사각형, 오각형, 육각형등 사용자의 정의에 따라 달라지지만 편의를 위해 사각형으로 계산하겠습니다.
아래의 그리드 맵을 보시면 미리 정의된 비어있는 그리드 맵에 시작점(초록색), 도착점(빨간색)을 입력하였습니다.
격자지도를 이루는 사각형의 중심을 노드(node)라고 부르겠습니다.
A* 알고리즘은 시작노드를 둘러싸고 있는 노드들을 탐색하여 비용을 측정하고 가장 저렴한 비용을 가지고 있는 노드로 확장하여 도착노드에 도달할 때까지 반복하여 경로를 생성합니다.
경로 비용 계산
위의 그림은 그리드 맵 위에 시작, 도착 좌표를 그린 것입니다.
앞서 말씀드렸듯이 A* 알고리즘은 최소 비용값을 계산해서 경로를 생성합니다.
위의 그림에서 보라색 셀을 보시면 f(n), g(n), h(n)이 적혀있습니다.
각 셀을 이동하기 위해서 발생되는 비용을 계산하는 공식은 아래와 같습니다.
f(n) = g(n) + h(n)
g(n) : 출발 노드에서 현재 노드까지 도달하기 위한 최단 비용.
h(n) : 현재 노드에서 목표 노드까지의 예상 이동 비용으로, 휴리스틱 비용이라고도 함.
f(n) : g(n)과 h(n)을 더한 총비용이다. Heuristic cost function이라고도 함.
각 비용의 자세한 내용은 아래의 그림을 보면서 설명드리겠습니다.
출발 노드에서부터 경로 탐색을 시작합니다.
먼저 g(n)을 살펴보면 출발 노드에서 현재 노드까지 최단 비용 즉, 최소 거리를 나타냅니다.
최소 거리를 구하는 방법은 여러 가지가 있습니다.
어떠한 방법을 사용해서 계산할지는 사용자가 본인의 환경에서 테스트를 해보며 찾아야 합니다.
그리드를 이루는 노드 한 칸이 10의 거리 비용을 가진다면
처음 시작 노드는 값이 당연히 0이 됩니다.
시작 노드를 둘러싼 다른 노드를 계산해 보면 각각 10, 14, 10의 값을 가지게 됩니다.
앞서 말씀드린 유클라디안 거리를 사용했을 경우입니다.
다음으로 h(n)을 살펴보면 휴리스틱 비용 즉, 현재 노드에서 목표 노드까지의 예상 이동 비용을 나타냅니다.
시작 노드에서부터 목표 노드까지 가기 위한 예상 이동 비용을 구하는 방법도 여러 가지가 있지만 여기선 맨해튼 거리를 사용하겠습니다.
맨허튼 거리는 가로 세로로만 이동 가능하며 대각선으로 이동은 불가능합니다.
즉 현재 노드에서 목표 노드까지 가로, 세로로 이동하며 갈 수 있는 거리를 계산하는 것입니다.
위의 그림은 시작 좌표에서 목적 좌표까지 h(n)을 구하는 방법을 그림으로 표현한 것입니다.
위의 과정을 모든 노드에서 동일한 방법으로 계산하면 됩니다.
다음으로 f(n)을 살펴보면 위에서 계산된 g(n)과 h(n)을 합한 총비용을 나타냅니다.
시작노드에서부터 시작하여 총비용이 작은 노드로 이동을 합니다.
이동한 노드를 현재 위치로 설정하고 다시 주위의 노드의 비용을 계산합니다.
오늘은 휴리스틱 기반의 경로 탐색 알고리즘인 A* 알고리즘에 대해 알아봤습니다.
지난 시간에 다뤘던 Dijkstra 알고리즘의 변형된 알고리즘으로 연산량, 계산 속도 부분에서 향상된 알고리즘입니다.
다음 포스팅에서는 곡선 주행 및 방향성을 가지는 Dubin path에 대해 알아보겠습니다.