来源：DeepMind

编辑：小匀

你是不是也经历过这样的故事？计划着和女友约会，按照地图预计的实时路况做准备，可是却往往不太准时……

眼看着上班就要迟到，明明显示会在10分钟后到达的公交车，并没有如期而至……

如果您是拼车服务的司机，地图还会获取接送时间信息，并依据此来估计价格。

全世界都有类似的烦恼。预估到达时间（ETA）准确率低，就是上述烦恼的原因。

ETA为什么低？

谷歌地图也有一套预测算法。但毕竟世界是动态的，每天的状况都有可能不同，特别是疫情期间。

例如，尽管上下班高峰时间都会发生在早上、晚上，但具体的确切时间可能每天、每月都有很大差异；一条小巷的拥堵，就会蔓延到下一个大路——这一点，地图往往无法实时监控；另外，道路质量、限速、事故和封路等因素，都会给预测模型带来麻烦。

近日，DeepMind宣布帮「兄弟一把」——与谷歌地图展开合作，利用了一种图神经网络（GNN），成功提升了谷歌地图在柏林、东京、悉尼等大城市的实时 ETA 准确率，最高提升了50%。

DeepMind此次的研究，就是如何解决这个动态预测问题。

把道路划片处理

道路网（road network），指的是在一定区域内，由各种道路组成的相互联络、交织成网状分布的道路系统，类似下图这样：

但这样的数据太庞大了，于是，谷歌地图将道路网划分为几个「超级路段」。超级路段就是指几个相邻的路段，因为这些路段的交通流会互相影响。

目前，谷歌Maps交通预测系统由以下部分组成：

(1)路由分析器，以构建超路段

(2)新GNN 模型，利用多个目标函数进行优化，能够预测每个超级路段的行程时间。

确定最优路线及其出行时间的模型架构

解决架构问题

研究人员要面对一个挑战：架构问题。

利用现有的交通系统，特别是已有的道路网分割和实时数据 pipeline，全连接神经网络模型表现良好。但是，每个超级路段都需要单独训练神经网络模型。

要想实现大规模部署，则必须训练数百万个这样的模型，这就对基础设施构成了巨大的挑战。

因此，该团队开始研究能够处理可变长度序列的模型，例如循环神经网络（RNN）。但是，向 RNN 添加来自道路网络的结构也不是容易的事。

最后，研究者决定用图神经网络。在对交通情况进行建模时，车辆如何穿过道路网络是该研究的关注点，而图神经网络可以对网络动态和信息传播进行建模。

该团队提出的模型将局部道路网络视为一个图，其中每个路段对应一个节点，连接两个路段（节点）的边要么在同一条道路上，要么通过交叉点（路口）连接。

在训练过程中动态调整图神经网络的学习速率，以使系统学习自己的最佳学习速率时间表。根据DeepMind的说法，通过在训练过程中自动调整学习率，该模型不仅表现优异，还学会了自动降低学习率。

实验表明，似乎范围越大，预测能力越强。例如，考虑小路上的拥堵状况对大路交通情况的影响。通过跨越多个交叉路口，该模型能够预测转弯处的延误、并道引起的延误，以及走走停停交通状况的通行时间。

但每个超级路段的长度和复杂度可能各有不同（从简单的两段路到包含了数百个节点的较长路径），但它们都可以使用同一个图神经网络模型进行处理。

DeepMind与谷歌地图团队的合作，延续了该实验室与谷歌产品部门的其他合作，包括努力改进谷歌Play Store的发现系统。除了谷歌，DeepMind还贡献了算法、框架和方法论来支持Waymo的自动驾驶系统。

参考链接：

https://venturebeat.com/2020/09/03/deepmind-claims-its-ai-improved-google-maps-travel-time-estimates-by-up-to-50/

https://deepmind.com/blog/article/traffic-prediction-with-advanced-graph-neural-networks