1314.26 액션의 적용 가능성 판단

1. 적용 가능성의 형식적 정의

액션의 적용 가능성(applicability)은 특정 상태에서 해당 액션을 실행할 수 있는지 여부를 결정하는 기준이다. 그라운드 액션 $a$ 가 상태 $s$ 에서 적용 가능하려면, $a$ 의 전제 조건이 $s$ 에서 참이어야 한다:

$\text{applicable}(a, s) \iff s \models \text{pre}(a)$

적용 불가능한 상태에서 액션을 적용하는 것은 정의되지 않으며(undefined), 플래너는 적용 가능한 액션만을 탐색 후보로 고려한다.

2. STRIPS 수준의 적용 가능성 판정

STRIPS 의미론에서 전제 조건이 긍정적 리터럴의 접합으로 제한되는 경우, 적용 가능성 판정은 집합 포함(subset) 검사로 단순화된다:

$\text{applicable}(a, s) \iff \text{pre}^+(a) \subseteq s$

여기서 $\text{pre}^+(a)$ 는 전제 조건의 긍정적 리터럴 집합이다. 해시 집합(hash set) 기반 상태 표현에서 이 검사의 시간 복잡도는 $O(k)$ 이다. 여기서 $k$ 는 전제 조건의 리터럴 수이다.

3. ADL 수준의 적용 가능성 판정

ADL 확장에서 전제 조건이 부정, 선언, 양화 등의 복합 논리식을 포함하는 경우, 적용 가능성 판정은 재귀적 논리식 평가로 수행된다:

$s \models (\text{and} \ \phi_1 \ \ldots \ \phi_n) \iff \forall i: s \models \phi_i$

$s \models (\text{or} \ \phi_1 \ \ldots \ \phi_n) \iff \exists i: s \models \phi_i$

$s \models (\text{not} \ \phi) \iff s \not\models \phi$

$s \models (\text{forall} \ (?x - T) \ \phi) \iff \forall o \in \text{objects}(T): s \models \phi[?x/o]$

$s \models (\text{exists} \ (?x - T) \ \phi) \iff \exists o \in \text{objects}(T): s \models \phi[?x/o]$

양화사의 존재로 인해 최악의 경우 평가 비용이 다항식 이상으로 증가할 수 있으나, 실제 도메인에서 양화사의 사용이 제한적이므로 실용적 성능은 대부분 허용 가능한 수준이다.

4. 적용 가능 액션의 열거

전방 탐색에서 플래너는 각 상태에서 적용 가능한 모든 그라운드 액션을 열거해야 한다. 이 과정은 다음의 단계로 수행된다:

1단계: 그라운드 액션 후보 생성

각 액션 스키마에 대해 타입 호환 바인딩을 열거하여 그라운드 액션 후보 집합을 생성한다.

2단계: 전제 조건 평가

각 후보에 대해 전제 조건을 현재 상태에서 평가하고, 참인 경우만 적용 가능 집합에 포함한다:

$\text{applicable}(s) = \{a \in \mathcal{A}_{\text{ground}} \mid s \models \text{pre}(a)\}$

3단계: 최적화

도달 가능성 분석, 상호 배제(mutex) 정보, 인덱싱 등을 활용하여 후보 집합을 사전에 축소한다.

5. 적용 가능성 판정의 최적화 기법

5.1 술어 인덱싱

상태를 술어별로 인덱싱하여, 특정 전제 조건 리터럴을 만족하는 그라운드 액션을 빠르게 조회할 수 있다:

인덱스 구조:
  robot_at(robot1, wp1) → {move(robot1, wp1, wp2), move(robot1, wp1, wp3),
                            pick_up(robot1, *, wp1), ...}

5.2 조기 종료

접합적 전제 조건에서 하나의 리터럴이라도 거짓이면 전체가 거짓이므로, 첫 번째 거짓 리터럴 발견 시 즉시 판정을 종료할 수 있다(단락 평가, short-circuit evaluation).

5.3 증분 평가

상태 전이 시 변경된 술어만을 기반으로 적용 가능성의 변화를 추적한다. 이전 상태에서 적용 가능했던 액션 중, 변경된 술어에 의존하지 않는 액션은 재평가 없이 적용 가능 상태를 유지한다.

6. 적용 가능성과 탐색 분기 요인

적용 가능 액션의 수는 탐색의 분기 요인(branching factor) $b$ 를 결정한다. 분기 요인은 상태에 따라 달라지며, 이는 플래닝 복잡도에 직접적인 영향을 미친다:

$b(s) = |\text{applicable}(s)|$

분기 요인이 높으면 탐색 공간이 기하급수적으로 확장된다. 깊이 $d$ 의 탐색에서 확장되는 노드 수는 $O(b^d)$ 이다. 따라서 전제 조건의 적절한 설계를 통해 각 상태에서의 분기 요인을 관리하는 것이 중요하다.

전제 조건이 지나치게 약하면 분기 요인이 높아져 탐색이 비효율적이고, 전제 조건이 지나치게 강하면 분기 요인이 낮아져 유효한 계획을 찾지 못할 수 있다.

7. 로봇 도메인에서의 적용 가능성 분석 예시

다음의 상태에서 적용 가능한 액션을 분석한다:

;; 현재 상태
s = {(robot_at r1 wp1), (object_at box1 wp2), (connected wp1 wp2),
     (connected wp2 wp3), (gripper_free r1)}

;; 도메인 액션
(:action move :parameters (?r - robot ?from ?to - waypoint)
    :precondition (and (robot_at ?r ?from) (connected ?from ?to)))

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

적용 가능한 그라운드 액션:

(move r1 wp1 wp2) — robot_at(r1, wp1) ∈ s, connected(wp1, wp2) ∈ s → 적용 가능
(move r1 wp2 wp3) — robot_at(r1, wp2) ∉ s → 적용 불가
(pick_up r1 box1 wp1) — object_at(box1, wp1) ∉ s → 적용 불가
(pick_up r1 box1 wp2) — robot_at(r1, wp2) ∉ s → 적용 불가

이 상태에서 유일한 적용 가능 액션은 (move r1 wp1 wp2)이다. 분기 요인은 1이므로, 플래너는 이 액션을 선택할 수밖에 없다.

8. 참고 문헌

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
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.