상태 공간 표현 방법 (State Space Representation Methods)

상태 공간 표현 방법 (State Space Representation Methods)

1. 개요

상태 공간(state space)의 표현 방법은 AI 플래닝에서 세계의 가능한 상태를 어떻게 인코딩할 것인지를 정의하며, 계획기의 효율성과 표현력에 직접적인 영향을 미친다. 명제적 표현, 일차 술어 논리 기반 표현, SAS+ 표현 등 다양한 방법이 존재한다.

2. 명제적 표현 (Propositional Representation)

2.1 원리

상태를 참인 명제(ground atom)의 집합으로 표현한다. 폐쇄 세계 가정(Closed World Assumption)에 의해, 상태에 포함되지 않은 명제는 거짓으로 간주한다.

s = \{at(robot, A), on(box, B), connected(A, B)\}

상태 공간의 크기

n개의 명제가 있을 때 이론적 상태 공간의 크기는 |S| = 2^n이다.

장점과 한계

장점한계
단순하고 직관적상태 공간이 지수적으로 증가
대부분의 계획기가 지원수치적 상태(거리, 속도) 표현 제한
효율적 비트 벡터 인코딩 가능연속 상태 표현 불가

일차 술어 논리 기반 표현 (First-Order Logic Representation)

원리

PDDL에서 사용하는 방식으로, 술어(predicate)와 객체(object)의 인스턴스화를 통해 상태를 표현한다.

술어: at(?robot, ?location), on(?object, ?location)
객체: robot1, room_A, room_B, box1
인스턴스: at(robot1, room_A), on(box1, room_B)

인스턴스화 (Grounding)

일차 술어 논리의 변수를 구체적 객체로 대치하여 명제로 변환한다.

\text{at}(?r, ?l) \xrightarrow{\text{grounding}} \{at(r1, A), at(r1, B), at(r2, A), at(r2, B), \ldots\}

2.2 인스턴스화된 명제의 수

k-인자 술어 p와 o개 객체에서 인스턴스의 수: O(o^k)

3. SAS+ 표현 (SAS+ Representation)

3.1 원리

상태를 다치(multi-valued) 변수의 집합으로 표현한다. 각 변수는 유한한 값 도메인을 가진다.

\text{variable: } v_i \in D_i

예시:

position(robot) ∈ {room_A, room_B, room_C}
holding(robot) ∈ {nothing, box1, box2}
location(box1) ∈ {room_A, room_B, on_robot}

SAS+의 장점

장점설명
상호 배타 자동 처리로봇이 동시에 두 위치에 있을 수 없음이 자연스럽게 표현됨
효율적 휴리스틱인과 그래프(causal graph) 기반 휴리스틱 계산
Fast Downward의 기반현대 최고 성능 계획기의 내부 표현

표현 방법 비교

특성명제적일차 술어 논리SAS+
변수 타입이진이진 (인스턴스화 후)다치
상태 공간2^n2^n\prod \lvert D_i \rvert
상호 배타명시적 처리 필요명시적 처리 필요자동 처리
PDDL 호환간접적직접적변환 필요
대표 계획기GraphplanFF, POPFFast Downward, LAMA

참고 문헌

  • Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
  • Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5-6), 503-535.
버전날짜변경 사항
v0.12026-04-05초안 작성