1316.23 POCL 알고리즘의 원리

1. POCL의 정의

POCL(Partial-Order Causal Link) 알고리즘은 부분 순서 플래닝의 표준적 형태로, 인과 링크(causal link)를 사용하여 액션 간의 인과적 의존 관계를 명시적으로 추적하는 플래닝 알고리즘이다. POCL의 핵심은 인과 링크를 통한 계획의 정당성 유지와, 위협(threat)의 체계적 해소이다(Penberthy & Weld, 1992; McAllester & Rosenblitt, 1991).

2. 인과 링크

인과 링크(causal link) $a_i \xrightarrow{p} a_j$ 는 다음을 의미한다:

액션 $a_i$ 는 명제 $p$ 를 추가 효과로 생산한다: $p \in \text{eff}^+(a_i)$
액션 $a_j$ 는 명제 $p$ 를 전제 조건으로 요구한다: $p \in \text{pre}(a_j)$
$a_i$ 는 $a_j$ 이전에 실행된다: $a_i \prec a_j$
$a_i$ 와 $a_j$ 사이에 $p$ 를 삭제하는 액션이 실행되지 않아야 한다

인과 링크는 계획의 정당성(correctness)을 보장하는 핵심 메커니즘이다.

3. 위협과 해소

3.1 위협의 정의

인과 링크 $a_i \xrightarrow{p} a_j$ 에 대해, 액션 $a_k$ 가 다음 조건을 만족하면 위협(threat)이다:

$a_k$ 가 $p$ 를 삭제한다: $p \in \text{eff}^-(a_k)$
$a_k$ 가 $a_i$ 와 $a_j$ 사이에 실행될 수 있다: $a_i \prec a_k \prec a_j$ 가 가능한 순서

3.2 위협 해소 방법

승격(Promotion): $a_k$ 를 $a_i$ 이전으로 이동시킨다:
$O \leftarrow O \cup \{a_k \prec a_i\}$

강등(Demotion): $a_k$ 를 $a_j$ 이후로 이동시킨다:
$O \leftarrow O \cup \{a_j \prec a_k\}$

분리(Separation): 리프팅된 계획에서 변수 바인딩을 조정하여 $a_k$ 의 효과가 $p$ 와 달라지도록 한다(ADL 수준).

4. POCL 알고리즘

POCL(problem):
    ;; 초기 부분 계획
    A ← {a_init, a_goal}
    O ← {a_init ≺ a_goal}
    L ← {}
    C ← {}
    plan ← (A, O, L, C)

    WHILE plan has open conditions or threats:
        ;; 결함 선택 (선택 전략이 효율에 영향)
        flaw ← SELECT_FLAW(plan)

        IF flaw is open_condition (a_need, p):
            ;; p를 생산하는 액션 또는 기존 액션 찾기
            FOR EACH resolver:
                IF resolver is existing action a_sup:
                    L ← L ∪ {a_sup →p→ a_need}
                    O ← O ∪ {a_sup ≺ a_need}
                ELSE IF resolver is new action a_new:
                    A ← A ∪ {a_new}
                    L ← L ∪ {a_new →p→ a_need}
                    O ← O ∪ {a_init ≺ a_new ≺ a_goal}
                    O ← O ∪ {a_new ≺ a_need}
                ;; 새로운 위협 검사 및 해소

        ELSE IF flaw is threat (a_threat, a_i →p→ a_j):
            ;; 승격 또는 강등
            CHOOSE: promote(a_threat, a_i) OR demote(a_threat, a_j)

    RETURN plan

5. 결함 선택 전략

POCL의 성능은 결함 선택 전략(flaw selection strategy)에 크게 의존한다:

전략	설명	효과
LIFO	가장 최근 결함 우선	DFS와 유사한 탐색
FIFO	가장 오래된 결함 우선	BFS와 유사한 탐색
최소 비용 우선	해소 옵션이 적은 결함 우선	가지치기 효과
위협 우선	위협을 열린 조건보다 먼저 해소	계획 안정성 향상

경험적으로 “최소 비용 우선(least cost first)” 또는 “위협 우선(threats first)” 전략이 효과적이다.

6. POCL의 정확성

POCL은 건전하고(sound) 완전하다(complete):

건전성: 모든 결함이 해소된 계획은 유효하다. 인과 링크가 모든 전제 조건을 지원하고, 위협이 없으므로 인과 관계가 보호된다.
완전성: 해가 존재하면 POCL이 반드시 찾는다. 체계적 탐색(역추적 포함)에 의해 보장된다.

7. 대표적 POCL 플래너

플래너	개발	특성
UCPOP	Penberthy & Weld (1992)	ADL 지원, 부분 순서
VHPOP	Younes & Simmons (2003)	시간적 부분 순서 플래닝
SNLP	McAllester & Rosenblitt (1991)	초기 POCL 구현

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

POCL은 이론적 기여는 크지만, 현대 벤치마크에서 전방 휴리스틱 탐색 플래너에 비해 성능이 열세이다. 그러나 POCL의 인과 링크 개념은 현대 플래너의 랜드마크(landmark) 추출과 인과 분석에 영향을 미쳤다.

9. 참고 문헌

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