1316.12 회귀 계획과 관련 상태 집합 탐색

1. 회귀의 형식적 정의

회귀(regression)는 목표 조건 집합에서 역방향으로 액션을 적용하여, 해당 액션 실행 전에 성립해야 하는 선행 조건 집합을 도출하는 연산이다. 형식적으로, 목표 조건 집합 $g$ 와 액션 $a$ 에 대한 회귀는 다음과 같이 정의된다(Ghallab, Nau, & Traverso, 2004):

$\text{regress}(g, a) = (\text{pre}(a) \cup (g \setminus \text{eff}^+(a))) \setminus \text{eff}^-(a)$

이 정의의 직관적 의미:

$g \setminus \text{eff}^+(a)$ : 목표 중 액션의 추가 효과로 달성되는 부분을 제거한다(이 부분은 액션이 제공하므로 사전에 필요하지 않다).
$\text{pre}(a) \cup \ldots$ : 액션의 전제 조건을 추가한다(액션이 실행되려면 전제 조건이 먼저 성립해야 한다).
$\ldots \setminus \text{eff}^-(a)$ : 삭제 효과에 해당하는 리터럴을 제거한다.

2. 관련성과 일관성 조건

회귀가 유효하려면 액션이 목표에 대해 관련성과 일관성을 가져야 한다.

2.1 관련성(Relevance)

액션 $a$ 가 목표 $g$ 에 관련되려면, $a$ 의 추가 효과가 $g$ 의 일부 리터럴을 달성해야 한다:

$\text{relevant}(a, g) \iff \text{eff}^+(a) \cap g \neq \emptyset$

관련성이 없는 액션은 목표 달성에 기여하지 않으므로 탐색에서 제외된다.

2.2 일관성(Consistency)

액션 $a$ 의 삭제 효과가 목표 $g$ 의 다른 리터럴을 파괴하지 않아야 한다:

$\text{consistent}(a, g) \iff \text{eff}^-(a) \cap (g \setminus \text{eff}^+(a)) = \emptyset$

일관성이 없으면 액션 적용 후 목표의 일부가 파괴되므로, 해당 회귀는 무효하다.

3. 관련 상태 집합 탐색

후방 탐색에서 각 탐색 노드는 완전한 상태가 아닌 관련 상태 집합(relevant state set)을 나타낸다. 관련 상태 집합은 목표 달성에 필요한 조건들의 접합이며, 해당 조건을 만족하는 모든 상태의 집합을 암묵적으로 표현한다.

$\text{StateSet}(g) = \{s \in S \mid g \subseteq s\}$

탐색은 $\text{StateSet}(g_{\text{goal}})$ 에서 시작하여, 회귀를 통해 $\text{StateSet}(\text{regress}(g, a))$ 로 확장되며, $s_0 \in \text{StateSet}(g')$ 인 조건 집합 $g'$ 에 도달하면 계획이 발견된다.

4. 회귀 계획의 예시

도메인:

(:action move :parameters (?r - robot ?from ?to - waypoint)
    :precondition (and (robot_at ?r ?from) (connected ?from ?to))
    :effect (and (not (robot_at ?r ?from)) (robot_at ?r ?to)))

(:action pick :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))))

목표: $g = \{(\text{holding} \ r1 \ box1)\}$

회귀 단계 1: pick 액션으로 회귀

관련성: $\text{eff}^+(\text{pick}) \cap g = \{(\text{holding} \ r1 \ box1)\} \neq \emptyset$ ✓
회귀 결과: $g_1 = \{(\text{robot\_at} \ r1 \ ?loc), (\text{object\_at} \ box1 \ ?loc), (\text{gripper\_free} \ r1)\}$

회귀 단계 2: move 액션으로 $(\text{robot\_at} \ r1 \ ?loc)$ 달성

회귀 결과: $g_2 = \{(\text{robot\_at} \ r1 \ ?from), (\text{connected} \ ?from \ ?loc), (\text{object\_at} \ box1 \ ?loc), (\text{gripper\_free} \ r1)\}$

$s_0 \supseteq g_2$ 이면 계획 발견: move(r1, ?from, ?loc), pick(r1, box1, ?loc)

5. 후방 탐색에서의 실용적 과제

5.1 부정 리터럴의 처리

STRIPS 수준에서 목표가 긍정적 리터럴만 포함하면 회귀가 비교적 단순하다. 그러나 부정적 목표나 ADL 확장이 포함되면 회귀 계산이 복잡해진다.

5.2 조건 집합의 일관성 유지

회귀 결과가 상호 모순되는 리터럴을 포함하면(예: $(p)$ 와 $(\text{not} \ p)$ 가 동시에 존재), 해당 노드는 달성 불가능하므로 가지치기해야 한다.

5.3 변수 바인딩의 관리

리프팅된(lifted) 후방 탐색에서 회귀 결과는 미결정 변수를 포함할 수 있다. 이러한 변수의 바인딩은 탐색 과정에서 점진적으로 결정된다.

6. 참고 문헌

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Bonet, B. & Geffner, H. (2001). “Planning as Heuristic Search.” Artificial Intelligence, 129(1–2), 5–33.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.