—
Ep.8
보행자길 — 숲길 경로 개발,
멀티모달 경로 탐색 구현을 위한 구성요소 및 방법
멀티모달 경로 탐색이란 서로 다른 속성을 가진 도로의 경로 탐색 결과를 통합해 사용자에게 하나의 경로 결과를 제공하는 기술입니다.
멀티모달 경로 탐색을 가장 쉽게 접할 수 있는 서비스로는 집에서 회사까지의 대중교통 경로를 탐색하는 경우를 예로 들 수 있습니다.
— 집에서 집 앞 버스정류장까지의 도보 경로
— 버스 승차 위치에서 버스 하차 위치까지의 대중교통 경로
— 버스 정류장에서 회사까지의 도보 경로를 통합하여 제공
이번 글에서는 아이나비시스템즈가 보유하는 다양한 도로 정보 중, 보행자길과 숲길 네트워크 간의 연결성을 확보하고 경로 탐색 결과를 통합하는 방법에 대해 이야기하고자 합니다.
기반 설명을 간단히 하자면, 경로 탐색이란 링크와 노드로 구성된 데이터에서 지정된 두 지점을 최소의 비용으로 연결하는 기술입니다.
- 링크는 실 세계의 길(도로)이며, 길이와 너비(차선), 종류(레벨)을 비롯한 다양한 속성을 가진 정보입니다. 하나의 링크는 반드시 노선을 통해 다른 링크와 연결되어 있습니다.
- 노드는 실 세계의 도로 분기점이며, 교차로 또는 도로 속성이 변경되는 지점(교량, 고가 등의 시/종점)으로 설명할 수 있습니다. 분기점에는 하나 이상의 길이 연결되어 있으며, 연결된 모든 길은 상황에 따라 통행이 가능 할 수도 있고, 통행이 불가능 할 수도 있습니다. 노드는 반드시 한 개 이상의 링크와 연결되어 있습니다.
- 경로 탐색은 실 세계의 다양한 도로 정보를 링크와 노드로 이해하고 구성되며, 도로 네트워크 정보는 데이터 간 서로 연결성을 가지고 있습니다.
- 아이나비시스템즈에서는 이러한 도로 네트워크를 실 세계와 최대한 유사하게 정의하기 위해 노력하고 있으며, 새로운 도로에 대한 신규 작업과 변화 감지에 대한 업데이트에 신속하게 대응하고 있습니다.
도로 네트워크 데이터는 데이터화가 가능한 모든 정보를 포함하고 있으며, 이는 서로 다른 목적의 도로를 하나의 데이터로 묶어 관리하기 어려운 이유입니다.
아이나비시스템즈에서는 차량의 안전한 주행 안내를 위해 일찍이 내비게이션을 개발하고, 자율주행을 위한 HD Map에 관한 활발한 연구를 진행하고 있습니다. 이를 통해 차량 도로 데이터와 경로 탐색 및 안내를 위한 방대한 데이터를 보유하고 있으나, 차량 이외의 도로에서는 이보다 단순한 데이터만으로도 충분한 서비스를 제공할 수 있는 경우가 많습니다. 보행자 도로나 자전거, 숲길 도로는 차량 도로에 비해 적은 양의 데이터로도 충분한 경로 탐색 결과를 기대할 수 있으며, 안내를 위한 최소한의 정보만으로도 유용한 기술을 선보일 수 있습니다.
그러나, 차도를 포함한 보행자/숲길 도로들은 각각의 정보를 유지하기 위한 속성뿐만 아니라 정보의 양에서도 차이가 발생합니다. 이 때문에 성질이 다른 여러 도로 데이터를 단일 구조로 구성하지 않고, 기본적인 정보 외에는 서로 다른 데이터 포맷으로 구성/관리하고 있습니다. 이는 현재까지도 차량에서 도보, 도보에서 숲길을 통합하여 경로 탐색하고 안내해 주는 내비게이션이 없는 이유입니다.
하지만 차량-도보-숲길 통합 경로 탐색 기술을 필요로 하는 서비스 분야는 점점 늘어나고 있으며, 개인용 모빌리티 기술이 발달함에 따라 기존 서비스들도 다양한 고객 요구 충족을 위한 신규 서비스를 준비하고 있습니다. 이러한 시장 움직임에 발맞춰, 아이나비시스템즈는 카카오VX와 함께 보행자-숲길 네트워크를 활용한 서비스를 준비 중입니다.
이번 글에서는 숲길과 보행자길을 연결하고 경로를 제공하는 기술 내용을 소개하고자 합니다. 소개되는 기술은 설명된 서비스에만 국한되지 않고 차량/도보/이륜차 및 이 외 특수 상황에서의 네트워크 연계를 위한 기술에도 동일하게 적용될 수 있습니다.
서로 다른 네트워크 데이터를 연결하고 경로를 탐색하기 위해서는 우선 두 데이터 간 동일성을 갖는 데이터를 확보해야 합니다. 실제 숲길과 보행자길은 산길 입구라는 정보를 가지고 있으며, 보행자길과 숲길이 연결되는 지점 정보를 가지고 있습니다. 우리는 이 정보를 입구점이라고 부르도록 하겠습니다.
입구점에는 두 개 이상의 상이한 네트워크 간 연결성을 확보하기 위한 정보가 있으며, 우리는 이를 위해 보행자길과 숲길 각각의 노드 정보를 함께 포함하도록 구성했습니다. 즉, 하나의 입구점에는 이 지점을 지나는 숲길 노드와 보행자 노드 정보가 하나씩 존재하며, 이 정보를 통해 숲길에서 보행자길을, 보행자길에서 숲길을 인지하고 각각의 경로 탐색 결과를 공유할 수 있는 정보로 사용하고 있습니다.
멀티모달 경로 탐색을 위해서는 네트워크의 특징을 파악하고 그에 맞는 탐색 절차를 구성해야 합니다.
- 보행자 네트워크는 모든 링크 간 연결성에 끊어짐이 없음을 보장합니다. (단, 섬 지역(제주도 등)은 네트워크 단절이 있을 수 있음)
- 숲길 네트워크는 모든 링크 간 연결성을 보장하지 않지만, 개별 숲 정보를 구성하는 네트워크는 반드시 보행자 네트워크와의 입구점을 하나 이상 가지고 있음을 보장합니다.
(서로 다른 숲은 네트워크가 단절되어 있음) - 입구점은 반드시 보행자길과 숲길의 노드 정보로 구성되어 있음을 보장합니다.
위 탐색 절차에 의해 멀티모달 경로 탐색을 수행할 수 있는 경우는 다음과 같습니다.
- 보행자길 -> 숲길
- 숲길 -> 보행자길
- 숲길 -> 숲길 (연결되지 않은 서로 다른 숲길 네트워크 간)
이 글에서는 경로 탐색 수행에 있어 출발지와 목적지 간 탐색만을 대상으로 설명합니다. 경유지 기능은 기본 탐색인 출발지 — 목적지 탐색의 연속이기에 이 글에서는 생략합니다.
- Ex) 출발지 — 경유지 — 목적지의 경우: 출발지 — 목적지(경유지) 경로탐색 1회, 출발지(경유지) -> 목적지 경로 탐색 1회의 반복 수행
또한, 한가지 네트워크 데이터로 수행 가능한 보행자 — 보행자, (동일 네트워크의) 숲길 — 숲길 간 경로 탐색 또한 생략하도록 하겠습니다.
멀티모달 경로 탐색을 위해 링크 선형이 너무 복잡하지 않고, 설명이 쉬운 숲길 네트워크인 독립문 근처의 안산(숲길)과 그 인근을 예시로 설정하겠습니다.
해당 지형의 보행자길, 숲길, 입구점 데이터의 구성은 아래와 같습니다.
멀티 모달 경로를 위해 보행자길, 숲길의 경로 탐색 시 각 경로 탐색은 하나의 출발지가 여러 목적지를 가질 수 있는 다중 목적지 탐색을 지원하도록 합니다. 이 때의 출발지는 사용자가 설정한 출발지 및 목적지가 되며, 이에 연결될 입구점들이 목적지가 됩니다.
또한, 다중 목적지로 설정될 최대 입구점(=최대 다중 목적지) 개수는 최적의 경로 탐색 결과를 도출하기 위한 값으로 정의합니다. 예를 들어 국립 공원 등의 숲길은 수천개의 입구점을 보유하기 때문에 설정된 출/도착지와의 관계를 고려하여 최대 입구점 개수의 한정이 필요합니다. 이 글을 위한 예시 경로 탐색에서는 100개의 입구점을 최대치로 한정합니다.
1. 보행자길 → 숲길 경로 탐색
1.1 숲길 경로 탐색 수행
— 목적지와 매칭되는 숲길 링크 선정
— 선정된 숲길 링크를 출발지로 정의하고 역방향 경로 확장 시작
— 확장된 링크의 노드 정보와 주변의 입구점 정보 비교
— 확장된 링크의 노드가 입구점 정보의 숲길 노드와 일치할 경우, 해당 탐색 경로 정보(탐색된 링크열 등) 등록
— 모든 링크의 확장이 완료되거나 지정된 입구점 개수 초과 시, 경로 확장 종료
1.2 보행자길 경로 탐색 수행
— 출발지와 매칭되는 보행자길 링크 선정
— 1.1에서 탐색 된 입구점 정보를 목적지로 선정하고, 목적지 목록 관리
— 경로 확장 시작
— 확장된 링크의 노드가 목적지로 선정된 입구점 목록의 보행자길 노드 정보와 일치하는지 확인
— 확장 정보가 입구점 노드와 일치하는 경우, 탐색 된 경로 정보 등록
— 모든 입구점 정보와 매칭이 완료될 때까지 확장을 진행하고, 매칭이 완료되면 경로 확장 종료
1.3 보행자 경로와 숲길 경로 조합
— 1.2 보행자 경로 탐색 결과와 1.1숲길 경로 탐색 결과 중 동일한 입구점을 가지는 각각의 경로 확장 코스트를 연산하여, 가장 작은 코스트를 가지는 각각의 경로 정보 추출
— 추출된 경로 정보를 출발지 — 입구점 — 도착지 배열에 맞도록 순서 정렬하고, 하나의 경로 정보로 완성
2. 숲길 → 보행자길 경로 탐색
2.1 숲길 경로 탐색 수행
— 출발지와 매칭되는 숲길 링크 선정
— 선정된 링크를 출발지로 정의하고 경로 확장 시작
— 확장된 링크의 노드가 입구점 정보와 일치할 경우, 해당 입구점 정보와 출발지로부터 탐색 된 경로 정보 등록
— 모든 링크의 확장이 완료되거나 지정된 입구점 개수 초과 시, 경로 확장 종료
2.2 보행자길 경로 탐색 수행
— 목적지와 매칭되는 보행자길 링크 선정
— 2.1에서 탐색 된 입구점 정보를 목적지로 선정하고, 목적지 목록 관리
— 선정된 링크를 출발지로 정의하고 역방향 경로 확장 시작
— 확장된 링크의 노드가 목적지로 선정된 입구점 목록의 보행자길 노드 정보와 일치하는지 확인
— 확장 정보가 입구점 노드와 일치하는 경우, 탐색 된 경로 정보를 등록
— 모든 입구점 정보와 매칭이 완료될 때까지 확장을 진행하고, 매칭이 완료되면 경로 확장 종료
2.3 숲길 경로와 보행자 경로 조합
— 2.1 숲길 경로 탐색 결과와 2.2의 보행자길 경로 탐색 결과 중 동일한 입구점을 가지는 각각의 경로 확장 코스트를 연산하여, 가장 작은 코스트를 가지는 각각의 경로 정보 추출
— 추출된 경로 정보를 출발지–입구점-도착지 배열에 맞도록 순서 정렬하고, 하나의 경로 정보로 완성
3. 숲길1 → 숲길2 경로 탐색
3.1 출발지/목적지 숲길 경로 탐색 수행
— 출발지/목적지와 매칭되는 숲길 링크 선정
— 숲길1에 선정된 링크를 출발지로 정의하고 경로 확장 시작
— 숲길2에 선정된 링크를 출발지로 정의하고 역방향 경로 확장 시작
— 확장된 링크의 노드가 입구점 정보와 일치할 경우, 해당 입구점 정보와 출발지로부터 탐색 된 경로 정보 등록
— 모든 링크의 확장이 완료되거나 지정된 입구점 개수 초과 시, 경로 확장 종료
3.2 보행자길 경로 탐색 수행
— 3.1에서 탐색 된 숲길1의 입구점들을 출발지로 선정
— 3.1에서 탐색 된 숲길2의 입구점들을 목적지로 선정
— 다중 출발지/다중 목적지 경로 탐색 수행
— 탐색 완료된 경로를 다중 탐색 결과 목록으로 등록
— 모든 출발/목적지에 대한 경로 탐색 결과가 완료되면 경로 탐색 종료
3.3 숲길 — 보행자길 — 숲길 경로 조합
— 3.1의 숲길1 경로와 3.2의 보행자 경로, 그리고 3.1의 숲길2 경로 결과를 연산하여, 코스트가 가장 작은 경로를 최종 경로 결과로 선정
— 추출된 경로 정보를 출발지–입구점-입구점–도착지 배열에 맞도록 순서 정렬하고, 하나의 경로 정보로 완성
이상으로 보행자길과 숲길의 이종 네트워크 간 경로를 탐색하고, 결과를 통합하여 하나의 경로로 제공하는 멀티모달 경로 탐색 기술에 대해 설명을 마치겠습니다.
이 글은 보행자 — 숲길 간 등산 경로에 대해 예를 들어 작성했습니다. 현재 보행자길/숲길에는 도보, 등산로 속성뿐만이 아닌 자전거, 둘레길, 종주길(테마길) 등 다양한 정보가 있고 이를 활용해 유용한 정보로 제공할 수 있도록 계속해서 개발 중입니다.
다양한 활용 사례로, 도보 또는 자전거로 국토 장정을 준비하는 사용자에게 최적의 경로 계획을 제공할 수 있습니다. 차량과 도보 숲길으 연계하여 집에서 국립공원 주차장까지의 차량 정보, 주차장에서 가장 가까운 숲길까지의 도보 경로, 산 정상을 등산하고 복귀하는 숲길 경로를 통합하여 제공할 수 있습니다. 또한 대중교통 경로를 반영하여 집 — 버스 — 테마길(시점) — 테마길(종점) — 버스 — 집 등의 코스를 제공할 수도 있습니다.
이외에도 현재 준비 중인 건물 내 네트워크와 로봇을 연계하여, 실내 — 외 경로를 제공한다면 로봇 배셩 서비스를 제공할 수 있고, 드론 주행 가능 네트워크를 구성하여 연계한다면 무인 항공 서비스로도 쉬운 연계가 가능합니다.
이렇듯 아이나비시스템즈는 기술의 한계를 정하지 않고 보다 편리하고 안전한 경로 서비스를 제공하기 위해 부단히 노력하며 전진하고 있습니다.
—
by 아이나비시스템즈 경로기술개발팀
참조1. ITS 국가교통센터 링크/노드 개념 소개
https://www.its.go.kr/nodelink/
