부분 순서 플래닝의 개념 (Concept of Partial-Order Planning)

1. 개요

부분 순서 플래닝(Partial-Order Planning, POP)은 행동 간의 순서를 필요한 만큼만 지정하는 계획 방식이다. 전체 순서(total-order) 계획이 행동의 완전한 선형 순서를 결정하는 것과 달리, 부분 순서 계획은 인과 관계에 의해 필수적인 순서 제약만을 부여하고 나머지는 자유롭게 둔다.

2. 부분 순서 계획의 구조

부분 순서 계획 $\pi_{PO}$ 는 다음 요소로 구성된다.

요소	기호	설명
행동 집합	$A_\pi$	계획에 포함된 행동의 집합
순서 제약	$\prec$	행동 쌍 간의 순서 관계 $(a_i \prec a_j$ : $a_i$ 가 $a_j$ 보다 먼저)
인과 링크	$CL$	$(a_i, p, a_j)$ : $a_i$ 의 효과 $p$ 가 $a_j$ 의 전제 조건 $p$ 를 지원
개방 전제 조건	$OC$	아직 지원되지 않은 전제 조건

3. 인과 링크 (Causal Link)

$a_i \xrightarrow{p} a_j$

“행동 $a_i$ 가 명제 $p$ 를 달성하여 행동 $a_j$ 의 전제 조건을 지원한다“는 의미이다.

인과 링크의 보호

다른 행동 $a_k$ 가 인과 링크 $a_i \xrightarrow{p} a_j$ 를 위협(threaten)하면 안 된다. $a_k$ 가 $p$ 를 삭제하고 $a_i$ 와 $a_j$ 사이에 실행될 수 있는 경우 위협이 발생한다.

부분 순서 vs 완전 순서

특성	완전 순서	부분 순서
행동 순서	완전 결정	필요한 순서만 결정
유연성	없음	높음 (실행 시 순서 선택)
병렬화	별도 분석 필요	자연스럽게 식별
계획 공간 크기	$n!$ 순열	부분 순서의 수 (더 작음)
탐색 효율	모든 순열 탐색	순서 무관 부분 제거

예시

목표: on(A, table) ∧ on(B, table)

완전 순서: place(A) → place(B)  또는  place(B) → place(A)
부분 순서: {place(A), place(B)} (순서 무관)

시간적 계획에서의 의의

부분 순서 계획은 시간적(temporal) 계획에서 병렬 실행 가능한 행동을 자동으로 식별한다. POPF(Partial-Order Planning Forward) 계획기가 이 접근을 채택한다.

참고 문헌

Penberthy, J., & Weld, D. (1992). “UCPOP: A Sound, Complete, Partial Order Planner for ADL.” KR 1992.
Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.

버전	날짜	변경 사항
v0.1	2026-04-05	초안 작성