自动驾驶轨迹预测算法：NeurIPS挑战赛冠军方案
近日，美团无人车配送中心团队获得NeurIPS 2020 INTERPRET轨迹预测挑战赛Generalizability赛道冠军、Regular赛道亚军。本文主要是算法层面的介绍，希望能给从事相关工作的同学有所帮助或者启发。
01 背景
NeurIPS （Conference on Neural Information Processing Systems） 是机器学习和计算神经科学相关的学术会议，也是人工智能方向的顶级会议。INTERPRET轨迹预测挑战赛（INTERACTION-Dataset-based PREdicTion Challenge）隶属于NeurIPS 2020 Workshop: Competition Track Saturday。该竞赛由UC Berkeley MSC Lab主办，旨在建立一个公共数据集来评估自动驾驶领域各类轨迹预测算法的性能。
02 赛题简介
INTERPRET竞赛共包含两条赛道：Generalizability Track和Regular Track。Generalizability赛道中，测试集轨迹与训练集差异较大（采自不同的场景），且不带有高精地图；而Regular赛道中测试集轨迹分布与训练集相同（采自相同的场景），同时带有高精地图。数据集采自于美国、中国、德国等多个国家，包含并线/变道的高速与城市道路、带停车/让车标志的环形路、无保护左转路口等场景。此外，场景中的障碍物包含行人、自行车和机动车3种类型。
本次竞赛中，参赛队伍需要根据每个障碍物过去1秒（10帧）的运动轨迹，预测出它在未来3秒（30帧）的轨迹。障碍物的轨迹使用离散采样点集合来表示，采样的频率是10赫兹，即每0.1秒采样一个轨迹点。竞赛允许参赛队伍对于每个障碍物输出50条预测轨迹，但只根据最优轨迹（排序第1条）的平均位移误差（Average Displacement Error，ADE）来排名。平均位移误差的计算方式为：
03 算法介绍
Part 1 地图数据处理
由于Generalizability Track和Regular Track数据形式不一致（前者带有高精地图，后者不带高精地图），为保证算法的有效性，我们使用了两种形式来更好地表达场景。如下图1：
在Regular Track中，所有测试集都附带高精地图，我们可以通过查询地图的方式得到任意位置附近的车道线（如图1-左所示，场景中道路拓扑非常完整）；而对于Generalizability Track，测试集没有给出对应的高精地图，无法获取完整的道路结构化信息。对此，我们设计了一种基于地理位置的语义地图来描述非结构化场景下的可行驶区域。基于地理位置的语义地图依赖于场景中障碍物的历史观测轨迹，具体绘制流程主要分为3个步骤：
Part 2 预测模型设计
轨迹预测算法设计过程中通常需要考虑一个重要问题：即在预测时如何建模障碍物与周围环境的复杂交互，这里周围环境通常包含多类交通元素，例如其他交通参与者，路网拓扑，交通信号灯等。
在现有的预测算法中，对障碍物交互的建模方式也不尽相同，例如较早期基于简单位置关系的交互[1-3]，基于语义地图+CNN编码的交互[4-6]，基于（图）注意力机制的交互[7-11]等。随着对障碍物交互认知的加深以及新技术的迭代，轨迹预测算法的精度也在逐步提高。
本次竞赛中，我们提出一种基于混合注意力机制的预测算法，以通用的形式解决两个赛道的预测问题。算法是基于目前主流的图注意力机制，整体设计思路是通过引入混合注意力机制，促使算法更准确地提取障碍物运动特性与车道拓扑特性，同时编码障碍物之间、障碍物与车道间的复杂交互。
上图2是算法的整体结构，整个模型基于主流的Encoder-Decoder结构，包含特征编码网络（Feature Embedding Network）和交互&预测网络（Interaction & Prediction Network）。特征编码网络使用Timewise + Agentwise Attention双注意力机制与双通道GRU对障碍物轨迹和地图信息进行高质量特征强化与时序编码；交互预测网络则使用Agentwise + Conditional Attention双注意力机制建模智能体间交互行为，并输出多模态预测轨迹及其概率。
上述两个网络都是基于混合注意力的图网络，其核心是Enc-MAT和Dec-MAT（Mixture Attention Transformer encoder）模块。Enc-MAT和Dec-MAT是现有BERT-like模型（Transformer encoder）的改进结构，下图3对比了传统Transformer encoder、Enc-MAT和Dec-MAT的区别。
从图3可以看到，相比于传统Transformer encoder，Enc-MAT和Dec-MAT改进并额外新增加了一个注意力通道，混合注意力机制也由此而来。Enc-MAT编码器使用了Timewise和Agentwise混合注意力机制；Dec-MAT编码器则是使用了Agentwise和Conditional（同图3-c中的Distance-base Attention）混合注意力机制。算法使用混合注意力代替原有单注意力机制，目的在于结合实际需求来强化障碍物与环境拓扑的特征表达。图2下半部分展示了三种Attention结构，从计算形式上看，三种注意力方式的计算公式是一致的：
Part 3 轨迹预测流程
首先对符号作一些说明：
编码过程主要包含障碍物历史轨迹编码与场景拓扑编码。以障碍物特征编码为例，流程主要分为两步：
对于道路拓扑的编码也采用相似的方式，但与轨迹编码有两个区别：
解码过程主要包含高层交互和轨迹预测两个阶段。前者采用混合注意力网络Dec-MAT，后者使用基础的MLP实现轨迹与概率的多任务预测。在介绍流程前，我们先阐述两个相对合理的事实：
- 事实1：障碍物运动方向和场景中车道走向存在关联（运动趋势关联）。
- 事实2：障碍物运动更依赖与距离它更近的邻近车道（相对位置关联）。
基于上述两个事实，解码器两个阶段的流程分别可以描述为：
最终在Generalizability赛道上，我们以ADE 0.5339米获得冠军；Regular赛道上，我们以ADE 0.1912米获得亚军。
04 总结
障碍物轨迹预测对无人车安全行驶具有重要的意义，它也是学界与工业界公认有很大挑战性的课题。我们希望通过努力做出更好的解决方案，持续提升自动驾驶系统对障碍物的预测能力，为美团实际业务及出行领域提供更多的技术支持。
05 参考文献
[1] Alahi A, Goel K, Ramanathan V, et al. Social lstm: Human trajectory prediction in crowded spaces[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016: 961-971.
[2] Gupta A, Johnson J, Fei-Fei L, et al. Social gan: Socially acceptable trajectories with generative adversarial networks[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018: 2255-2264.
[3] Zhu Y, Qian D, Ren D, et al. StarNet: Pedestrian trajectory prediction using deep neural network in star topology[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 2019: 8075-8080.
[4] Chai Y, Sapp B, Bansal M, et al. Multipath: Multiple probabilistic anchor trajectory hypotheses for behavior prediction[J]. arXiv preprint arXiv:1910.05449, 2019.
[5] Chang M F, Lambert J, Sangkloy P, et al. Argoverse: 3d tracking and forecasting with rich maps[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019: 8748-8757.
[6] Liang J, Jiang L, Niebles J C, et al. Peeking into the future: Predicting future person activities and locations in videos[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019: 5725-5734.
[7] Mohamed A, Qian K, Elhoseiny M, et al. Social-STGCNN: A Social Spatio-Temporal Graph Convolutional Neural Network for Human Trajectory Prediction[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020: 14424-14432.
[8] Liang M, Yang B, Hu R, et al. Learning lane graph representations for motion forecasting[C]//European Conference on Computer Vision. Springer, Cham, 2020: 541-556.
[9] Huang Y, Bi H K, Li Z, et al. STGAT: Modeling spatial-temporal interactions for human trajectory prediction[C]//Proceedings of the IEEE International Conference on Computer Vision. 2019: 6272-6281.
[10] Gao J, Sun C, Zhao H, et al. VectorNet: Encoding HD maps and agent dynamics from vectorized representation[J]. arXiv preprint arXiv:2005.04259, 2020.
[11] Zhao H, Gao J, Lan T, et al. Tnt: Target-driven trajectory prediction[J]. arXiv preprint arXiv:2008.08294, 2020.
06 作者简介
炎亮、傅 壮、德恒、冬淳等，均为美团无人车配送中心算法工程师。
鸿蒙系统 （HarmonyOS）是华为推出的一款分布式操作系统，那么如何在保证开发迭代效率的前提下，以相对低的成本将移动应用快速移植到鸿蒙平台上呢？美团外卖 MTFlutter 团队近期做了一次技术探 ...