A* 알고리즘 - 경로 계획 알고리즘 공부한다면 기본이죠...?

안녕하세요. 오늘은 A* 알고리즘에 대해서 공부하려고 합니다.

• HART, Peter E.; NILSSON, Nils J.; RAPHAEL, Bertram. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 1968, 4.2: 100-107.

 

A* 알고리즘은 경로 계획 알고리즘이 필요한 경우에는 게임, 로봇, 항공 등 분야를 가리지 않고 사용됩니다.

저는 휴리스틱 함수를 마음대로 갈아끼울 수 있는 강점이 그 이유라고 생각합니다.

• 상황에 따라서 적절한 휴리스틱 함수를 고를 수 있다는 점에서 A*알고리즘은 단순한 경로 계획 알고리즘이라기보다는 프레임워크라고 생각할 수도 있을 것 같습니다.

이번에 증명과 함께 알고리즘의

---

A* 알고리즘

알고리즘을 설명하기에 앞서서 사용되는 용어들을 정리해봤습니다.

• 시작 노드 s
• 목표로 하는 노드 집합 G={t1, t2, ..., tn}
• 노드 n과 연결된 노드들의 집합 Connected(n)
• 탐색할 노드들의 집합 OPEN = {}
• 탐색이 완료된 노드들의 집합 CLOSED = {}
• 평가 함수 f `(n)
  • 논문에서는 f hat을 사용하지만 입력하기 어려운 관계로 f `이라고 표현했습니다ㅜ

알고리즘

1. 시작 노드 s를 OPEN에 추가하고 평가 함수 f `(n)을 이용해서 f ` 값을 계산합니다.
2. OPEN에서 f ` 값이 가장 작은 노드 n을 추출합니다.
   • f ` 값이 최소인 노드들이 있다면 랜덤하게 아무 노드나 선택합니다.
   • 하지만 G에 포함된 노드가 있다면 해당 노드를 먼저 고릅니다.
3. 만약 선택된 노드 n이 G에 포함된다면 알고리즘을 종료합니다.
4. 선택된 노드 n이 G에 포함되지 않는다면 n을 CLOSED에 추가합니다.
5. Connected(n)들의 f `값을 계산합니다.
6. Connected(n)들 중에서 CLOSED에 포함되어 있지 않은 노드들을 OPEN에 추가합니다.
   • 이미 CLOSED에 포함되어 있는 경우, 새롭게 계산된 f `값이 기계산된 f `값보다 작을 경우에만 CLOSED에서 추출하고, OPEN에 추가합니다.
7. 2로 돌아갑니다.

 

평가 함수 f `(n)

위에서 설명한 알고리즘이 효율적이기 위해서는 평가 함수 f `(n)의 책임이 막중합니다.

논문에서는 적절한 f `(n)을 찾기 위해서 optimal path와 heuristic 함수를 이용합니다.

 

f `(n) = g `(n) + h `(n)

 

• g `(n)은 알고리즘에 의해 탐색된 시작 노드 s로부터 노드 n까지의 경로를 계산하는 함수입니다.
• h `(n)은 노드 n으로부터 목적지 g까지의 거리를 휴리스틱하게 계산하는 함수입니다.

그런데 A* 알고리즘이 정말 최적 경로를 찾을 수 있을까요?

뭐 하나 최적의 값을 사용하지 않고 있는데 의심이 됩니다...

A* 알고리즘의 완전성과 최적성을 증명해봅시다.

 

완전성 증명

Lemma

CLOSED에 포함되어 있지 않은 노드 n에 대해서

시작 노드 s와 노드 n의 최적 경로 P에 포함된 노드들 중 g `(n`) = g(n`)을 만족하는 노드 n`이 존재한다

Collorary

만약 모든 n에 대해서 h `(n) ≤ h(n) 이고 A* 탐색이 끝나지 않았다면

f `(n`) ≤ f(s) 를 만족하는 OPEN 노드 n`이 시작 노드 s와 목표 노드 g 사이의 최적 경로 P에 존재한다.

 

Theorem

만약 모든 n에 대해서 h `(n) ≤ h(n) 이라면 A* 알고리즘은 완전성을 가집니다.

Theorem 1 증명

A* 알고리즘이 완전성을 가지지 못한다는 뜻은 탐색이 끝났지만 반환된 경로가 최적의 경로가 아닌 경우일 것입니다.
귀류법을 사용해서 증명해보겠습니다.

최적의 경로가 아닌 경로가 반환되고 알고리즘이 종료되는 시점을 생각해봅시다.
f `(t) = g `(t) 인 t에서 알고리즘이 끝났을 것입니다.
그리고 최적의 경로가 아니므로 f `(t) = g `(t) > f(s) 입니다.

하지만 Collorary에 의해서 f `(n`) ≤ f(s)를 만족하는 n`이 OPEN에 존재합니다.
그렇다면 f `(n`)이 f `(t)보다 작기 때문에 t가 탐색되면 안되었고, 이는 가정에 모순입니다.

 

최적성 증명

consistency assumption

여기서 설명하는 consistency assumption은 사용하는 휴리스틱 함수에 대한 가정입니다.

 

휴리스틱 함수 h `에 의해서 계산된 m까지의 거리는 휴리스틱 함수 h `에 의해서 계산된 n까지의 거리 + m부터 n까지의 실제 거리보다 작다는 가정인데요.

h(m, n) + h `(n) ≥ h `(m)

• 이 가정이 최적성을 증명하는데 중요한 역할을 하더라고요!

 

Lemma 2

consistency assumption이 만족할 때, A* 알고리즘에 의해서 닫혀진 노드 n은 g `(n) = g(n)을 만족합니다.

 

Lemma 3

A* 알고리즘에 의해서 (n1, n2, ..., nk) 노드들이 순서대로 CLOSE에 추가되어 있을 때,

consistency assumption이 만족한다면 f `(np) ≤ f `(nq)가 성립합니다. (p ≤ q)

 

Corollary

Lemma 3에 의해서 CLOSE에 포함되어 있는 노드 n에 대해서 f `(n)  ≤ f(s)가 성립합니다.

 

Theorem 2

A* 알고리즘보다 노드 확장에 대한 정보가 없느 어떤 최적 경로 계획 알고리즘 A가 있다고 가정한다.

A* 알고리즘이 consistency assumption을 만족할 때, A* 알고리즘이 탐색한 노드는 A 알고리즘에 의해서도 탐색됩니다.

=> 최적성 증명 완료!

Theorem 2 증명

 

귀류법을 사용해서 증명해보겠습니다.

A* 알고리즘에 의해서 탐색되었지만 A 알고리즘에 의해서는 탐색되지 않은 노드  n이 있다고 가정합시다.

 

f `(t) = g `(t) + h `(t) = g (t) = f (t) = f (s)

f `(n) ≤ f `(t) = f (t)

 

h `(n) = h (n) 일 때, Lemma 2 에 의해서 f `(n) = f (n) 이 됩니다.

A 알고리즘은 A* 알고리즘보다 노드 확장에 대한 정보가 없기 때문에 n을 탐색하지 않았다면 A 알고리즘은 최적 경로 계획이 아니게 됩니다...!

 

가정이 모순이므로 명제는 참입니다.

 

휴리스틱 함수

논문에서는 유클리드 거리, 맨하튼 거리를 휴리스틱 함수의 예시로 듭니다.

A* 알고리즘의 성능이 1) 사용된 휴리스틱 함수가 문제 영역의 지식을 충분히 가지고 있는지와 2) 연산량에 따라 결정된다고 설명합니다.

 

• MAPF 연구들을 보면 모두 A* 기반 알고리즘이고 어떤 휴리스틱 함수를 사용했고, 사용한 휴리스틱 함수의 정당성을 증명하고 있습니다.
• 정당성이 여기서 말하는 문제 영역의 지식을 충분히 가지고 있는지 인 것 같습니다.