397.27 그래프 탐색 기반 임무 계획

1. 개요

그래프 탐색 기반 임무 계획은 로봇의 임무 공간(mission space)을 그래프(graph)로 모델링하고, 그래프 위에서의 탐색(search)을 통해 목표를 달성하는 행동 시퀀스를 생성하는 접근 방식이다. 그래프 표현은 상태 공간(state space), 작업 관계(task relation), 환경 위상(environmental topology) 등 다양한 추상화 수준에서 임무 계획 문제를 형식화할 수 있는 범용적 프레임워크를 제공한다. 본 절에서는 임무 계획의 그래프 모델링 기법, 대표적 그래프 탐색 알고리즘의 적용, 그리고 로봇 시스템에서의 실질적 구현 방법론을 기술한다.

2. 임무 계획의 그래프 모델링

2.1 상태 전이 그래프(State Transition Graph)

상태 전이 그래프(STG)는 임무 계획의 가장 기본적인 그래프 모델로, 가능한 세계 상태를 노드로, 행동에 의한 상태 전이를 방향 간선으로 표현한다.

\mathcal{G}_{\text{STG}} = (S, E, w)

여기서 각 구성 요소는 다음과 같다.

• S: 가능한 세계 상태의 집합 (노드)
• E \subseteq S \times S: 행동에 의한 상태 전이의 집합 (방향 간선)
• w : E \rightarrow \mathbb{R}_{\geq 0}: 간선 가중치 함수로, 전이 비용(시간, 에너지 등)을 나타냄

간선 (s, s') \in E는 상태 s에서 어떤 행동 a를 적용하여 상태 s'에 도달할 수 있음을 의미한다. 하나의 상태 쌍 (s, s')에 대해 여러 행동이 존재할 수 있으므로, 다중 그래프(multigraph)가 될 수 있다.

임무 계획 문제: 초기 상태 s_0 \in S에서 목표 조건 G를 만족하는 목표 상태 s_G \in S_G \subseteq S까지의 최적 경로를 탐색하는 문제이다.

\pi^* = \arg\min_{\pi \in \Pi(s_0, S_G)} \text{cost}(\pi)

여기서 \Pi(s_0, S_G)는 s_0에서 S_G로의 모든 유효한 경로의 집합이다.

2.2 작업 그래프(Task Graph)

작업 그래프는 임무를 구성하는 개별 작업(task)을 노드로, 작업 간의 관계(선후 관계, 인과 관계, 자원 공유 관계 등)를 간선으로 표현한 고수준 추상화 모델이다.

\mathcal{G}_{\text{task}} = (\mathcal{T}, E_{\text{prec}}, E_{\text{sync}})

• \mathcal{T}: 작업 노드의 집합
• E_{\text{prec}} \subseteq \mathcal{T} \times \mathcal{T}: 선후 관계(precedence) 간선. (t_i, t_j) \in E_{\text{prec}}는 t_i가 t_j보다 먼저 완료되어야 함을 나타냄
• E_{\text{sync}} \subseteq \mathcal{T} \times \mathcal{T}: 동기화(synchronization) 간선. 동시 시작, 동시 종료 등의 시간적 제약을 나타냄

작업 그래프 위에서의 임무 계획은 선후 관계를 준수하면서 모든 작업을 수행하는 유효한 실행 순서를 결정하는 문제이다.

2.3 토폴로지 그래프(Topology Graph)

토폴로지 그래프는 환경의 공간적 구조를 노드와 간선으로 추상화한 모델이다. 로봇이 작업을 수행하는 위치를 노드로, 위치 간의 이동 가능성을 간선으로 표현한다.

\mathcal{G}_{\text{topo}} = (L, E_{\text{nav}}, d)

• L: 위치(location) 노드의 집합
• E_{\text{nav}} \subseteq L \times L: 이동 가능 간선
• d : E_{\text{nav}} \rightarrow \mathbb{R}_{\geq 0}: 이동 거리 또는 비용 함수

임무 계획에서 토폴로지 그래프는 작업 간의 전이 비용을 계산하기 위한 기반 인프라로 활용된다. 로봇이 작업 t_i를 위치 l_i에서 수행하고, 다음 작업 t_j를 위치 l_j에서 수행하는 경우, 전이 비용은 토폴로지 그래프에서 l_i에서 l_j까지의 최단 경로 비용이다.

c(t_i, t_j) = \text{shortest-path}(\mathcal{G}_{\text{topo}}, l_i, l_j)

2.4 곱 그래프(Product Graph)와 복합 그래프

임무 계획에서 여러 차원의 정보(위치, 작업 상태, 자원 상태 등)를 동시에 고려하기 위해 **곱 그래프(product graph)**를 구성할 수 있다. 곱 그래프는 개별 그래프의 노드 조합을 노드로, 동시에 유효한 전이를 간선으로 갖는다.

예를 들어, 토폴로지 그래프 \mathcal{G}_{\text{topo}}와 작업 상태 오토마톤 \mathcal{A}_{\text{task}}의 곱 그래프는 다음과 같이 정의된다.

\mathcal{G}_{\otimes} = \mathcal{G}_{\text{topo}} \otimes \mathcal{A}_{\text{task}}

곱 그래프의 노드는 (l, q)의 형태이며, 여기서 l \in L은 위치이고 q는 작업 상태이다. 간선은 위치 전이와 작업 상태 전이가 동시에 유효한 경우에만 존재한다.

3. 대표적 그래프 탐색 알고리즘의 적용

3.1 Dijkstra 알고리즘

Dijkstra 알고리즘(Dijkstra, 1959)은 비음수(non-negative) 가중치를 갖는 그래프에서 단일 출발점 최단 경로(single-source shortest path)를 구하는 알고리즘이다. 임무 계획 그래프에서 초기 상태로부터 모든 도달 가능한 상태까지의 최소 비용 경로를 계산한다.

Dijkstra 알고리즘의 시간 복잡도는 이진 힙(binary heap)을 사용하는 경우 O((|V| + |E|) \log |V|), 피보나치 힙(Fibonacci heap)을 사용하는 경우 O(|V| \log |V| + |E|)이다.

임무 계획에서 Dijkstra 알고리즘은 다음의 경우에 적합하다.

• 상태 공간 그래프가 명시적으로 구성 가능하고, 크기가 관리 가능한 경우
• 휴리스틱 함수를 설계하기 어려운 도메인에서 최적 해를 보장하려는 경우
• 초기 상태에서 다수의 후보 목표까지의 비용을 동시에 계산하려는 경우

3.2 D* 및 D* Lite 알고리즘

D (Dynamic A)** 알고리즘(Stentz, 1994)과 그 개선된 버전인 D Lite*(Koenig & Likhachev, 2002)는 동적으로 변하는 그래프에서 최단 경로를 증분적으로(incrementally) 갱신하는 알고리즘이다. 환경의 변화(새로운 장애물 발견, 간선 비용 변경 등)가 발생할 때, 전체 탐색을 재수행하지 않고 이전 탐색 결과를 재활용하여 갱신된 최적 경로를 효율적으로 계산한다.

D* Lite의 핵심 원리는 **역방향 탐색(backward search)**에 기반한다. 목표 상태에서 현재 상태 방향으로 탐색을 수행하며, 간선 비용 변경이 감지되면 영향을 받는 노드만 선택적으로 재계산한다.

로봇 임무 계획에서 D* Lite는 다음의 상황에 적합하다.

• 환경이 동적으로 변하는 경우(동적 장애물, 도로 폐쇄 등)
• 계획 수립 후 실행 중에 그래프 구조가 변경되는 경우
• 재계획(replanning)이 빈번하게 필요한 경우

D* Lite의 증분적 갱신은 전체 재계획에 비해 계산 비용을 크게 절감한다.

3.3 다목적 그래프 탐색

다목적(multi-objective) 임무 계획에서는 비용, 시간, 에너지, 위험도 등 복수의 목적 함수를 동시에 최적화하여야 한다. 다목적 그래프 탐색에서는 파레토 최적(Pareto-optimal) 경로 집합을 구한다.

NAMOA* (New Approach to Multiobjective A*)(Mandow & Pérez de la Cruz, 2005)는 다목적 그래프 탐색을 위한 A*의 확장 알고리즘으로, 파레토 최적 경로의 집합을 탐색한다. 각 노드에 대해 비지배적(non-dominated) 비용 벡터의 집합을 유지하며, 파레토 프론티어를 점진적으로 구성한다.

비용 벡터 \mathbf{c}_1 = (c_1^{(1)}, c_1^{(2)}, \ldots, c_1^{(k)})이 \mathbf{c}_2 = (c_2^{(1)}, c_2^{(2)}, \ldots, c_2^{(k)})를 **지배(dominate)**하는 조건은 다음과 같다.

c_1^{(i)} \leq c_2^{(i)}, \quad \forall i \in \{1, \ldots, k\}, \quad \exists j \in \{1, \ldots, k\}: c_1^{(j)} < c_2^{(j)}

3.4 제약 그래프 탐색(Constrained Graph Search)

자원 제약이 있는 임무 계획에서는 제약 조건을 만족하면서 비용을 최소화하는 경로를 탐색한다. **자원 제약 최단 경로 문제(Resource-Constrained Shortest Path Problem, RCSPP)**는 NP-hard 문제로 알려져 있으며, 의사 다항 시간(pseudo-polynomial time) 알고리즘 또는 라그랑지 완화(Lagrangian relaxation) 기반 근사 알고리즘으로 해결한다.

상태를 (v, r)로 확장한다. 여기서 v는 현재 노드이고, r은 잔여 자원 벡터이다. 전이 시 자원 소모를 반영한다.

\gamma((v, r), e) = (v', r - r_e), \quad r - r_e \geq \mathbf{0}

여기서 r_e는 간선 e를 통과할 때 소모되는 자원 벡터이다.

4. 그래프 탐색 기반 임무 계획의 구현

4.1 명시적 그래프와 암묵적 그래프

임무 계획의 그래프 표현은 **명시적 그래프(explicit graph)**와 **암묵적 그래프(implicit graph)**로 구분된다.

명시적 그래프: 모든 노드와 간선이 미리 열거되어 메모리에 저장된 그래프이다. 토폴로지 그래프, 소규모 작업 그래프 등이 이에 해당한다. 명시적 그래프는 전체 구조에 대한 사전 분석(연결성, 강연결 성분, 최단 경로 사전 계산 등)이 가능하다.

암묵적 그래프: 노드와 간선이 탐색 시에 동적으로 생성되는 그래프이다. 상태 전이 그래프의 경우, 상태 공간의 크기가 매우 크므로 전체를 미리 열거하는 것이 불가능하다. 암묵적 그래프에서는 **후속 상태 생성 함수(successor generation function)**를 통해 탐색 시 필요한 간선만 생성한다.

from abc import ABC, abstractmethod
from typing import List, Tuple, Set, Dict
import heapq

class MissionGraph(ABC):
    """임무 계획 그래프의 추상 기반 클래스"""
    
    @abstractmethod
    def get_initial_state(self):
        """초기 상태를 반환한다."""
        pass
    
    @abstractmethod
    def is_goal(self, state) -> bool:
        """목표 상태 여부를 검사한다."""
        pass
    
    @abstractmethod
    def get_successors(self, state) -> List[
        Tuple[object, float, str]
    ]:
        """
        후속 상태와 전이 비용을 반환한다.
        Returns: [(successor_state, cost, action_label)]
        """
        pass

class ExplicitMissionGraph(MissionGraph):
    """명시적 임무 그래프의 구현"""
    
    def __init__(self):
        self.adjacency: Dict[object, List[
            Tuple[object, float, str]
        ]] = {}
        self.initial = None
        self.goals: Set = set()
    
    def add_node(self, state, is_initial=False,
                 is_goal=False):
        """노드를 추가한다."""
        if state not in self.adjacency:
            self.adjacency[state] = []
        if is_initial:
            self.initial = state
        if is_goal:
            self.goals.add(state)
    
    def add_edge(self, from_state, to_state, cost,
                 action=""):
        """간선을 추가한다."""
        self.adjacency[from_state].append(
            (to_state, cost, action)
        )
    
    def get_initial_state(self):
        return self.initial
    
    def is_goal(self, state) -> bool:
        return state in self.goals
    
    def get_successors(self, state):
        return self.adjacency.get(state, [])

class ImplicitMissionGraph(MissionGraph):
    """암묵적 임무 그래프의 구현 (위치-작업 복합 상태)"""
    
    def __init__(self, topology, tasks, cost_fn):
        """
        Args:
            topology: 토폴로지 그래프
            tasks: 수행할 작업 목록
            cost_fn: 전이 비용 함수
        """
        self.topology = topology
        self.tasks = tasks
        self.cost_fn = cost_fn
        self.num_tasks = len(tasks)
    
    def get_initial_state(self):
        """초기 상태: (현재 위치, 빈 작업 비트마스크)"""
        return (self.topology.start_location, 0)
    
    def is_goal(self, state) -> bool:
        """모든 작업이 완료된 상태"""
        _, completed = state
        return completed == (1 << self.num_tasks) - 1
    
    def get_successors(self, state):
        """후속 상태를 동적으로 생성한다."""
        current_loc, completed = state
        successors = []
        
        # 인접 위치로의 이동
        for neighbor in self.topology.neighbors(
            current_loc
        ):
            move_cost = self.topology.edge_cost(
                current_loc, neighbor
            )
            new_state = (neighbor, completed)
            successors.append(
                (new_state, move_cost,
                 f"move_to_{neighbor}")
            )
        
        # 현재 위치에서 수행 가능한 작업
        for i, task in enumerate(self.tasks):
            if completed & (1 << i):
                continue  # 이미 완료된 작업
            if task.location != current_loc:
                continue  # 다른 위치의 작업
            
            task_cost = task.execution_cost
            new_completed = completed | (1 << i)
            new_state = (current_loc, new_completed)
            successors.append(
                (new_state, task_cost,
                 f"execute_{task.name}")
            )
        
        return successors

4.2 범용 그래프 탐색 엔진

다양한 임무 계획 그래프에 대해 통합적으로 사용할 수 있는 범용 그래프 탐색 엔진의 구현 예시이다.

class GraphSearchEngine:
    """범용 그래프 탐색 엔진"""
    
    def dijkstra(self, graph: MissionGraph):
        """Dijkstra 알고리즘으로 최적 경로를 탐색한다."""
        init = graph.get_initial_state()
        g = {init: 0.0}
        parent = {init: (None, None)}
        open_list = [(0.0, 0, init)]
        closed = set()
        counter = 1
        
        while open_list:
            cost, _, state = heapq.heappop(open_list)
            
            if state in closed:
                continue
            
            if graph.is_goal(state):
                return self._extract_path(
                    parent, state, g[state]
                )
            
            closed.add(state)
            
            for succ, edge_cost, action in (
                graph.get_successors(state)
            ):
                new_g = g[state] + edge_cost
                if succ not in g or new_g < g[succ]:
                    g[succ] = new_g
                    parent[succ] = (state, action)
                    heapq.heappush(
                        open_list,
                        (new_g, counter, succ)
                    )
                    counter += 1
        
        return None
    
    def astar(self, graph: MissionGraph,
              heuristic):
        """A* 알고리즘으로 최적 경로를 탐색한다."""
        init = graph.get_initial_state()
        g = {init: 0.0}
        parent = {init: (None, None)}
        h0 = heuristic(init)
        open_list = [(h0, 0, init)]
        closed = set()
        counter = 1
        
        while open_list:
            f, _, state = heapq.heappop(open_list)
            
            if state in closed:
                continue
            
            if graph.is_goal(state):
                return self._extract_path(
                    parent, state, g[state]
                )
            
            closed.add(state)
            
            for succ, edge_cost, action in (
                graph.get_successors(state)
            ):
                new_g = g[state] + edge_cost
                if succ not in g or new_g < g[succ]:
                    g[succ] = new_g
                    parent[succ] = (state, action)
                    h = heuristic(succ)
                    heapq.heappush(
                        open_list,
                        (new_g + h, counter, succ)
                    )
                    counter += 1
        
        return None
    
    def _extract_path(self, parent, state, total_cost):
        """역추적으로 경로를 추출한다."""
        path = []
        while parent[state][0] is not None:
            prev, action = parent[state]
            path.append((action, state))
            state = prev
        path.reverse()
        return {
            'actions': [a for a, _ in path],
            'states': [s for _, s in path],
            'cost': total_cost
        }

5. 그래프 표현의 최적화 기법

5.1 그래프 축소(Graph Reduction)

대규모 임무 계획 그래프에서 탐색 효율을 향상시키기 위해 그래프 축소 기법을 적용할 수 있다.

노드 축약(Node Contraction): 차수(degree)가 2인 노드(중간 경유 노드)를 제거하고, 양쪽 이웃 노드를 직접 연결하는 간선으로 대체한다. 이를 통해 그래프의 크기를 줄이면서 최단 경로의 최적성을 보존한다.

계층적 그래프 분해(Hierarchical Graph Decomposition): 그래프를 여러 수준의 추상화로 분해하여, 상위 수준에서 대략적 경로를 탐색하고 하위 수준에서 세부 경로를 정제하는 계층적 탐색 전략을 적용한다. HPA* (Hierarchical Pathfinding A*)(Botea et al., 2004) 등의 알고리즘이 이 접근을 구현한다.

대칭 축소(Symmetry Reduction): 그래프에서 대칭 구조를 식별하여 동등한 경로의 중복 탐색을 방지한다. 대칭 축소는 격자 그래프(grid graph) 기반의 로봇 내비게이션 계획에서 특히 효과적이다.

5.2 사전 계산과 캐싱

전체 쌍 최단 경로(All-Pairs Shortest Path, APSP): 토폴로지 그래프와 같은 소규모 명시적 그래프에서는 Floyd-Warshall 알고리즘 등을 사용하여 모든 노드 쌍 간의 최단 경로를 사전 계산할 수 있다. 사전 계산된 거리 행렬은 O(1) 시간에 전이 비용을 조회할 수 있게 하여 온라인 계획의 효율을 크게 향상시킨다.

D[i][j] = \text{shortest-path}(\mathcal{G}_{\text{topo}}, l_i, l_j), \quad \forall l_i, l_j \in L

Floyd-Warshall 알고리즘의 시간 복잡도는 O(|L|^3)이며, 공간 복잡도는 O(|L|^2)이다.

경로 캐싱(Path Caching): 빈번하게 탐색되는 노드 쌍에 대한 최적 경로를 캐시에 저장하여, 반복적 탐색을 회피한다.

6. 로봇 임무 계획에서의 그래프 탐색 응용

6.1 위상 기반 내비게이션 계획

실내 로봇의 내비게이션 계획에서 토폴로지 그래프를 활용한 고수준 경로 계획이 널리 활용된다. 건물의 방(room), 복도(corridor), 교차점(junction) 등을 노드로, 이동 가능 경로를 간선으로 모델링한 토폴로지 그래프 위에서 Dijkstra 또는 A* 탐색을 수행하여 방문 순서를 결정한다. 이후 각 간선에 대해 하위 수준의 경로 계획기가 장애물 회피 경로를 생성한다.

6.2 드론 정찰 경로 계획

정찰 지점들을 방문하는 드론 임무에서, 정찰 지점을 노드로, 지점 간의 비행 경로 비용을 간선으로 갖는 완전 그래프(complete graph)를 구성한다. 이 그래프 위에서 제약 최단 경로 탐색을 수행하여, 배터리 잔량 제약을 만족하면서 모든 정찰 지점을 방문하는 최적 경로를 생성한다.

6.3 멀티 레이어 그래프 기반 임무 계획

복잡한 임무 환경에서는 단일 그래프로 모든 정보를 표현하기 어렵다. **멀티 레이어 그래프(multi-layer graph)**는 물리적 공간 레이어, 작업 상태 레이어, 자원 레이어 등을 분리하여 표현하고, 레이어 간의 연결(inter-layer edges)을 통해 통합적 탐색을 수행한다.

각 레이어는 독립적으로 관리·갱신할 수 있으므로, 환경 변화 시 영향을 받는 레이어만 갱신하면 되어 유지보수의 효율성이 높다. 멀티 레이어 그래프 위에서의 탐색은 곱 그래프 탐색과 유사하나, 레이어 간 전이 비용을 명시적으로 모델링할 수 있는 유연성을 제공한다.

7. 그래프 탐색 기반 임무 계획의 한계와 대응

7.1 상태 공간 폭발(State Space Explosion)

그래프 탐색 기반 임무 계획의 가장 핵심적 한계는 상태 공간의 지수적 증가이다. 명제 변수의 수 |\mathcal{F}|에 대해 상태의 수는 O(2^{|\mathcal{F}|})이며, 기저화된 행동의 수도 객체 수에 대해 다항적으로 증가한다. 이를 완화하기 위한 주요 기법은 다음과 같다.

1. 추상화(Abstraction): 상태 공간을 축소된 추상 공간으로 매핑하여 탐색 공간을 줄인다.
2. 대칭 축소(Symmetry Breaking): 동등한 상태의 중복 탐색을 방지한다.
3. 가지치기(Pruning): 목표 도달 불가능 상태를 조기에 식별하여 탐색 공간에서 제거한다.
4. 계층적 분해: 문제를 상위·하위 수준으로 분해하여 각 수준에서의 탐색 공간을 축소한다.

7.2 동적 환경에서의 그래프 갱신

로봇이 동작하는 환경은 동적으로 변하므로, 임무 계획 그래프도 실시간으로 갱신되어야 한다. 새로운 장애물의 출현, 경로의 차단, 작업 조건의 변경 등에 대응하기 위해 그래프의 간선 추가·삭제·비용 갱신이 효율적으로 이루어져야 한다. D* Lite 등의 증분적 탐색 알고리즘은 이러한 동적 갱신에 특화되어 있다.

7.3 불완전 정보 하의 탐색

실제 로봇 시스템에서는 환경에 대한 정보가 불완전할 수 있다. 미탐색 영역의 구조, 장애물의 존재 여부 등이 불확실한 경우, 그래프의 일부 간선이 불확실한 상태에서 탐색을 수행하여야 한다. **낙관적 탐색(optimistic search)**은 불확실한 간선을 이동 가능한 것으로 가정하고 탐색을 수행하며, 실행 중 간선의 불가능이 확인되면 그래프를 갱신하고 재탐색을 수행하는 전략이다.

8. 참고 문헌

• Dijkstra, E. W. (1959). “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik, 1, 269–271.
• Stentz, A. (1994). “Optimal and Efficient Path Planning for Partially-Known Environments.” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 1994), 3310–3317.
• Koenig, S., & Likhachev, M. (2002). “D* Lite.” Proceedings of the 18th National Conference on Artificial Intelligence (AAAI 2002), 476–483.
• Mandow, L., & Pérez de la Cruz, J. L. (2005). “A New Approach to Multiobjective A* Search.” Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2005), 218–223.
• Botea, A., Müller, M., & Schaeffer, J. (2004). “Near Optimal Hierarchical Path-Finding.” Journal of Game Development, 1(1), 7–28.
• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.

v0.2.0