1316.32 번역 단계와 SAS+ 표현

1. SAS+ 표현의 정의

SAS+(State-variable representation with Axioms and Sequencing)는 Bäckström과 Nebel(1995)이 제안한 플래닝 형식으로, PDDL의 이진 명제 기반 표현을 유한 도메인 다치 변수(multi-valued variable) 기반으로 변환한 것이다. Fast Downward의 번역기(translator)가 이 변환을 수행한다(Helmert, 2009).

2. PDDL에서 SAS+로의 번역 과정

2.1 불변량 분석(Invariant Analysis)

번역의 첫 단계는 PDDL 도메인에서 상태 불변량(state invariant)을 식별하는 것이다. 불변량은 모든 도달 가능 상태에서 유지되는 제약이다:

상호 배타적 불변량: 특정 시점에 정확히 하나만 참인 명제 그룹

{(robot_at r1 wp1), (robot_at r1 wp2), (robot_at r1 wp3)}
→ 정확히 하나만 참 (로봇은 한 위치에만 있음)

정확히 하나 불변량(exactly-one invariant): $n$ 개의 명제 중 정확히 하나가 참
최대 하나 불변량(at-most-one invariant): $n$ 개의 명제 중 최대 하나가 참 (전부 거짓 가능)

2.2 다치 변수 생성

불변량 분석 결과를 기반으로, 상호 배타적 명제 그룹을 하나의 다치 변수로 합친다:

PDDL 명제:
  (robot_at r1 wp1), (robot_at r1 wp2), (robot_at r1 wp3)

SAS+ 변수:
  V_robot_at_r1 ∈ {wp1, wp2, wp3}

PDDL 명제:
  (holding r1 box1), (gripper_free r1)

SAS+ 변수:
  V_gripper_r1 ∈ {holding_box1, free}

최대 하나 불변량의 경우, “none” 값이 추가되어 모든 명제가 거짓인 상태를 표현한다.

2.3 SAS+ 연산자 생성

PDDL 액션이 SAS+ 연산자로 변환된다:

PDDL 액션:
  move(r1, wp1, wp2)
  pre: (robot_at r1 wp1), (connected wp1 wp2)
  eff: (not (robot_at r1 wp1)), (robot_at r1 wp2)

SAS+ 연산자:
  move(r1, wp1, wp2)
  pre: V_robot_at_r1 = wp1, V_connected_wp1_wp2 = true
  eff: V_robot_at_r1 := wp2

3. SAS+ 표현의 이점

3.1 상태 표현의 간결성

$n$ 개의 이진 명제 대신 더 적은 수의 다치 변수로 상태를 표현한다. 이에 따라:

표현	변수 수	상태 비교 비용
PDDL (이진)	$n$ 명제	$O(n)$
SAS+ (다치)	$m$ 변수 ( $m \ll n$ )	$O(m)$

3.2 휴리스틱의 효율적 계산

다치 변수 기반 표현에서 인과 그래프, 도메인 전이 그래프 등의 분석이 자연스럽게 수행되어, 추상화 휴리스틱의 설계가 용이해진다.

3.3 효과의 명시적 표현

SAS+ 연산자에서 효과는 “변수의 값을 $v_1$ 에서 $v_2$ 로 변경“하는 형태이다. 이진 표현에서의 “추가+삭제” 대신 단일 값 할당으로 표현되어, 전이 구조 분석이 용이하다.

4. 인과 그래프(Causal Graph)

SAS+ 표현에서 변수 간의 인과적 의존 관계를 방향 그래프로 표현한다:

$(v_i, v_j) \in CG \iff \exists \text{op}: v_i \in \text{pre}(\text{op}) \wedge v_j \in \text{eff}(\text{op}) \wedge v_i \neq v_j$

인과 그래프는 Fast Downward의 인과 그래프 휴리스틱( $h^{\text{CG}}$ )과 합병-축소 휴리스틱의 기반이 된다.

5. 도메인 전이 그래프(Domain Transition Graph, DTG)

각 SAS+ 변수에 대해, 해당 변수의 값 간 전이를 그래프로 표현한다:

$DTG(v_i) = (D_i, E_i) \quad \text{where } (d_1, d_2) \in E_i \iff \exists \text{op}: v_i = d_1 \in \text{pre} \wedge v_i := d_2 \in \text{eff}$

DTG는 변수의 값 변경 경로를 분석하여 휴리스틱을 계산하는 데 활용된다.

6. 로봇 도메인에서의 SAS+ 변환 예시

PDDL 도메인:
  술어: robot_at(?r, ?w), object_at(?o, ?w), holding(?r, ?o), gripper_free(?r)
  객체: robot1, wp1, wp2, wp3, box1

SAS+ 변수:
  V_robot_at_robot1 ∈ {wp1, wp2, wp3}
  V_object_at_box1 ∈ {wp1, wp2, wp3, none}
  V_gripper_robot1 ∈ {free, holding_box1}

7. 참고 문헌

Bäckström, C. & Nebel, B. (1995). “Complexity Results for SAS+ Planning.” Computational Intelligence, 11(4), 625–655.
Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5–6), 503–535.
Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.