1317.24 POPF 플래너의 통합
1. POPF 플래너의 개요
POPF(Partial Order Planning Forward)는 시간적 계획(temporal planning)을 지원하는 전진 탐색(forward-chaining) 기반의 자동화된 플래너이다. POPF는 King’s College London의 연구팀에 의해 개발되었으며, PDDL2.1의 시간적 확장(temporal extension)을 완전히 지원한다. 구체적으로, 지속 시간을 갖는 액션(durative action), 시작 조건(at start), 종료 조건(at end), 불변 조건(over all), 수치 효과(numeric effect) 등을 처리할 수 있다. PlanSys2는 POPF를 기본 플래너(default planner)로 채택하고 있으며, 이는 로봇 공학 도메인에서 시간적 계획이 필수적이라는 점을 반영한 선택이다(Coles et al., 2010; Martín et al., 2021).
2. POPF의 알고리즘적 기반
2.1 전진 상태 공간 탐색
POPF는 전진 상태 공간 탐색(forward state-space search) 방식을 기본 탐색 전략으로 사용한다. 초기 상태에서 출발하여 적용 가능한 액션을 순차적으로 적용하면서 목표 상태에 도달하는 경로를 탐색한다. 탐색 과정에서 휴리스틱 함수(heuristic function)를 사용하여 목표까지의 추정 비용을 계산하고, 이를 기반으로 탐색을 안내한다.
2.2 부분 순서 계획의 통합
POPF의 핵심 기여는 전진 탐색과 부분 순서 계획(partial-order planning)을 결합한 점이다. 순수한 전진 탐색은 액션 간의 총 순서(total order)를 강제하지만, POPF는 인과적 의존성(causal dependency)이 없는 액션들 사이의 순서를 유연하게 처리한다. 이를 통해 동시 실행 가능한 액션들을 병렬로 스케줄링할 수 있으며, 이는 시간적 계획의 품질을 향상시킨다.
2.3 시간적 제약의 처리
POPF는 Simple Temporal Network(STN)를 사용하여 액션 간의 시간적 제약을 관리한다. 각 액션의 시작 시점과 종료 시점 사이의 관계, 액션 간의 순서 제약, 불변 조건의 유효 구간 등이 STN의 시간적 제약으로 표현되며, 시간적 일관성(temporal consistency)이 확인된 계획만이 유효한 해로 채택된다.
3. PlanSys2에서의 POPF 통합 구조
3.1 POPFPlanSolver 플러그인
PlanSys2는 plansys2_popf_plan_solver 패키지를 통해 POPF 플래너를 플러그인 형태로 통합한다. 이 패키지에는 POPFPlanSolver 클래스가 구현되어 있으며, 이 클래스는 PlanSolverBase 추상 클래스를 상속하여 POPF와의 인터페이스를 구현한다.
POPFPlanSolver의 주요 동작 절차는 다음과 같다.
- 임시 파일 생성: 플래너 노드로부터 수신한 도메인 PDDL 문자열과 문제 PDDL 문자열을
/tmp디렉터리의 임시 파일로 저장한다. - POPF 프로세스 실행: POPF 실행 파일을 자식 프로세스로 생성하고, 도메인 파일과 문제 파일의 경로를 명령행 인자로 전달한다.
- 표준 출력 캡처: POPF는 계획 결과를 표준 출력(stdout)으로 출력하므로, 자식 프로세스의 표준 출력을 파이프(pipe)를 통해 캡처한다.
- 출력 파싱: 캡처된 출력에서 계획 항목을 추출하여
Plan자료 구조로 변환한다. - 결과 반환: 변환된 계획을 플래너 노드에 반환한다.
3.2 POPF 실행 명령
POPF 플러그인이 외부 프로세스로 POPF를 호출할 때 사용하는 명령 형식은 다음과 같다.
popf <domain_file> <problem_file>
POPF는 다양한 명령행 옵션을 지원하며, PlanSys2에서는 파라미터를 통해 이를 구성할 수 있다. 주요 옵션은 다음과 같다.
| 옵션 | 설명 |
|---|---|
-n | 첫 번째 해를 찾으면 즉시 종료한다 |
-citation | POPF의 인용 정보를 출력한다 |
-T | 시간 제한을 설정한다(단위: 초) |
기본적으로 PlanSys2의 POPF 플러그인은 최적해 탐색보다 신속한 해 도출을 우선시하는 구성을 사용한다. 이는 로봇 시스템의 실시간 요구사항에 부합하는 선택이다.
3.3 POPF 출력 형식의 파싱
POPF의 표준 출력에는 탐색 통계, 휴리스틱 값, 계획 결과 등 다양한 정보가 포함된다. POPFPlanSolver는 출력에서 계획 결과 영역만을 추출해야 한다. POPF의 계획 출력 형식은 다음과 같다.
; Time 0.000
0.000: (move robot1 kitchen corridor) [5.000]
0.000: (charge robot2 station) [10.000]
5.001: (move robot1 corridor bedroom) [5.000]
각 행의 구조는 다음과 같다.
- 시작 시각: 소수점 세 자리의 부동 소수점(단위: 초)
- 액션 표현: 괄호로 둘러싸인 PDDL 액션과 인자
- 지속 시간: 대괄호로 둘러싸인 부동 소수점(단위: 초)
POPFPlanSolver는 정규 표현식(regular expression)을 사용하여 각 행을 파싱하고, 시작 시각, 액션 문자열, 지속 시간을 추출하여 PlanItem 구조체에 저장한다. 세미콜론(;)으로 시작하는 주석 행이나 빈 행은 무시된다.
4. POPF의 PDDL 지원 범위
POPF가 지원하는 PDDL 요구사항(requirements)은 다음과 같다.
| PDDL 요구사항 | 지원 여부 | 설명 |
|---|---|---|
:strips | 지원 | 기본 STRIPS 계획 |
:typing | 지원 | 타입 시스템 |
:equality | 지원 | 등호 비교 |
:durative-actions | 지원 | 시간적 액션 |
:numeric-fluents | 지원 | 수치 함수 |
:conditional-effects | 부분 지원 | 조건부 효과 |
:derived-predicates | 미지원 | 파생 술어 |
:preferences | 미지원 | 선호도 기반 계획 |
이 지원 범위는 PlanSys2에서 도메인 모델을 설계할 때 고려해야 하는 제약 조건이다. POPF가 지원하지 않는 PDDL 기능을 도메인에서 사용할 경우, 해당 기능을 지원하는 다른 플래너 플러그인으로 교체해야 한다.
5. POPF 빌드와 의존성
PlanSys2에서 POPF를 사용하기 위해서는 POPF 실행 파일이 시스템에 설치되어 있어야 한다. PlanSys2는 ros-<distro>-popf 패키지를 통해 POPF의 사전 빌드된 바이너리를 제공한다. 이 패키지는 ROS2 배포판의 패키지 관리자를 통해 설치할 수 있다.
POPF의 주요 빌드 의존성은 다음과 같다.
- Coin-OR CLP: 선형 프로그래밍 솔버로, POPF의 수치 계획에서 시간적 제약과 수치 제약을 처리하는 데 사용된다.
- Coin-OR CBC: 혼합 정수 프로그래밍 솔버이다.
- GSL(GNU Scientific Library): 수학적 연산에 사용된다.
이러한 의존성은 POPF의 수치적 계획 수립 기능을 지원하기 위한 것이며, 순수한 논리적 계획에서는 활용되지 않는다.
6. POPF 통합의 한계와 고려사항
POPF를 PlanSys2에 통합하여 사용할 때 인지해야 할 한계는 다음과 같다.
- 탐색 공간 폭발: 객체 수와 액션 수가 증가하면 탐색 공간이 지수적으로 증가하여 계획 수립 시간이 급격히 늘어날 수 있다. 이는 POPF에 국한된 문제가 아니라 자동화된 계획 수립의 일반적 특성이다.
- 최적성 보장의 부재: POPF는 기본적으로 만족해(satisficing solution)를 반환하며, 최적해(optimal solution)의 생성을 보장하지 않는다. 다만, 계획의 만듦새(makespan)를 최소화하려는 탐색 전략을 사용한다.
- 파생 술어 미지원: POPF는 파생 술어(derived predicate)를 지원하지 않으므로, 이 기능이 필요한 도메인에서는 대체 플래너를 사용해야 한다.
- 프로세스 기반 호출의 오버헤드: POPF는 외부 프로세스로 실행되므로, 프로세스 생성과 파일 입출력에 따른 오버헤드가 발생한다. 빈번한 재계획이 필요한 상황에서는 이 오버헤드가 누적될 수 있다.
이러한 한계에도 불구하고, POPF는 시간적 계획을 지원하는 효율적인 플래너로서 로봇 공학의 다양한 임무 계획 시나리오에 적합하며, PlanSys2의 기본 플래너로서 광범위하게 활용되고 있다(Coles et al., 2010; Martín et al., 2021).
참고 문헌
- Coles, A. J., Coles, A. I., Fox, M., & Long, D. (2010). “Forward-Chaining Partial-Order Planning.” Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS), 42–49.
- Martín, F., Cañas, J. M., Ginés, J., & Fuentetaja, R. (2021). “PlanSys2: A Planning System Framework for ROS2.” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
- Fox, M., & Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61–124.
버전: v1.0