1316.39 선호도 기반 탐색 전략

1316.39 선호도 기반 탐색 전략

1. 선호도 기반 탐색의 개요

선호도 기반 탐색(preference-based search)은 탐색의 각 단계에서 특정 기준에 의해 선호되는(preferred) 액션이나 상태를 우선적으로 확장하는 전략이다. 이는 전체 탐색 공간을 동등하게 취급하는 대신, 유망한 방향에 탐색 자원을 집중함으로써 실질적 성능을 향상시킨다.

2. 선호적 연산자(Preferred Operators)

Fast Downward와 LAMA에서 사용되는 선호도 기반 탐색의 핵심 메커니즘이다. 각 상태에서 휴리스틱에 의해 특별히 유망하다고 식별된 액션을 선호적 연산자로 분류한다:

2.1 FF 기반 선호적 연산자

삭제 완화 계획의 첫 번째 수준 액션:
\text{Pref}_{\text{FF}}(s) = \{a \in \text{applicable}(s) \mid a \in \pi^+_0(s)\}

2.2 랜드마크 기반 선호적 연산자

미달성 랜드마크를 달성하는 액션:
\text{Pref}_{\text{LM}}(s) = \{a \in \text{applicable}(s) \mid \exists l \in \text{unachieved\_LM}: l \in \text{eff}^+(a)\}

3. 이중 큐 전략

선호적 연산자를 활용하는 표준 전략은 이중 큐(dual-queue) 방식이다:

preferred_queue: 선호적 연산자로 생성된 후속 상태만 포함
regular_queue: 모든 적용 가능 액션으로 생성된 후속 상태 포함

탐색 루프:
  ALTERNATE:
    상태 ← preferred_queue에서 추출 (부스팅 적용)
    상태 ← regular_queue에서 추출

3.1 부스팅(Boosting)

선호적 큐를 일반 큐보다 높은 빈도로 선택하는 전략이다. 부스팅 비율 b는 선호적 큐를 b번 선택한 후 일반 큐를 1번 선택하는 것을 의미한다.

LAMA의 기본 부스팅 비율은 약 5:1(선호적 큐 5회, 일반 큐 1회)이다.

4. 다중 휴리스틱 선호도 결합

LAMA에서는 FF와 랜드마크 두 휴리스틱의 선호적 연산자를 각각 추출하고 별도의 큐로 관리한다:

큐 1: h_FF 일반 큐
큐 2: h_LM 일반 큐  
큐 3: h_FF 선호 큐 (FF 기반 선호적 연산자)
큐 4: h_LM 선호 큐 (랜드마크 기반 선호적 연산자)

순환: Q3 → Q4 → Q3 → Q4 → Q1 → Q3 → Q4 → Q3 → Q4 → Q2 → ...
;; 선호 큐를 일반 큐보다 4배 자주 선택

5. 선호도 기반 탐색의 효과

5.1 분기 요인 감소

선호적 연산자는 일반적으로 적용 가능 전체 액션의 일부이므로, 선호적 큐에서의 탐색은 효과적으로 낮은 분기 요인을 가진다.

5.2 탐색 다양성 유지

일반 큐를 함께 사용함으로써, 선호적 연산자에 의한 편향을 보정하고 완전성을 유지한다. 선호적 연산자가 부적절한 방향을 가리키는 경우에도 일반 큐가 대안적 경로를 탐색한다.

5.3 첫 해 발견 속도 향상

IPC 벤치마크에서 선호도 기반 탐색은 순수 GBFS 대비 첫 해 발견 속도를 평균 2~5배 향상시키는 것으로 보고된다(Richter & Westphal, 2010).

6. 참신성 기반 선호도(Novelty-Based Preference)

Lipovetzky와 Geffner(2012)가 제안한 참신성(novelty) 기반 접근에서는, 이전에 관찰되지 않은 사실 조합을 생성하는 액션을 선호한다:

\text{novelty}(s') = \min \{k \mid \exists \text{k-tuple in } s' \text{ not seen before}\}

참신성이 높은 상태를 생성하는 액션이 선호된다.

7. 설계 시 고려사항

  1. 부스팅 비율의 조정: 도메인에 따라 최적 비율이 다르므로 경험적 조정이 필요하다.
  2. 선호도 소스의 다양성: 여러 독립적 소스(FF, 랜드마크, 참신성)에서 선호적 연산자를 추출하여 다양성을 확보한다.
  3. 완전성 보장: 반드시 일반 큐를 함께 유지하여 선호적 연산자의 편향을 보정한다.

8. 참고 문헌

  • Richter, S. & Westphal, M. (2010). “The LAMA Planner.” Journal of Artificial Intelligence Research, 39, 127–177.
  • Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
  • Lipovetzky, N. & Geffner, H. (2012). “Width and Serialization of Classical Planning Problems.” Proceedings of ECAI, 540–545.