397.57 토폴로지 그래프 구성과 활용

1. 토폴로지 그래프의 정의와 기본 개념

토폴로지 그래프(Topological Graph)는 로봇이 활동하는 환경을 노드(Node)와 간선(Edge)으로 추상화한 그래프 구조이다. 여기서 노드는 환경 내의 의미적으로 중요한 장소(Place)나 관심 지점(Point of Interest)을 나타내며, 간선은 두 노드 사이의 연결 가능성(Navigability)을 나타낸다. 이러한 추상화는 복잡한 연속 공간(Continuous Space)을 이산적인 그래프 구조로 변환하여 임무 계획의 계산 복잡도를 현저히 감소시키는 핵심적 역할을 수행한다.

형식적으로 토폴로지 그래프는 $G = (V, E, w)$ 로 정의된다. 여기서 $V = \{v_1, v_2, \ldots, v_n\}$ 은 노드의 집합, $E \subseteq V \times V$ 는 간선의 집합, $w: E \rightarrow \mathbb{R}^+$ 는 간선에 부여된 가중치 함수이다. 가중치는 두 노드 간의 이동 비용(Travel Cost), 거리, 소요 시간 또는 에너지 소비량 등 다양한 메트릭을 표현할 수 있다.

토폴로지 그래프는 메트릭 맵(Metric Map)과 대비되는 개념이다. 메트릭 맵이 환경의 기하학적 정보를 정밀하게 표현하는 반면, 토폴로지 그래프는 환경의 구조적·위상적 관계만을 포착한다. 이로 인해 메모리 효율성과 계산 효율성이 우수하여 대규모 환경에서의 임무 계획에 적합하다.

2. 토폴로지 그래프의 구성 방법

2.1 보로노이 다이어그램 기반 구성

보로노이 다이어그램(Voronoi Diagram)은 환경 내 장애물의 경계로부터 등거리에 위치한 점들의 집합으로 구성되는 기하학적 구조이다. 보로노이 다이어그램의 꼭짓점(Vertex)과 간선(Edge)을 직접 토폴로지 그래프의 노드와 간선으로 매핑하면, 장애물로부터 최대한 이격된 안전 경로를 자연스럽게 확보할 수 있다.

일반화된 보로노이 그래프(Generalized Voronoi Graph, GVG)는 $n$ 차원 환경에서 장애물 경계로부터의 등거리 집합을 $(n-1)$ 차원 이하의 구조로 축약한 것이다. GVG의 구성 알고리즘은 다음과 같다.

$\text{GVG} = \{q \in \mathcal{C}_{\text{free}} \mid d(q, o_i) = d(q, o_j), \; \forall i \neq j, \; o_i, o_j \in \mathcal{O}\}$

여기서 $\mathcal{C}_{\text{free}}$ 는 자유 공간(Free Configuration Space), $d(\cdot, \cdot)$ 는 거리 함수, $\mathcal{O}$ 는 장애물 집합이다.

2.2 가시성 그래프 기반 구성

가시성 그래프(Visibility Graph)는 환경 내 장애물의 꼭짓점들과 시작점·목표점을 노드로 설정하고, 서로 직선 가시선(Line of Sight)이 확보되는 노드 쌍을 간선으로 연결하여 구성한다. 가시성 그래프는 다각형 장애물 환경에서 최단 경로를 보장하는 특성이 있으나, 장애물 수가 증가할수록 간선 수가 $O(n^2)$ 로 급증하는 한계가 존재한다.

2.3 확률적 로드맵 기반 구성

확률적 로드맵(Probabilistic Roadmap, PRM)은 자유 공간 내에서 무작위 표본 점(Sample Point)을 생성한 후, 인접한 표본 점 간의 충돌 없는 연결 가능성을 검증하여 간선을 형성하는 방법이다. PRM의 구성 과정은 학습 단계(Learning Phase)와 질의 단계(Query Phase)로 구분된다.

학습 단계에서는 $N$ 개의 무작위 형상(Configuration) $q_i$ 를 표본 추출하고, 각 $q_i$ 에 대해 $k$ -최근접 이웃( $k$ -Nearest Neighbor) 또는 반경 $r$ 이내의 이웃 노드를 탐색하여 충돌 없는 간선을 추가한다. 질의 단계에서는 시작 형상과 목표 형상을 로드맵에 연결한 후, 그래프 탐색 알고리즘(예: A*, Dijkstra)을 적용하여 경로를 탐색한다.

2.4 SLAM 기반 토폴로지 구성

동시 위치 추정 및 맵 생성(Simultaneous Localization and Mapping, SLAM) 시스템의 결과를 활용하여 토폴로지 그래프를 구성하는 방법이 존재한다. 특히 그래프 기반 SLAM(Graph-Based SLAM)에서는 로봇의 포즈(Pose)를 노드로, 연속적인 포즈 간의 오도메트리(Odometry) 계측 및 루프 폐쇄(Loop Closure) 제약을 간선으로 구성한다.

토폴로지 SLAM(Topological SLAM)은 환경의 기하학적 세부 정보를 생략하고, 장소 인식(Place Recognition)에 기반하여 노드를 생성한다. 장소 인식은 시각적 특징 벡터(Visual Feature Descriptor), 라이다(LiDAR) 스캔 매칭, 또는 의미적 분류(Semantic Classification) 결과를 활용하여 수행된다.

3. 토폴로지 그래프의 속성과 표현

3.1 노드 속성

토폴로지 그래프의 각 노드 $v_i \in V$ 는 다음과 같은 속성 벡터를 포함할 수 있다.

$\text{attr}(v_i) = \langle \text{id}, \; \text{pos}, \; \text{label}, \; \text{cap}, \; \text{status} \rangle$

여기서 $\text{id}$ 는 고유 식별자, $\text{pos} \in \mathbb{R}^d$ 는 좌표 정보(선택적), $\text{label}$ 은 의미적 레이블(Semantic Label)(예: “충전소”, “적재 구역”, “검사 지점”), $\text{cap}$ 는 동시 수용 가능한 로봇 수(용량), $\text{status}$ 는 현재 점유 상태이다.

3.2 간선 속성

간선 $e_{ij} = (v_i, v_j) \in E$ 는 다음과 같은 속성을 포함한다.

$\text{attr}(e_{ij}) = \langle w_{ij}, \; \text{type}, \; \text{clearance}, \; \text{constraint} \rangle$

여기서 $w_{ij}$ 는 이동 비용, $\text{type}$ 은 간선 유형(단방향/양방향, 수평/수직, 엘리베이터 등), $\text{clearance}$ 는 통과 가능한 최소 폭(Clearance), $\text{constraint}$ 는 통행 제약 조건(시간대별 접근 제한, 허가 요구 등)이다.

3.3 인접 행렬과 인접 리스트 표현

토폴로지 그래프는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)의 두 가지 표준 자료 구조로 표현된다.

인접 행렬 $\mathbf{A} \in \mathbb{R}^{n \times n}$ 은 다음과 같이 정의된다.

$A_{ij} = \begin{cases} w_{ij}, & \text{if } (v_i, v_j) \in E \\ 0, & \text{otherwise} \end{cases}$

인접 행렬은 간선 존재 여부를 $O(1)$ 에 확인할 수 있으나, 희소 그래프(Sparse Graph)에서는 $O(n^2)$ 의 메모리를 소비하므로 비효율적이다. 대규모 환경에서는 인접 리스트 표현이 메모리 효율성 측면에서 우월하며, 공간 복잡도는 $O(n + m)$ 이다. 여기서 $m = |E|$ 는 간선의 수이다.

4. 임무 계획에서의 토폴로지 그래프 활용

4.1 심볼릭 내비게이션 계획과의 결합

토폴로지 그래프는 심볼릭 내비게이션(Symbolic Navigation)에서 환경의 추상적 표현으로 활용된다. 로봇의 임무를 노드 시퀀스로 표현함으로써, 고수준 임무 계획기가 기하학적 세부 사항에 의존하지 않고 임무를 수립할 수 있다.

임무 계획기는 토폴로지 그래프 $G$ 위에서 노드 시퀀스 $\pi = (v_{s}, v_1, v_2, \ldots, v_{g})$ 을 생성하여 시작 노드 $v_s$ 에서 목표 노드 $v_g$ 까지의 경로를 결정한다. 이때 최적 경로는 다음의 최적화 문제로 정의된다.

$\pi^* = \arg\min_{\pi} \sum_{k=0}^{|\pi|-2} w(v_k, v_{k+1})$

이 문제는 Dijkstra 알고리즘 또는 A* 알고리즘을 통해 효율적으로 해결할 수 있다. A* 알고리즘은 휴리스틱 함수 $h(v)$ 를 활용하여 탐색 공간을 축소하며, 허용적(Admissible) 휴리스틱을 사용하면 최적해를 보장한다.

4.2 멀티 로봇 임무 할당에서의 활용

멀티 로봇 시스템에서 토폴로지 그래프는 임무 할당(Task Allocation) 문제의 기반 구조로 활용된다. 각 로봇 $r_i$ 의 현재 위치와 할당된 임무 목표를 토폴로지 그래프 위의 노드로 매핑하면, 임무 할당 문제를 그래프 기반 최적화 문제로 변환할 수 있다.

다중 여행 외판원 문제(Multiple Traveling Salesman Problem, mTSP)의 관점에서, $m$ 대의 로봇이 $n$ 개의 임무 지점을 방문해야 할 때, 총 이동 비용을 최소화하는 할당은 다음과 같이 정의된다.

$\min \sum_{i=1}^{m} \sum_{(v_j, v_k) \in \pi_i} w(v_j, v_k)$

$\text{subject to } \bigcup_{i=1}^{m} \text{visited}(\pi_i) = V_{\text{task}}, \quad \text{visited}(\pi_i) \cap \text{visited}(\pi_j) = \emptyset \; (i \neq j)$

여기서 $V_{\text{task}} \subseteq V$ 는 임무 지점의 집합이다.

4.3 시간 확장 그래프를 통한 시간적 계획

시간 확장 그래프(Time-Expanded Graph)는 토폴로지 그래프의 각 노드를 시간 축으로 복제하여 시공간적 임무 계획을 가능하게 하는 확장 구조이다. 이산 시간 단계 $t = 0, 1, \ldots, T$ 에 대해, 시간 확장 그래프 $G_T = (V_T, E_T)$ 는 다음과 같이 구성된다.

$V_T = \{(v, t) \mid v \in V, \; t \in \{0, 1, \ldots, T\}\}$

$E_T = \{((v, t), (v', t + \delta)) \mid (v, v') \in E, \; \delta = \lceil w(v, v') \rceil\} \cup \{((v, t), (v, t+1)) \mid v \in V\}$

후자의 간선 유형은 “대기(Wait)” 행동을 나타내며, 이를 통해 로봇 간의 충돌 회피와 시간 제약 조건의 이행을 동시에 계획할 수 있다. 다중 에이전트 경로 탐색(Multi-Agent Path Finding, MAPF) 문제에서 시간 확장 그래프는 충돌 없는 경로 계획의 핵심 자료 구조로 활용된다.

4.4 형식 논리 기반 임무 명세와의 결합

토폴로지 그래프는 선형 시제 논리(LTL) 또는 계산 트리 논리(CTL)로 명세된 임무 요구사항과 결합하여 제어 정책을 생성하는 데 활용된다. 토폴로지 그래프 $G$ 를 전이 시스템(Transition System) $\mathcal{T} = (S, \text{Act}, \delta, s_0, \text{AP}, L)$ 으로 변환하면, LTL 임무 명세 $\phi$ 를 만족하는 경로를 탐색할 수 있다.

여기서 상태 집합 $S = V$ , 행동 집합 $\text{Act}$ 는 간선에 대응하는 이동 행동, 전이 함수 $\delta: S \times \text{Act} \rightarrow S$ , 초기 상태 $s_0 = v_s$ , 원자 명제 집합 $\text{AP}$ 는 각 노드에 부여된 레이블, 레이블 함수 $L: S \rightarrow 2^{\text{AP}}$ 이다.

LTL 공식 $\phi$ 로부터 생성된 뷔히 오토마톤(Büchi Automaton) $\mathcal{A}_\phi$ 와 전이 시스템 $\mathcal{T}$ 의 제품 오토마톤(Product Automaton) $\mathcal{P} = \mathcal{T} \otimes \mathcal{A}_\phi$ 을 구성한 후, $\mathcal{P}$ 위에서 수용 조건(Acceptance Condition)을 만족하는 경로를 탐색함으로써 임무를 충족하는 최적 경로를 도출한다.

5. 동적 토폴로지 그래프와 증분 갱신

실제 운용 환경에서는 장애물의 이동, 통로의 폐쇄, 새로운 지점의 발견 등으로 인해 토폴로지 그래프가 동적으로 변화할 수 있다. 동적 토폴로지 그래프(Dynamic Topological Graph)는 이러한 변화를 실시간으로 반영하기 위한 증분 갱신(Incremental Update) 메커니즘을 제공한다.

간선의 추가·삭제에 대한 효율적인 최단 경로 갱신은 D* Lite 알고리즘이나 증분적 A*(Incremental A*) 알고리즘을 통해 수행된다. D* Lite는 목표 노드에서 역방향으로 탐색하며, 간선 비용 변경 시 영향을 받는 노드만 선택적으로 재계산하여 계산 효율성을 확보한다.

그래프 구조 자체의 변경(노드 추가·삭제)에 대해서는 연결 성분(Connected Component) 분석과 도달 가능성(Reachability) 검사를 갱신하여 임무 계획의 실현 가능성을 지속적으로 보장하여야 한다.

6. 계층적 토폴로지 그래프

대규모 환경에서는 단일 수준의 토폴로지 그래프가 지나치게 커져 계획 효율성이 저하될 수 있다. 계층적 토폴로지 그래프(Hierarchical Topological Graph)는 그래프를 다수의 추상화 수준으로 계층화하여 이 문제를 해결한다.

계층적 구성에서는 하위 수준(Low-Level) 그래프의 노드 군집(Cluster)을 상위 수준(High-Level) 그래프의 단일 노드로 대표하고, 군집 간의 연결을 상위 수준 간선으로 매핑한다. 이를 형식적으로 기술하면, 상위 그래프 $G^{(l+1)} = (V^{(l+1)}, E^{(l+1)})$ 은 하위 그래프 $G^{(l)} = (V^{(l)}, E^{(l)})$ 의 분할(Partition) $\{C_1, C_2, \ldots, C_k\}$ 로부터 다음과 같이 구성된다.

$V^{(l+1)} = \{C_1, C_2, \ldots, C_k\}, \quad C_i \subseteq V^{(l)}$

$E^{(l+1)} = \{(C_i, C_j) \mid \exists (v, v') \in E^{(l)}, \; v \in C_i, \; v' \in C_j, \; i \neq j\}$

계획 과정에서는 먼저 상위 수준 그래프에서 대략적인 경로를 탐색한 후, 해당 경로를 구성하는 군집들 내부에서 하위 수준의 세밀한 경로를 결정한다. 이와 같은 계층적 분해(Hierarchical Decomposition)는 탐색 공간의 크기를 대폭 축소하여 계획 시간을 단축한다.

7. 토폴로지 그래프의 응용 사례

7.1 물류 창고 로봇 내비게이션

물류 창고 환경에서는 선반(Rack), 적재 구역(Loading Zone), 충전소(Charging Station) 등을 노드로, 통행 가능한 통로를 간선으로 구성하여 토폴로지 그래프를 형성한다. 수십 대의 자율 이동 로봇(Autonomous Mobile Robot, AMR)이 동시에 운용되는 환경에서는 시간 확장 그래프를 활용한 충돌 없는 다중 경로 계획이 필수적이다.

7.2 실외 자율 주행 차량

도로 네트워크를 토폴로지 그래프로 추상화하여 경로 수준(Route-Level)의 임무 계획을 수행한다. 교차로를 노드로, 도로 구간을 간선으로 매핑하며, 교통량, 도로 상태, 법적 제한(일방통행, 진입 금지)을 간선 속성에 반영한다.

7.3 건물 내부 서비스 로봇

다층 건물에서 각 층의 방과 복도를 토폴로지 그래프로 구성하고, 엘리베이터와 계단을 층 간 연결 간선으로 추가하여 3차원 환경의 토폴로지 표현을 완성한다. 이때 엘리베이터 간선에는 대기 시간과 용량 제약을 속성으로 부여하여 현실적인 임무 계획을 지원한다.

8. 참고 문헌

Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., & Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.
Belta, C., Yordanov, B., & Gol, E. A. (2017). Formal Methods for Discrete-Time Dynamical Systems. Springer.
Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, L., Kumar, T. K. S., Barták, R., & Boyarski, E. (2019). “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks.” Proceedings of the International Symposium on Combinatorial Search (SoCS).

버전: 2026-03-24