A* algorithm이란?
A* 알고리즘(A* star algorithm)은 주어진 출발 노드(node)에서부터 목표 노드(node)까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다. 주어진 지도(map)에서 출발 지점부터 목표 지점까지의 최적의 경로를 찾는 기술인 전역 경로 계획(Global path planning) 중 Path/Graph Search algorithm에 사용되기도 한다. 이 알고리즘은 Dijkstra' algorithm과 유사하나 차이점은 목표 노드(node) n까지의 휴리스틱(Heuristic) 거리 측정값인 h(n)도 사용한다는 점이다.
A* algorithm 구현
단도직입적으로 A* 알고리즘이 어떤 식으로 구현되는지 알아보자. 일단 아래와 같이 격자 지도(grid map)를 생성하여 지도(map)를 단순화한다. 이때 오각형, 육각형, 직사각형 등의 격자를 사용하지 않고 정사각형 격자를 쓴 이유는 가장 단순한 모양이기 때문에 성능 저하를 막고 빠르게 처리할 수 있기 때문이다. 그리고 생성된 격자 지도에서 출발 지점(초록 사각형)과 목표 지점(빨강 사각형)을 임의로 지정하였다. 여기서 각 사각형의 중심점을 노드(node)라고 부르기로 한다. 각 사각형은 빈 공간이여서 '이동 가능'하거나 또는 장애물이 있어서 '이동 불가능'한 2가지 상태 중 하나를 갖는다. 이때 A* 알고리즘의 목적은 주어진 아래 지도에서 출발 지점(node)과 목표 지점(node) 사이의 최단 거리를 찾는 것이다.
비용 계산
위 그림에서 맨 오른쪽 바깥 격자 보면 f(n), g(n), h(n)이라는 표시가 있는데 이는 비용(cost)를 뜻한다. 경로를 탐색하기 위해서는 각 사각형(node)마다 이동에 소요되는 비용을 계산이 필요한데, 이중 가장 작은 비용을 가진 사각형들을 서로 이으면 시작 지점과 목표 지점을 잇는 경로가 생성이 된다. 각 비용이 적게 드는 node끼리 연결했으므로 찾아낸 경로가 최단 경로라고 짐작할 수 있다. 각 비용의 의미는 다음과 같다.
Heuristic cost function: f(n) = g(n) + h(n)
g(n): 출발 노드에서 현재 노드 n까지 도달하기 위한 최단 비용
h(n): 현재 노드 n에서 목표 노드까지의 예상 이동 비용으로, 휴리스틱(Heuristic) 거리 측정값이라고 한다.
f(n): 현재 노드 n까지의 최단 비용 g(n)과 목표 노드까지의 예상 이동 비용 h(n)을 더한 총 비용이다. Heuristic cost function이라고 한다.
자세하게 설명하자면, g(n)은 출발 노드에서 현재 노드까지의 이동하는 데 드는 최소 이동 비용을 일컫는다. 여기서는 g(n)을 유클리디안 거리(Euclidean distance)를 사용하여 나타내기로 한다. 가로/세로 한 칸 이동당 10을, 대각선 한 칸 이동은 14로 설정하기로 한다. 대각선 한 칸 이동이 14인 이유는 피타고라스 정리에 따라 대각선의 이동 거리는 가로/세로 이동 거리의 1.414배이기 때문이다. 이때 정확하게 계산하면 14.14가 되는데 소수보다는 정수가 컴퓨터가 처리하는 데 더 빠르므로 소수점을 제외하여 14라고 설정한다. 만약 출발 노드에서 현재 노드까지 오는데 가로 한 칸 이동, 세로 한 칸 이동, 대각선 한 칸 이동이라면 g(n)=10+10+14=34가 되는 것이다. 여기서는 g(n)은 사각형의 왼쪽 아래에 표기하기로 한다.
그 다음으로 h(n)은 다양한 측정 방식을 사용할 수 있는데 여기서는 맨하탄 거리(Manhattan distance)를 사용하기로 한다. 해당 방식의 이름의 유래는 미국의 도시 중 하나인 맨하탄(Manhattan)으로부터 유래됐다. 맨하탄에는 블록마다 건물이 빽빽하게 들어가 있기 때문에 두 지점 사이를 오갈 때 대각선으로는 갈 수 없고 오직 가로/세로로만 이동할 수가 있는데, 이와 같은 방식으로 거리를 계산하기 때문에 맨하탄 거리라고 명명되었다. 이름의 유래처럼, 이 방식은 현재 노드에서 목표 노드까지 도달하기 위한 이동에서 대각선 이동을 제외하고 오직 가로/수직 이동만의 비용을 계산한다. 가로/세로 이동 한 칸당 10이 더해진다. 이를테면, 만약 가로 2칸, 세로 3칸을 이동한 경우 총 5칸을 이동했으므로 h(n)=50이 되는 것이다. h(n)은 오른쪽 아래에 표기하기로 한다.
마지막으로 f(n)은 g(n)와 h(n)를 더한 총 비용 값이다. 이 값을 통해 경로 탐색을 할 때 어느 노드가 가장 작은 비용을 가지는지 판단하게 된다. f(n)은 사각형 왼쪽 위에 표기하기로 한다.
위 그림에서 초록색 출발 사각형의 오른쪽 사각형의 비용을 살펴보자. 출발 사각형으로부터 오른쪽 사각형까지 가로로 한 칸 이동해야 하기 때문에 해당 사각형 왼쪽 아래에 g(n)=10이라고 표기되어 있다. 그리고 오른쪽 사각형에서 빨간색 목표 사각형까지 가로 2칸, 세로 2칸 이동해야 하므로 사각형 오른쪽 아래에 h(n)=20+20=40이라고 표기되어 있다. 마지막으로 사각형의 왼쪽 위는 50이라고 써 있는데, 이는 총 비용인 f(n)=g(n)+h(n)=10+40=50을 표기한 것이다. 나머지 노드들도 비슷하게 계산할 수 있다.
이제 본격적으로 경로 탐색 방법에 대해 알아보도록 하자.
경로 탐색1
최단 경로 탐색을 위해 아래와 같은 순서로 탐색을 시작한다. 출발 노드부터 목표 노드까지 인접한 사각형을 확인해 가면서 경로를 만들어 나가게 된다.
(1) 출발 사각형(노드)를 '열린 목록(open list)'에 넣어준다. 이 목록은 일종의 장바구니와 같다. 지금은 출발 노드만 있지만 탐색하면서 점차 늘어날 것이다. 이때 열린 목록에 있는 노드는 초록 윤곽선으로 둘러싸서 표현할 것이다.
(2) 출발 사각형에 인접한 장애물은 무시하고 지나갈 수 있는 사각형을 '열린 목록'에 넣어 준다. 이 사각형들은 출발 사각형를 부모로 지정한다. (이떄 '부모 노드(parent node)'는 경로를 다 찾고 거슬로 올라갈 때 사용된다.) 출발 노드를 비롯한 열린 목록에 있는 사각형들의 f(n), g(n), h(n) 비용들을 계산하여 각각의 노드에 기입해 준다.
(3) '열린 목록'에서 출발 사각형을 없애고 다시 볼 필요 없는 '닫힌 목록'(closed list)에 추가해 준다. 이때 닫힌 목록에 있는 노드는 하늘색 윤곽선으로 둘러싸서 표현할 것이다.
위 과정을 순서대로 수행하면 아래와 같은 그림을 얻게 된다.
부모 노드와 화살표(포인터)
위 그림에서 가운데 있는 초록 사각형은 출발 사각형(노드)이다. 하늘색 윤곽선 테두리는 출발 노드가 '닫힌 목록'에 추가가 되어 더 이상 볼 필요가 없다는 것을 의미한다. 그리고 출발 노드에 인접한 8개의 사각형(노드)은 초록 윤곽선으로 둘러싸여 있다. 이는 '열린 목록'에 들어가 있다는 것을 뜻한다. 이때 회색 화살표 모양의 포인터(pointer)가 보이는데, 화살표는 해당 노드의 부모 노드(parent node)를 가리킨다. 인접한 8개의 사각형(노드)이 부모 노드인 초록 사각형을 가리키고 있는 것이다. 인접 노드들의 f(n), g(n), h(n) 비용을 계산해주면 아래와 같다.
경로 탐색2
계속 탐색하기 위해, '열린 목록'에 있는 사각형들 중에서 가장 작은 f(n) 비용을 가지고 있는 사각형(노드)을 선택한다. 그리고 아래의 순서에 따라 진행하면 된다.
(4) 선택한 사각형(노드)을 '열린 목록'에서 빼고 '닫힌 목록'에 넣어 준다. 이는 선택된 사각형이 '부모 노드'가 될 준비가 되었음을 의미한다.
(5) 인접한 사각형을 확인한다. 인접 사각형 중에 '닫힌 목록'에 있거나 장애물인 것들을 제외하고, 나머지 '열린 목록'에 사각형이 없다면 '열린 목록'에 추가한다. 그리고 현재 사각형을 '열린 목록'에 새롭게 추가된 사각형들의 '부모'로 만든다. (여기서 현재 사각형이란 (4)에서의 선택된 사각형을 말한다.) 이때 열린 목록에 있는 사각형들의 f(n), g(n), h(n) 비용들을 계산하여 각각의 노드에 기입해 준다.
※인접한 사각형의 g(n) 비용은 그 부모로부터 g(n) 비용을 얻어와서 부모로부터 가로/세로로 이동하면 10, 대각선으로 움직이면 14를 추가한다.
(6) 인접한 사각형이 이미 기존의 '열린 목록'에 있다면 현재 사각형을 기준으로 해당 인접한 사각형까지 이동할 때 g(n) 비용이 낮아지는 지 확인한다. 비용이 더 낮아지지 않으면 아무것도 하지 않는다. 만약 현재 사각형을 통해 해당 인접 사각형까지 이동하는 데 g(n) 비용이 더 낮게 나온다면, 해당 인접 사각형의 부모 노드를 현재 사각형으로 바꾼다. 그리고 해당 인접 사각형의 f(n), g(n)을 다시 계산한다. (부모 노드가 되면 해당 인접 사각형의 화살표가 부모 노드쪽으로 향하게 된다.)
(7) 위 과정이 끝나면 '열린 목록'에 있는 사각형들 중에서 가장 작은 f(n) 비용을 가지고 있는 사각형(노드)을 선택한다. 그리고 다시 경로 탐색 중 빨간색 목표 노드가 '열린 목록'에 추가되거나 '열린 목록'이 비어 있게 될 때까지 (4)~(6) 과정을 계속 반복한다.
(8) 빨간색 목표 노드가 '열린 목록'에 추가되면, 목표 사각형으로부터 각각의 사각형의 부모 사각형을 향하여 시작 사각형에 도착할때까지 거슬러 올라갑니다. 부모 사각형이 어디인지는 화살표의 방향을 보면 알 수 있다. 화살표가 가리키는 곳이 부모 노드이다.
위 (4) ~ (8) 작업들을 직접 해보자.
처음에 9개 사각형 중에 초록색 출발 사각형을 '닫힌 목록'에 넣은 뒤, 인접한 8개의 사각형을 '열린 목록'에 추가해줬다. 이들중 f(n) 비용이 가장 작은 것은 출발 사각형의 오른쪽 대각선쪽에 있는 f(n)=44 사각형이다.
(4) 따라서 이 사각형을 닫힌 목록에 추가하여 준다. 닫힌 목록에 들어 갔으므로 하늘색 윤곽선으로 표시해준다. 이는 선택된 사각형이 '부모 노드'가 될 준비가 되었음을 의미한다.
(5) 그런 다음 인접한 사각형을 확인한다. 선택된 현재 사각형의 왼쪽 위 대각선, 위쪽, 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선 모두 열린 목록에 없었으므로 '열린 목록'에 새로 추가해준다. 현재 사각형을 '열린 목록'에 새롭게 추가된 사각형들의 '부모 노드'로 만든다. 새롭게 추가된 사각형들의 화살표는 부모 노드를 향하게 된다. 더불어 열린 목록에 있는 사각형들의 f(n), g(n), h(n) 비용들을 계산하여 각각의 노드에 기입해 준다.
※인접한 사각형의 g(n) 비용은 그 부모로부터 g(n) 비용을 얻어와서 부모로부터 가로/세로로 이동하면 10, 대각선으로 움직이면 14를 추가한다.
(6) 현재 사각형의 왼쪽, 아래에 있는 사각형은 이미 '열린 목록'에 있는 사각형이다. 왼쪽, 아래쪽 사각형 모두 g(n)=10인데, 만약 현재 사각형을 거쳐서 이동하면 가로 또는 세로로 한 칸씩 이동해야 하므로 g(n) 비용은 10씩 추가되어 g(n)=24으로 늘어나게 된다. 따라서 현재 사각형을 통해 가도 g(n) 비용이 개선되지 않으므로 아무것도 하지 않는다.
(7) 선택된 현재 사각형의 인접 사각형을 모두 확인했으므로 '열린 목록'에 있는 사각형들 중에서 가장 작은 f(n) 비용을 가지고 있는 사각형을 선택한다. f(n)=38인 사각형이 가장 작은 f(n) 비용을 가지므로 이 사각형을 선택하여 닫힌 목록에 추가해 준다. 닫힌 목록에 들어 갔으므로 하늘색 윤곽선으로 표시해준다. 이때 인접한 노드 중 빨간색 목표 노드가 열린 목록에 추가되므로 더 이상의 탐색을 중단하고, 인접한 노드들의 f(n), g(n), h(n) 비용들을 계산해준다.
(8) 빨간색 목표 노드가 '열린 목록'에 추가됐으므로, 목표 사각형으로부터 각각의 사각형의 부모 사각형을 향하여 시작 사각형에 도착할때까지 거슬러 올라간다. 부모 사각형이 어디인지는 화살표의 방향을 보면 알 수 있다. 화살표가 가리키는 곳이 부모 노드이다. 찾아낸 최단 경로가 위 그림에서 노란색 테두리로 표시되어 있다.
A* 알고리즘 요약(Summary of the A* Method)
1. 출발 사각형에 인접한 지나갈 수 있는 사각형을 '열린 목록'에 넣어 준다.
2. 다음의 과정들을 반복한다.
(1) 열린 목록에서 가장 작은 f(n) 비용을 가진 사각형을 찾아 선택한다.
(2) 이것을 열린목록에서 꺼내 닫힌 목록에 추가한다.
(3) 선택한 사각형에 인접한 8 개의 사각형에 대해 탐색한다.a. 인접 사각형 중에 '닫힌 목록'에 있거나 장애물인 것은 제외하고, 나머지 '열린 목록'에 사각형이 없다면 '열린 목록'에 추가한다. 그리고 추가된 사각형의 부모 노드를 현재 사각형으로 만든다. 추가된 사각형의 f(n), g(n), h(n) 비용을 기입한다.
b. 인접한 사각형이 이미 기존의 '열린 목록'에 있다면 현재 사각형을 기준으로 해당 인접한 사각형까지 이동할 때 g(n) 비용이 낮아지는 지 확인한다. 비용이 더 낮아지지 않으면 아무것도 하지 않는다. 만약 현재 사각형을 통해 해당 인접 사각형까지 이동하는 데 g(n) 비용이 더 낮게 나온다면, 해당 인접 사각형의 부모 노드를 현재 사각형으로 바꾼다(부모 노드가 되면 해당 인접 사각형의 화살표가 부모 노드쪽으로 향하게 된다). 그리고 해당 인접 사각형의 f(n), g(n)을 다시 계산한다.
3. 탐색 중단 조건
(1) 경로 탐색 중 목표 사각형을 '열린 목록'에 추가했을 경우
(2) 열린 목록이 비게 되는 경우
(목표사각형을 찾는데 실패한 경우이다. 이 경우에는 길이 없는 경우다)
4. 최단 경로 도출
목표 사각형으로부터 각각의 사각형의 부모사각형을 향하여 시작사각형에 도착할때까지 거슬러 올라간다. 부모 사각형이 어디인지는 화살표의 방향을 보면 알 수 있다. 화살표가 가리키는 곳이 부모 노드이다.
참고 자료
1. http://egloos.zum.com/cozycoz/v/9748811
2. https://itmining.tistory.com/66
댓글