1314.27 액션 적용 후 상태 전이 계산

1. 상태 전이 함수의 정의

상태 전이 함수(state transition function) $\gamma$ 는 현재 상태와 적용 가능한 액션을 입력으로 받아 결과 상태를 산출하는 함수이다:

$\gamma: S \times A \rightarrow S$

여기서 $S$ 는 가능한 상태의 집합, $A$ 는 그라운드 액션의 집합이다. $\gamma$ 는 전제 조건이 만족되는 상태-액션 쌍에 대해서만 정의되는 부분 함수(partial function)이다:

$\gamma(s, a) = \begin{cases} (s \setminus \text{eff}^-(a)) \cup \text{eff}^+(a) & \text{if } s \models \text{pre}(a) \\ \text{undefined} & \text{otherwise} \end{cases}$

2. STRIPS 상태 전이의 계산 과정

STRIPS 의미론에서의 상태 전이 계산은 다음의 세 단계로 수행된다.

1단계: 삭제 효과 적용

$s_{\text{mid}} = s \setminus \text{eff}^-(a)$

상태 집합에서 삭제 효과에 명시된 술어 인스턴스를 제거한다.

2단계: 추가 효과 적용

$s' = s_{\text{mid}} \cup \text{eff}^+(a)$

중간 상태에 추가 효과의 술어 인스턴스를 추가한다.

3단계: 프레임 가정에 의한 보존

효과에 명시되지 않은 모든 술어 인스턴스는 변경 없이 보존된다. 이는 집합 연산의 자연스러운 결과로서, 별도의 처리가 필요하지 않다.

2.1 계산 예시

(:action pick_up
    :parameters (?r - robot ?obj - object ?loc - waypoint)
    :precondition (and
        (robot_at ?r ?loc)
        (object_at ?obj ?loc)
        (gripper_free ?r)
    )
    :effect (and
        (holding ?r ?obj)
        (not (object_at ?obj ?loc))
        (not (gripper_free ?r))
    )
)

상태: $s = \{(\text{robot\_at} \ r1 \ wp2), (\text{object\_at} \ box1 \ wp2), (\text{gripper\_free} \ r1), (\text{connected} \ wp1 \ wp2)\}$

그라운드 액션: (pick_up r1 box1 wp2)

1단계 - 삭제: $s_{\text{mid}} = s \setminus \{(\text{object\_at} \ box1 \ wp2), (\text{gripper\_free} \ r1)\}$

$s_{\text{mid}} = \{(\text{robot\_at} \ r1 \ wp2), (\text{connected} \ wp1 \ wp2)\}$

2단계 - 추가: $s' = s_{\text{mid}} \cup \{(\text{holding} \ r1 \ box1)\}$

$s' = \{(\text{robot\_at} \ r1 \ wp2), (\text{connected} \ wp1 \ wp2), (\text{holding} \ r1 \ box1)\}$

3. 조건부 효과가 있는 상태 전이

조건부 효과가 포함된 경우, 가드 조건의 평가 단계가 추가된다:

1단계: 가드 조건 평가

현재 상태 $s$ 에서 각 조건부 효과의 가드 조건을 평가하여 활성화되는 조건부 효과를 결정한다.

2단계: 활성 효과 수집

무조건적 효과와 활성화된 조건부 효과를 합산한다:

$\text{eff}^+(a, s) = \text{eff}^+_{\text{unc}}(a) \cup \bigcup_{\{j \mid s \models c_j\}} \text{eff}^+_j(a)$

$\text{eff}^-(a, s) = \text{eff}^-_{\text{unc}}(a) \cup \bigcup_{\{j \mid s \models c_j\}} \text{eff}^-_j(a)$

3단계: 상태 전이 적용

$s' = (s \setminus \text{eff}^-(a, s)) \cup \text{eff}^+(a, s)$

4. 계획의 상태 전이 시퀀스

계획 $\pi = \langle a_1, a_2, \ldots, a_n \rangle$ 의 실행에 의한 상태 시퀀스는 재귀적으로 정의된다:

$s_0 \text{ (초기 상태)}$

$s_i = \gamma(s_{i-1}, a_i) \quad \text{for } i = 1, 2, \ldots, n$

계획이 정당(valid)하려면 두 조건이 충족되어야 한다:

적용 가능성: 모든 $i$ 에 대해 $s_{i-1} \models \text{pre}(a_i)$
목표 달성: $s_n \models g$ (여기서 $g$ 는 목표 조건)

5. 상태 전이의 계산 복잡도

효과 유형	전이 계산 복잡도	비고
STRIPS (무조건적)	$O(k)$	$k$ : 효과 리터럴 수
조건부 효과	$O(k + \sum_j \lvert c_j \rvert)$	$c_j$ : 가드 조건 크기
양화 조건부 효과	$O(m \cdot k_c)$	$m$ : 객체 수, $k_c$ : 조건 크기

6. 상태 표현과 전이 효율

상태의 내부 표현 방식에 따라 전이 계산의 효율성이 달라진다.

6.1 집합 기반 표현

상태를 술어 인스턴스의 해시 집합으로 표현하면, 추가와 삭제가 각각 $O(1)$ 평균 시간에 수행된다. 전체 전이 비용은 $O(k)$ 이다.

6.2 비트 벡터 기반 표현

그라운딩 후 모든 술어 인스턴스에 고유 인덱스를 부여하고, 상태를 비트 벡터로 표현하면, 추가와 삭제가 비트 연산으로 수행되어 매우 효율적이다. 상태 비교도 비트 벡터의 동등성 비교로 단순화되어 중복 상태 검출이 빨라진다.

6.3 계층적 표현

대규모 도메인에서는 술어별로 분리된 계층적 자료 구조를 사용하여 특정 술어에 대한 조회와 갱신을 효율화할 수 있다.

7. 상태 전이와 계획 검증

생성된 계획의 정당성을 검증하는 가장 직접적인 방법은 초기 상태에서 계획의 각 액션을 순차적으로 적용하면서 상태 전이를 추적하는 것이다:

VALIDATE(plan, initial_state, goal):
    s ← initial_state
    FOR each action a in plan:
        IF s ⊭ pre(a):
            RETURN "Invalid: precondition not met at step i"
        s ← γ(s, a)
    IF s ⊭ goal:
        RETURN "Invalid: goal not achieved"
    RETURN "Valid"

이 검증의 시간 복잡도는 $O(n \cdot (k_{\text{pre}} + k_{\text{eff}}))$ 이며, 계획의 길이 $n$ 에 선형적이다. 이는 계획 생성의 최악 복잡도(PSPACE-hard)에 비해 극히 낮으므로, 생성된 계획의 사후 검증은 항상 실용적으로 수행 가능하다.

8. 참고 문헌

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Fikes, R. E. & Nilsson, N. J. (1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.” Artificial Intelligence, 2(3–4), 189–208.
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.