1316.38 랜드마크 추출 알고리즘

1. 랜드마크 추출의 개요

랜드마크 추출(landmark extraction)은 플래닝 문제의 도메인 분석을 통해 모든 유효한 계획에서 반드시 달성되어야 하는 사실(랜드마크)과 그 순서 관계를 자동으로 식별하는 과정이다. 정확한 랜드마크 식별은 PSPACE-완전이므로, 실용적 플래너는 다항 시간의 근사 알고리즘을 사용한다.

2. 후방 체이닝 기반 추출

Hoffmann, Porteous, Sebastia(2004)가 제안한 기본적 추출 방법이다:

EXTRACT_LANDMARKS(goal, domain):
    landmarks ← goal              ;; 목표 자체가 랜드마크
    queue ← goal
    orderings ← {}

    WHILE queue ≠ ∅:
        l ← DEQUEUE(queue)
        ;; l을 달성하는 모든 액션의 공통 전제 조건을 찾음
        achievers ← {a ∈ A | l ∈ eff+(a)}
        common_preconds ← ∩(pre(a) for a ∈ achievers)

        FOR EACH p ∈ common_preconds:
            IF p ∉ landmarks:
                landmarks ← landmarks ∪ {p}
                orderings ← orderings ∪ {p →_n l}
                ENQUEUE(queue, p)

    RETURN (landmarks, orderings)

이 알고리즘의 핵심 직관: 사실 l을 달성하는 모든 방법(achiever)의 공통 전제 조건은 반드시 l 이전에 달성되어야 하므로 랜드마크이다.

3. 삭제 완화 기반 추출

삭제 완화 문제에서의 분석을 통해 더 많은 랜드마크를 추출한다:

RELAXED_LANDMARK_EXTRACTION(s0, goal):
    ;; 삭제 완화 플래닝 그래프 구축
    rpg ← BUILD_RELAXED_PLANNING_GRAPH(s0)

    landmarks ← goal
    FOR EACH g ∈ goal:
        ;; g를 삭제 완화 RPG에서 역추적하여 랜드마크 식별
        backtrace_landmarks(g, rpg, landmarks)

    RETURN landmarks

4. 선언적 랜드마크의 추출

선언적 랜드마크(disjunctive landmark)는 여러 사실 중 적어도 하나가 달성되어야 하는 경우이다:

;; l을 달성하는 모든 액션의 전제 조건 합집합 중,
;; 각 달성자에 대해 적어도 하나의 전제 조건이 포함되는 집합을 찾음
FOR EACH achiever a of l:
    one_of(pre(a)) must be achieved
;; → {pre(a1) ∪ pre(a2) ∪ ...}의 최소 히팅 셋이 선언적 랜드마크

5. 순서 관계의 추출

5.1 자연 순서(Natural Ordering)

l1 →_n l2 iff:
  l1은 l2의 모든 achiever의 전제 조건에 포함됨

5.2 탐욕적 필요 순서(Greedy-Necessary Ordering)

l1 →_gn l2 iff:
  삭제 완화 문제에서 l1은 l2의 최초 achiever의 전제 조건에 포함됨

5.3 합리적 순서(Reasonable Ordering)

l1 →_r l2 iff:
  l2가 달성된 후 l1을 달성하면 l2가 삭제됨
  → l1이 l2보다 먼저 달성되는 것이 합리적

6. 랜드마크 그래프

추출된 랜드마크와 순서 관계를 방향 비순환 그래프(DAG)로 구성한다:

LM 그래프 예시:

(robot_at r1 wp1) →_gn (robot_at r1 wp2) →_gn (holding r1 box1)
                                                    ↓_n
                                         (robot_at r1 customer)
                                                    ↓_n
                                         (delivered box1 customer)

이 그래프는 탐색 중 “다음으로 달성해야 할 랜드마크“를 식별하는 데 사용되며, 선호적 연산자 추출의 기반이 된다.

7. 추출 알고리즘의 복잡도

실용적으로는 삭제 완화 기반과 합리적 순서의 조합이 정보성과 효율성의 균형을 달성한다.

8. 참고 문헌

• Hoffmann, J., Porteous, J., & Sebastia, L. (2004). “Ordered Landmarks in Planning.” Journal of Artificial Intelligence Research, 22, 215–278.
• Richter, S., Helmert, M., & Westphal, M. (2008). “Landmarks Revisited.” Proceedings of AAAI, 975–982.
• Helmert, M. & Domshlak, C. (2009). “Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?” Proceedings of ICAPS, 162–169.