397.19 결정론적 임무 계획(Deterministic Mission Planning) 기법

1. 결정론적 임무 계획의 정의

결정론적 임무 계획(Deterministic Mission Planning)은 환경과 행동의 결과가 완전히 알려져 있고 예측 가능한 상황에서, 초기 상태로부터 목표 상태에 도달하는 행동 시퀀스(action sequence)를 결정하는 계획 패러다임이다. 결정론적 계획에서는 각 행동의 효과가 유일하게 결정되므로, 확률적 불확실성이나 비결정론적 분기를 고려할 필요가 없다 (Ghallab, Nau, & Traverso, 2004).

결정론적 임무 계획의 핵심적 가정은 다음과 같다:

1. 완전 관측 가능성(Full Observability): 계획 시점에서 환경의 상태가 완전하게 관측 가능하다.
2. 결정론적 행동(Deterministic Actions): 각 행동의 실행 결과가 유일하게 결정된다.
3. 정적 환경(Static Environment): 로봇의 행동 외에는 환경이 변화하지 않거나, 변화가 사전에 완전히 예측 가능하다.
4. 유한 상태 공간(Finite State Space): 고려해야 하는 상태의 수가 유한하다(또는 적절한 이산화를 통하여 유한으로 근사된다).

2. 상태 공간의 형식화

2.1 상태 전이 시스템

결정론적 임무 계획 문제는 상태 전이 시스템(state transition system) \Sigma = (S, A, \gamma, s_0, S_g)로 형식화된다:

• S: 유한 상태(state) 집합
• A: 유한 행동(action) 집합
• \gamma : S \times A \rightarrow S: 상태 전이 함수(transition function)
• s_0 \in S: 초기 상태
• S_g \subseteq S: 목표 상태 집합

상태 전이 함수 \gamma는 결정론적이므로, 상태 s에서 행동 a를 실행하면 결과 상태 \gamma(s, a)가 유일하게 결정된다. 행동 a가 상태 s에서 실행 가능하려면 \gamma(s, a)가 정의되어야 한다.

2.2 계획의 정의

결정론적 계획(plan) \pi는 초기 상태 s_0에서 목표 상태 s_g \in S_g에 도달하는 행동의 유한 시퀀스이다:

\pi = \langle a_1, a_2, \ldots, a_n \rangle

이 시퀀스를 실행하면 상태의 추적(trace)이 생성된다:

s_0 \xrightarrow{a_1} s_1 \xrightarrow{a_2} s_2 \xrightarrow{} \cdots \xrightarrow{a_n} s_n

여기서 s_{i} = \gamma(s_{i-1}, a_i)이고, s_n \in S_g이다.

2.3 최적 계획

비용 함수(cost function) c : S \times A \rightarrow \mathbb{R}_{\geq 0}가 주어졌을 때, 계획 \pi의 총 비용은 다음과 같이 정의된다:

C(\pi) = \sum_{i=1}^{n} c(s_{i-1}, a_i)

최적 계획(optimal plan) \pi^*는 총 비용을 최소화하는 계획이다:

\pi^* = \arg\min_{\pi \in \Pi} C(\pi)

여기서 \Pi는 실행 가능한(feasible) 모든 계획의 집합이다.

3. 탐색 기반 결정론적 계획

결정론적 임무 계획 문제는 상태 공간 그래프(state space graph)에서의 경로 탐색(path search) 문제로 환원된다. 초기 상태를 시작 노드로, 목표 상태를 종단 노드로 설정하고, 행동을 에지로 모델링하면, 그래프 탐색 알고리즘을 직접 적용할 수 있다.

3.1 너비 우선 탐색(BFS)

너비 우선 탐색(Breadth-First Search, BFS)은 상태 공간을 깊이 순서대로 탐색하여, 최소 행동 수(최소 단계)의 계획을 보장한다. 시간 복잡도와 공간 복잡도는 모두 O(b^d)이며, 여기서 b는 분기 계수(branching factor), d는 최적 계획의 깊이이다.

3.2 깊이 우선 탐색(DFS)

깊이 우선 탐색(Depth-First Search, DFS)은 상태 공간을 깊이 우선으로 탐색하며, 공간 복잡도가 O(b \cdot m)으로 BFS에 비하여 효율적이나 최적성을 보장하지 않는다. 여기서 m은 탐색 트리의 최대 깊이이다.

3.3 반복 심화 탐색(IDS)

반복 심화 탐색(Iterative Deepening Search, IDS)은 깊이 제한을 점진적으로 증가시키는 DFS를 반복 수행하여, BFS의 최적성과 DFS의 공간 효율성을 동시에 달성한다. 시간 복잡도는 O(b^d)이고, 공간 복잡도는 O(b \cdot d)이다 (Korf, 1985).

3.4 균일 비용 탐색(UCS)

균일 비용 탐색(Uniform Cost Search, UCS)은 누적 비용이 가장 낮은 노드를 우선 확장하여, 비용 최적 계획을 보장한다. UCS는 다익스트라 알고리즘(Dijkstra’s algorithm)과 동일한 원리에 기반하며, 시간 복잡도는 O(b^{1+\lfloor C^*/\epsilon \rfloor})이다. 여기서 C^*는 최적 비용, \epsilon은 최소 행동 비용이다.

4. 휴리스틱 탐색 기반 계획

4.1 A* 알고리즘의 적용

A* 알고리즘은 평가 함수 f(n) = g(n) + h(n)을 사용하여, 허용적(admissible) 휴리스틱 h를 통한 효율적 최적 탐색을 수행한다. 여기서 g(n)은 시작 노드에서 노드 n까지의 실제 비용, h(n)은 노드 n에서 목표까지의 추정 비용이다.

임무 계획에서 휴리스틱 함수의 설계는 문제의 효율적 해결에 핵심적이다. 대표적 휴리스틱 설계 기법은 다음과 같다:

1. 완화 휴리스틱(Relaxation Heuristic): 문제의 제약 조건을 완화하여 얻어지는 보다 쉬운 문제의 최적해를 원 문제의 하계(lower bound)로 사용한다.
2. 추상화 휴리스틱(Abstraction Heuristic): 상태 공간을 추상화하여 축소된 문제의 해를 휴리스틱으로 사용한다.
3. 패턴 데이터베이스(Pattern Database): 부분 문제의 최적 비용을 사전 계산하여 테이블로 저장하고, 계획 시 참조한다 (Culberson & Schaeffer, 1998).

4.2 가중 A* 알고리즘

가중 A*(Weighted A*) 알고리즘은 평가 함수를 f(n) = g(n) + w \cdot h(n)으로 수정하여, 가중치 w > 1을 통하여 탐색 속도와 최적성 사이의 교환(trade-off)을 조절한다. 이 알고리즘은 w-최적(w-optimal) 해, 즉 최적 비용의 w배 이내의 비용을 가진 해를 보장한다 (Pohl, 1970).

5. 결정론적 임무 계획의 복잡도

결정론적 임무 계획의 계산 복잡도는 문제의 표현 방식에 따라 달라진다. 상태 공간의 크기가 \lvert S \rvert인 경우, 그래프 탐색의 시간 복잡도는 O(\lvert S \rvert + \lvert A \rvert)이다. 그러나 실질적인 임무 계획 문제에서는 상태 공간이 상태 변수의 수에 대하여 지수적으로 증가하므로(상태 공간 폭발, state space explosion), 명시적 열거(explicit enumeration)가 불가능한 경우가 빈번하다.

Bylander(1994)는 명제적 STRIPS 계획 문제의 판정(계획 존재 여부)이 PSPACE-complete임을 증명하였다. 이러한 높은 복잡도에도 불구하고, 효과적인 휴리스틱과 탐색 전략을 통하여 실질적인 규모의 문제를 해결하는 것이 가능하다.

6. 자율 로봇 임무에서의 적용

6.1 적용 조건

결정론적 임무 계획은 다음과 같은 조건이 충족되는 자율 로봇 임무에 적합하다:

1. 환경의 지도(map)가 사전에 알려져 있으며, 임무 수행 중 변화하지 않거나 예측 가능한 변화만 발생하는 경우
2. 행동의 결과가 확정적이며, 센서 불확실성이 무시 가능한 수준인 경우
3. 통제된 실내 환경(공장, 창고, 연구실)에서의 반복적 임무

6.2 적용 사례

물류 창고 로봇: 레이아웃이 사전에 고정된 창고 환경에서, 로봇이 물품의 적재 위치에서 출하 위치까지 이동하며 물품을 수집하는 임무는 결정론적 계획으로 효과적으로 해결할 수 있다. 각 상태는 로봇의 현재 위치와 수집된 물품의 집합으로 정의되며, 행동은 이동(move), 적재(pick), 하역(place) 등으로 구성된다.

제조 공정 로봇: 미리 정해진 조립 순서에 따라 부품을 조립하는 산업용 로봇의 작업 계획은 결정론적 계획의 전형적 사례이다. 각 조립 단계의 전제조건(precondition)과 효과(effect)가 명확히 정의되므로, STRIPS 또는 PDDL 기반의 고전적 계획 기법을 직접 적용할 수 있다.

6.3 비결정론적 계획과의 관계

결정론적 계획은 비결정론적(nondeterministic) 또는 확률적(stochastic) 환경에서는 직접 적용하기 어렵다. 센서 잡음, 행동 실패, 동적 장애물 등의 불확실성이 존재하는 환경에서는 마르코프 결정 과정(MDP), 부분 관측 마르코프 결정 과정(POMDP), 조건부 계획(contingent planning) 등의 확장된 계획 기법이 필요하다. 그러나 결정론적 계획은 이러한 확장의 이론적 기반을 제공하며, 실무에서도 재계획(replanning) 전략과 결합하여 비결정론적 환경에 대응하는 접근법이 널리 사용된다.

재계획 접근법에서는 결정론적 계획기를 반복적으로 호출하여, 환경의 변화가 감지될 때마다 현재 상태에서 새로운 계획을 수립한다. 이 전략의 효과는 계획기의 응답 속도(계획 수립에 소요되는 시간)와 환경 변화의 빈도에 의하여 결정된다 (Stentz, 1995).

7. 참고문헌

• Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” Artificial Intelligence, 69(1-2), 165–204.
• Culberson, J. C., & Schaeffer, J. (1998). “Pattern Databases.” Computational Intelligence, 14(3), 318–334.
• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• Korf, R. E. (1985). “Depth-First Iterative-Deepening: An Optimal Admissible Tree Search.” Artificial Intelligence, 27(1), 97–109.
• Pohl, I. (1970). “Heuristic Search Viewed as Path Finding in a Graph.” Artificial Intelligence, 1(3–4), 193–204.
• Stentz, A. (1995). “The Focussed D* Algorithm for Real-Time Replanning.” In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1652–1659.