Google Maps是使用最廣泛的地圖app之一，其能預(yù)測(cè)交通情況的能力使其成為許多司機(jī)不可或缺的工具。近日，DeepMind宣布與其合作，幫助Google Maps變得更準(zhǔn)確。

你是不是也經(jīng)歷過(guò)這樣的故事?計(jì)劃著和女友約會(huì)，按照地圖預(yù)計(jì)的實(shí)時(shí)路況做準(zhǔn)備，可是卻往往不太準(zhǔn)時(shí)……

眼看著上班就要遲到，明明顯示會(huì)在10分鐘后到達(dá)的公交車，并沒(méi)有如期而至……

如果您是拼車服務(wù)的司機(jī)，地圖還會(huì)獲取接送時(shí)間信息，并依據(jù)此來(lái)估計(jì)價(jià)格。

全世界都有類似的煩惱。預(yù)估到達(dá)時(shí)間(ETA)準(zhǔn)確率低，就是上述煩惱的原因。

ETA為什么低?

谷歌地圖也有一套預(yù)測(cè)算法。但畢竟世界是動(dòng)態(tài)的，每天的狀況都有可能不同，特別是疫情期間。

例如，盡管上下班高峰時(shí)間都會(huì)發(fā)生在早上、晚上，但具體的確切時(shí)間可能每天、每月都有很大差異;一條小巷的擁堵，就會(huì)蔓延到下一個(gè)大路——這一點(diǎn)，地圖往往無(wú)法實(shí)時(shí)監(jiān)控;另外，道路質(zhì)量、限速、事故和封路等因素，都會(huì)給預(yù)測(cè)模型帶來(lái)麻煩。

近日，DeepMind宣布幫「兄弟一把」——與谷歌地圖展開(kāi)合作，利用了一種圖神經(jīng)網(wǎng)絡(luò)(GNN)，成功提升了谷歌地圖在柏林、東京、悉尼等大城市的實(shí)時(shí) ETA 準(zhǔn)確率，最高提升了50%。

DeepMind此次的研究，就是如何解決這個(gè)動(dòng)態(tài)預(yù)測(cè)問(wèn)題。

把道路劃片處理

道路網(wǎng)(road network)，指的是在一定區(qū)域內(nèi)，由各種道路組成的相互聯(lián)絡(luò)、交織成網(wǎng)狀分布的道路系統(tǒng)，類似下圖這樣：

但這樣的數(shù)據(jù)太龐大了，于是，谷歌地圖將道路網(wǎng)劃分為幾個(gè)「超級(jí)路段」。超級(jí)路段就是指幾個(gè)相鄰的路段，因?yàn)檫@些路段的交通流會(huì)互相影響。

目前，谷歌Maps交通預(yù)測(cè)系統(tǒng)由以下部分組成：

(1)路由分析器，以構(gòu)建超路段

(2)新GNN 模型，利用多個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化，能夠預(yù)測(cè)每個(gè)超級(jí)路段的行程時(shí)間。

確定最優(yōu)路線及其出行時(shí)間的模型架構(gòu)

解決架構(gòu)問(wèn)題

研究人員要面對(duì)一個(gè)挑戰(zhàn)：架構(gòu)問(wèn)題。

利用現(xiàn)有的交通系統(tǒng)，特別是已有的道路網(wǎng)分割和實(shí)時(shí)數(shù)據(jù) pipeline，全連接神經(jīng)網(wǎng)絡(luò)模型表現(xiàn)良好。但是，每個(gè)超級(jí)路段都需要單獨(dú)訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型。

要想實(shí)現(xiàn)大規(guī)模部署，則必須訓(xùn)練數(shù)百萬(wàn)個(gè)這樣的模型，這就對(duì)基礎(chǔ)設(shè)施構(gòu)成了巨大的挑戰(zhàn)。

因此，該團(tuán)隊(duì)開(kāi)始研究能夠處理可變長(zhǎng)度序列的模型，例如循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)。但是，向 RNN 添加來(lái)自道路網(wǎng)絡(luò)的結(jié)構(gòu)也不是容易的事。

最后，研究者決定用圖神經(jīng)網(wǎng)絡(luò)。在對(duì)交通情況進(jìn)行建模時(shí)，車輛如何穿過(guò)道路網(wǎng)絡(luò)是該研究的關(guān)注點(diǎn)，而圖神經(jīng)網(wǎng)絡(luò)可以對(duì)網(wǎng)絡(luò)動(dòng)態(tài)和信息傳播進(jìn)行建模。

該團(tuán)隊(duì)提出的模型將局部道路網(wǎng)絡(luò)視為一個(gè)圖，其中每個(gè)路段對(duì)應(yīng)一個(gè)節(jié)點(diǎn)，連接兩個(gè)路段(節(jié)點(diǎn))的邊要么在同一條道路上，要么通過(guò)交叉點(diǎn)(路口)連接。

在訓(xùn)練過(guò)程中動(dòng)態(tài)調(diào)整圖神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)速率，以使系統(tǒng)學(xué)習(xí)自己的最佳學(xué)習(xí)速率時(shí)間表。根據(jù)DeepMind的說(shuō)法，通過(guò)在訓(xùn)練過(guò)程中自動(dòng)調(diào)整學(xué)習(xí)率，該模型不僅表現(xiàn)優(yōu)異，還學(xué)會(huì)了自動(dòng)降低學(xué)習(xí)率。

實(shí)驗(yàn)表明，似乎范圍越大，預(yù)測(cè)能力越強(qiáng)。例如，考慮小路上的擁堵?tīng)顩r對(duì)大路交通情況的影響。通過(guò)跨越多個(gè)交叉路口，該模型能夠預(yù)測(cè)轉(zhuǎn)彎處的延誤、并道引起的延誤，以及走走停停交通狀況的通行時(shí)間。

但每個(gè)超級(jí)路段的長(zhǎng)度和復(fù)雜度可能各有不同(從簡(jiǎn)單的兩段路到包含了數(shù)百個(gè)節(jié)點(diǎn)的較長(zhǎng)路徑)，但它們都可以使用同一個(gè)圖神經(jīng)網(wǎng)絡(luò)模型進(jìn)行處理。

DeepMind與谷歌地圖團(tuán)隊(duì)的合作，延續(xù)了該實(shí)驗(yàn)室與谷歌產(chǎn)品部門的其他合作，包括努力改進(jìn)谷歌Play Store的發(fā)現(xiàn)系統(tǒng)。除了谷歌，DeepMind還貢獻(xiàn)了算法、框架和方法論來(lái)支持Waymo的自動(dòng)駕駛系統(tǒng)。