397.56 환경 토폴로지 맵 기반 심볼릭 내비게이션 계획

1. 개요

환경 토폴로지 맵(topological map) 기반 심볼릭 내비게이션 계획(symbolic navigation planning)은 로봇의 작업 공간을 메트릭(metric) 좌표가 아닌 토폴로지적 구조로 추상화하여, 고수준 임무 계획에 적합한 이산적 내비게이션 표현을 제공하는 방법론이다. 토폴로지 맵은 환경의 핵심 영역(방, 복도, 교차로 등)을 노드(node)로, 영역 간 연결 관계를 간선(edge)으로 표현하는 그래프 구조이다.

이 추상화는 기하학적 세부 정보를 은닉하고 환경의 구조적 연결성(connectivity)만을 보존함으로써, 형식 논리 기반 임무 명세와의 자연스러운 통합을 가능하게 한다. 특히 LTL(Linear Temporal Logic)이나 PDDL(Planning Domain Definition Language) 등의 심볼릭 표현에서 토폴로지 노드를 원자 명제(atomic proposition)나 상태 변수로 직접 참조할 수 있어, 임무 계획의 형식화와 자동 합성을 촉진한다.

2. 토폴로지 맵의 구성

2.1 환경 분할

토폴로지 맵의 구성은 연속적 작업 공간을 유한 개의 의미적(semantic) 영역으로 분할하는 것에서 시작된다. 대표적 분할 방법은 다음과 같다:

보로노이 분할(Voronoi decomposition): 장애물 경계로부터 등거리에 있는 점들의 궤적(일반화된 보로노이 다이어그램)을 기반으로 통행 가능 공간을 분할한다. Thrun(1998)은 보로노이 다이어그램의 임계점(critical point)을 토폴로지 노드로, 연결 경로를 간선으로 설정하는 방법을 제안하였다.
의미적 분할(Semantic segmentation): 방, 복도, 문, 계단 등의 건축적 구조를 기반으로 환경을 의미적 영역 단위로 분할한다. 실내 환경에서는 Bormann 등(2016)의 레이저 스캔 기반 방 분할 알고리즘이 활용된다.
격자 기반 클러스터링: 점유 격자 맵(occupancy grid map)의 셀들을 공간적 근접성과 연결성에 따라 클러스터링하여 거시적 영역을 생성한다.
랜드마크 기반 분할: SLAM(Simultaneous Localization and Mapping)에서 식별된 시각적 또는 기하학적 랜드마크를 노드로 설정하고, 랜드마크 간 통행 가능성을 간선으로 연결한다.

2.2 그래프 구조

토폴로지 맵은 다음과 같은 속성 그래프(attributed graph)로 형식화된다:

$\mathcal{G} = (V, E, \ell_V, \ell_E)$

여기서 $V$ 는 노드 집합(영역), $E \subseteq V \times V$ 는 간선 집합(연결 관계), $\ell_V: V \rightarrow \mathcal{A}_V$ 는 노드 속성 함수, $\ell_E: E \rightarrow \mathcal{A}_E$ 는 간선 속성 함수이다.

노드 속성 $\ell_V(v)$ 는 영역의 의미적 레이블(예: “사무실”, “창고”, “충전소”), 원자 명제 집합(예: $\{\text{has\_object}, \text{is\_safe}\}$ ), 기하학적 대표점(centroid) 등을 포함한다.

간선 속성 $\ell_E(e)$ 는 물리적 이동 비용(거리, 시간, 에너지), 통행 가능 조건(문의 개폐 상태, 통행 권한), 통행 방향성(양방향/단방향) 등을 포함한다.

3. 심볼릭 내비게이션 계획

3.1 전이 시스템으로의 변환

토폴로지 맵 $\mathcal{G}$ 는 형식 임무 계획에서 사용되는 전이 시스템(transition system) $\mathcal{T}$ 로 직접 변환된다:

$\mathcal{T} = (S, s_0, \delta, AP, L)$

여기서 $S = V$ (토폴로지 노드 = 상태), $s_0 \in V$ (초기 위치 노드), $\delta = E$ (간선 = 전이), $AP$ 는 원자 명제 집합, $L: S \rightarrow 2^{AP}$ 는 각 노드의 의미적 속성을 원자 명제로 매핑하는 레이블링 함수이다.

이 전이 시스템은 LTL 명세 기반 임무 계획에서 제품 오토마톤 구성의 입력으로 사용된다.

3.2 심볼릭 행동 표현

토폴로지 맵에서의 로봇 행동은 다음의 심볼릭 표현으로 추상화된다:

이동(Move): $\text{move}(v_i, v_j)$ — 노드 $v_i$ 에서 인접 노드 $v_j$ 로 이동. 전제 조건은 $(v_i, v_j) \in E$ 이고, 효과는 로봇 위치가 $v_j$ 로 갱신됨.
관찰(Observe): $\text{observe}(v)$ — 노드 $v$ 에서 환경 속성을 관측. 원자 명제의 진릿값을 갱신.
조작(Manipulate): $\text{pick}(o, v)$ , $\text{place}(o, v)$ — 노드 $v$ 에서 물체 $o$ 의 집기/놓기.

이러한 심볼릭 행동은 PDDL 도메인으로 직접 기술 가능하며, PDDL 계획기(예: Fast Downward, POPF)를 통해 임무 계획을 수립할 수 있다.

3.3 LTL 기반 심볼릭 내비게이션

토폴로지 맵의 노드에 부여된 원자 명제를 활용하여 LTL 임무 명세를 작성할 수 있다. 예를 들어:

$\varphi = \square \Diamond \text{warehouse} \wedge \square \Diamond \text{office} \wedge \square \neg \text{restricted}$

이 명세는 “창고와 사무실을 반복적으로 방문하면서 제한 구역을 항상 회피하라“를 의미한다. 토폴로지 맵의 노드 레이블이 원자 명제에 대응하므로, 명세 작성이 직관적이다.

4. 계층적 내비게이션 아키텍처

4.1 -계층 구조

토폴로지 기반 심볼릭 내비게이션은 통상 다음의 2-계층 아키텍처로 구현된다:

고수준 계층(High-level layer): 토폴로지 맵 위에서 심볼릭 경로 계획을 수행한다. 그래프 탐색(BFS, DFS, Dijkstra, A* 등) 또는 형식 합성 기법을 적용하여 노드 방문 시퀀스를 결정한다.

저수준 계층(Low-level layer): 고수준 계획에서 결정된 각 토폴로지 전이(노드 $v_i$ 에서 $v_j$ 로의 이동)에 대해, 메트릭 맵 위에서의 경로 계획 및 동작 제어를 수행한다. ROS2의 Nav2 스택(navigation stack)이 대표적이다.

인터페이스: 고수준 계층은 토폴로지 전이의 성공 여부를 저수준 계층으로부터 피드백 받아 계획을 수정한다. 전이 실패 시(장애물 차단, 경로 불가 등) 대안 경로를 재계획한다.

4.2 -계층 구조

더 복잡한 시스템에서는 임무 계층(mission layer), 행동 계층(behavior layer), 제어 계층(control layer)의 3-계층 구조가 적용된다:

임무 계층: LTL/PDDL 기반 심볼릭 임무 계획으로 고수준 행동 시퀀스를 결정한다.
행동 계층: 토폴로지 맵 위의 내비게이션 경로를 결정하고, 행동 트리(behavior tree) 또는 유한 상태 기계(FSM)를 통해 실행을 관리한다.
제어 계층: 메트릭 경로 추종, 장애물 회피, 자세 제어 등의 저수준 제어를 수행한다.

5. 동적 토폴로지 맵

5.1 환경 변화의 반영

동적 환경에서는 토폴로지 맵의 구조가 시간에 따라 변화할 수 있다. 문의 개폐, 장애물의 출현/소멸, 새로운 영역의 발견 등에 따라 노드와 간선이 추가·삭제·수정된다.

동적 토폴로지 맵의 관리를 위한 주요 기법은 다음과 같다:

증분적 갱신(Incremental update): 새로운 관측에 따라 영향 받는 노드와 간선만 갱신하여 전체 맵 재구성을 방지한다.
확률적 간선 가중치: 환경의 불확실성을 반영하여 간선의 통행 가능 확률을 유지하고, 관측에 따라 베이지안 갱신(Bayesian update)을 수행한다.
시간적 유효성: 각 간선에 시간적 유효 기간(temporal validity)을 부여하여, 일정 시간 경과 후 재검증이 필요함을 표시한다.

5.2 재계획 트리거

토폴로지 맵의 변화가 현재 계획에 영향을 미치는 경우, 재계획(replanning)이 트리거된다. 재계획의 효율성을 위해 현재 토폴로지 상태에서의 잔여 계획을 재사용하는 전략이 적용된다.

6. 도구와 소프트웨어 프레임워크

ROS2 Nav2: ROS2의 표준 내비게이션 스택으로, 토폴로지 맵 레이어와 웨이포인트 팔로어(waypoint follower)를 통한 심볼릭 내비게이션을 지원한다.
TuLiP: Python 기반 형식 임무 계획 도구로, 전이 시스템 모델링과 GR(1) 합성을 통한 토폴로지 내비게이션 제어기 합성을 지원한다.
RTAB-Map: 실시간 외관 기반 매핑(Real-Time Appearance-Based Mapping) 도구로, 시각적 토폴로지 맵의 자동 생성을 지원한다.

7. 참고 문헌

Thrun, S. (1998). “Learning Metric-Topological Maps for Indoor Mobile Robot Navigation.” Artificial Intelligence, 99(1), pp. 21–71.
Kuipers, B. (2000). “The Spatial Semantic Hierarchy.” Artificial Intelligence, 119(1–2), pp. 191–233.
Bormann, R., Jordan, F., Li, W., Hampp, J., Hägele, M. (2016). “Room Segmentation: Survey, Implementation, and Analysis.” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 1–7.
Kress-Gazit, H., Fainekos, G.E., Pappas, G.J. (2009). “Temporal-Logic-Based Reactive Mission and Motion Planning.” IEEE Transactions on Robotics, 25(6), pp. 1370–1381.

버전: 2026-03-24
출처: Robotics Engineering 서적, Volume 9, Part 53, Chapter 397