상태 공간과 행동 공간의 모델링 (Modeling State Space and Action Space)

1. 개요

상태 공간(state space)과 행동 공간(action space)의 모델링은 자율 계획 시스템의 기반이다. 상태 공간은 로봇과 환경의 가능한 모든 상태를 표현하며, 행동 공간은 로봇이 수행할 수 있는 모든 행동을 정의한다. 이 두 공간의 형식적 정의에 의해 계획기가 유효한 행동 시퀀스를 탐색할 수 있다.

2. 상태 공간의 모델링

2.1 명제적 표현 (Propositional Representation)

상태를 참/거짓 값을 가지는 명제(proposition)의 집합으로 표현한다.

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

여기서 \mathcal{F}는 모든 가능한 명제(fluent)의 집합이며, s에 포함된 명제는 참이고 포함되지 않은 명제는 거짓이다.

술어 기반 표현

PDDL에서는 술어(predicate)와 객체(object)의 인스턴스화(grounding)를 통해 상태를 표현한다.

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

상태: {at(robot1, room_A), on(box1, room_B)}

상태 공간의 크기

n개의 명제가 있을 때 상태 공간의 크기는 |S| = 2^n이다. 실제 시스템에서는 술어와 객체의 조합에 의해 명제 수가 결정된다.

실제 탐색에서는 도달 가능한(reachable) 상태만을 고려하므로, 유효 상태 공간은 이론적 최대보다 훨씬 작다.

행동 공간의 모델링

행동의 형식적 정의

행동 a는 다음으로 구성된다.

a = \langle \text{name}, \text{params}, \text{pre}(a), \text{eff}^+(a), \text{eff}^-(a) \rangle

2.2 행동의 인스턴스화

스키마(schema) 수준의 행동이 구체적 객체와 결합하면 인스턴스화된 행동(grounded action)이 된다.

스키마: move(?robot, ?from, ?to)
인스턴스: move(robot1, room_A, room_B)

2.3 행동 공간의 크기

m개의 행동 스키마에 대해, 각 매개변수에 대입 가능한 객체의 조합 수가 행동 공간의 크기를 결정한다. m개 스키마, 평균 k개 매개변수, o개 객체에서:

|A_{\text{grounded}}| \approx m \times o^k

PDDL에서의 상태-행동 모델링 예시

(define (domain delivery)
  (:types robot location object)
  (:predicates
    (at ?r - robot ?l - location)
    (holding ?r - robot ?o - object)
    (on ?o - object ?l - location)
    (connected ?l1 ?l2 - location))

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

  (:action pick
    :parameters (?r - robot ?o - object ?l - location)
    :precondition (and (at ?r ?l) (on ?o ?l))
    :effect (and (holding ?r ?o) (not (on ?o ?l))))

  (:action place
    :parameters (?r - robot ?o - object ?l - location)
    :precondition (and (at ?r ?l) (holding ?r ?o))
    :effect (and (on ?o ?l) (not (holding ?r ?o)))))

참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. Pearson.