그리드×도로 네트워크, 하이브리드 경로탐색 엔진 개발기
장애물과 도로 네트워크를 함께 고려하는 법
—
Ep.29
경로 탐색 기술은 게임 개발부터 내비게이션 시스템, 로봇 자율 주행, 드론 물류 시스템 등 다양한 분야의 핵심적인 기술입니다. 일반적으로 경로 탐색 기술은 크게 두 가지 접근 방식이 널리 사용되었습니다.
1. 그리드 기반(Grid-based) 경로 탐색
지도 환경을 2D 격자(Grid)로 나누고, 각 셀(Cell)을 탐색하면서 장애물을 회피하고 최단 경로를 탐색
대표 알고리즘: BFS(Breadth-First Search, 너비 우선 탐색), DFS(Depth-First Search, 깊이 우선 탐색), A*(A-star) 등
장점: 장애물 환경에 유연하고, 임의의 공간에서도 동작 가능
단점: 격자는 인공적인 구조라, 실제 도로 네트워크를 이용한 주행 궤적과 다르게 비현실적 경로 발생 가능성 있음
2. 도로 네트워크 기반(Road-network-based) 경로 탐색
실제 도로망(노드 = 교차점, 링크 = 도로)을 그래프 형태로 모델링하고, 최적 경로를 탐색
대표 알고리즘: Dijkstra’s Algorithm(다익스트라 알고리즘), A*(A-star) 등
장점: 빠르고 정확한 도로 경로 탐색 가능
단점: 도로 외부(예: 주차장 내부, 공터 등)에서는 적용하기 어려움
하지만, 실제 현실 세계의 경로 탐색 응용에서는 이 두 가지 상황이 동시에 필요할 때가 많습니다. 예를 들어, 자율주행 로봇이 창고 내부(격자 기반 환경)를 지나 도로 네트워크에 합류한 뒤 다시 세부 지역(그리드 기반 환경)으로 들어가야 하는 상황, 또는 도로에 있는 장애물(공사 구간, 위험물 등)을 고려해야 하는 경우에는 기존 방식 중 하나만으로는 부족합니다.
그럼 이제, "대" 아이나비시스템즈의 "최첨단" 경로기술개발팀의 "그리드 경로 탐색과 도로 네트워크 경로 탐색을 혼합한 하이브리드 경로 탐색 엔진"을 설계하고 개발한 경험을 공유해 봅니다.
경로 탐색, 기존 접근 방식의 한계
1. 그리드 기반 탐색의 한계
① 장점
구현이 쉽고 장애물 회피에 유리합니다.
② 단점
실제 도로 네트워크 반영이 어렵고, 격자 크기에 따라 탐색 속도와 정확도가 달라집니다.
복잡한 도시 도로망을 그리드로 모델링하면 "메모리 사용량"과 "탐색 시간"이 기하급수적으로 증가합니다. (예: 서울 도심을 1m 해상도의 그리드로 나누면 수십억 개의 셀이 필요합니다.)
그리드 기반 탐색에서 장애물을 회피하는 A* 알고리즘 예시
2. 도로 네트워크 기반 탐색의 한계
① 장점
실제 도로 정보를 그대로 반영할 수 있습니다.
② 단점
도로 외부(예: 주차장, 창고, 공원, 광장, 건물 내부 등) 공간에서는 도로 네트워크 데이터가 존재하지 않거나 매우 부정확합니다.
로봇이 장애물을 피해 자유롭게 움직여야 하는 영역에서는 도로 네트워크 그래프만으로는 불가능합니다.
도로 네트워크 기반 경로 탐색 예시하이브리드 경로 탐색의 필요성
실제 현실 세계의 경로 탐색 문제는 단순히 도로만 따라가면 해결되지 않습니다.
1. 자율주행 로봇
건물 입구까지 도로를 따라가다가 마지막 50m는 보도블록이나 잔디 위를 지나가야 할 수도 있습니다.
2. 물류/드론 배송
배송 주소지까지 도로 네트워크는 최적이지만, 최종 진입은 비포장 경로나 공터를 통해야 할 수도 있습니다.
3. 자전거/보행자 내비게이션
차량용 도로망 + 인도/공원/지하도까지 고려해야 합니다.
이를 해결하기 위해서는 '그리드 탐색과 도로 네트워크 탐색을 결합한 하이브리드 엔진'이 필요합니다.
도로 네트워크 + 그리드 맵이 혼합된 하이브리드 탐색 개념도하이브리드 경로 탐색 엔진 개념
하이브리드 경로 탐색 엔진은 다음과 같은 '두 가지 경로 탐색 방식을 혼합'합니다.
1. 로컬(Local) 영역
그리드 기반 탐색
주차장, 건물 내부, 비정형 공간 등
A* 알고리즘 기반 그리드 탐색으로 장애물 회피
2. 글로벌(Global) 영역
도로 네트워크 기반 탐색
도시 도로, 고속도로 등
Graph 기반 탐색 (Dijkstra, A* with heuristic)
위와 같은 두 영역을 '스위칭(전환)'하는 모듈을 두고, 필요에 따라 두 알고리즘을 자연스럽게 연결합니다.
하이브리드 경로 탐색 엔진 구조도하이브리드 경로 탐색 엔진 설계
1. 아키텍처 개요
하이브리드 엔진은 크게 3단계의 알고리즘 조합으로 동작합니다.
① 도로 네트워크 탐색
출발지부터 도착지까지 Dijkstra 또는 A* 알고리즘으로 빠른 최적 경로 탐색
② 비도로 구간 탐색
도로망에서 벗어난 영역(공원, 건물, 장애물 등)에 대해서는 A* 기반 그리드 탐색을 수행
③ 경로 결합(Post-processing)
두 탐색 결과를 연결하고 최적화하여 하나의 경로로 제공 (경계 구간은 비용 최소화)
하이브리드 경로 탐색 엔진 아키텍처 설계
1. 시스템 구성
① Grid Planner
장애물 환경에서 A* 기반 탐색 수행
② Graph Planner
도로 네트워크에서 최단 거리 탐색 수행
③ Hybrid Controller
두 Planner 간 전환 관리
④ Map Interface
GIS 데이터 → Grid + Graph 통합
2. 주요 흐름
① 시작 위치가 그리드 환경이면 Grid Planner 실행
② 도로 진입 지점까지의 경로 생성
③ 도로 네트워크로 전환 후 Graph Planner 실행
④ 목적지가 다시 비정형 공간이면 Grid Planner로 전환
경로 탐색 전환 과정 시퀀스 다이어그램3. 핵심 아이디어 - "전환 지점(Transition Point)"
도로 네트워크와 그리드 탐색을 연결하기 위해 전환 지점(Transition Point) 계산이 필요합니다.
① 전환 지점
도로 네트워크와 그리드 영역을 연결하는 접점 (예: 도로와 공원 입구, 인도와 광장 사이 경계 지점)
경로 탐색 시, 도로 네트워크 → 전환 지점 → 그리드 탐색 순서로 이동.
② 전환 지점 계산
Grid에서 Graph로 전환할 때, "가장 가까운 도로 네트워크 노드" 탐색
Graph에서 Grid로 전환할 때, "장애물이나 도로와 연결되지 않은 목적지 근처 도로 노드 → 그리드 좌표 변환"
전환 지점 계산 방식 예시도
아키텍처 구현 및 실험
1. 실험 환경
① 데이터
아이나비시스템즈 도로 네트워크 기반 가상의 도로 네트워크
가상의 도로 네트워크 위치 기반 5m 기준 생성 Grid Map
가상의 장애물
② 알고리즘
Road (Dijkstra + A*)
Grid (A*)
③ 테스트 케이스
순수 도로 탐색
순수 그리드 탐색
하이브리드 탐색
2. 실험 시나리오_첫 번째
출발지 인근 도로망 합류
도로망 탐색 → 목적지 인근 공원
목적지 인근 공원 내부 그리드 탐색으로 최종 목적지 도착
하이브리드 경로 탐색 시뮬레이션 결과 예시 – 도로망 + 공원 경유3. 실험 시나리오_두 번째
출발지 인근 도로망 합류
도로망 탐색 → 장애물 발생 지역
그리드 탐색 → 장애물 회피 도로 진입
그리드 탐색 종료 → 인근 도로망 합류
다시 도로망 탐색으로 최종 목적지 도착
하이브리드 경로 탐색 시뮬레이션 결과 예시 – 도로망 + 장애물 위치 회피4. 성능 비교
활용 사례 및 응용 분야
1. 로봇 내비게이션
건물 입구까지 도로망 → 이후 실내 그리드 탐색
2. 드론 배송
착륙 지점 근처 장애물 회피 + 글로벌 경로 탐색
3. 자전거/보행자 내비게이션
차량 도로망 + 인도/공원 혼합 경로 제공
4. 자율주행차
주차장에서 출발 → 도로 주행 → 목적지 주차장 진입
5. 물류 로봇
창고 내부 경로 탐색 + 외부 도로 주행
결론 및 앞으로의 과제
하이브리드 경로 탐색은 "실제 환경을 더 충실히 반영"하는 접근입니다. 향후 개선 방향 및 과제는 다음과 같습니다.
1. 동적 환경 대응
실시간 교통 정보 및 공사 정보 반영, 움직이는 장애물 반영
2. 다중 모달 경로 탐색
자동차 + 도보 + 자전거 연계 경로
3. 확장성 강화
대규모 지도 데이터(해외 커버리지) 적용
4. 분산 처리
클라우드 기반 대규모 시뮬레이션
5. AI 기반 비용 학습
단순 거리/시간이 아닌, 사용자 선호 기반 최적화
마치며
하이브리드 경로 탐색 엔진의 구현과 실험을 통해 단일한 탐색 방식으로는 현실 세계의 다양한 요구를 모두 해결하기 어렵다는 점을 확인했고, 단순한 알고리즘 비교가 아니라 "실제 환경과 응용에 적합한 엔진 설계"가 중요함을 다시 확인할 수 있었습니다.
그리드 탐색과 도로 네트워크 탐색을 결합한 하이브리드 방식으로 "현실성과 유연성"을 동시에 확보할 수 있었고, 향후 자율주행, 물류, 도보 내비게이션 서비스 등에서 큰 잠재력을 갖는다고 생각합니다.
“도로와 장애물 사이, 그리고 디지털 지도와 현실 세계 사이의 간극을 메우는 것이 하이브리드 경로 탐색의 핵심이다.”
이에, "대" 아이나비시스템즈 "최첨단" 경로기술개발팀은 앞으로도 "자율 주행 이동체의 maneuver Instruction 생성 주체"가 되기 위해 계속해서 나아갈 것입니다.
—
by 아이나비시스템즈 경로기술개발팀 정문규
✨ 하이브리드 경로 탐색 엔진처럼 빠르고 정확한 위치 기반 솔루션, iMPS를 만나보세요!
#경로탐색 #하이브리드경로탐색 #자율주행로봇 #그리드탐색 #도로네트워크 #아이나비 #아이나비시스템즈 #아이나비내비게이션
