1316.40 POPF 시간 플래너의 구조

1. POPF의 개요

POPF(Partial-Order Planning Forward)는 Coles et al.(2010)이 개발한 시간 플래너(temporal planner)로, PDDL 2.1의 듀레이티브 액션을 지원하며 전방 상태 공간 탐색을 기반으로 시간적 계획을 생성한다. PlanSys2의 기본 플래너로 사용되며, 로봇 시스템에서 시간적 병렬 계획 생성의 표준적 선택이다.

2. POPF의 핵심 특성

2.1 전방 탐색과 시간적 병렬성의 결합

POPF는 전방 상태 공간 탐색의 효율성과 부분 순서의 시간적 유연성을 결합한다. 각 탐색 노드는 완전한 세계 상태에 더해, 현재 진행 중인 듀레이티브 액션들의 시간적 정보를 포함한다.

2.2 지원하는 PDDL 기능

2.3 듀레이티브 액션의 처리

POPF는 듀레이티브 액션을 시작 이벤트와 종료 이벤트의 쌍으로 분해하여 처리한다:

듀레이티브 액션 move(r1, wp1, wp2):
  시작 이벤트 (at start):
    조건: (robot_at r1 wp1), (connected wp1 wp2)
    효과: (not (robot_at r1 wp1)), (moving r1)
  
  불변 조건 (over all):
    (battery_sufficient r1)
  
  종료 이벤트 (at end):
    조건: (not (blocked wp2))
    효과: (robot_at r1 wp2), (not (moving r1))

탐색의 각 단계에서 새 액션의 시작, 진행 중 액션의 종료, 또는 두 가지를 모두 수행할 수 있다.

3. 시간적 상태 표현

POPF의 각 탐색 노드는 다음의 정보를 포함한다:

1. 현재 세계 상태: 참인 술어와 수치 함수 값의 집합
2. 진행 중 액션 목록: 시작되었으나 아직 종료되지 않은 듀레이티브 액션들
3. 시간적 제약: 액션 간의 시간적 순서 제약
4. 보호 구간: over all 조건을 위한 불변 보호 정보

4. 탐색 알고리즘

POPF_SEARCH(s0, goal):
    open ← {(s0, temporal_state_0)}
    
    WHILE open ≠ ∅:
        (s, ts) ← SELECT(open)  ;; 휴리스틱 기반 선택
        
        IF s ⊨ goal AND no_active_actions(ts):
            RETURN plan
        
        ;; 가능한 다음 이벤트 생성
        ;; 1. 새로운 듀레이티브 액션의 시작
        FOR EACH startable action a:
            (s', ts') ← apply_start(s, ts, a)
            IF valid(s', ts'): INSERT(open, (s', ts'))
        
        ;; 2. 진행 중 액션의 종료
        FOR EACH endable action a in active(ts):
            (s', ts') ← apply_end(s, ts, a)
            IF valid(s', ts'): INSERT(open, (s', ts'))

5. 병렬 계획 생성

POPF는 시간적으로 중첩 가능한 듀레이티브 액션을 자동으로 병렬 배치한다. 상호 간섭하지 않는 액션의 시작 이벤트가 동일한 시점에 발생할 수 있으며, 이를 통해 다중 로봇의 동시 활동이 자연스럽게 계획된다.

6. PlanSys2에서의 POPF 통합

PlanSys2는 POPF를 기본 플래너로 내장하고 있으며, 다음의 인터페이스로 통합된다:

# PlanSys2 런치 파일에서 POPF 설정
Node(
    package='plansys2_bringup',
    executable='plansys2_node',
    parameters=[{
        'model_file': domain_file,
        'planner_plugin': 'plansys2::POPFPlanSolver'
    }]
)

POPF가 생성한 시간적 계획은 Executor 노드에 전달되어, 듀레이티브 액션의 시작과 종료가 시간적으로 관리된다.

7. POPF의 성능 특성

8. 참고 문헌

• Coles, A. J., Coles, A. I., Fox, M., & Long, D. (2010). “Forward-Chaining Partial-Order Planning.” Proceedings of ICAPS, 42–49.
• Fox, M. & Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61–124.
• Gonzalez, F., Martin, F., Matellán, V., & Rodriguez, F. J. (2021). “PlanSys2: A Planning System Framework for ROS2.” IEEE ICARSC.