1316.43 Scorpion 플래너의 최신 기법

1. Scorpion의 개요

Scorpion은 Seipp et al.이 개발한 비용 최적 플래너로, Fast Downward 프레임워크를 기반으로 포화 비용 분할(saturated cost partitioning)과 카르테시안 추상화(Cartesian abstraction)를 결합한 최신 추상화 휴리스틱을 사용한다. IPC의 비용 최적 트랙에서 최고 수준의 성능을 보이는 현대 플래너이다.

2. 핵심 기법

2.1 카르테시안 추상화(Cartesian Abstraction)

CEGAR(Counterexample-Guided Abstraction Refinement) 기법을 플래닝에 적용하여 추상화를 자동으로 구성한다(Seipp & Helmert, 2013):

1. 초기 추상화: 모든 상태를 단일 추상 상태로 합침(최대 추상화)
2. 반례 검출: 추상 계획이 원래 문제에서 유효하지 않으면 반례를 생성
3. 정제(Refinement): 반례의 원인이 되는 추상 상태를 분할하여 추상화를 세밀화
4. 반복: 유효한 계획이 추출되거나 추상화 크기 한계에 도달할 때까지 반복

2.2 포화 비용 분할(Saturated Cost Partitioning)

여러 추상화의 휴리스틱을 합산할 때, 각 추상화에 “필요한 만큼만” 비용을 할당하고 나머지를 다음 추상화에 전달하는 탐욕적 방법이다(Seipp et al., 2020):

c_i(o) = \min(c_{\text{remaining}}(o), \text{needed}_i(o))

포화 비용 분할은 최적 비용 분할의 근사이면서, LP 풀이 없이 다항 시간에 계산 가능하다.

2.3 다양한 추상화의 조합

Scorpion은 다수의 카르테시안 추상화를 생성하고 포화 비용 분할로 결합하여, 단일 추상화보다 훨씬 정보적인 합산 휴리스틱을 구성한다.

3. 알고리즘의 구조

SCORPION(problem):
    1. PDDL → SAS+ 번역
    2. 다수의 카르테시안 추상화 생성 (CEGAR 반복)
    3. 포화 비용 분할로 비용 할당
    4. 합산 휴리스틱 구성
    5. A* 탐색으로 비용 최적 계획 생성

4. IPC 결과

Scorpion은 특히 구조적으로 분해 가능한 도메인(물류, 운송, 자원 할당)에서 탁월한 성능을 보인다.

5. Fast Downward 설정

# Scorpion 구성으로 Fast Downward 실행
./fast-downward.py domain.pddl problem.pddl \
    --search "astar(cegar(subtasks=[goals,landmarks]))"

6. 참고 문헌

• Seipp, J. & Helmert, M. (2013). “Counterexample-Guided Cartesian Abstraction Refinement.” Proceedings of ICAPS, 347–351.
• Seipp, J., Keller, T., & Helmert, M. (2020). “Saturated Cost Partitioning for Optimal Classical Planning.” Journal of Artificial Intelligence Research, 67, 129–167.
• Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.