1316.3 비순환적 탐색 기반 플래닝의 원리

1. 탐색 기반 플래닝의 기본 원리

고전적 플래닝 문제를 해결하는 가장 직접적인 방법은 상태 공간을 그래프로 모델링하고, 초기 상태에서 목표 상태까지의 경로를 탐색(search)하는 것이다. 이 접근에서 각 상태는 그래프의 노드, 각 적용 가능한 액션은 간선에 해당하며, 계획은 초기 노드에서 목표 조건을 만족하는 노드까지의 경로이다.

2. 상태 공간 그래프

상태 공간 그래프 $G = (V, E)$ 는 다음과 같이 정의된다:

노드 $V = S$ : 가능한 모든 상태의 집합
간선 $E = \{(s, s') \mid \exists a \in A: s \models \text{pre}(a) \wedge s' = \gamma(s, a)\}$ : 상태 전이를 나타내는 유향 간선

이 그래프에서 초기 상태 $s_0$ 에서 목표 조건 $g$ 를 만족하는 상태 $s_g$ 까지의 경로를 찾는 것이 플래닝 문제의 해결이다.

3. 비순환적 탐색의 필요성

상태 공간 그래프에는 순환(cycle)이 존재할 수 있다. 예를 들어, 로봇이 wp1 → wp2 → wp1로 이동하면 원래 상태로 돌아오는 순환이 발생한다. 순환을 처리하지 않으면 탐색이 무한히 반복될 수 있다.

비순환적 탐색(acyclic search)은 이미 방문한 상태를 기록하고 재방문을 차단함으로써 순환을 방지하는 기법이다:

SEARCH(initial_state, goal):
    open ← {initial_state}
    closed ← ∅
    
    WHILE open ≠ ∅:
        s ← SELECT(open)
        IF s ⊨ goal: RETURN path to s
        closed ← closed ∪ {s}
        FOR EACH action a applicable in s:
            s' ← γ(s, a)
            IF s' ∉ closed AND s' ∉ open:
                open ← open ∪ {s'}
    RETURN "No plan found"

closed 집합(닫힌 목록)이 이미 방문한 상태를 추적하여 중복 방문을 방지한다.

4. 탐색 전략의 분류

전략	open 자료 구조	특성
너비 우선 탐색 (BFS)	큐 (FIFO)	최단 계획 보장, 메모리 집약적
깊이 우선 탐색 (DFS)	스택 (LIFO)	메모리 효율적, 최적성 미보장
최선 우선 탐색 (Best-First)	우선순위 큐	휴리스틱 의존, 효율적
A*	우선순위 큐 ( $f = g + h$ )	비용 최적 (허용 가능 $h$ 시)

5. 상태 표현과 중복 검출

중복 상태 검출(duplicate state detection)은 closed 집합에서의 멤버십 검사를 효율적으로 수행하는 데 의존한다:

해시 기반: 상태를 해시 값으로 변환하여 $O(1)$ 평균 시간에 검사. 해시 충돌에 주의
정렬 기반: 상태를 정규화하여 정렬된 자료 구조에 삽입. $O(\log n)$ 검사
비트 벡터: 명제 수준의 상태를 비트 벡터로 표현하여 빠른 비교

6. 메모리 관리

상태 공간이 매우 클 경우(수백만 이상의 노드), closed 집합의 메모리 소비가 문제가 된다. 이를 완화하는 기법:

반복 심화 깊이 우선 탐색 (IDA)*: closed 집합 없이 깊이 제한을 점진적으로 증가시키며 탐색. 메모리 $O(bd)$ ( $b$ : 분기 요인, $d$ : 깊이)
지연 중복 검출: 확장 시점까지 중복 검출을 지연하여 메모리 사용을 줄임
대칭성 제거: 대칭적 상태를 동일한 것으로 간주하여 탐색 공간을 축소

7. 플래닝에의 적용

고전적 플래닝에서 비순환적 탐색의 핵심 요소:

상태 표현: PDDL의 술어 인스턴스 집합 → 비트 벡터 또는 해시 집합
후속 상태 생성: 적용 가능한 모든 액션의 효과를 현재 상태에 적용
목표 검사: 현재 상태가 목표 조건의 모든 리터럴을 포함하는지 확인
경로 추적: 초기 상태에서 목표 상태까지의 액션 시퀀스를 재구성

8. 참고 문헌

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Russell, S. & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. 4th Edition. Pearson.
Bonet, B. & Geffner, H. (2001). “Planning as Heuristic Search.” Artificial Intelligence, 129(1–2), 5–33.