1316.31 다중 큐 최선 우선 탐색

1316.31 다중 큐 최선 우선 탐색

1. 다중 큐 탐색의 동기

단일 휴리스틱에 기반한 최선 우선 탐색(best-first search)은 해당 휴리스틱의 특성에 전적으로 의존한다. 특정 도메인에서 효과적인 휴리스틱이 다른 도메인에서는 비효과적일 수 있으며, 단일 휴리스틱의 편향에 의해 탐색이 비생산적 방향으로 유도될 수 있다. 다중 큐 최선 우선 탐색(multi-queue best-first search)은 여러 휴리스틱의 장점을 조합하여 이 문제를 해결한다(Helmert, 2006; Richter & Westphal, 2010).

2. 다중 큐의 구조

다중 큐 탐색에서는 여러 개의 독립적인 우선순위 큐(open list)를 유지하며, 각 큐는 서로 다른 기준으로 노드를 정렬한다:

큐 1: h_FF 값 기준 정렬
큐 2: h_LM 값 기준 정렬
큐 3: preferred operators만 포함 (h_FF 기준)
큐 4: preferred operators만 포함 (h_LM 기준)

2.1 큐 선택 전략

각 탐색 단계에서 어떤 큐에서 노드를 추출할지를 결정하는 전략:

라운드 로빈(Round-Robin): 큐를 순서대로 번갈아 선택한다. LAMA에서 사용되는 기본 전략이다.

확장 순서: Q1 → Q2 → Q3 → Q4 → Q1 → Q2 → ...

부스팅(Boosting): 선호적 연산자 큐에 더 높은 우선순위를 부여한다:

확장 순서: Q_preferred → Q_preferred → Q_regular → Q_preferred → Q_preferred → Q_regular → ...
;; preferred 큐를 regular 큐보다 2배 자주 선택

3. LAMA의 다중 큐 구성

LAMA(Richter & Westphal, 2010)는 다음의 네 가지 큐를 사용한다:

  1. h^{\text{FF}} 큐: FF 휴리스틱 값으로 정렬된 전체 노드
  2. h^{\text{LM}} 큐: 랜드마크 휴리스틱 값으로 정렬된 전체 노드
  3. h^{\text{FF}} 선호 큐: FF 기반 선호적 연산자로 생성된 노드만 포함
  4. h^{\text{LM}} 선호 큐: 랜드마크 기반 선호적 연산자로 생성된 노드만 포함

라운드 로빈으로 네 큐를 순환하되, 선호 큐에 부스팅을 적용하여 선호적 연산자가 더 자주 확장되도록 한다.

4. 다중 큐의 이점

4.1 휴리스틱 보완

서로 다른 휴리스틱이 서로 다른 도메인 구조를 포착하므로, 하나의 휴리스틱이 실패하는 구간에서 다른 휴리스틱이 효과적으로 탐색을 유도할 수 있다:

  • h^{\text{FF}}: 삭제 완화 기반, 단기 목표 달성에 효과적
  • h^{\text{LM}}: 랜드마크 기반, 장기 구조적 진전에 효과적

4.2 탐색 다양성

단일 큐 탐색은 동일한 비용 영역의 노드를 반복적으로 확장하는 경향이 있다. 다중 큐는 다양한 관점에서의 노드를 교대로 확장하여 탐색의 다양성(diversity)을 보장한다.

4.3 선호적 연산자의 안전한 활용

별도의 선호 큐를 사용함으로써, 선호적 연산자의 가지치기 효과를 활용하면서도 완전성을 유지한다. 선호 큐가 고갈되면 일반 큐에서 노드를 추출하여 탐색을 계속한다.

5. 다중 큐와 반복적 개선

LAMA는 다중 큐 탐색으로 첫 번째 해를 빠르게 찾은 후, 비용 제한(cost bound)을 설정하여 더 나은 해를 탐색하는 반복적 개선(anytime) 전략을 사용한다:

1차 탐색: GBFS + 다중 큐 → 첫 해 발견 (비용 C1)
2차 탐색: 비용 < C1인 해 탐색 → 더 나은 해 발견 (비용 C2)
3차 탐색: 비용 < C2인 해 탐색 → 더 나은 해 발견 (비용 C3)
...
시간 제한까지 반복

6. 구현상의 고려사항

  1. 큐 간 중복 노드: 동일한 노드가 여러 큐에 삽입될 수 있다. closed 집합으로 중복 확장을 방지한다.
  2. 메모리 관리: 다중 큐는 단일 큐보다 메모리를 더 사용한다. 큐 크기 제한이 필요할 수 있다.
  3. 부스팅 비율 조정: 도메인에 따라 최적의 부스팅 비율이 다르며, 경험적 조정이 필요하다.

7. 참고 문헌

  • Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
  • Richter, S. & Westphal, M. (2010). “The LAMA Planner.” Journal of Artificial Intelligence Research, 39, 127–177.
  • Röger, G. & Helmert, M. (2010). “The More, the Merrier: Combining Heuristic Estimators for Satisficing Planning.” Proceedings of ICAPS, 246–249.