A* 알고리즘
Reference
Path Planning Technologies for Autonomous Underwater Vehicles-A Review, 2021
Path planning with modified A star algorithm for a mobile robot, 2014
나무위키
example : https://www.gatevidyalay.com/a-algorithm-a-algorithm-example-in-ai/
A* 알고리즘은 가장 잘 알려진 경로 탐색 알고리즘 중 하나로, 다익스트라(Dijkstra) 알고리즘을 확장하여 만들어졌다.
Dijkstra's algorithm (다익스트라 알고리즘)
weighted graph에서, source point부터 각 정점까지의 최단거리를 찾아 array를 만든다. 최종적으로 가장 짧은 경로로 구성된 tree를 얻게 된다.
A* algorithm(에이스타 알고리즘)
다익스트라 알고리즘을 현실에 적용하기 어렵기 때문에, 다익스트라 알고리즘에 휴리스틱 함수 $h(v)$를 추가하여 효율적으로 최단 경로를 찾는다. 즉, 현재 노드에 목표 포인트의 추정 비용(estimated cost)을 추가한다.
공간 상의 각 cell은 다음과 같이 $f(v)$로 평가되며, $f(v)$가 최소가 되는 지점을 우선적으로 탐색한다.
$$f(v) = g(v) + h(v)$$
- $g(v)$ : 현재 상태의 비용 함수. 시작 노드에서 현재 노드 $v$까지의 실제 비용
- $h(v)$ : 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수. 현재 노드 $v$에서 목표 노드까지의 추정 비용(휴리스틱 비용)
휴리스틱 함수 $h(v)$로 무엇을 쓰느냐에 따라 성능이 매우 크게 차이난다.
- $h(v)=0$ : $f(v)=g(v)$이므로 다익스트라 알고리즘과 동일하다.
- Manhattan : 2차원 평면 좌표계에서 두 정점을 $(x_i, y_i), (x_j,y_j)$라고 하면 $|x_i-x_j|+|y_i-y_j|$
- Euclidean : 2차원 평면 좌표계에서 두 정점을 $(x_i, y_i), (x_j,y_j)$라고 하면 $\sqrt{(x_i-x_j|)^2+(y_i-y_j)^2}$
- Chebyshev : 2차원 평면 좌표계에서 두 정점을 $(x_i, y_i), (x_j,y_j)$라고 하면 $\max(|x_i-x_j|,|y_i-y_j|)$
장단점
A* 알고리즘의 장점은 여러 종류의 거리를 고려할 수 있다는 것이다. 사용하는 $h(v)$에 따라 시간, 에너지 소비 또는 안전을 고려할 수 있다. 하지만 셀이 많아지면 계산 시간도 늘어난다. 이를 극복하기 위해 다양한 variants가 등장했다.
알고리즘
A* 알고리즘은 다음과 같이 동작한다. open list는 방문할 노드, closed list는 방문한 노드이다.
- 출발 노드를 open list에 추가한다.
- open list가 비어있지 않다면 아래 과정을 반복한다.
- open list에서 $f(v)$가 가장 낮은 노드를 제거(pop)하고 이를 현재 노드로 한다.
- 현재 노드가 목표 노드인지 확인하고, 목표 노드가 맞다면 종료한다.
- 현재 노드를 closed list에 추가한다.
- 현재 노드의 각 이웃에 대해
- 이웃 노드가 closed list에 있는지 확인하고, 있다면 무시한다.
- 이웃 노드가 open list에 없으면 open list에 추가하고, 현재 노드를 이웃 노드의 부모로 설정한다.
- 이웃 노드가 이미 open list에 있으면, 이웃을 현재 경로를 통해 방문하는 것이 더 낮은 $g(v)$를 가지는지 확인한다. 만약 그렇다면 이웃의 부모를 현재 노드로 업데이트 하고, $f(v)$와 $g(v)$를 다시 계산한다.
Example 1 : 8-puzzle
A* 알고리즘을 이용해 initial state의 타일을 final state의 형태로 정렬해보자.
$g(v)$는 현재까지 이동한 횟수, $h(v)$는 잘못된 위치에 있는 타일의 수로 설정할 수 있다.
아래 솔루션을 보면 step이 늘어날 때마다 이동횟수 $g$가 1씩 증가하는 것을 볼 수 있다.
잘못된 위치에 있는 타일의 수 $h$를 계산해 $f=g+h$가 가장 작은 경우를 선택한다.
Example 2
A를 시작 노드, J를 도착 노드로 하여 A* 알고리즘을 이용해 경로를 탐색해보자.
노드 사이의 edge에 있는 검은색 숫자는 노드 간의 거리를 나타내고, 빨간색 숫자는 각 노드에서 목표 노드 J까지의 휴리스틱 함수 값이다.
Step 1
노드 A에서 시작하므로 B 또는 F로 갈 수 있다.
f(B) = 6 + 8 =14
f(F) = 3 + 6 = 9
f(F)가 더 작은 값을 가지므로 노드 F로 향한다.
Step 2
노드 F에서는 G 또는 H로 갈 수 있다.
f(G) = (3 + 1) + 5 = 9
f(H) = (3 + 7) + 3 = 13
f(G)가 더 작은 값을 가지므로 노드 G로 향한다.
Step 3
노드 G에서는 I로 갈 수 있다.
f(I) = (3 + 1 + 3) + 1 = 8
노드 I로 향한다.
Step 3
노드 I에서는 E 또는 H 또는 J로 갈 수 있다.
f(E) = (3 + 1 + 3 + 5) + 3 = 15
f(H) = (3 + 1 + 3 + 2) + 3 = 12
f(J) = (3 + 1 + 3 + 3) + 0 = 10
f(J)가 가장 작은 값을 가지므로 노드 J로 향한다.
따라서 A* 알고리즘으로 구한 경로는 다음과 같다. : A - F - G - I - J
