1316.16 솔루션 추출을 위한 역방향 탐색

1316.16 솔루션 추출을 위한 역방향 탐색

1. 솔루션 추출의 개요

GraphPlan의 솔루션 추출(solution extraction) 단계는 확장된 플래닝 그래프에서 역방향으로 탐색하여, 각 수준에서 목표를 달성하는 비뮤텍스 액션 집합을 선택하는 과정이다. 이 과정은 그래프의 마지막 수준(목표 조건이 포함된 수준)에서 시작하여 첫 번째 수준(초기 상태)까지 역방향으로 진행한다(Blum & Furst, 1997).

2. 역방향 탐색 알고리즘

EXTRACT_SOLUTION(graph, goals, level):
    IF level = 0:
        IF goals ⊆ P_0:
            RETURN []          ;; 빈 계획 (초기 상태가 목표를 만족)
        ELSE:
            RETURN FAILURE

    ;; 현재 수준에서 목표를 달성하는 액션 집합 선택
    action_sets ← SELECT_ACTIONS(goals, level)

    FOR EACH action_set IN action_sets:
        IF no_mutex_in(action_set):
            ;; 선택된 액션들의 전제 조건이 이전 수준의 새로운 목표가 됨
            new_goals ← union of preconditions of actions in action_set
            sub_plan ← EXTRACT_SOLUTION(graph, new_goals, level - 1)
            IF sub_plan ≠ FAILURE:
                RETURN sub_plan + action_set

    ;; 메모이제이션: 실패한 (goals, level) 쌍을 기록
    memo[goals, level] ← FAILURE
    RETURN FAILURE

3. 액션 선택 과정

각 수준에서 목표 리터럴을 달성하는 액션을 선택하는 과정:

  1. 목표 리터럴 분배: 각 목표 리터럴 g_i에 대해, 수준 l의 액션 계층에서 g_i를 효과로 포함하는 액션을 하나 선택한다.
  2. 뮤텍스 검사: 선택된 액션 집합 내에 뮤텍스 쌍이 존재하지 않는지 확인한다.
  3. 역추적: 뮤텍스가 발견되면 다른 액션 조합을 시도한다.

4. 메모이제이션(Memoization)

솔루션 추출의 효율성을 위해, 실패한 (목표 집합, 수준) 쌍을 메모이제이션 테이블에 기록한다. 동일한 목표 집합이 동일한 수준에서 다시 요청되면 즉시 실패를 반환하여 중복 탐색을 방지한다.

EXTRACT_SOLUTION(graph, goals, level):
    IF (goals, level) ∈ memo:
        RETURN FAILURE         ;; 이전에 실패한 조합
    ...

메모이제이션은 솔루션 추출의 성능을 크게 향상시키며, GraphPlan의 실용적 효율성에 핵심적인 기여를 한다.

5. 솔루션 추출의 예시

목표: \{(\text{holding} \ r1 \ box1), (\text{robot\_at} \ r1 \ wp2)\}, 수준 3에서 추출 시작

수준 3 → 수준 2:

  • (holding r1 box1) 달성: pick(r1, box1, wp2) 선택
  • (robot_at r1 wp2) 달성: no-op(robot_at r1 wp2) 선택
  • 뮤텍스 검사: pick과 no-op(robot_at r1 wp2)가 뮤텍스가 아닌지 확인
  • 새로운 목표: {(robot_at r1 wp2), (object_at box1 wp2), (gripper_free r1)}

수준 2 → 수준 1:

  • (robot_at r1 wp2) 달성: move(r1, wp1, wp2) 선택
  • (object_at box1 wp2) 달성: no-op(object_at box1 wp2) 선택
  • (gripper_free r1) 달성: no-op(gripper_free r1) 선택
  • 새로운 목표: {(robot_at r1 wp1), (connected wp1 wp2), (object_at box1 wp2), (gripper_free r1)}

수준 1 → 수준 0:

  • 모든 목표가 P_0(초기 상태)에 포함 → 성공

결과 계획: [move(r1, wp1, wp2), pick(r1, box1, wp2)]

6. 솔루션 추출의 복잡도

솔루션 추출은 최악의 경우 NP-완전이다. 각 수준에서 목표 리터럴에 대한 액션 선택이 CSP(제약 충족 문제)에 해당하며, 뮤텍스 제약의 충족을 확인하는 것이 핵심적 어려움이다.

그러나 메모이제이션과 가지치기에 의해 실제 성능은 대부분의 벤치마크 도메인에서 효율적이다.

7. 솔루션 추출 실패와 그래프 재확장

수준 k에서 솔루션 추출이 실패하면, 그래프를 한 수준 더 확장하여 수준 k+1에서 다시 솔루션 추출을 시도한다. 추가 수준의 확장은 새로운 액션과 명제를 도입하고 뮤텍스를 감소시켜, 이전에 불가능했던 액션 조합이 가능해질 수 있다.

그래프가 수렴한 후에도 연속으로 솔루션 추출이 실패하면(메모이제이션 테이블도 수렴), 문제에 해가 없다고 판정한다.

8. 참고 문헌

  • Blum, A. L. & Furst, M. L. (1997). “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence, 90(1–2), 281–300.
  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.