民以⾷为天，如何提升超⼤规模配送⽹络的整体配送效率，改善数亿消费者在”吃“⽅⾯的体验，是⼀项极具挑战的技术难题。⾯向未来，美团正在积极研发⽆⼈配送机器⼈，建⽴⽆⼈配送开放平台，与产学研各⽅共建⽆⼈配送创新⽣态，希望能在⼀个场景相对简单、操作⾼度重复的物流配送中，提⾼物流配送效率。在此过程中，美团⽆⼈配送团队也取得了⼀些技术层⾯的突破，⽐如，论⽂已发表在IROS 2019。IROS 的全称是IEEE/RSJ International Conference on Intelligent Robots and Systems，IEEE智能机器⼈与系统国际会议，它和、并称为机器⼈领域三⼤国际顶会。
1.1 ⾏⼈轨迹预测的意义
在⽆⼈车⾏驶过程中，它需要对周围的⾏⼈进⾏轨迹预测，这能帮助⽆⼈车更加安全平稳地⾏驶。我们可以⽤图1来说明预测周围⾏⼈的运动轨迹对于⽆⼈车⾏驶的重要性。
图1 主车规划轨迹跳变问题
图1中蓝⾊⽅块代表⽆⼈车，⽩⾊代表⾏⼈。上半部分描述的是在不带⾏⼈轨迹预测功能情况下⽆⼈车的⾏为。这种情况下，⽆⼈车会把⾏⼈当做静态物体，但由于每个时刻⾏⼈都会运动，导致⽆⼈车规划出来的⾏驶轨迹会随着时间不停地变化，加⼤了控制的难度，同时还可能产⽣碰撞的风险，这样违背了安
全平稳⾏驶的⽬标。下半部分是有了⾏⼈轨迹预测功能情况下的⽆⼈车⾏为。这种情况下，⽆⼈车会预测周围⾏⼈的⾏驶轨迹，因此在规划⾃⾝⾏驶时会考虑到未来时刻是否会与⾏⼈碰撞，最终规划出来的轨迹更具有“预见性”，所以避免了不必要的轨迹变化和碰撞风险。
1.2 ⾏⼈轨迹预测的难点
总体⽽⾔，⾏⼈轨迹预测的难点主要有两个：
第⼀，⾏⼈运动灵活，预测难度⼤。本⾝精确预测未来的运动轨迹是⼀个⼏乎不可能完成的任务，但是通过观察某个障碍物历史时刻的运动轨迹，可以根据⼀些算法来⼤致估计出未来的运动轨迹（最简单的是匀速直线运动）。在实际中，相⽐于⾃⾏车、汽车等模型，⾏⼈运动更加灵活，很难对⾏⼈建⽴合理的动⼒学模型（因为⾏⼈可以随时转弯、停⽌、运动等），这加剧了⾏⼈预测的难度。 第⼆，⾏⼈之间的交互，复杂⼜抽象。在实际场景中，某⼀⾏⼈未来的运动不仅受⾃⼰意图⽀配，同样也受周围⾏⼈的影响（例如避障）。这种交互⾮常抽象，在算法中往往很难精确地建模出来。⽬前，⼤部分算法都是⽤相对空间关系来进⾏建模，例如相对位置、相对朝向、相对速度⼤⼩等。神经网络预测
1.3 相关⼯作介绍
传统算法在做预测⼯作时会使⽤⼀些跟踪的算法，最常见的是各类时序模型，例如卡尔曼滤波（Kalm
an Filter, KF）、隐马尔可夫（Hidden Markov Model, HMM）、⾼斯过程（Gaussian Process, GP）等。这类⽅法都有⼀个很明显的特点，就是根据历史时序数据，建⽴时序递推数学公式：$X^t=f\left(X^{t-1}\right)$或者$p\left(X^t \mid \ X^{t-1}\right)$。因为这类⽅法具有严格的数学证明和假设，也能处理⼀些常规的问题，但是对于⼀些复杂的问题就变得“束⼿⽆策”了。这是因为这些算法中都会引⼊⼀些先验假设，例如隐变量服从⾼斯分布，线性的状态转换⽅程以及观测⽅程等，⽽最终这些假设也限制了算法的整体性能。神经⽹络⼀般不需要假设固定的数学模型，凭借⼤规模的数据集促使⽹络学习更加合理的映射关系。本⽂我们主要介绍⼀些基于神经⽹络的⾏⼈预测算法。
基于神经⽹络的预测算法（主要以长短期记忆神经⽹络Long Short Term Memory，LSTM为主）在最近5年都⽐较流⾏，预测效果确实⽐传统算法好很多。在CVPR（IEEE Conference on Computer Vision and Pattern Recognition） 2019上，仅⾏⼈预测算法的论⽂就有10篇左右。这⾥我们简单介绍2篇经典的⾏⼈预测算法思路，如果对这⽅⾯感兴趣的同学，可以通过⽂末的参考⽂献深⼊了解⼀下。第⼀篇是CVPR 2016斯坦福⼤学的⼯作Social-LSTM，也是最经典的⼯作之⼀。Social-LSTM为每个⾏⼈都配备⼀个LSTM⽹络预测其运动轨迹，同时提出了⼀个Social Pooling Layer的模块来计算周围其他⾏⼈对其的影响。具体的计算思路是将该⾏⼈周围的区域划分成NxN个⽹格，每个⽹络都是相同的⼤⼩，落⼊这些⽹格中的⾏⼈将会参与交互的计算。
图2 左：Social LSTM原理 右：Social Pooling计算过程
第⼆篇是CVPR 2019卡耐基梅隆⼤学&⾕歌&斯坦福⼤学的⼯作，他们的⼯作同样使⽤LSTM来接收历史信息并预测⾏⼈的未来轨迹。不同于其他算法的地⽅在于，这个模型不仅接收待预测⾏⼈的历史位置信息，同时也提取⾏⼈外观、⼈体⾻架、周围场景布局以及周围⾏⼈位置关系，通过增加输⼊信息提升预测性能。除了预测具体的轨迹，算法还会做粗粒度预测（决策预测），输出⾏⼈未来时刻可能所在的区域。
图3 算法整体结构
其他的相关⼯作，还包括基于语义图像/占有⽹格（Occupancy Grid Map, OGM）的预测算法，基于信息传递（Message Passing, MP）的预测算法，基于图⽹络（Graph Neural Network, GNN）的预测算法（GCN/GAT等）等等。
2. StarNet介绍
⽬前，现有的轨迹预测算法主要还是聚焦在对⾏⼈之间交互的建模，轨迹预测通常只使⽤LSTM预测即可。如下图4左，现有关于轨迹预测的相关⼯作基本都是考虑⾏⼈之间两两交互，很少有考虑所有⾏⼈之间的全局交互（即使是GCN，也需要设计对应的相似矩阵来构造拉普拉斯矩阵，这也是⼀个难点）。我们可以举⼀个例⼦来说明现有其他算法预测的流程：
假设感知模块检测到当前N个⾏⼈的位置，如何计算第⼀个⾏⼈下⼀时刻的位置？ Step 1计算其他⼈对于第⼀个⾏⼈的交互影响。将第i个⾏⼈在第t时刻的位置记为（⼀般是坐标x和y）。可以通过以下公式计算第⼀个⾏⼈的交互向量： $$Interaction_1^t =
f\left(P_2^t-P_1^t, P_3^t-P_1^t, \cdots, P_N^t-P_1^t\right)$$ 从上述公式可以⼤致看到，相对位置关系是最重要的计算指标，计算的函数f⼀般是⼀个神经⽹络。 Step 2 计算第⼀个⾏⼈下个时刻的位置。通常需要根据上⼀时刻的位置与交互向量：
$$P_1^{t+1} = g\left(P_1^t, Interaction_1^t\right)$$ 上述公式中，计算的函数g同样是神经⽹络，即上⾯提到的长短期记忆神经⽹络LSTM。
图4 算法思路对⽐图上：传统算法 下：StarNet
两两交互的⽅式存在两个问题：
1. 障碍物2和3确实会影响障碍物1的运动，但是障碍物2和3之间同样也存在相互影响，因此不能直接将其他障碍物对待预测障碍物的影
响单独剥离出来考虑，这与实际情况不相符。
2. 两两计算消耗的资源⼤，如果有N个障碍物，那么两两交互就需要N的平⽅次计算，随着N的变⼤，计算量呈平⽅倍增长。我们希望障
碍物之间的交互能否只计算1次⽽⾮N次，所有障碍物的轨迹预测都共享这个全局交互那就更好了。
基于上述两个问题，我们提出了⼀种新的模型，该模型旨在⾼效解决计算全局交互的问题。因为传统算法普遍存在计算两两交互的问题（即使是基于Attention注意⼒机制的Message Passing也很难考虑到全局的交互），本⽂想尝试通过⼀些更加简单直观的⽅式来考虑所有障碍物之间的全局交互，我们的算法⼤致思路如下：
每个时刻所有障碍物的位置可以构成⼀张静态的“地图”，随着时间的变化，这些静态地图就变成了⼀张带有时序信息的动态图。这张动态图中记录了每个区域内的障碍物运动信息，其中运动信息是由所有障碍物⼀起影响得到的，⽽⾮单独地两两交互形成。对于每个障碍物的预测阶段，只要根据该障碍物的位置，就可以在这张时序地图中查询该区域在历史时刻的障碍物运动信息（例如这个区域在历史时刻中，障碍物1、2、4、5都有其运动的轨迹）。通过“共享全局交互地图+个体查询”的⽅式，就可以做到计算全局交互以及压缩计算开销。
图5 StarNet⽹络结构图
我们的算法结构如上图5所⽰，Host Network是基于LSTM的轨迹预测⽹络； Hub Network是基于LSTM的全局时序交互计算⽹络。在论⽂具体的实现中，⾸先Hub Network的静态地图模块是通过接受所有障碍物同⼀时刻的位置信息、全连接⽹络和最⼤池化操作得到⼀个定长的特征向量$s^t$； 然后动态地图模块使⽤LSTM⽹络对上述的特征向量$s^t$进⾏时序编码，最终得到⼀个全局交互向量$r^t$。Host Network⾸先根据⾏⼈（假设要预测第⼀个⾏⼈下时刻的位置）的位置$P_1^t$去动态地图$r^t$中查询⾃⼰当前位置区域内的交互
$q_1^t$，具体我们采⽤简单的点乘操作（类似于Attention机制）。最终⾃⼰的位置$P_1^t$和交互$q_1^t$⼀起输⼊LSTM⽹络预测下时刻的的位置$P_1^{t+1}$。
实验阶段，我们与4种经典的算法作⽐较，使⽤的数据集为UCYÐ数据集，这两个数据集包含4个⼦场景，分别为ZARA-1/ZARA-2、UNIV、ETH、HOTEL。在预测过程中，所有算法根据每个⾏⼈过去3.2秒的运动轨迹，预测出它在未来3.2秒的轨迹。每0.4秒采样⼀个离散点，因此3.2秒的轨迹可以⽤8个轨迹离散点表⽰。对⽐的指标有：
（a）平均距离差ADE（Average Displacement Error）：⽤算法预测出的轨迹到真实轨迹所有8个点之间的平均距离差。 （b）终点距离差FDE（Final Displacement Error）：⽤算法预测出的轨迹与真实轨迹最后⼀个终点之间的距离差。 （c）前向预测时间以及参数量。
最终的实验结果如下表：
从实验结果可以看到，我们的算法在80%的场景下都优于其他算法，且实时性⾼（表中LSTM的推理时间为0.029秒，最快速是由于该算法不计算交互，因此速度最快参数也最少，但是性能较差）。
总结⼀下，我们提出算法StarNet的优势主要包括以下两点：
使⽤全局动态地图的形式来描述⾏⼈之间在时间和空间上的相互影响，更加合理，也更加准确。
Hub Network全局共享的特征提升了整个算法的计算效率。
3. 未来⼯作
⾸先，我们会进⼀步探索新的模型结构。虽然我们的算法在数据集上取得了不错的效果，但这是我们的第⼀次尝试，模型设计也⽐较简单，如果提升模型结构，相信可以取得更好的结果。
其次，我们会提升预测的可解释性。同现有算法⼀样，⽬前的模型对计算到的交互缺乏可解释性，仍然依赖于数据驱动。在今后的⼯作中，我们将通过对交互的可解释建模来提升预测的准确性。
最后，在构建时序的动态地图过程中，引⼊对于每个障碍物的跟踪信息。换句话说，我们知道每块区域在各个时间点障碍物的位置，但⽬前算法没有对障碍物在时序上做跟踪（例如时刻1有三个障碍物，时刻2三个障碍物运动了得到新的位置，⽹络输⼊为三个障碍物的位置信息，但是⽹络⽆法理解两个时刻中障碍物的对应关系，这降低了交互的性能），这点在以后的⼯作中还需要继续改进。
参考⽂献
[1] A. Alahi, K. Goel, V. Ramanathan, A. Robicquet, F. Li and S. Savarese, “Social lstm: Human trajectory prediction in crowded spaces,” in 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE 2016, pp. 961-971.
[2] H. Wu, Z. Chen, W. Sun, B. Zheng and W. Wang, “Modeling trajectories with recurrent neural networks,” in 28th International Joint Conference on Artificial Intelligence (IJCAI). 2017, pp. 3083-3090.
[3] A. Gupta, J. Johnson, F. Li, S. Savarese and A. Alahi, “Social GAN: Socially acceptable trajectories with generative adversarial networks,” in 2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2018, pp. 2255-2264.
[4] A. Vemula, K. Muelling and J. Oh, “Social attention: Modeling attention in human crowds,” in 2018 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2018, pp. 1-7.
[5] Y. Xu, Z. Piao and S. Gao S, “Encoding crowd interaction with deep neural network for pPedestrian trajectory prediction,” in 2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2018, pp. 5275-5284.
[6] D. Varshneya, G. Srinivasaraghavan, “Human trajectory prediction using spatially aware deep attention models,” arXiv preprint arXiv:1705.09436, 2017.
[7] T. Fernando, S. Denma, S. Sridharan and C. Fookes, “Soft+hardwired attention: An lstm framework for human
trajectory prediction and abnormal event detection,” arXiv preprint arXiv:1702.05552, 2017.
[8] J. Liang, L. Jiang, J. C. Niebles, A. Hauptmann and F. Li, “Peeking into the future: Predicting future person activities and locations in videos,” in 2019 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2019, pp. 5725-5734.
[9] A. Sadeghian, V. Kosaraju, Ali. Sadeghian, N. Hirose, S. H. Rezatofighi and S. Savarese, “SoPhie: An attentive GAN for predicting paths compliant to social and physical constraints,” in 2019 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2019, pp. 5725-5734.
[10] R. Chandra, U. Bhattacharya and A. Bera, “TraPHic: Trajectory prediction in dense and heterogeneous traffic using weighted interactions,” in 2019 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2019, pp. 8483-8492.
[11] J. Amirian, J. Hayet and J. Pettre, “Social Ways: Learning multi-modal distributions of pedestrian trajectories with GANs,” arXiv preprint arXiv:1808.06601, 2018.
作者简介
朱炎亮，美团⽆⼈配送部
钱德恒，美团⽆⼈配送部
任冬淳，美团⽆⼈配送部
夏华夏，美团⽆⼈配送部
招聘信息
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议