397.21 STRIPS 계획 형식주의

1. 개요

STRIPS(Stanford Research Institute Problem Solver)는 1971년 Richard Fikes와 Nils Nilsson이 개발한 자동 계획 시스템으로, 인공지능 계획(AI Planning) 분야의 가장 기본적이고 영향력 있는 형식주의(formalism)이다. STRIPS는 로봇의 행동을 전제 조건(preconditions)과 효과(effects)로 표현하는 간결한 표현 체계를 제시하였으며, 이후 개발된 거의 모든 계획 언어와 계획기(planner)의 이론적 기초가 되었다. 로봇 임무 계획 분야에서 STRIPS 형식주의는 고수준 작업의 모델링과 자동 시퀀싱에 필수적인 역할을 수행한다.

2. STRIPS의 역사적 맥락

STRIPS는 원래 Stanford Research Institute(현 SRI International)에서 이동 로봇 Shakey를 위한 계획 시스템으로 개발되었다(Fikes & Nilsson, 1971). Shakey 로봇은 실내 환경에서 물체를 밀고, 방을 이동하며, 조명 스위치를 조작하는 등의 작업을 수행하였다. 이 과정에서 로봇의 행동을 형식적으로 기술하고, 주어진 목표를 달성하기 위한 행동 시퀀스를 자동으로 생성하는 문제가 대두되었다. STRIPS는 이 문제를 해결하기 위해 1차 술어 논리(first-order predicate logic)에 기반한 행동 표현 체계와 수단-목적 분석(means-ends analysis) 기반의 탐색 알고리즘을 결합하였다.

3. STRIPS 문제의 형식적 정의

STRIPS 계획 문제는 다음의 3-튜플(triple)로 정의한다.

\mathcal{P}_{\text{STRIPS}} = \langle \mathcal{F}, \mathcal{O}, I, G \rangle

각 요소의 정의는 다음과 같다.

3.1 유한 명제 집합(Finite Set of Propositions)

\mathcal{F} = \{f_1, f_2, \ldots, f_n\}는 도메인을 기술하는 데 사용되는 유한한 명제(fact) 또는 기저 원자(ground atom)의 집합이다. 각 명제는 세계의 특정 속성을 나타내며, 참(true) 또는 거짓(false)의 진리값을 가진다.

예시:
\mathcal{F} = \{ \text{at}(\text{robot}, \text{room1}),\ \text{at}(\text{robot}, \text{room2}),\ \text{door\_open}(\text{d1}),\ \text{holding}(\text{box1}) \}

3.2 연산자 집합(Set of Operators)

\mathcal{O} = \{o_1, o_2, \ldots, o_m\}는 에이전트가 수행할 수 있는 행동을 기술하는 연산자(operator)의 집합이다. 각 연산자는 다음의 3-튜플로 정의한다.

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

• \text{Pre}(o) \subseteq \mathcal{F}: **전제 조건(preconditions)**으로, 연산자 o를 적용하기 위해 현재 상태에서 참이어야 하는 명제들의 집합이다.
• \text{Add}(o) \subseteq \mathcal{F}: **추가 목록(add list)**으로, 연산자 o의 실행 결과로 참이 되는 명제들의 집합이다.
• \text{Del}(o) \subseteq \mathcal{F}: **삭제 목록(delete list)**으로, 연산자 o의 실행 결과로 거짓이 되는 명제들의 집합이다.

3.3 초기 상태(Initial State)

I \subseteq \mathcal{F}는 계획 수립 시점에서 참인 명제들의 집합으로 표현한 초기 상태이다. **닫힌 세계 가정(Closed-World Assumption, CWA)**에 의해 I에 포함되지 않은 모든 명제는 거짓으로 간주한다.

3.4 목표 조건(Goal Condition)

G \subseteq \mathcal{F}는 달성하고자 하는 목표 조건을 나타내는 명제들의 집합이다. 모든 g \in G가 현재 상태에서 참이 되면 목표가 달성된 것으로 판정한다.

4. STRIPS 연산자의 적용 규칙

4.1 적용 가능성(Applicability)

연산자 o가 상태 s에서 적용 가능하기 위한 필요충분조건은 전제 조건이 현재 상태의 부분집합인 것이다.

o \text{는 상태 } s \text{에서 적용 가능} \iff \text{Pre}(o) \subseteq s

4.2 상태 전이 함수(State Transition Function)

연산자 o가 상태 s에서 적용 가능할 때, 결과 상태 s'는 다음과 같이 계산한다.

s' = \gamma(s, o) = (s \setminus \text{Del}(o)) \cup \text{Add}(o)

이 전이 규칙의 핵심은 다음과 같다.

1. 먼저 현재 상태 s에서 삭제 목록 \text{Del}(o)에 속하는 명제들을 제거한다.
2. 이후 추가 목록 \text{Add}(o)에 속하는 명제들을 추가한다.

삭제와 추가의 적용 순서가 중요하며, 동일한 명제가 추가 목록과 삭제 목록에 동시에 존재할 경우 해당 명제는 결과 상태에서 참이 된다. 이는 추가 연산이 삭제 연산 이후에 적용되기 때문이다.

5. STRIPS 연산자 정의 예시

5.1 로봇 이동 연산자

로봇이 위치 l_1에서 위치 l_2로 이동하는 연산자를 다음과 같이 정의한다.

\text{move}(l_1, l_2) = \langle \{ \text{at}(\text{robot}, l_1),\ \text{connected}(l_1, l_2) \},\ \{ \text{at}(\text{robot}, l_2) \},\ \{ \text{at}(\text{robot}, l_1) \} \rangle

• 전제 조건: 로봇이 l_1에 있고, l_1과 l_2가 연결되어 있어야 한다.
• 추가 효과: 로봇이 l_2에 위치하게 된다.
• 삭제 효과: 로봇이 l_1에 있다는 사실이 제거된다.

5.2 물체 집기 연산자

\text{pick\_up}(x, l) = \langle \{ \text{at}(\text{robot}, l),\ \text{at}(x, l),\ \text{gripper\_empty} \},\ \{ \text{holding}(x) \},\ \{ \text{at}(x, l),\ \text{gripper\_empty} \} \rangle

• 전제 조건: 로봇과 물체 x가 동일한 위치 l에 있고, 그리퍼가 비어 있어야 한다.
• 추가 효과: 로봇이 물체 x를 잡고 있게 된다.
• 삭제 효과: 물체의 위치 정보와 그리퍼의 빈 상태가 제거된다.

5.3 물체 내려놓기 연산자

\text{put\_down}(x, l) = \langle \{ \text{holding}(x),\ \text{at}(\text{robot}, l) \},\ \{ \text{at}(x, l),\ \text{gripper\_empty} \},\ \{ \text{holding}(x) \} \rangle

6. STRIPS 계획 문제의 풀이 과정

6.1 문제 설정 예시

다음과 같은 간단한 STRIPS 문제를 고려하자.

명제 집합:
\mathcal{F} = \{ \text{at}(\text{robot}, A),\ \text{at}(\text{robot}, B),\ \text{at}(\text{box}, A),\ \text{at}(\text{box}, B),\ \text{holding}(\text{box}),\ \text{gripper\_empty},\ \text{connected}(A, B),\ \text{connected}(B, A) \}

초기 상태:
I = \{ \text{at}(\text{robot}, A),\ \text{at}(\text{box}, A),\ \text{gripper\_empty},\ \text{connected}(A, B),\ \text{connected}(B, A) \}

목표 조건:
G = \{ \text{at}(\text{box}, B) \}

6.2 계획 도출

이 문제의 해는 다음의 행동 시퀀스이다.

\pi = \langle \text{pick\_up}(\text{box}, A),\ \text{move}(A, B),\ \text{put\_down}(\text{box}, B) \rangle

각 단계에서의 상태 변화를 추적하면 다음과 같다.

단계 1: \text{pick\_up}(\text{box}, A) 적용

s_1 = (I \setminus \{ \text{at}(\text{box}, A),\ \text{gripper\_empty} \}) \cup \{ \text{holding}(\text{box}) \}

s_1 = \{ \text{at}(\text{robot}, A),\ \text{holding}(\text{box}),\ \text{connected}(A, B),\ \text{connected}(B, A) \}

단계 2: \text{move}(A, B) 적용

s_2 = (s_1 \setminus \{ \text{at}(\text{robot}, A) \}) \cup \{ \text{at}(\text{robot}, B) \}

s_2 = \{ \text{at}(\text{robot}, B),\ \text{holding}(\text{box}),\ \text{connected}(A, B),\ \text{connected}(B, A) \}

단계 3: \text{put\_down}(\text{box}, B) 적용

s_3 = (s_2 \setminus \{ \text{holding}(\text{box}) \}) \cup \{ \text{at}(\text{box}, B),\ \text{gripper\_empty} \}

s_3 = \{ \text{at}(\text{robot}, B),\ \text{at}(\text{box}, B),\ \text{gripper\_empty},\ \text{connected}(A, B),\ \text{connected}(B, A) \}

G = \{ \text{at}(\text{box}, B) \} \subseteq s_3이므로 목표가 달성되었다.

7. STRIPS의 탐색 알고리즘

7.1 수단-목적 분석(Means-Ends Analysis)

원래의 STRIPS 시스템은 **수단-목적 분석(means-ends analysis)**에 기반한 탐색을 수행하였다. 이 기법은 현재 상태와 목표 상태 간의 차이(difference)를 식별하고, 그 차이를 줄이는 데 적합한 연산자를 선택하는 방식으로 동작한다.

수단-목적 분석의 절차는 다음과 같다.

1. 현재 상태 s와 목표 G를 비교하여 미달성 목표 명제 g \in G \setminus s를 식별한다.
2. g를 추가 목록에 포함하는 연산자 o (즉, g \in \text{Add}(o))를 선택한다.
3. o의 전제 조건 \text{Pre}(o)가 현재 상태에서 충족되지 않으면, \text{Pre}(o)를 하위 목표(subgoal)로 설정하고 재귀적으로 계획을 수립한다.
4. o를 적용하여 상태를 갱신하고, 나머지 미달성 목표에 대해 과정을 반복한다.

7.2 수단-목적 분석의 한계

수단-목적 분석은 **수지키 이상(Sussman Anomaly)**에 취약한 것으로 잘 알려져 있다. 이 문제는 블록 세계(blocks world)에서 발생하는 대표적인 예로, 두 개의 하위 목표가 상호 간섭(interference)을 일으키는 상황이다.

예를 들어, 블록 A를 B 위에 놓고, 블록 B를 C 위에 놓아야 하는 목표가 있을 때, 하위 목표를 독립적으로 해결하면 하나의 하위 목표를 달성하는 과정에서 다른 하위 목표가 파괴될 수 있다. 이 문제는 하위 목표 간의 상호 작용을 고려하지 않는 단순한 수단-목적 분석의 근본적 한계를 보여 준다.

8. 리프팅된 STRIPS(Lifted STRIPS)

기본 STRIPS 형식주의에서 연산자는 기저(ground) 수준으로 정의되어 모든 변수에 구체적인 값이 대입된 형태이다. 그러나 실제 계획 문제에서는 연산자를 리프팅된(lifted) 형태, 즉 변수를 포함하는 연산자 스키마(operator schema)로 정의하는 것이 일반적이다.

리프팅된 연산자 스키마는 다음과 같이 정의한다.

o(\vec{x}) = \langle \text{Pre}(o, \vec{x}),\ \text{Add}(o, \vec{x}),\ \text{Del}(o, \vec{x}) \rangle

여기서 \vec{x} = (x_1, x_2, \ldots, x_k)는 연산자의 매개변수(parameter)이다.

예를 들어, 리프팅된 이동 연산자는 다음과 같다.

\text{move}(?from, ?to) = \langle \{ \text{at}(\text{robot}, ?from),\ \text{connected}(?from, ?to) \},\ \{ \text{at}(\text{robot}, ?to) \},\ \{ \text{at}(\text{robot}, ?from) \} \rangle

이 연산자 스키마는 구체적인 위치 값을 대입(grounding)함으로써 기저 연산자 인스턴스를 생성한다. 리프팅된 표현은 도메인 기술의 간결성과 일반성을 크게 향상시키며, 현대 계획 언어인 PDDL의 기반이 된다.

9. STRIPS의 표현적 한계

STRIPS 형식주의는 그 간결성으로 인해 다음과 같은 표현적 한계를 갖는다.

9.1 조건부 효과의 부재

STRIPS 연산자의 효과는 무조건적(unconditional)이다. 즉, 연산자가 적용되면 추가 목록과 삭제 목록이 전제 조건과 관계없이 일괄적으로 적용된다. 조건부 효과(conditional effects), 즉 “전제 조건 c가 참이면 효과 e를 적용한다“와 같은 표현은 기본 STRIPS에서 지원되지 않는다.

이를 표현하기 위해서는 조건의 각 경우에 대해 별도의 연산자를 정의하여야 한다. 이는 연산자의 수가 조건의 조합에 비례하여 지수적으로 증가하는 문제를 야기한다.

9.2 수치적 속성의 부재

STRIPS는 명제적(propositional) 표현만을 지원하며, 수치적 상태 변수(numeric state variable)를 직접 표현할 수 없다. 예를 들어, 배터리 잔량 \text{battery} = 75와 같은 연속적 수치 정보는 STRIPS 명제로 자연스럽게 표현되지 않는다.

9.3 시간적 정보의 부재

행동의 수행 소요 시간, 동시 실행, 마감 기한 등의 시간적 속성은 STRIPS에서 모델링할 수 없다. 모든 행동은 즉각적이고 순차적으로 실행되는 것으로 가정한다.

9.4 불확실성의 미지원

STRIPS의 상태 전이 함수는 결정론적이다. 행동의 결과가 확률적이거나, 관측이 불완전한 상황은 표현할 수 없다.

10. ADL(Action Description Language)에 의한 확장

Pednault(1989)가 제안한 **ADL(Action Description Language)**은 STRIPS의 표현적 한계를 극복하기 위한 확장이다. ADL은 다음과 같은 추가 기능을 제공한다.

ADL의 조건부 효과는 다음과 같이 표현한다.

\text{when } c: e^+, e^-

이는 조건 c가 현재 상태에서 참일 때에만 효과 e^+(추가)와 e^-(삭제)가 적용됨을 의미한다.

11. STRIPS에서 PDDL로의 발전

STRIPS 형식주의는 이후 PDDL(Planning Domain Definition Language)(McDermott, 1998)의 기초가 되었다. PDDL 1.0은 STRIPS와 ADL의 표현력을 통합하고, 표준화된 문법을 제공하여 다양한 계획기 간의 호환성을 보장하였다. PDDL의 후속 버전들(PDDL 2.1, PDDL 3.0 등)은 수치적 유창어(numeric fluent), 시간 계획(temporal planning), 선호도(preferences) 등으로 표현력을 지속적으로 확장하였다.

STRIPS의 핵심 구조인 전제 조건-추가 목록-삭제 목록의 3-튜플 표현은 PDDL의 :precondition, :effect 절에 직접 반영되어 있으며, 현대 로봇 임무 계획 시스템에서도 여전히 기본적인 행동 모델링 패러다임으로 활용되고 있다.

12. 로봇 임무 계획에서의 STRIPS의 의의

STRIPS 형식주의는 로봇 임무 계획 분야에서 다음과 같은 핵심적 의의를 갖는다.

도메인 독립적 계획의 기반: STRIPS의 형식적 프레임워크는 특정 도메인에 종속되지 않는 범용적 계획기의 개발을 가능하게 하였다. 도메인 정보를 연산자 집합으로 분리하여 기술함으로써, 동일한 계획 알고리즘을 다양한 로봇 응용에 적용할 수 있다.

계산적 분석의 토대: STRIPS 문제의 계산 복잡도 분석(Bylander, 1994)은 계획 문제의 이론적 난이도를 이해하는 기초를 제공하였으며, 효율적인 휴리스틱 설계의 출발점이 되었다.

표준화된 벤치마크: STRIPS와 그 확장에 기반한 표준 벤치마크 도메인(예: Blocksworld, Logistics, Gripper 등)은 계획 알고리즘의 성능 비교와 평가를 위한 공통 기반을 제공하여 왔다.

13. 참고 문헌

• 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.
• Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” Artificial Intelligence, 69(1-2), 165–204.
• Pednault, E. P. D. (1989). “ADL: Exploring the Middle Ground Between STRIPS and the Situation Calculus.” Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning (KR-89), 324–332.
• McDermott, D. (1998). “PDDL—The Planning Domain Definition Language.” Technical Report CVC TR-98-003, Yale Center for Computational Vision and Control.
• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• Russell, S. J., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.

v0.1.0