1315.38 파생 술어의 성능 영향 분석
1. 성능 영향의 개요
파생 술어는 도메인의 표현력과 간결성을 향상시키지만, 플래닝 과정에서 추가적인 계산 비용을 발생시킨다. 각 상태 전이 시 파생 술어의 값을 재계산해야 하므로, 파생 술어의 수, 복잡도, 재귀 깊이가 전체 플래닝 성능에 영향을 미친다.
2. 계산 비용의 원천
2.1 고정점 계산 비용
재귀적 파생 술어는 고정점에 도달할 때까지 반복 계산이 필요하다. 각 반복에서 모든 파생 술어 규칙이 모든 가능한 바인딩에 대해 평가된다.
단일 상태에서의 파생 술어 평가 비용:
C_{\text{derived}} = \sum_{i=1}^{k} \text{iterations}_i \times \lvert \text{groundings}_i \rvert \times \text{eval\_cost}_i
여기서 k는 파생 술어의 수, \text{iterations}_i는 고정점 도달까지의 반복 횟수, \lvert \text{groundings}_i \rvert는 그라운딩된 인스턴스 수이다.
2.2 상태 전이당 오버헤드
파생 술어 평가는 매 상태 전이에서 수행되므로, 탐색의 각 노드 확장에 추가 비용이 발생한다:
C_{\text{total}} = N_{\text{expansions}} \times C_{\text{derived}}
여기서 N_{\text{expansions}}는 총 노드 확장 수이다.
3. 파생 술어 유형별 성능 영향
| 유형 | 반복 횟수 | 인스턴스 증가 | 성능 영향 |
|---|---|---|---|
| 비재귀적 단순 접합 | 1 | 없음 | 미미함 |
| 비재귀적 양화 | 1 | 양화 변수 수에 비례 | 중간 |
| 재귀적 (선형 체인) | O(n) | 경로 수에 비례 | 중간~높음 |
| 재귀적 (일반 그래프) | O(n^2) | O(n^2) | 높음 |
| 다중 계층 재귀 | 계층 수에 비례 | 누적적 증가 | 매우 높음 |
4. 실험적 분석
Thiébaux, Hoffmann, & Nebel(2005)의 연구에 따르면, 파생 술어(공리)의 적절한 사용은 오히려 플래닝 성능을 향상시킬 수 있다. 파생 술어가 복합 전제 조건을 대체하면:
- 상태 표현의 축소: 명시적으로 관리해야 하는 술어 수가 감소한다.
- 그라운딩 공간의 축소: 파생 술어가 전제 조건을 간소화하여 적용 가능 액션의 열거 비용이 감소한다.
- 휴리스틱 정보의 향상: 파생 술어가 제공하는 추상화가 휴리스틱의 정보성을 높일 수 있다.
반면, 재귀적 파생 술어의 과도한 사용은 성능을 저하시킬 수 있다.
5. 성능 최적화 전략
5.1 비재귀적 파생 술어 선호
가능하면 재귀적 정의를 비재귀적으로 변환하거나, 기반 술어로 사전 계산하여 설정한다:
;; 재귀적 파생 술어 대신 기반 술어로 사전 계산
;; 문제 파일에서 모든 도달 가능 쌍을 명시
(:init
(reachable wp1 wp2) (reachable wp1 wp3) (reachable wp1 wp4)
(reachable wp2 wp3) (reachable wp2 wp4)
(reachable wp3 wp4)
)
이 방법은 연결 그래프가 정적인(실행 중 변하지 않는) 경우에 적합하다.
5.2 파생 술어의 범위 제한
양화사의 범위를 구체적 타입으로 제한하여 인스턴스 수를 줄인다:
;; 넓은 범위 (비효율)
(:derived (all_clear ?z - zone)
(forall (?x - object) (not (obstacle ?x ?z))))
;; 좁은 범위 (효율)
(:derived (all_clear ?z - zone)
(forall (?obs - obstacle) (not (obstacle_at ?obs ?z))))
5.3 계층 깊이 제한
파생 술어 계층을 3~4 수준 이내로 제한한다. 깊은 계층은 계산 비용을 누적적으로 증가시킨다.
5.4 증분적 평가
Fast Downward 등의 플래너는 이전 상태에서의 파생 술어 값을 캐싱하고, 변경된 기반 술어에 영향받는 파생 술어만 재평가하는 증분적 접근을 사용한다.
6. 파생 술어 vs 대안적 모델링의 성능 비교
| 접근 | 도메인 크기 | 플래닝 효율 | 유지 보수성 |
|---|---|---|---|
| 파생 술어 사용 | 간결 | 상태에 따라 다름 | 높음 |
| 전제 조건 복제 | 장황 | 간단한 경우 유리 | 낮음 |
| 기반 술어 사전 계산 | 초기 상태 확장 | 정적 그래프에서 유리 | 중간 |
| 보조 액션 도입 | 액션 수 증가 | 동적 환경에서 유리 | 중간 |
7. 권장 사항
- 비재귀적 파생 술어는 성능 우려 없이 사용 가능하다. 전제 조건의 반복을 대체하여 오히려 성능을 향상시킬 수 있다.
- 재귀적 파생 술어는 도메인 규모에 따라 신중히 사용하라. 웨이포인트 수가 수십 개 이내이면 실용적이나, 수백 개 이상이면 성능 테스트가 필요하다.
- 성능 문제 발생 시 프로파일링을 통해 병목을 식별하라. 특정 파생 술어의 평가가 전체 시간의 대부분을 차지하는 경우, 해당 술어를 기반 술어로 대체하는 것을 고려한다.
8. 참고 문헌
- Thiébaux, S., Hoffmann, J., & Nebel, B. (2005). “In Defense of PDDL Axioms.” Artificial Intelligence, 168(1–2), 38–69.
- Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5–6), 503–535.
- Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.