1316.21 SATPLAN의 병렬 계획 생성 능력
1. 병렬 계획의 정의
병렬 계획(parallel plan)은 동일한 시간 단계에서 여러 액션이 동시에 실행되는 계획이다. SATPLAN은 부호화 구조상 각 시간 단계에서 비간섭(non-interfering) 액션의 동시 실행을 자연스럽게 허용하므로, 병렬 계획 생성에 본질적으로 적합하다.
2. SATPLAN의 병렬성 메커니즘
2.1 시간 단계 기반 부호화
SATPLAN의 부호화에서 각 시간 단계는 하나의 “슬롯“에 해당하며, 해당 슬롯에 여러 액션 변수가 동시에 TRUE일 수 있다:
시간 0: a1^0 = TRUE, a2^0 = TRUE, a3^0 = FALSE, ...
시간 1: a4^1 = TRUE, a5^1 = FALSE, ...
2.2 상호 배제에 의한 병렬성 제어
동시 실행이 허용되지 않는 액션 쌍만 상호 배제 절로 제한된다:
\neg a_i^t \vee \neg a_j^t \quad \text{(간섭하는 액션 쌍에 대해서만)}
간섭하지 않는 액션 쌍에 대해서는 이러한 절이 추가되지 않으므로, SAT 솔버가 자연스럽게 동시 실행을 선택할 수 있다.
3. 병렬 계획의 makespan 최적성
SATPLAN은 시간 단계 T를 1부터 점진적으로 증가시키므로, 처음 충족 가능해지는 T가 최소 makespan(최소 병렬 길이)이다. 이에 따라 SATPLAN은 makespan 최적 병렬 계획을 보장한다.
순차 플래너가 생성하는 계획 길이와 SATPLAN의 makespan을 비교하면:
;; 순차 계획 (길이 6)
move(r1, wp1, wp2)
move(r2, wp3, wp4)
pick(r1, box1, wp2)
pick(r2, box2, wp4)
move(r1, wp2, wp5)
move(r2, wp4, wp5)
;; 병렬 계획 (makespan 3)
T=0: {move(r1, wp1, wp2), move(r2, wp3, wp4)}
T=1: {pick(r1, box1, wp2), pick(r2, box2, wp4)}
T=2: {move(r1, wp2, wp5), move(r2, wp4, wp5)}
동일한 목표를 달성하되, 병렬 계획은 시간적으로 절반의 단계로 완료된다.
4. 다중 로봇 도메인에서의 병렬 계획
SATPLAN의 병렬 계획 생성 능력은 다중 로봇 도메인에서 특히 유용하다. 각 로봇이 독립적으로 행동할 수 있는 액션은 동일 시간 단계에 배치되어 전체 임무 수행 시간이 단축된다:
;; 3대 로봇의 병렬 배송 계획
T=0: {move(r1, base, wp_A), move(r2, base, wp_B), move(r3, base, wp_C)}
T=1: {pick(r1, pkg1, wp_A), pick(r2, pkg2, wp_B), pick(r3, pkg3, wp_C)}
T=2: {move(r1, wp_A, cust1), move(r2, wp_B, cust2), move(r3, wp_C, cust3)}
T=3: {deliver(r1, pkg1, cust1), deliver(r2, pkg2, cust2), deliver(r3, pkg3, cust3)}
5. 병렬 계획의 선형화
병렬 계획을 순차적으로 실행해야 하는 경우, 각 시간 단계 내의 비간섭 액션을 임의의 순서로 나열하여 선형화(linearization)한다. 비간섭 액션 간의 순서는 결과에 영향을 미치지 않으므로 임의의 순서가 유효하다.
6. SATPLAN과 시간 플래너의 비교
| 특성 | SATPLAN (병렬) | POPF (시간 플래닝) |
|---|---|---|
| 병렬성 표현 | 이산 시간 단계 | 연속 시간 |
| makespan 최적 | 보장 (이산 단위) | 가능 (연속 시간) |
| 듀레이티브 액션 | 미지원 | 지원 |
| 수치 플루언트 | 미지원 | 지원 |
| 실행 모델 | 동시 순간 액션 | 시간적 중첩 |
SATPLAN은 순간적 액션의 병렬 실행을 모델링하는 반면, POPF 등의 시간 플래너는 지속 시간이 있는 듀레이티브 액션의 시간적 중첩을 처리할 수 있다. PlanSys2에서는 POPF가 기본 플래너이므로, 듀레이티브 액션을 통한 병렬 실행이 더 자연스러운 접근이다.
7. 병렬 계획 생성의 실용적 이점
- 임무 수행 시간 단축: 다중 로봇의 동시 활동으로 전체 시간 감소
- 자원 활용 극대화: 유휴 로봇 없이 모든 로봇이 동시에 작업
- 확장성: 로봇 수 증가에 따라 병렬성이 자연스럽게 증가
- 비간섭 보장: 상호 배제 절이 충돌 방지를 자동으로 보장
8. 참고 문헌
- Kautz, H. & Selman, B. (1996). “Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search.” Proceedings of AAAI, 1194–1201.
- Rintanen, J. (2014). “Madagascar: Scalable Planning with SAT.” IPC 2014 Planner Abstracts.
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.