1. Navigation이란?
Navigation(네비게이션)은 로봇이 목표 지점까지 안전하게 이동할 수 있도록 경로를 계획하고 이를 따라가게 만드는 기술이다. 이는 로봇의 위치 추정(Localization), 지도 생성(Mapping), 경로 계획(Path Planning)을 포함하며, 다양한 센서 데이터와 알고리즘을 통해 이루어진다.
1.1. 주요 구성 요소
- Localization(위치 추정): 로봇의 현재 위치를 정확하게 추정하는 과정이다. LiDAR, 카메라, IMU 센서 등을 활용하여 로봇의 위치를 추정한다.
- Mapping(지도 생성): 로봇이 이동한 환경의 지도를 만드는 과정이다. SLAM(Simultaneous Localization and Mapping) 기법이 자주 사용된다.
- Path Planning(경로 계획): 목표 지점까지 최적의 경로를 계획하는 과정이다. A* 알고리즘(에이스타 알고리즘), Dijkstra 알고리즘(다익스트라 알고리즘) 등이 사용된다. (처음 봤을 때 알고리즘 발음에 대한 고민이 있었기에 적어두었다.
실제로 난 에이별 알고리즘이라 읽은 적이 있다🤦♂️)
위치 추정과 지도 생성은 주로 전에 포스팅했던 Cartographer SLAM에서처럼 맵핑 툴을 이용해서 함께 진행하게 된다. 즉, 이번 글에서는 Path Planning에 대해서 간단하게 이게 어떤 것인지 이해할 수 있을 정도만 다룰 것이다.
2. Path Planning이란?
Path Planning은 말 그대로 경로 계획으로, 로봇이 목표 지점까지 이동할 수 있도록 최적의 경로를 찾는 알고리즘이다. 이 과정에서는 장애물 회피와 같은 조건을 고려해서 가능한 경로 중 가장 효율적이고 안전한 경로를 선택하게 된다.
2.1. 경로 계획의 종류
-
Global Path Planning
전체 환경에 대한 정보를 바탕으로 목표 지점까지의 경로를 계산하는 방식이다.- 대표 알고리즘: A*, Dijkstra, RRT(일부 최적화 버전은 실시간 적용도 가능)
- 사용 사례: 자율주행 자동차, 로봇 청소기 등의 장거리 경로 계획
-
Local Path Planning
실시간으로 변화하는 환경을 고려하여 장애물 회피와 같은 세부적인 경로를 계획하는 방식이다.- 대표 알고리즘: DWA(Dynamic Window Approach), Teb Local Planner
- 사용 사례: 군집 로봇, 공장 내 자율 이동 로봇(AGV)
우리가 흔히 아는 Nav2 등의 오픈소스에선 Global과 Local Path Planning을 독립적으로 설정할 수 있게 구성되어있다.(이게 제일 효율적이기도 하다)
3. 핵심 알고리즘
3.1. A* 알고리즘
A* 알고리즘은 가장 널리 사용되는 전역 경로 계획 알고리즘 중 하나이다. 휴리스틱 함수(Heuristic Function)를 사용하여, 시작 지점에서 목표 지점까지의 최단 경로를 탐색한다. 이 과정에서 f(n) = g(n) + h(n) 방식으로 탐색을 최적화하여 목표 지점까지의 경로만 빠르게 탐색한다.
- 장점: 빠르고 최적해(Optimal Solution)에 가깝다.
- 단점: 복잡한 환경에서는 연산량이 많아질 수 있다.
식에 대해 이해하기 쉽게 설명을 덧붙이자면
f(n)은 총 비용,
g(n)은 시작점에서 현재 노드 n까지 실제로 소요된 비용,
h(n)은 현재 노드 n에서 목표 노드까지 도달할 것으로 예상되는 비용이다.
지도에서 시작점에서 목표 지점으로 이동할 때 g(n)은 지금까지 이동한 실제 거리이며 h(n)은 현재 위치에서 목적지까지 남은 예상 거리이다. 이 두 값을 더한 f(n)은 해당 노드를 통해 전체 경로의 총 비용이 얼마나 될지를 예측하는 값이다.
이 과정을 반복해서 위 이미지처럼 빠르게 목표지점까지 도달할 경로를 찾을 수 있다.
3.2. Dijkstra 알고리즘
Dijkstra 알고리즘은 A*와 유사하지만, 휴리스틱 함수를 사용하지 않고 모든 가능한 경로를 탐색하여 가장 짧은 경로를 찾는 방식이다.
- 장점: 모든 노드에 대해 최단 경로를 보장
- 단점: 연산량이 많아 실시간 적용이 어렵다.
3.3. RRT (Rapidly-exploring Random Tree)
RRT 알고리즘은 확률적 경로 계획 방식으로, 복잡한 환경에서 빠르게 경로를 탐색하는 데 유리한 알고리즘이다.
- 장점: 빠르게 경로를 탐색할 수 있으며, 비정형적인 환경에서도 활용 가능
- 단점: 최적의 경로를 보장하지 않으며, 후처리(Smoothing)가 필요할 수 있다.
3.4. DWA (Dynamic Window Approach)
DWA는 Local Path Planning에서 많이 사용되는 알고리즘이다. 로봇의 속도와 회전을 고려하여, 주어진 시간 내에 이동할 수 있는 최적의 경로를 계산한다.
- 장점: 실시간 장애물 회피가 가능
- 단점: 장애물이 많은 환경에서는 경로가 비효율적일 수 있다.
속도와 가속도를 고려한 동역학적 제약이 있기 때문에 로봇이 급격한 방향 전환을 하기 어렵다.
3.5. DWB
DWB는 DWA의 기본 아이디어를 발전시킨 알고리즘으로 ROS2의 오픈소스 Nav2 등에서 Local Path Planning에 사용된다.
DWB 역시 DWA와 같이 로봇의 속도와 회전, 가속도 제한을 고려하여 단기간 실행 가능한 속도 명령의 집합을 산출한다.
다만 DWA와 달리 후보 경로 생성과 비용 평가 과정을 더욱 모듈화하여 분리한 점이 특징이다.
- 장점: 모듈화된 설계 덕분에 각 단계를 독립적으로 조정 및 튜닝할 수 있다. 복잡한 동적 환경에서도 정교한 비용 평가를 통해 안정적이고 효율적인 경로 선택이 가능하다.
- 단점: 보다 세밀한 평가를 위해 추가적인 계산이 요구되기 때문에 환경에 따라 DWA보다 약간의 연산 부담이 있을 수 있다. 또한 탐색 영역이 제한되기에 local minimum에 빠질 가능성이 있다
위 사진은 nav2 스택을 이용한 turtlebot의 주행 모습이다.
참고 깃허브:
https://github.com/zhm-real/PathPlanning
https://github.com/pangfumin/CudaDwa
https://github.com/ros-navigation/navigation2/tree/main/nav2_regulated_pure_pursuit_controller
4. Navigation과 Path Planning의 응용 분야
4.1. 자율주행 자동차
당연하게도 자율주행 자동차에서는 경로 계획과 네비게이션 기술이 핵심 요소이다. 차량이 도로를 따라 이동할 때 장애물을 감지하고 최적의 경로를 실시간으로 계획하여 목표 지점까지 안전하게 도달할 수 있도록 한다.
4.2. 드론
드론은 3D 공간에서 경로 계획을 수행해야 하므로 기존의 2D 경로 계획보다 더 복잡한 알고리즘이 요구된다. 자율비행을 위해 빠르고 정확한 네비게이션과 장애물 회피를 실시간으로 처리해야 한다.
4.3. 스마트 팜
스마트 팜에서는 로봇이 자동으로 농작물을 수확하거나 모니터링할 수 있도록 네비게이션과 경로 계획 기술이 활용된다.
5. 마무리
Navigation과 Path Planning은 자율주행 로봇의 핵심 기술이며, A* 알고리즘, Dijkstra 알고리즘, RRT, DWA 등 다양한 경로 계획 알고리즘이 존재한다. 이러한 알고리즘들은 각각의 환경과 요구에 맞춰 최적의 경로를 찾아 로봇이 안전하고 효율적으로 목표를 향해 이동할 수 있도록 돕기 때문에 각 환경에 따른 적용이 필요하다. 간단하게 알아도 따와서 적용하는 건 가능하겠지만 기능들을 세밀하게 커스텀하거나 연구하려면 조금 더 심층적인 탐구가 필요할 것 같다.
향후에는 더욱 발전된 알고리즘과 인공지능(AI) 기술을 통해 실시간으로 환경을 인식하고 더 복잡한 경로를 계획할 수 있는 로봇 네비게이션 시스템이 등장할 것으로 기대된다. 온디바이스 AI 기술이 발전하는 등의 변화가 있다면 더 선택지는 넓어질 것이다.!
