1316.22 부분 순서 플래너의 구조와 동작

1. 부분 순서 계획의 정의

부분 순서 계획(partial-order plan)은 액션 간에 필요한 순서 관계만을 명시하고, 불필요한 순서는 미결정 상태로 유지하는 계획 표현이다. 전순서 계획(total-order plan)이 모든 액션 간의 순서를 고정하는 것과 달리, 부분 순서 계획은 “A는 B 이전에 실행되어야 한다“는 필수적 순서만 포함하므로 실행의 유연성이 높다(Weld, 1994).

2. 부분 순서 계획의 구성 요소

부분 순서 계획 $\pi$ 는 다음의 네 가지 구성 요소로 정의된다:

$\pi = \langle A, O, L, C \rangle$

$A$ (액션 집합): 계획에 포함된 액션의 집합. 가상의 시작 액션( $a_{\text{init}}$ )과 종료 액션( $a_{\text{goal}}$ )을 포함한다.
$O$ (순서 제약): 액션 간의 부분 순서 관계. $a_i \prec a_j$ 는 $a_i$ 가 $a_j$ 이전에 실행되어야 함을 의미한다.
$L$ (인과 링크): 액션 간의 인과 관계. $a_i \xrightarrow{p} a_j$ 는 $a_i$ 의 효과 $p$ 가 $a_j$ 의 전제 조건 $p$ 를 지원(support)함을 의미한다.
$C$ (바인딩 제약): 변수 바인딩에 대한 동등성/부등성 제약.

3. 부분 순서 플래너의 탐색 공간

부분 순서 플래너의 탐색 공간에서 각 노드는 부분 계획이며, 탐색은 다음의 결함(flaw)을 해소하면서 진행된다:

3.1 열린 조건(Open Condition)

아직 지원되지 않은(인과 링크가 설정되지 않은) 전제 조건이다. 해소 방법:

기존 액션 재사용: 이미 계획에 포함된 액션의 효과로 지원
새 액션 추가: 해당 조건을 효과로 가지는 새 액션을 계획에 추가

3.2 위협(Threat)

인과 링크 $a_i \xrightarrow{p} a_j$ 에 대해, 제3의 액션 $a_k$ 가 $p$ 를 삭제할 수 있으며 $a_i$ 와 $a_j$ 사이에 실행될 수 있는 상황이다. 해소 방법:

승격(Promotion): $a_k$ 를 $a_i$ 이전으로 순서 제약 추가 ( $a_k \prec a_i$ )
강등(Demotion): $a_k$ 를 $a_j$ 이후로 순서 제약 추가 ( $a_j \prec a_k$ )

4. 기본 알고리즘: POP (Partial-Order Planning)

POP(initial_plan):
    plan ← initial_plan  ;; {a_init, a_goal}, {a_init ≺ a_goal}, {}, {}

    WHILE plan has flaws:
        flaw ← SELECT_FLAW(plan)

        IF flaw is open_condition (a_j needs p):
            resolvers ← FIND_RESOLVERS(plan, a_j, p)
            IF resolvers = ∅: RETURN FAILURE
            ;; 비결정적 선택 (역추적 가능)
            resolver ← CHOOSE(resolvers)
            APPLY_RESOLVER(plan, resolver)

        IF flaw is threat (a_k threatens a_i →p→ a_j):
            ;; 승격 또는 강등 선택
            IF can_promote(a_k, a_i): ADD_ORDER(plan, a_k ≺ a_i)
            ELSE IF can_demote(a_k, a_j): ADD_ORDER(plan, a_j ≺ a_k)
            ELSE: RETURN FAILURE

    RETURN plan

5. 부분 순서 계획의 장점

최소 위임(Least Commitment): 필요하지 않은 순서를 결정하지 않아 탐색 공간이 줄어들 수 있다.
실행 유연성: 부분 순서 계획은 여러 전순서 선형화를 허용하므로, 실행 시 상황에 따라 적합한 순서를 선택할 수 있다.
병렬 실행 지원: 순서 제약이 없는 액션은 병렬로 실행 가능하다.

6. 부분 순서 계획의 단점

효율적 휴리스틱의 부재: 부분 계획에 대한 정보적 휴리스틱 설계가 어렵다.
구현 복잡성: 인과 링크 관리, 위협 검출, 역추적 처리가 상태 공간 탐색보다 복잡하다.
성능 열세: 현대 벤치마크에서 전방 휴리스틱 탐색 플래너에 비해 성능이 낮다.

7. 현대 플래닝에서의 위치

UCPOP, VHPOP 등의 부분 순서 플래너가 개발되었으나, 2000년대 이후 전방 휴리스틱 탐색 플래너(FF, Fast Downward)에 의해 주류에서 벗어났다. 그러나 부분 순서의 개념은 POPF 등의 시간 플래너에서 듀레이티브 액션의 병렬 실행 관리에 계승되고 있다.

8. 참고 문헌

Weld, D. S. (1994). “An Introduction to Least Commitment Planning.” AI Magazine, 15(4), 27–61.
Penberthy, J. S. & Weld, D. S. (1992). “UCPOP: A Sound, Complete, Partial Order Planner for ADL.” Proceedings of KR, 103–114.
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.