1.背景

民以食為天，如何提升超大規(guī)模配送網(wǎng)絡(luò)的整體配送效率，改善數(shù)億消費(fèi)者在”吃“方面的體驗(yàn)，是一項(xiàng)極具挑戰(zhàn)的技術(shù)難題。面向未來，美團(tuán)正在積極研發(fā)無人配送機(jī)器人，建立無人配送開放平臺，與產(chǎn)學(xué)研各方共建無人配送創(chuàng)新生態(tài)，希望能在一個場景相對簡單、操作高度重復(fù)的物流配送中，提高物流配送效率。在此過程中，美團(tuán)無人配送團(tuán)隊(duì)也取得了一些技術(shù)層面的突破，比如基于神經(jīng)網(wǎng)絡(luò)StarNet的行人軌跡交互預(yù)測算法，論文已發(fā)表在IROS 2019。IROS 的全稱是IEEE/RSJ International Conference on Intelligent Robots and Systems，IEEE智能機(jī)器人與系統(tǒng)國際會議，它和ICRA、RSS并稱為機(jī)器人領(lǐng)域三大國際頂會。

1.1??行人軌跡預(yù)測的意義

在無人車行駛過程中，它需要對周圍的行人進(jìn)行軌跡預(yù)測，這能幫助無人車更加安全平穩(wěn)地行駛。我們可以用圖1來說明預(yù)測周圍行人的運(yùn)動軌跡對于無人車行駛的重要性。

圖1 主車規(guī)劃軌跡跳變問題

圖1中藍(lán)色方塊代表無人車，白色代表行人。上半部分描述的是在不帶行人軌跡預(yù)測功能情況下無人車的行為。這種情況下，無人車會把行人當(dāng)做靜態(tài)物體，但由于每個時刻行人都會運(yùn)動，導(dǎo)致無人車規(guī)劃出來的行駛軌跡會隨著時間不停地變化，加大了控制的難度，同時還可能產(chǎn)生碰撞的風(fēng)險，這樣違背了安全平穩(wěn)行駛的目標(biāo)。下半部分是有了行人軌跡預(yù)測功能情況下的無人車行為。這種情況下，無人車會預(yù)測周圍行人的行駛軌跡，因此在規(guī)劃自身行駛時會考慮到未來時刻是否會與行人碰撞，最終規(guī)劃出來的軌跡更具有“預(yù)見性”，所以避免了不必要的軌跡變化和碰撞風(fēng)險。

1.2??行人軌跡預(yù)測的難點(diǎn)

總體而言，行人軌跡預(yù)測的難點(diǎn)主要有兩個：

第一，行人運(yùn)動靈活，預(yù)測難度大。本身精確預(yù)測未來的運(yùn)動軌跡是一個幾乎不可能完成的任務(wù)，但是通過觀察某個障礙物歷史時刻的運(yùn)動軌跡，可以根據(jù)一些算法來大致估計(jì)出未來的運(yùn)動軌跡（最簡單的是勻速直線運(yùn)動）。在實(shí)際中，相比于自行車、汽車等模型，行人運(yùn)動更加靈活，很難對行人建立合理的動力學(xué)模型（因?yàn)樾腥丝梢噪S時轉(zhuǎn)彎、停止、運(yùn)動等），這加劇了行人預(yù)測的難度。

第二，行人之間的交互，復(fù)雜又抽象。在實(shí)際場景中，某一行人未來的運(yùn)動不僅受自己意圖支配，同樣也受周圍行人的影響（例如避障）。這種交互非常抽象，在算法中往往很難精確地建模出來。目前，大部分算法都是用相對空間關(guān)系來進(jìn)行建模，例如相對位置、相對朝向、相對速度大小等。

1.3??相關(guān)工作介紹

傳統(tǒng)算法在做預(yù)測工作時會使用一些跟蹤的算法，最常見的是各類時序模型，例如卡爾曼濾波（Kalman Filter, KF）、隱馬爾可夫（Hidden Markov Model, HMM）、高斯過程（Gaussian Process, GP）等。這類方法都有一個很明顯的特點(diǎn)，就是根據(jù)歷史時序數(shù)據(jù)，建立時序遞推數(shù)學(xué)公式：$X^t=f\left(X^{t-1}\right)$或者$p\left(X^t \mid \ X^{t-1}\right)$。因?yàn)檫@類方法具有嚴(yán)格的數(shù)學(xué)證明和假設(shè)，也能處理一些常規(guī)的問題，但是對于一些復(fù)雜的問題就變得“束手無策”了。這是因?yàn)檫@些算法中都會引入一些先驗(yàn)假設(shè)，例如隱變量服從高斯分布，線性的狀態(tài)轉(zhuǎn)換方程以及觀測方程等，而最終這些假設(shè)也限制了算法的整體性能。神經(jīng)網(wǎng)絡(luò)一般不需要假設(shè)固定的數(shù)學(xué)模型，憑借大規(guī)模的數(shù)據(jù)集促使網(wǎng)絡(luò)學(xué)習(xí)更加合理的映射關(guān)系。本文我們主要介紹一些基于神經(jīng)網(wǎng)絡(luò)的行人預(yù)測算法。

基于神經(jīng)網(wǎng)絡(luò)的預(yù)測算法（主要以長短期記憶神經(jīng)網(wǎng)絡(luò)Long Short Term Memory，LSTM為主）在最近5年都比較流行，預(yù)測效果確實(shí)比傳統(tǒng)算法好很多。在CVPR（IEEE Conference on Computer Vision and Pattern Recognition） 2019上，僅行人預(yù)測算法的論文就有10篇左右。這里我們簡單介紹2篇經(jīng)典的行人預(yù)測算法思路，如果對這方面感興趣的同學(xué)，可以通過文末的參考文獻(xiàn)深入了解一下。第一篇是CVPR 2016斯坦福大學(xué)的工作Social-LSTM，也是最經(jīng)典的工作之一。Social-LSTM為每個行人都配備一個LSTM網(wǎng)絡(luò)預(yù)測其運(yùn)動軌跡，同時提出了一個Social Pooling Layer的模塊來計(jì)算周圍其他行人對其的影響。具體的計(jì)算思路是將該行人周圍的區(qū)域劃分成NxN個網(wǎng)格，每個網(wǎng)絡(luò)都是相同的大小，落入這些網(wǎng)格中的行人將會參與交互的計(jì)算。

圖2 左：Social LSTM原理 右：Social Pooling計(jì)算過程

第二篇是CVPR 2019卡耐基梅隆大學(xué)&谷歌&斯坦福大學(xué)的工作，他們的工作同樣使用LSTM來接收歷史信息并預(yù)測行人的未來軌跡。不同于其他算法的地方在于，這個模型不僅接收待預(yù)測行人的歷史位置信息，同時也提取行人外觀、人體骨架、周圍場景布局以及周圍行人位置關(guān)系，通過增加輸入信息提升預(yù)測性能。除了預(yù)測具體的軌跡，算法還會做粗粒度預(yù)測（決策預(yù)測），輸出行人未來時刻可能所在的區(qū)域。

圖3 算法整體結(jié)構(gòu)

其他的相關(guān)工作，還包括基于語義圖像/占有網(wǎng)格（Occupancy Grid Map, OGM）的預(yù)測算法，基于信息傳遞（Message Passing, MP）的預(yù)測算法，基于圖網(wǎng)絡(luò)（Graph Neural Network, GNN）的預(yù)測算法（GCN/GAT等）等等。

2. StarNet介紹

目前，現(xiàn)有的軌跡預(yù)測算法主要還是聚焦在對行人之間交互的建模，軌跡預(yù)測通常只使用LSTM預(yù)測即可。如下圖4左，現(xiàn)有關(guān)于軌跡預(yù)測的相關(guān)工作基本都是考慮行人之間兩兩交互，很少有考慮所有行人之間的全局交互（即使是GCN，也需要設(shè)計(jì)對應(yīng)的相似矩陣來構(gòu)造拉普拉斯矩陣，這也是一個難點(diǎn)）。我們可以舉一個例子來說明現(xiàn)有其他算法預(yù)測的流程：

假設(shè)感知模塊檢測到當(dāng)前N個行人的位置，如何計(jì)算第一個行人下一時刻的位置？ Step 1計(jì)算其他人對于第一個行人的交互影響。將第i個行人在第t時刻的位置記為（一般是坐標(biāo)x和y）。可以通過以下公式計(jì)算第一個行人的交互向量： $$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)$$ 從上述公式可以大致看到，相對位置關(guān)系是最重要的計(jì)算指標(biāo)，計(jì)算的函數(shù)f一般是一個神經(jīng)網(wǎng)絡(luò)。 Step 2 計(jì)算第一個行人下個時刻的位置。通常需要根據(jù)上一時刻的位置與交互向量： $$P_1^{t+1} = g\left(P_1^t, Interaction_1^t\right)$$ 上述公式中，計(jì)算的函數(shù)g同樣是神經(jīng)網(wǎng)絡(luò)，即上面提到的長短期記憶神經(jīng)網(wǎng)絡(luò)LSTM。

圖4 算法思路對比圖 上：傳統(tǒng)算法 下：StarNet

兩兩交互的方式存在兩個問題：

障礙物2和3確實(shí)會影響障礙物1的運(yùn)動，但是障礙物2和3之間同樣也存在相互影響，因此不能直接將其他障礙物對待預(yù)測障礙物的影響單獨(dú)剝離出來考慮，這與實(shí)際情況不相符。

兩兩計(jì)算消耗的資源大，如果有N個障礙物，那么兩兩交互就需要N的平方次計(jì)算，隨著N的變大，計(jì)算量呈平方倍增長。我們希望障礙物之間的交互能否只計(jì)算1次而非N次，所有障礙物的軌跡預(yù)測都共享這個全局交互那就更好了。

基于上述兩個問題，我們提出了一種新的模型，該模型旨在高效解決計(jì)算全局交互的問題。因?yàn)閭鹘y(tǒng)算法普遍存在計(jì)算兩兩交互的問題（即使是基于Attention注意力機(jī)制的Message Passing也很難考慮到全局的交互），本文想嘗試通過一些更加簡單直觀的方式來考慮所有障礙物之間的全局交互，我們的算法大致思路如下：

每個時刻所有障礙物的位置可以構(gòu)成一張靜態(tài)的“地圖”，隨著時間的變化，這些靜態(tài)地圖就變成了一張帶有時序信息的動態(tài)圖。這張動態(tài)圖中記錄了每個區(qū)域內(nèi)的障礙物運(yùn)動信息，其中運(yùn)動信息是由所有障礙物一起影響得到的，而非單獨(dú)地兩兩交互形成。對于每個障礙物的預(yù)測階段，只要根據(jù)該障礙物的位置，就可以在這張時序地圖中查詢該區(qū)域在歷史時刻的障礙物運(yùn)動信息（例如這個區(qū)域在歷史時刻中，障礙物1、2、4、5都有其運(yùn)動的軌跡）。通過“共享全局交互地圖+個體查詢”的方式，就可以做到計(jì)算全局交互以及壓縮計(jì)算開銷。

圖5 StarNet網(wǎng)絡(luò)結(jié)構(gòu)圖

我們的算法結(jié)構(gòu)如上圖5所示，Host Network是基于LSTM的軌跡預(yù)測網(wǎng)絡(luò)； Hub Network是基于LSTM的全局時序交互計(jì)算網(wǎng)絡(luò)。在論文具體的實(shí)現(xiàn)中，首先Hub Network的靜態(tài)地圖模塊是通過接受所有障礙物同一時刻的位置信息、全連接網(wǎng)絡(luò)和最大池化操作得到一個定長的特征向量$s^t$； 然后動態(tài)地圖模塊使用LSTM網(wǎng)絡(luò)對上述的特征向量$s^t$進(jìn)行時序編碼，最終得到一個全局交互向量$r^t$。Host Network首先根據(jù)行人（假設(shè)要預(yù)測第一個行人下時刻的位置）的位置$P_1^t$去動態(tài)地圖$r^t$中查詢自己當(dāng)前位置區(qū)域內(nèi)的交互$q_1^t$，具體我們采用簡單的點(diǎn)乘操作（類似于Attention機(jī)制）。最終自己的位置$P_1^t$和交互$q_1^t$一起輸入LSTM網(wǎng)絡(luò)預(yù)測下時刻的的位置$P_1^{t+1}$。

實(shí)驗(yàn)階段，我們與4種經(jīng)典的算法作比較，使用的數(shù)據(jù)集為UCY&ETH數(shù)據(jù)集，這兩個數(shù)據(jù)集包含4個子場景，分別為ZARA-1/ZARA-2、UNIV、ETH、HOTEL。在預(yù)測過程中，所有算法根據(jù)每個行人過去3.2秒的運(yùn)動軌跡，預(yù)測出它在未來3.2秒的軌跡。每0.4秒采樣一個離散點(diǎn)，因此3.2秒的軌跡可以用8個軌跡離散點(diǎn)表示。對比的指標(biāo)有：

（a）平均距離差A(yù)DE（Average Displacement Error）：用算法預(yù)測出的軌跡到真實(shí)軌跡所有8個點(diǎn)之間的平均距離差。 （b）終點(diǎn)距離差FDE（Final Displacement Error）：用算法預(yù)測出的軌跡與真實(shí)軌跡最后一個終點(diǎn)之間的距離差。 （c）前向預(yù)測時間以及參數(shù)量。??????????????????

最終的實(shí)驗(yàn)結(jié)果如下表：

從實(shí)驗(yàn)結(jié)果可以看到，我們的算法在80%的場景下都優(yōu)于其他算法，且實(shí)時性高（表中LSTM的推理時間為0.029秒，最快速是由于該算法不計(jì)算交互，因此速度最快參數(shù)也最少，但是性能較差）。

總結(jié)一下，我們提出算法StarNet的優(yōu)勢主要包括以下兩點(diǎn)：

• 使用全局動態(tài)地圖的形式來描述行人之間在時間和空間上的相互影響，更加合理，也更加準(zhǔn)確。
• Hub Network全局共享的特征提升了整個算法的計(jì)算效率。

3. 未來工作

首先，我們會進(jìn)一步探索新的模型結(jié)構(gòu)。雖然我們的算法在數(shù)據(jù)集上取得了不錯的效果，但這是我們的第一次嘗試，模型設(shè)計(jì)也比較簡單，如果提升模型結(jié)構(gòu)，相信可以取得更好的結(jié)果。

其次，我們會提升預(yù)測的可解釋性。同現(xiàn)有算法一樣，目前的模型對計(jì)算到的交互缺乏可解釋性，仍然依賴于數(shù)據(jù)驅(qū)動。在今后的工作中，我們將通過對交互的可解釋建模來提升預(yù)測的準(zhǔn)確性。

最后，在構(gòu)建時序的動態(tài)地圖過程中，引入對于每個障礙物的跟蹤信息。換句話說，我們知道每塊區(qū)域在各個時間點(diǎn)障礙物的位置，但目前算法沒有對障礙物在時序上做跟蹤（例如時刻1有三個障礙物，時刻2三個障礙物運(yùn)動了得到新的位置，網(wǎng)絡(luò)輸入為三個障礙物的位置信息，但是網(wǎng)絡(luò)無法理解兩個時刻中障礙物的對應(yīng)關(guān)系，這降低了交互的性能），這點(diǎn)在以后的工作中還需要繼續(xù)改進(jìn)。

參考文獻(xiàn)

[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.

作者簡介

朱炎亮，美團(tuán)無人配送部

錢德恒，美團(tuán)無人配送部

任冬淳，美團(tuán)無人配送部

夏華夏，美團(tuán)無人配送部

招聘信息

美團(tuán)軌跡預(yù)測組招聘深度學(xué)習(xí)算法工程師，我們希望你：

• 具有扎實(shí)的編程能力，能夠熟練使用C++或Python作為編程語言。
• 具有深度學(xué)習(xí)相關(guān)知識，能熟練使用TensorFlow或Pytorch作為深度學(xué)習(xí)算法研發(fā)框架。
• 對預(yù)測無人車周圍障礙物的未來軌跡感興趣。

歡迎有興趣的同學(xué)投送簡歷到 tech@meituan.com（郵件標(biāo)題注明：美團(tuán)軌跡預(yù)測組）。

總結(jié)

以上是生活随笔為你收集整理的顶会论文：基于神经网络StarNet的行人轨迹交互预测算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。