STRIPS 표현 체계의 구조와 원리 (Structure and Principles of the STRIPS Representation)

1. 개요

STRIPS(Stanford Research Institute Problem Solver)는 Fikes와 Nilsson(1971)이 개발한 최초의 형식적 계획 표현 체계로, 현대 AI 플래닝과 PDDL의 이론적 토대이다. 상태를 명제 집합으로, 행동을 전제 조건-추가-삭제 리스트로 표현하는 간결하고 명확한 체계를 제공한다.

2. STRIPS의 구조

2.1 상태 표현

상태 s는 참인 명제(ground atom)의 집합이다.

s = \{p_1, p_2, \ldots, p_k\} \subseteq \mathcal{F}

\mathcal{F}는 모든 가능한 명제의 집합이다. 폐쇄 세계 가정(CWA)��� 의해 s에 포함되지 않은 명제는 거짓이다.

행동 표현

STRIPS 행동 a는 세 구성 요소로 정의된다.

a = \langle \text{Pre}(a), \text{Add}(a), \text{Del}(a) \rangle

2.2 상태 전이 함수

\gamma(s, a) = \begin{cases} (s \setminus \text{Del}(a)) \cup \text{Add}(a) & \text{if } \text{Pre}(a) \subseteq s \\ \text{undefined} & \text{otherwise} \end{cases}

STRIPS의 원리

폐쇄 세계 가정 (CWA)

명시적으로 참으로 선언되지 않은 모든 명제는 거짓으로 간주한다. 이로 인해 상태의 표현이 간결해진다.

프레임 공리 (Frame Axiom)

행동의 효과에 명시적으로 포함되지 않은 명제는 변하지 않는다. STRIPS의 추가/삭제 리스트 구조에 의해 프레임 문제가 자연스럽게 해결된다.

p \in s \wedge p \notin \text{Del}(a) \Rightarrow p \in \gamma(s, a)

2.3 프래그먼트 가정

전제 조건은 양의 명제의 결합(conjunction)으로만 구성된다. 부정, 분리, 양화사는 허용되지 않는다.

3. STRIPS 예시: 로봇 배달

3.1 행동 정의

move(robot, from, to):
  Pre: {at(robot, from), connected(from, to)}
  Add: {at(robot, to)}
  Del: {at(robot, from)}

pick(robot, obj, loc):
  Pre: {at(robot, loc), on(obj, loc), gripper_empty(robot)}
  Add: {holding(robot, obj)}
  Del: {on(obj, loc), gripper_empty(robot)}

place(robot, obj, loc):
  Pre: {at(robot, loc), holding(robot, obj)}
  Add: {on(obj, loc), gripper_empty(robot)}
  Del: {holding(robot, obj)}

3.2 계획 실행 추적

s0 = {at(r, A), on(box, B), gripper_empty(r), connected(A,B), connected(B,C)}

move(r, A, B):
  s1 = {at(r, B), on(box, B), gripper_empty(r), connected(A,B), connected(B,C)}

pick(r, box, B):
  s2 = {at(r, B), holding(r, box), connected(A,B), connected(B,C)}

move(r, B, C):
  s3 = {at(r, C), holding(r, box), connected(A,B), connected(B,C)}

place(r, box, C):
  s4 = {at(r, C), on(box, C), gripper_empty(r), connected(A,B), connected(B,C)}
  → 목표 on(box, C) 달성 ✓

4. STRIPS의 의의

STRIPS는 AI 플래닝의 기본 프레임워크를 확립하여, 이후 ADL, PDDL 등 모든 계획 언어의 기반이 되었다. 그 단순성에도 불구하고, 현대 계획기의 핵심 메커니즘에 여전히 활용되고 있다.

5. 참고 문헌

• Fikes, R., & Nilsson, N. (1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.” Artificial Intelligence, 2(3-4), 189-208.
• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.