2020.09.08

"매일 10억 km 이상 안내, 구글 지도가 최적의 경로를 산출하는 방법은..."

김달훈 | CIO KR
교통 정보 분석을 기반으로 한 최적화된 이동 경로 예측은, 지도 서비스의 핵심적인 기능 중 하나다. 현재 위치와 목적지를 선택하면, 불과 몇 초 만에 최적 경로를 알 수 있다. 빠르면 1-2초 만에 끝나 버리기 때문에 간단한 작업처럼 보이지만 실제 그 이면에서는 수많은 작업이 수행된다.

그렇다면 구글 지도는 어떻게 이동 경로를 결정하고, 이동 시간과 도착 시간을 예측할까? 구글 지도 제품 관리자인 요한 라우(Johann Lau)가 구글 블로그를 통해, 구글 지도가 최적 경로를 계산하고 이동 시간을 예측하는 방법에 대해 다음과 같이 소개했다.


구글 지도에 딥마인드의 머신러닝을 활용한 교통 정보 예측이 적용되면서, 전 세계 주요 도시의 예측 정확도가 개선됐다. (자료 : DeepMind)

구글 지도가 전 세계 사용자들에게 하루 동안 제공하는 이동 거리 안내는 10억 킬로미터 이상이다. 서비스 지역에 있다면, 이동 경로 추천과 교통정보, 예상 이동 시간과 도착 시간 등의 정보와 같은 경로 안내 기능을 활용할 수 있다.

교통량을 분석하고 예측하는 데 필요한 정보나 방법은 다양하고, 이를 활용해 경로를 예측하는 알고리즘도 여럿이다. 구글 지도의 경우는 과거에 수집된 데이터를 기반으로, 시간 경과에 따른 교통 패턴을 먼저 분석한다. 그리고 이렇게 분석한 과거의 교통 패턴에 실시간 교통정보를 결합하고, 이를 활용해 이동 시간과 도착 시간 등을 예측한다.

단순하게 현재의 교통 정보만을 가지고, 운전자가 이동하면서 만나게 될 교통 상황을, 단순하게 예측하는 것이 아니라는 의미다. 바로 과거의 데이터를 기반으로 교통 패턴을 분석하는 단계에서, 구글 지도는 고급 기계학습(Advanced Machine Learning)이라는 아키텍처를 사용한다.

예를 들어 평균 주행 속도가 아침 6~7시 사이에는 80km지만, 늦은 오후가 되면 30~40km로 떨어지는 도로가 있다고 하자. 구글 지도는 이러한 두 가지 데이터 세트를 기반으로, 이 도로 구간에서의 교통 상황과 정보를 머신러닝으로 예측한다. 그리고 이렇게 나온 결과는 실시간 교통 정보와 결합해 최종적인 경로와 시간을 예측하는 것이다.

요한 라우는 “우리의 ETA(Estimated Time of Arrival) 예측은 97%의 정확성을 가질 만큼 정확하다. 최근에는 이러한 교통 예측 기능의 정확성을 더욱더 높이기 위해 알파벳(Alphabet)의 딥마인드(DeepMind)와 협력하고 있다. 이 과정에서 GNN(Graph Neural Networks)을 활용하면서 부정확한 ETA 비율을 더욱 줄일 수 있었다”고 밝혔다.


구글 지도에서 최적의 경로와 이동 시간을 결정하는 데 적용한 모델 아키텍처 (자료 : DeepMind)
 
이렇게 교통 데이터 분석과 예측에 고급 기계학습 기술을 적용하는 것은, 분석 과정이 매우 복잡하고 까다롭다. 예를 들어 출퇴근 시간에 차량 정체가 발생하는 것은 누구나 알지만 정확한 출퇴근 시간은 매일 조금씩 달라질 수 있다. 또한, 도로 상태, 속도 제한, 사고나 공사 등 차량 흐름에 변수가 될 수 있는 조건들은 상당히 많다.

이를 해결하기 위해 딥마인드는 교통량을 공유하는 여러 인접 도로 세그먼트로 구성한 ‘슈퍼 세그먼트(Supersegments)로 도로를 분할했다. 구글 지도의 교통 예측 시스템은 테라바이트의 교통 정보를 처리하여 슈퍼 세그먼트로 구성하는 경로 분석기와 최적화된 경로를 예측하는 새로운 GNN 모델로 구성된다. 이와 관련한 자세한 내용은 딥마인드 블로그에 소개된 ‘향상된 GNN을 활용한 교통 예측’을 참고하면 된다.

아울러 코로나19(COVID-19)가 구글 지도의 교통 정보 예측에까지 영향을 끼쳤다는 점도 공개했다.  코로나19(COVID-19)가 빠르게 확산하면서, 강도 높은 사회적 거리두기나 봉쇄 조치를 내리는 나라가 많아졌다. 이렇게 코로나19가 확산하면서 전 세계 교통량은 최대 50%가 감소했다.

수년간 축적된 신뢰도가 높았던 교통 패턴이 갑작스럽게 바뀐 것이다, 구글 지도와 딥마인드는 이러한 갑작스러운 변화에 대응하기 위해, 갑작스럽게 교통 데이터가 변화한 지역에서는 최근 2~4주 동안의 과거 트래픽 패턴의 우선순위를 높게 하고, 이전의 패턴은 우선순위를 낮추도록 예측 모델을 업그레이드했다. ciokr@idg.co.kr



2020.09.08

"매일 10억 km 이상 안내, 구글 지도가 최적의 경로를 산출하는 방법은..."

김달훈 | CIO KR
교통 정보 분석을 기반으로 한 최적화된 이동 경로 예측은, 지도 서비스의 핵심적인 기능 중 하나다. 현재 위치와 목적지를 선택하면, 불과 몇 초 만에 최적 경로를 알 수 있다. 빠르면 1-2초 만에 끝나 버리기 때문에 간단한 작업처럼 보이지만 실제 그 이면에서는 수많은 작업이 수행된다.

그렇다면 구글 지도는 어떻게 이동 경로를 결정하고, 이동 시간과 도착 시간을 예측할까? 구글 지도 제품 관리자인 요한 라우(Johann Lau)가 구글 블로그를 통해, 구글 지도가 최적 경로를 계산하고 이동 시간을 예측하는 방법에 대해 다음과 같이 소개했다.


구글 지도에 딥마인드의 머신러닝을 활용한 교통 정보 예측이 적용되면서, 전 세계 주요 도시의 예측 정확도가 개선됐다. (자료 : DeepMind)

구글 지도가 전 세계 사용자들에게 하루 동안 제공하는 이동 거리 안내는 10억 킬로미터 이상이다. 서비스 지역에 있다면, 이동 경로 추천과 교통정보, 예상 이동 시간과 도착 시간 등의 정보와 같은 경로 안내 기능을 활용할 수 있다.

교통량을 분석하고 예측하는 데 필요한 정보나 방법은 다양하고, 이를 활용해 경로를 예측하는 알고리즘도 여럿이다. 구글 지도의 경우는 과거에 수집된 데이터를 기반으로, 시간 경과에 따른 교통 패턴을 먼저 분석한다. 그리고 이렇게 분석한 과거의 교통 패턴에 실시간 교통정보를 결합하고, 이를 활용해 이동 시간과 도착 시간 등을 예측한다.

단순하게 현재의 교통 정보만을 가지고, 운전자가 이동하면서 만나게 될 교통 상황을, 단순하게 예측하는 것이 아니라는 의미다. 바로 과거의 데이터를 기반으로 교통 패턴을 분석하는 단계에서, 구글 지도는 고급 기계학습(Advanced Machine Learning)이라는 아키텍처를 사용한다.

예를 들어 평균 주행 속도가 아침 6~7시 사이에는 80km지만, 늦은 오후가 되면 30~40km로 떨어지는 도로가 있다고 하자. 구글 지도는 이러한 두 가지 데이터 세트를 기반으로, 이 도로 구간에서의 교통 상황과 정보를 머신러닝으로 예측한다. 그리고 이렇게 나온 결과는 실시간 교통 정보와 결합해 최종적인 경로와 시간을 예측하는 것이다.

요한 라우는 “우리의 ETA(Estimated Time of Arrival) 예측은 97%의 정확성을 가질 만큼 정확하다. 최근에는 이러한 교통 예측 기능의 정확성을 더욱더 높이기 위해 알파벳(Alphabet)의 딥마인드(DeepMind)와 협력하고 있다. 이 과정에서 GNN(Graph Neural Networks)을 활용하면서 부정확한 ETA 비율을 더욱 줄일 수 있었다”고 밝혔다.


구글 지도에서 최적의 경로와 이동 시간을 결정하는 데 적용한 모델 아키텍처 (자료 : DeepMind)
 
이렇게 교통 데이터 분석과 예측에 고급 기계학습 기술을 적용하는 것은, 분석 과정이 매우 복잡하고 까다롭다. 예를 들어 출퇴근 시간에 차량 정체가 발생하는 것은 누구나 알지만 정확한 출퇴근 시간은 매일 조금씩 달라질 수 있다. 또한, 도로 상태, 속도 제한, 사고나 공사 등 차량 흐름에 변수가 될 수 있는 조건들은 상당히 많다.

이를 해결하기 위해 딥마인드는 교통량을 공유하는 여러 인접 도로 세그먼트로 구성한 ‘슈퍼 세그먼트(Supersegments)로 도로를 분할했다. 구글 지도의 교통 예측 시스템은 테라바이트의 교통 정보를 처리하여 슈퍼 세그먼트로 구성하는 경로 분석기와 최적화된 경로를 예측하는 새로운 GNN 모델로 구성된다. 이와 관련한 자세한 내용은 딥마인드 블로그에 소개된 ‘향상된 GNN을 활용한 교통 예측’을 참고하면 된다.

아울러 코로나19(COVID-19)가 구글 지도의 교통 정보 예측에까지 영향을 끼쳤다는 점도 공개했다.  코로나19(COVID-19)가 빠르게 확산하면서, 강도 높은 사회적 거리두기나 봉쇄 조치를 내리는 나라가 많아졌다. 이렇게 코로나19가 확산하면서 전 세계 교통량은 최대 50%가 감소했다.

수년간 축적된 신뢰도가 높았던 교통 패턴이 갑작스럽게 바뀐 것이다, 구글 지도와 딥마인드는 이러한 갑작스러운 변화에 대응하기 위해, 갑작스럽게 교통 데이터가 변화한 지역에서는 최근 2~4주 동안의 과거 트래픽 패턴의 우선순위를 높게 하고, 이전의 패턴은 우선순위를 낮추도록 예측 모델을 업그레이드했다. ciokr@idg.co.kr

X