Hirearchical A* - HCA 공부하는데 계속해서 언급되는 HA*를 모르겠어요

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

• HOLTE, Robert C., et al. Hierarchical A*: Searching abstraction hierarchies efficiently. In: AAAI/IAAI, Vol. 1. 1996. p. 530-535.

해결하려는 문제를 조금 더 쉬운 형태로 추상화시키는 접근법은 여러 분야에서 활용되고 있습니다.

 

Hirearchical A*도 기존 A*의 문제 영역을 추상화시켜서 더 효율적으로 문제를 해결하는 방법입니다.

하지만 마냥 쉽게 효율적인 해결책이 나오는 것은 아니겠죠?

 

어떤 어려움이 있고, 어떻게 해결했는지 살펴볼까요?

---

용어 정리

• admissible heuristic function
  • 휴리스틱 함수를 h`라고 하고, goal 노드까지의 최적 거리를 계산해주는 함수를 h라고 한다.
  • 노드 n이 집합 S에 포함되어 있을 때,
  • 모든 노드 n에 대해서 h`(n) ≤ h(n) 일 경우에, h`을 admissible heuristic function이라고 한다.
• state space
  • state의 집합 S(간단히 말하면 노드들의 집합 S)가 있고,
  • 각 state 간의 거리를 계산하는 함수 d(s1, s2)가 있을 때,
    • s1에서 s2로 가는 경로가 없을 때, d(s1, s2) = ∞ 이다.
  • state space는 <S, d> 쌍으로 표현할 수 있다.
• problem
  • 집합 S의 state 중 하나인 S가 있고,
  • 집합 S의 state들의 부분집합인 G가 있을 때,
  • problem은 <S, G>로 표현할 수 있다.
• abstraction transformation
  • state space SS=<States, d>가 있고,
  • state space SS`=<States`, d`>가 있을 때,
  • d`(∮(S1), ∮(S2)) ≤ d(S1, S2)이면 States에서 States`로의 mapping ∮ 를 abstraction transformation이라고 한다.

Introduction

요약

• 필요한 용어들을 간단하게 설명하고, 지금까지 연구되었던 abstraction transformation에 대해서 설명합니다.
• heuristic function의 위험성에 대해 설명하고, 이를 어떻게 해결했는지 설명합니다.

embedding

일반적으로 abstraction transformation 분야에서 "embedding" 분야가 가장 많이 연구되습니다.

 

간단하게 설명하면 state space SS에 edge를 추가하는 abstraction transformation ∮가 있다면 이를 "embedding"이라고 할 수 있습니다.

• 공식으로 표현하면 다음과 같습니다.
  • state space SS=<States, d>가 있고,  SS`=<States`, d`>이 있을 때,
  • States` ⊇ States이고 ∮(S) = S, ∀S ∈ State 이면 ∮는 embedding 이라고 합니다.
• 따라서 모든 embedding은 abstraction transformation입니다.

homomorphism

그 다음으로 많이 연구된 분야는 "homomorphism" 입니다.

 

간단하게 설명하면 state space SS의 몇몇 state가 state space SS`의 하나의 state로 맵핑된다면 이를 "homomorphism"이라고 합니다.

 

heuristic function

앞에서 abstraction transformation을 설명한 이유는 바로 heuristic function이 기존 state space를 abstraction transformation 하여 얻어진 거리 계산 함수라고 할 수 있기 때문입니다.

heuristic function을 사용하는 가장 큰 이유는 탐색의 속도를 높이기 위함입니다.

heuristic function이 없다면 A* 탐색 알고리즘은 결국 모든 경우를 전부 탐색해야 해서 빠른 속도라는 장점을 잃게 됩니다.

 

하지만 heuristic function을 이용했다고 마냥 좋은 것은 아닙니다. heuristic function을 이용하여 탐색했을 때의 연산 비용이 더 커질 수도 있기 때문입니다.

 

실제로 embedding을 통해서 얻어진 heuristic function은 기존 state space를 blind search 하는 것보다 빠를 수 없다는 연구가 있습니다.

• VALTORTA, Marco. A result on the computational complexity of heuristic estimates for the A∗ algorithm. Information Sciences, 1984, 34.1: 47-59.
• 본 논문에서는 이 연구를 토대로 "Valtorta's Barrier"라는 용어를 정의했습니다.
• Valtorta's Barrier는 기존 state space에서 blind search를 진행했을 때의 탐색하게 될 경우의 수를 뜻합니다.

위의 연구에서는 embedding을 통해서는 Valtorta's Barrier가 깨지지 않는다고 서술했습니다.

 

그렇다면 다른 종류의 abstraction transformation에 대해서도 Valtorta's Barrier가 적용될까요?

• Absolver II 연구에서 깨졌다고 하네요.

 

본 논문에서는 homomorphic abstraction을 이용하여 효율적인 heuristic function을 찾을 수 있다는 것을 보여줍니다.

 

사용된 2가지 접근법을 간단하게 설명드리면 다음과 같습니다.

1. homomorphic abstraction hirearchy와 이를 보완하는 알고리즘을 이용하여 탐색 수를 줄였고,
2. 덜 세밀한(less fine-grained abstraction 이라고 표현되어 있습니다) abstraction을 사용하는 것입니다.

위의 2가지 방법을 모두 사용할 경우, 테스트의 사용된 state space들의 Valtorta's Barrier를 깰 수 있다고 합니다.

Valtorta's Theorem Generalized

위에서 언급한 Voltorta's Barrier를 일반화 시키면 다음과 같습니다.

∮를 SS에서 SS`으로의 abstration mapping 이라고 하고, h ∮(S)를 SS`의  ∮(S)에서  ∮(Goal)로의 최단 경로를 계산해주는 함수라고 하자.

만약 SS를 blind search 할 때, S가 확장되어야 한다면 h ∮에서 S 혹은  ∮(S)도 확장됩니다.

간단하게 말하면 blind search를 진행하면서 확장되는 모든 state S는 A*에서도 확장된다고 이해하면 될 것 같습니다.

그래서 embedding으로는 큰 효과를 못 보고, homomorphic으로 효과를 볼 수 있는 것입니다.

Hirearchical Search using A*

이제 실제로 abstraction 을 이용해서 탐색 수를 줄여보도록 하겠습니다.

제일 먼저간단한 abstraction인 STAR abstraction을 이용한 naive hierarchical A*의 효용성을 알아보고, 이를 개선해보도록 하겠습니다.

STAR abstraction technique

STAR abstraction에 대해서 간단히 설명드리면 다음과 같습니다. 

1. degree가 가장 큰 노드와 연결된 노드들 중 거리가 abstraction distance보다 작은 노드들을 하나의 하나의 abstract state로 묶습니다.
2. 하나의 abstract가 남을 때까지 이를 반복합니다.

단순히 STAR abstraction technique을 이용하여 hirearchical A* 알고리즘을 수행하면 오히려 탐색 수가 늘어납니다.

그 이유는 high level에서 탐색된 노드가 low level에서도 다시 탐색되기 때문입니다.

 

Customizing A* for Hierarchical Search

이런 문제를 해결하기 위해서 논문에서는 다음 3가지 방법을 소개합니다.

1. h* caching
2. optimal path caching
3. optimal path caching + P-g caching

h* caching은 high level에서 계산된 h* 휴리스틱 함수를 low level에서도 활용하는 것입니다.

• optimal path caching, P-g caching은 이해하지 못했습니다... 다른 논문들을 공부하면서 이해되면 다시 정리하도록 하겠습니다.

 

Varying the Granularity of Abstraction

STAR abstraction technique에서 언급한 abstraction distance를 조절하면서 탐색 수가 어떻게 변하는지 양상을 살펴보았다.

실험에서는 abstraction distance를 2~5로 조절해보았으나, 상관 관계를 발견하지는 못했다고 한다.

Conclusions

비록 runtime을 고려하면 시간 단축 효과를 내지 못했지만 아주 간단한 abstraction을 통해서 전체 탐색 수를 줄였다는 점에서 hirearchical A*의 가능성을 보였다.