1316.29 FF 플래너의 도움 행동 추출 기법

1. 도움 행동의 개념

도움 행동(helpful actions)은 FF 플래너(Hoffmann & Nebel, 2001)의 핵심 가지치기(pruning) 기법으로, 현재 상태에서 목표를 향해 진전을 이룰 가능성이 높은 액션만을 탐색 후보로 선택하는 메커니즘이다. 이 기법은 탐색의 분기 요인을 극적으로 줄여 실질적 성능을 크게 향상시킨다.

2. 도움 행동의 추출 과정

2.1 단계: 완화된 계획의 생성

현재 상태 s에서 삭제 무시 플래닝 그래프를 확장하고, 역방향 탐욕적 추출을 통해 완화된 계획 \pi^+(s)를 생성한다.

2.2 단계: 첫 번째 수준의 액션 식별

완화된 계획 \pi^+(s)에서 첫 번째 수준(level 0, 현재 상태에서 직접 적용 가능)의 액션을 추출한다:

\text{HA}(s) = \{a \in \text{applicable}(s) \mid a \in \pi^+(s) \text{ at level 0}\}

2.3 단계: 탐색 후보 제한

탐색 시 도움 행동만을 후보로 사용한다. 이에 의해 분기 요인이 \lvert\text{applicable}(s)\rvert에서 \lvert\text{HA}(s)\rvert로 축소된다.

3. 도움 행동의 직관적 이해

완화된 계획은 “삭제 효과를 무시할 때 목표에 도달하는 경로“이다. 이 경로의 첫 번째 단계에 있는 액션들은 목표를 향한 진전에 직접적으로 기여할 가능성이 높다. 이 직관에 따라, 도움 행동은 “현재 상태에서 목표로의 완화된 경로를 시작하는 행동“으로 이해할 수 있다.

4. 분기 요인 축소 효과

도메인에 따라 도움 행동의 수는 적용 가능한 전체 액션 수의 극소 비율일 수 있다:

이러한 축소는 탐색의 효율성을 수 배에서 수십 배까지 향상시킨다.

5. 도움 행동과 완전성

5.1 완전성의 제약

도움 행동만으로 탐색을 수행하면 완전성이 보장되지 않는다. 완화된 계획이 실제 계획과 다를 수 있으므로, 도움 행동에 포함되지 않은 액션이 실제로 필요한 경우가 존재한다.

5.2 FF의 대응 전략

FF는 도움 행동으로 해를 찾지 못하면 두 가지 대응을 수행한다:

1. IMPROVE 함수 내 확장: EHC의 BFS에서 도움 행동으로 개선을 찾지 못하면, 모든 적용 가능 액션으로 확장하여 재시도한다.
2. 대안 탐색 전환: EHC 전체가 실패하면 가중 A*로 전환하여, 도움 행동 제한 없이 완전한 탐색을 수행한다.

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

Fast Downward와 LAMA에서는 도움 행동의 개념을 선호적 연산자(preferred operators)로 일반화하였다. 여러 휴리스틱에서 독립적으로 선호적 연산자를 추출하고, 이들을 별도의 우선순위 큐(preferred queue)로 관리한다:

탐색 큐:
  preferred_queue: 선호적 연산자로 생성된 노드 (우선 탐색)
  regular_queue: 모든 적용 가능 액션으로 생성된 노드 (대안 탐색)

두 큐를 번갈아 사용함으로써, 도움 행동의 이점을 활용하면서도 완전성을 유지한다.

7. 도움 행동 추출의 변형

7.1 h^{\text{add}} 기반 도움 행동

h^{\text{add}} 휴리스틱에서도 유사한 도움 행동을 추출할 수 있다. 현재 상태의 h^{\text{add}} 값을 최적으로 달성하는 경로의 첫 번째 액션을 도움 행동으로 식별한다.

7.2 랜드마크 기반 선호 연산자

LAMA에서는 미달성 랜드마크(unachieved landmark)를 달성하는 액션을 선호적 연산자로 추출한다.

8. 참고 문헌

• Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
• 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.