길찾기, 경로 보정의 핵심 OSRM 톺아보기

OSRM이란

osrm-backend

오픈 소스 라우팅 머신의 약자로 OpenStreetMap(OSM) 데이터를 활용해서 경로를 찾아주는 라우팅 엔진이다.

 

라우팅 엔진은 두 지점 간의 최적 경로를 계산하는 소프트웨어로 지도 데이터를 그래프 자료구조로 변환하고 최단 경로 알고리즘을 적용해 경로를 찾는다.

 

우아한형제들, 네이버 등 빅테크 기업에서도 해당 엔진을 활용할만큼 대중적으로 사용되고 있으며, 오픈 소스인만큼 무료이고 커스터마이징이 자유롭다는 장점이 있다. 또한, C++이기에 굉장히 빠른 속도로 경로 계산을 수행할 수 있다.

 

Valhalla나 GraphHopper 같은 대체제가 존재하지만 OSRM이 한국 내에서 사용 사례가 많고, 문서화도 잘 되어있다.

 

Contraction Hierarchies

OSRM이 빠른 이유는 C++인 것도 있지만, 가장 큰 핵심은 Contraction Hierarchies(CH) 알고리즘을 사용하기 때문이다. 일반적으로 다익스트라는 모든 노드에 대해서 탐색하지만, 해당 알고리즘은 도로망을 계층적으로 구조화하여 중요한 간선도로를 우선 탐색한다.

 

예를 들어 서울 -> 부산까지의 경로를 찾을 때 모든 길에 대해서 탐색하는게 아니라 고속도로 -> 국도 -> 지방도로 순으로 계층적 탐색을 수행한다. 이를 통해 탐색 공간을 대폭 줄여 밀리초 단위 응답이 가능하다.

 

이러한 알고리즘을 활용하려면 OSM 데이터를 그대로 활용할 순 없고, 반드시 데이터 전처리 과정을 거쳐야 한다.

 

데이터 전처리

전처리 과정은 다음 3가지로 이루어진다.

1. osrm-extract: OSM PBF 파일에서 도로 네트워크만 추출
2. osrm-contract: Contraction Hierarchies 그래프로 변환
3. osrm-routed: 전처리된 데이터로 서버 실행

이 과정이 필요한 이유는 OSM 데이터 원본이 수십 GB에 해당하기에 매번 요청 시마다 전처리 작업을 수행할 수 없기 때문이다. 전처리 과정을 통해 최적화된 그래프를 메모리에 미리 올려두면 동일한 쿼리를 수 밀리초 안에 처리할 수 있게 되는 것이다.

 

OSRM Service API

OSRM에서는 최적 경로 계산 뿐만 아니라 여러 RESTful API를 제공하고 있다. 요청 시 profile을 지정하여 보낼 수 있는데, 각각은 foot, car, bike로 구성되어 있다. 이름에서 보이듯이 도보와 차량 그리고 자전거로 갈 수 있는 도로에 맞게 응답해준다.

 

런세권에서는 주로 두 개의 API를 활용하고 있다.

1. Route API
두 지점 간의 최단 경로를 계산하는 핵심 API이다.

GET /route/v1/{profile}/{coordinates}

ex. GET /route/v1/foot/127.0276,37.4979;127.0476,37.5139

 

위와 같이 OSRM를 띄운 서버에 요청하면, 최적 경로를 계산해준다. 최적 경로 계산은 앞서 얘기한 Contraction Hierarchies 알고리즘을 활용한다.

 

해당 API는 다음과 같이 동작한다.

1. 입력받은 좌표를 가장 가까운 도로로 이동
2. 출발지, 도착지 노드를 전처리된 CH 그래프에서 찾는다.
3. 출발지에서 도착지로, 도착지에서 출발지로 동시에 탐색을 시작한다.
4. 계층 구조를 따라 상위 계층(고속도로 등)으로 빠르게 이동한다.
5. 두 탐색이 만나는 지점에서 최단 경로를 확정한다.

여기서 계층 구조라는 말이 잘 이해가 되지않아 더 찾아보았다.

이전에 데이터 전처리 과정에서 각 도로 노드는 레벨을 가진다. 이는 '축약' 과정에서 부여되는 것인데, 보통 골목길 -> 지방도로 -> 국도 -> 고속도로 순으로 높은 레벨을 갖게된다.

 

축약이란, 각 노드의 Edge Difference를 계산하여 가장 작은 노드부터 해당 노드를 지나는 최단 거리가 있는 경우 shortcut을 추가하는 과정이다. Edge Difference는 특정 노드를 축약했을 때 생기는 shortcut 개수 - 제거될 edge 개수이며 이 값이 작을수록 그래프가 단순해진다. 즉, 먼저 축약된다.

    2km        2km 
A -------- B -------- C
\                    / 
 \------ 5km -------/

이처럼 A -> C로 가는 방법이 B를 거쳐가는 방법과 직접 가는 방법이 있다고 할 때 B를 거쳐가는 방법이 4km로 더 짧다. 따라서 B를 축약할 때 B를 거치는 최단 경로를 보존하기 위해 A->C shortcut을 추가한다.

    2km        2km 
A -------- B -------- C
\                    / 
 \------ 5km -------/
  \----- 4km ------/

위의 그림처럼 만들어 두는 것이다. 이런식으로 모든 노드들을 축약하여 중요한 경로들을 shortcut으로 저장해두고 나중에 경로 계산에 이용한다.

 

프로젝트에서도 해당 Service API를 활용하고 있는데, 사용자의 위치를 기준으로 러닝 코스와 가장 가까운 점을 찾아 최적 경로로 길찾기를 제공해주고 있다.

 

2. Match API

GPS 궤적 데이터를 실제 도로에 매칭시키는 API이다. 각 좌표와 정밀도를 입력받아 가장 가능성이 높은 경로를 찾아 반환해준다.

GET /match/v1/{profile}/{coordinates}?timestamps={timestamps}

ex. GET /match/v1/foot/127.027,37.497;127.028,37.498;127.029,37.499 ?timestamps=1701234567;1701234577;1701234587 &overview=full&geometries=geojson

해당 API의 핵심 로직은 '은닉 마르코프 모델(Hidden Markov Model/HMM)'을 기반으로 한 Viterbi 알고리즘을 이용해 구현된다. 해당 알고리즘의 동작은 다음과 같이 이뤄진다.

1. 각 GPS 좌표마다 반경 내의 가능한 도로 지점들(후보)을 찾는다.
2. 각 후보에 대해 방출 확률과 전이 확률을 계산한다.
3. Viterbi 알고리즘으로 가장 확률이 높은 경로를 선택한다.

구체적으로 '은닉 마르코프 모델'에 대해 설명하면 아래와 같다.

실제 도로: Road1 -------- Road2 -------- Road3 
          |               |             | 
        GPS1            GPS2           GPS3 
       (관측값)          (관측값)         (관측값) 

GPS1은 Road1 근처에서 측정 GPS2는 Road2에서 멀리 튐 GPS3은 Road3 근처에서 측정 

문제: GPS2가 실제로는 어느 도로에 있었을까?

즉, 관측값을 보고 가장 가능성 높은 숨겨진 상태(실제 있었던 도로 위치)를 찾는 것이다. 이는 확률로 기반하여 찾는다.

 

• 방출 확률 (Emission Probability)

특정 도로 위에 특정 좌표가 발견될 확률이다.

 

간단하게 설명하면 수학적 계산을 통해 확률을 구하고, 이 값이 클수록 가능성이 높다고 판단한다. 영향을 주는 변수로는 GPS 좌표의 정확도와 도로와 좌표 사이의 거리가 있다.

 

• 전이 확률 (Transition Probability)

이는 이전 도로 지점에서 현재 도로 지점으로 이동했을 확률을 구하는 것이다.

 

실제 도로를 따라 이동한 거리와 주어진 좌표 간 직선 거리를 비교한다. 두 값의 차이가 작을수록 높은 확률을 가진다.

 

프로젝트에서는 해당 API를 이용해 도로에 정확하게 매핑되지 않은 러닝 코스 좌표들을 수정하기 위해서 사용하고 있다.