1314.16 긍정적 효과와 부정적 효과

1314.16 긍정적 효과와 부정적 효과

1. 긍정적 효과

긍정적 효과(positive effect, add effect)는 액션 실행 후 세계 상태에 새로운 술어 인스턴스를 추가하는 효과이다. 긍정적 효과는 PDDL 효과에서 not 연산자 없이 직접 기술된 술어 리터럴에 해당한다.

:effect (and
    (robot_at ?r ?to)        ;; 긍정적 효과: 새로운 위치 추가
    (visited ?to)             ;; 긍정적 효과: 방문 표시 추가
)

형식적으로, 긍정적 효과 집합 \text{eff}^+(a)는 액션 a 실행 후 상태에 추가되는 술어 인스턴스의 집합이다:

\text{eff}^+(a) = \{(p \ o_1 \ \ldots \ o_n) \mid (p \ o_1 \ \ldots \ o_n) \text{이 효과에 긍정적으로 명시됨}\}

상태 전이에서 긍정적 효과의 적용은 집합 합집합(union) 연산에 해당한다:

s' \supseteq s \cup \text{eff}^+(a)

2. 부정적 효과

부정적 효과(negative effect, delete effect)는 액션 실행 후 세계 상태에서 기존의 술어 인스턴스를 제거하는 효과이다. not 연산자로 감싸진 술어 리터럴로 표현된다.

:effect (and
    (not (robot_at ?r ?from))    ;; 부정적 효과: 이전 위치 삭제
    (not (gripper_free ?r))      ;; 부정적 효과: 그리퍼 가용성 삭제
)

형식적으로, 부정적 효과 집합 \text{eff}^-(a)는 액션 a 실행 후 상태에서 제거되는 술어 인스턴스의 집합이다:

\text{eff}^-(a) = \{(p \ o_1 \ \ldots \ o_n) \mid (\text{not} \ (p \ o_1 \ \ldots \ o_n)) \text{이 효과에 명시됨}\}

상태 전이에서 부정적 효과의 적용은 집합 차집합(set difference) 연산에 해당한다:

s' \subseteq s \setminus \text{eff}^-(a)

3. 상태 전이에서의 적용 순서

STRIPS 의미론에서 긍정적 효과와 부정적 효과의 적용 순서가 중요하다. 표준적 정의에 따르면:

s' = (s \setminus \text{eff}^-(a)) \cup \text{eff}^+(a)

삭제가 먼저 적용되고 추가가 그 다음에 적용된다. 이 순서의 실질적 의미는, 동일한 술어 인스턴스가 삭제 효과와 추가 효과에 동시에 나타나는 경우에 드러난다:

;; 동일 술어가 삭제와 추가 모두에 포함
:effect (and
    (not (status ?r idle))
    (status ?r idle)       ;; 삭제 후 다시 추가됨
)

이 경우, 먼저 (status ?r idle)이 삭제된 후 다시 추가되므로, 결과적으로 해당 술어는 상태에 존재하게 된다. 실무적으로 이러한 상황은 도메인 설계 오류의 징후일 수 있으므로 주의가 필요하다.

4. 긍정적 효과와 부정적 효과의 조합 패턴

로봇 도메인에서 긍정적 효과와 부정적 효과는 일반적으로 쌍을 이루어 나타난다. 이는 물리적 세계에서의 상태 변화가 통상적으로 “이전 상태의 해제“와 “새로운 상태의 설정“을 동시에 수반하기 때문이다.

4.1 위치 변경 패턴

:effect (and
    (not (robot_at ?r ?from))    ;; 이전 위치 해제
    (robot_at ?r ?to)             ;; 새로운 위치 설정
)

4.2 소유권 이전 패턴

:effect (and
    (not (object_at ?obj ?loc))   ;; 물체의 이전 위치 해제
    (holding ?r ?obj)             ;; 파지 상태 설정
    (not (gripper_free ?r))       ;; 그리퍼 가용성 해제
)

4.3 상태 전환 패턴

:effect (and
    (not (robot_idle ?r))          ;; 이전 상태 해제
    (robot_active ?r)              ;; 새로운 상태 설정
    (task_in_progress ?t)          ;; 태스크 상태 변경
)

4.4 누적적 효과 패턴

일부 효과는 이전 상태를 삭제하지 않고 새로운 정보만을 추가한다. 이는 비가역적(irreversible) 행동이나 정보 축적 행동에서 나타난다:

;; 방문 기록: 삭제 없이 추가만 수행
:effect (visited ?loc)

;; 데이터 수집: 기존 데이터를 유지하면서 새 데이터 추가
:effect (and
    (data_collected ?r ?sensor ?loc)
    (has_data ?r)
)

5. 효과의 일관성 검증

5.1 상호 배타적 술어의 관리

상호 배타적(mutually exclusive)인 술어 쌍(예: robot_idle과 robot_active)에 대해, 하나를 추가할 때 다른 하나를 반드시 삭제해야 한다:

;; 올바른 상호 배타 관리
:effect (and
    (not (robot_idle ?r))
    (robot_active ?r)
)

;; 오류: 삭제 누락으로 모순적 상태 발생
:effect (robot_active ?r)
;; 결과: robot_idle과 robot_active가 동시에 참

5.2 단일 값 술어의 관리

로봇의 위치처럼 특정 시점에 하나의 값만 가져야 하는 술어에 대해, 이전 값의 삭제를 보장해야 한다:

;; 올바른 단일 값 관리
:effect (and
    (not (robot_at ?r ?from))
    (robot_at ?r ?to)
)

PDDL은 단일 값 제약(single-valuedness constraint)을 구문적으로 강제하지 않으므로, 도메인 설계자가 효과의 삭제 부분을 통해 수동으로 관리해야 한다.

6. 삭제 효과와 플래닝 복잡도

삭제 효과의 존재는 플래닝의 계산 복잡도에 근본적인 영향을 미친다. 삭제 효과가 없는 플래닝 문제(단조 플래닝, monotone planning)는 계산적으로 상대적으로 용이하다. 술어가 한번 참이 되면 영원히 참으로 유지되므로, 상태 공간의 크기가 제한된다.

반면, 삭제 효과가 존재하는 일반적인 플래닝 문제에서는 동일한 술어가 반복적으로 추가되고 삭제될 수 있어, 상태 공간의 크기가 기하급수적으로 증가할 수 있다. 이는 STRIPS 플래닝이 PSPACE-완전(PSPACE-complete)인 이유 중 하나이다(Bylander, 1994).

삭제 완화 휴리스틱(delete relaxation heuristic)은 이러한 삭제 효과를 무시함으로써 완화된 문제에서의 비용을 효율적으로 추정한다. 완화된 문제에서는 모든 효과가 긍정적이므로 상태가 단조적으로 확장되며, 목표 달성 비용의 하한(lower bound)을 제공한다.

7. 로봇 도메인에서의 효과 설계 지침

  1. 물리적 상태 변화를 완전히 반영하라. 액션의 물리적 결과에 해당하는 모든 상태 변화를 효과에 포함해야 한다. 누락된 효과는 후속 액션의 전제 조건과의 불일치를 초래한다.

  2. 삭제 효과의 누락에 주의하라. 긍정적 효과의 추가는 직관적이지만, 부정적 효과(이전 상태의 해제)는 간과되기 쉽다. 각 긍정적 효과에 대해 “이전 상태는 여전히 유효한가?“를 점검해야 한다.

  3. 상호 배타적 술어의 일관성을 보장하라. 한 술어를 참으로 만들 때, 논리적으로 모순되는 다른 술어를 반드시 거짓으로 만들어야 한다.

  4. 불필요한 효과를 포함하지 말라. 실제로 변경되지 않는 상태 요소를 효과에 포함하면, 프레임 가정에 의해 자동으로 보존되는 정보를 불필요하게 재설정하는 결과를 초래한다.

8. 참고 문헌

  • 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.
  • Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.