A* 알고리즘
휴리스틱 함수 h(n)은 A알고리즘에게 현재 위치n에서 *목표까지의 최소비용**을 산정해 알려준다. 따라서 휴리스틱 함수를 어떻게 지정할지가 중요하다.
A* Use of the Heuristic
휴리스틱은 A*알고리즘의 행동(이동)을 제어한다.
- 하나의 극점에서, 만약 h(n)이 0이면, g(n)만 역할을 수행하고 A*는 다익스트라 알고리즘이 된다. (다익스트라는 가장 짧은 경로를 찾는데 보증된 알고리즘)
- 만약 h(n) 값이 항상 n에서 goal까지 이동하는 비용보다 늘 작거나 같다면, A도 최단 경로를 찾는다고 보장할 수 있다. h(n)값이 작을수록, A가 더 많은 노드를 탐색할 것이고, 더 느리게 만들 것임.
- h(n)이 n에서 목표까지의 cost와 정확히 일치하는 경우, A는 최선의 경로만을 따라 이동할 것이고(그 외의 노드는 탐색하지 않음) 가장 빠를 것이다. 항상 일치하게 할 수는 없겠지만, 일부 특별한 케이스에 한해서는 가능하다. 만약 perfect한 정보를 알고 있는 경우, A는 완벽하게 수행할 것임.
- h(n)이 n에서 목표까지 가는 비용보다 클 경우, A*가 최단경로를 찾는다고 보장할 수는 없지만 훨씬 빠르게 작동할 것이다.
- 다른 극점에서, 만약 h(n)이 g(n)과 굉장히 연관되어 있는 경우, 오직 h(n)만 온전히 작동하고 A* 알고리즘은 Greedy Best-First-Search 알고리즘으로 변할 것임.(탐욕 알고리즘)
100% 정확한 추정이 있다면 우리는 굉장히 빠르게 최단경로를 탐색할 것이고, 너무 낮더라도 최단경로를 탐색하겠지만 느려질 것이다. 너무 높으면 최단 경로를 찾지는 못해도 굉장히 빠를 것이다.
Speed or accuracy
A*의 move는 휴리스틱 함수와 코스트 함수에 따라 굉장히 달라진다. 당신의 문제를 해결하는데있어 속도와 정확도의 tradeoff 관계가 너의 상황을 빠르게 만들어줄 것이다. 대부분 상황에서 best path가 꼭 필요하지는 않다. 다만 굉장히 유사한 값이 필요할 뿐이다. 당신이 필요한 값은 당신의 game 안에서 무엇이 일어나는지 혹은 컴퓨터가 얼마나 빠른지에 달려있다. ‘보장된다’는 함수들은 절대 cost를 oversetimates를 하지 않는다 – 가끔은 굉장히 근소한 차이로 underestimate한다.
당신의 game에 두가지 타입의 지형이 있다고 생각해보자 – cost가 1인 평지와 cost가 3인 산 – A는 산악 지역을 통하는 길을 찾는 동안, 평지로 통하는 3배 더 긴 길을 찾을 것이다. 왜냐하면 산을 돌아가는 평지를 찾기가 가능하기 때문이다. 당신은 두 지형 공간 사이에 1.5배의 heuristic dinstance를 사용해 속도를 더 높일 수 있다. A는 3과 1.5를 비교할텐데, 3과 1을 비교하는 것보다 특별히 나빠보이지 않는다.
산악지형에 대해 큰 불만을 갖지 않기 때문에, A*는 돌아가는 길을 찾는데 많은 시간을 소비하지 않을 것이다.
혹은 그 대신, 탐색(산을 돌아가는 길)해야ㄷ할 양을 줄여줌으로써 속도를 높일 수 있따. – 산을 오르는 오르는 cost가 3이 아닌 2라고 알려주는 것
그럼 이제 산약 지형을 찾는 동안 오직 산악지형의 두배에 해당하는 평지만 찾을 것이다.
어느 쪽이든 더 빨리 무언가를 얻기 위한 이상적인 길을 포기한다.
속도와 정확도 사이의 선택은 정적일 필요가 없다.(항상 정해져있을 필요가 없다) 당신은 cpu의 속도, 길찾기에 걸릴 시간, 지도 위의 unit 수, 유닛의 중요도, 그룹의 크기, 난이도 혹은 그 외의 요소들에 따라 동적으로(dynamically) 결정하면 된다. 한가지 방법으로 격자 한칸을 이동하는데 드는 최소 비용은 1이라 가정하고 그 식을 세우면
g'(n) = 1 + alpha * (g(n) - 1)
만약 알파값이 0이라면, cost function값은 항상 1이 될 것이다. 이렇게 설정하면, 지형에 따른 비용이 완전히 무시될 것이고, A는 이동 가능 여부만 생각하는 수준에서 움직일 것이다. 만약 알파값이 1이라면, 원래의 cost function이 사용될 것이고, A의 이점을 모두 사용할 수 있다. 당신은 알파값을 그 사이의 아무 값이나 설정하면 된다.
휴리스틱 함수가 cost의 절대적인 최솟값을 반환하는 것이 아닌, 예상 최솟값을 반환하는 것으로 바꾸는 것도 고려해얗 한다. 예를 들어 이동비용이 2인 초원에서 몇몇 비용은 1인 길이 있다면 당신은 휴리스틱 함수에 길이 없다고 생각하고 거리 * 2를 반환할 것이다.
속도와 정확도 사이에서의 선택은 꼭 전역적이지 않아도 된다. 지도의 지역에 따라 동적으로 고를 수 있다. 예를 들어 현재 위치 근처에서 좋은 길을 찾는 것이 중요할 경우, path를 재계산 하거나 어떤 지점에서 방향을 바꾸는 것을 마쳤을 때, 왜 길에서 먼 부분에 신경을 쓰고 있는가? safe area에서 최단 경로를 찾는 것은 그다지 중요한 것이 아니지만, 적 마을을 몰래 지나갈 때는 신속성과 안전이 필수적이다.
Scale
A는 f(n) = g(n) + h(n)을 계산한다. 두가지 값을 더하기 위해서, 두 값은 같은 scale을 가졍야 한다. 만약 g(n)이 시간 단위로 츠겆ㅇ 되고 h(n)이 meter로 측정된 경우, A는 g나 h를 너무 크게, 혹은 너무 작게 고려함으로써 그닥 좋은 path를 얻지 못할 수도 있고, A*도 느려질 것이다.
Exact heuristics
만약 당신의 heuristic 값이 optimal path의 거리와 똑같은 경우, 다음 섹션의 이미지처럼 A가 굉장히 적은 노드를 탐색한다는 것을 확인할 수 있다. A 안에서는 매 노드에서 f(n) = g(n) + h(n)을 계산하고 있는 것이다. h(n)이 g(n)과 완벽히 match될 때는 f(n)의 값이 변하지 않는다. 올바른 길에 있지 않은 모든 노드들의 f값은, 올바른 길에 있는 노드들의 f값보다 클 것이다. A는 f값이 높은 노드를 최소의 f값 노드라고 생각하기 전까지 길을 고르지 않기 때문이다.(의역)Since A doesn’t consider higher-valued f nodes until it has considered lower-valued f nodes, it never strays off the shortest path.
Precomputed exact heuristic
정확한 휴리스틱 함수를 구성하는 방법은 모든 points 짝의 최단 경로의 길이를 먼저 구하는 것이다. 사실 이것은 모든 game map에서 가능한 것은 아니다. 하지만 heuristic에 근사하는 몇가지 방법들이 있다.
- 미세한 grid 위에 거친 격자를 겹친다. 거친 그리드에서 최단 경로를 미리 계산한다.
- waypoints(길에 해당하는 포인트)들의 짝에서의 최단경로를 미리 계산한다. coarse grid 접근법의 일반화된 버전이다.
그 뒤에 근처의 points로 이동하는데 쓰이는 비용을 계산해 h'에 더해준다. 원한다면 후자도 미리 계산할 수 있다. 그렇게 되면 최종 heurisitc 함수는 다음과 같다.
h(n) = h'(n, w1) + distance(w1, w2) + h'(w2, goal)
혹은 더 비싸지만 더 나은 휴리스틱을 원한다면 상대적으로 현재 노드와 목표에 가까운 모든 w1과 w2가 갖는 pairs에 대해 계산할 수 있다.
Linear exact heuristic
특별한 상황에서, 미리 계산하지 않고도 정확한 휴리스틱을 만들 수 있다. 당신의 map에 느려지는 구간이나 장애물이 없다면 당신의 최단 경로는 시작지점과 목표지점 사이의 직선 경로일 것이다.
만약 당신이 단순한 휴리스틱(지도 상의 장애물 고려 x)을 사용한다면, 정확한(exact) 휴리스틱과 일치할 것이다. 그렇지 않다면(사용하지 않는다면) scale이나 휴리스틱의 type에 문제가 있을 가능성이 높다.
Heuristics for grid maps
grid에서 몇가지 잘 알려진 함수들이 있다.
- 4방향으로 이동이 가능한 square grid: 맨하튼 거리(L1)
- 8방향으로 이동 가능한 square gird: Diagonal 거리(L∞)
- 어느방향이든 이동 가능한 sqaure grid: 유클리드 거리(L2), 만약 격자위가 아닌 곳에서의 움직임을 허용한다면 지도를 다른 방식으로 표현하고 싶을 수도 있다.https://www.redblobgames.com/pathfinding/grids/algorithms.html