基于深度學習改進的機器人軌跡規(guī)劃算法

劉玉 鄧琛 李文帥 韓寶磊

摘要：在公路環(huán)境巡邏機器人軌跡規(guī)劃問題中，實時準確的交通流量預測對機器人軌跡規(guī)劃尤為重要。然而由于車流量的隨機非線性，使得機器人軌跡規(guī)劃任務仍然充滿挑戰(zhàn)。提出一種深度神經(jīng)網(wǎng)絡與軌跡規(guī)劃算法相結(jié)合的融合算法。通過深度學習預測短期交通流量，優(yōu)化交通網(wǎng)絡圖并運用軌跡規(guī)劃算法完成路徑規(guī)劃。實驗表明，改進的機器人能夠更快、更安全地完成道路巡邏任務。

關(guān)鍵詞：機器人;深度學習;融合算法;優(yōu)化網(wǎng)絡圖;軌跡規(guī)劃

DOI：10.11907/rjdk.192115開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）006-0015-04

0 引言

巡邏機器人是一種自動、半自動或由人類控制完成安防工作的機器人，其主要技術(shù)之一就是軌跡規(guī)劃。蔣偉等通過拉格朗日插入值優(yōu)化A*運動軌跡點找尋最短軌跡;魏玉等提出偏向目標的改進RRT算法優(yōu)化機器人行駛時間;孫欽鵬等通過動態(tài)設置機器人最小轉(zhuǎn)彎半徑和最小安全距離以確保機器人安全導航。對于傳統(tǒng)軌跡規(guī)劃算法的優(yōu)化，雖然能得到一條較優(yōu)的規(guī)劃軌跡，但當?shù)缆钒l(fā)生擁堵、事故、人流量暴增等情況時，實用性會很差。

智能交通是智慧城市的重要組成部分。Tian等采用基于長短期記憶（LSTM）算法分析不規(guī)則采樣和丟失的交通流量數(shù)據(jù);程健等通過基于狀態(tài)的過濾模塊優(yōu)化交通物理對象（TPO）與交通信息空間（TIS）的人工智能算法;Chen等提出模糊深度學習方法FDCN預測交通流量。

這些交通流量預測研究為機器人軌跡規(guī)劃提供了較好的基礎(chǔ)。本文提出一種基于深度學習的改進機器人軌跡規(guī)劃算法。首先，使用深度學習算法對交通流量進行預測;其次，通過交通流量的預測結(jié)果優(yōu)化交通網(wǎng)絡圖;最后，采用軌跡規(guī)劃算法獲得行駛路徑。

1 系統(tǒng)模型

交通流量預測在城市交通管理中非常重要，目前產(chǎn)生了很多交通流量預測方法，一般將其分為參數(shù)模型和非參數(shù)模型兩類。

1.1 模型介紹

參數(shù)模型：此類算法通常由簡單模型實現(xiàn)并能夠明確理解，因此建模實現(xiàn)相對容易。常見的有嶺回歸算法（Ridge Regression）、彈性網(wǎng)絡（Elastic Net）、支持向量回歸（Support Vector Regression）等。但由于交通流的隨機性，參數(shù)模型無法很好地描述這種隨機特性。

非參數(shù)模型：指沒有固定結(jié)構(gòu)且沒有固定參數(shù)的模型。流行的非參數(shù)模型有k近鄰算法（k nearest neigh.bor，KNN）、隨機森林（Random Forest）、人工神經(jīng)網(wǎng)絡（Artificial Neural Network，ANN）等。基于神經(jīng)網(wǎng)絡的非參數(shù)模型具有優(yōu)越的映射能力，幾乎可以使所有函數(shù)適應任意精度。

對于公路環(huán)境路徑規(guī)劃問題，本文通過分析隨機性搜索算法（Rapidly exploring random Trees，RRT）、概率性搜索算法（Probabilistic Roadmap，PRM）和啟發(fā)性搜索算法A*（A-Star），尋找最優(yōu)規(guī)劃算法。

1.2 參數(shù)模型

Ridge回歸，即在線性回歸損失函數(shù)上直接加入一個正則項，使模型不但可以擬合數(shù)據(jù)，并且能夠使參數(shù)權(quán)重盡量小。這個正則項只需在訓練進程中加入損失函數(shù)。

Lasso回歸是另一種正則化的線性回歸。與嶺回歸相似，在損失函數(shù)上增加了一個正則化項，但是使用權(quán)重向量的L1范數(shù)而不是權(quán)重向量L2范數(shù)平方的一半。

Elastic Net彈性網(wǎng)絡介于Ridge回歸與Lasso回歸之間，它的正則項是Ridge回歸和Lasso回歸正則項的混合。該模型能夠調(diào)控它們的混合率，當r=0時，彈性網(wǎng)絡就是Ridge回歸，當r=1時，其就是Lasso回歸。

式（1）-式（3）分別是Ridge回歸、Lasso回歸和ElasticNet回歸的代價損失函數(shù)，其中Ridge回歸應用L2范數(shù)，Lasso回歸應用Ll范數(shù)，Elastic Net回歸應用L1+L2的混合范數(shù)，實現(xiàn)正則化。

SVM模型中邊界上的點以及兩條邊界內(nèi)部違反margin的點被當作支持向量，在后續(xù)預測中起作用。在SVR模型中邊界上的點以及兩條邊界以外的點被當作支持向量在預測中起作用。從圖1可以看到，在margin內(nèi)部的這些點誤差都為0，只有超出margin的點才會計算error。

1.3 非參數(shù)模型

1.3.1 LSTM神經(jīng)網(wǎng)絡

RNN神經(jīng)網(wǎng)絡最初用于語言模型，因為它具有長期記憶能力。但隨著時間增長，RNN的梯度可能會隨著網(wǎng)絡層數(shù)增加變?yōu)榉浅Ｉ畹那梆伾窠?jīng)網(wǎng)絡。為了解決梯度消失問題，提出了具有遺忘門的RNN結(jié)構(gòu)（LSTM）。

LSTM神經(jīng)網(wǎng)絡的典型結(jié)構(gòu)由輸入門、存儲單元、遺忘門和輸出門4個門組成。輸入門從外部獲取新數(shù)據(jù)，存儲單元接收輸入數(shù)據(jù)最后一次迭代結(jié)果，遺忘門決定何時遺忘輸出結(jié)果，輸出門計算所有的輸出單元為LSTM的輸出結(jié)果。

輸入的時間序列特征表示為X=（x1，x2，…，xn），隱藏層記憶細胞的狀態(tài)H=（h1，h2，…，hn），輸出時間序列結(jié)果為Y=（Y1，Y2，…，Yn），LSTM網(wǎng)絡計算如下：

其中，y代表實際交通流量，p代表預測交通流量。為了最小化訓練誤差，同時防止局部最優(yōu)出現(xiàn)，使用Adam梯度下降法。神經(jīng)網(wǎng)絡容易出現(xiàn)過擬合問題。常用正則化配合dropout的方法解決過擬合問題。由于LSTM神經(jīng)細胞的傳遞具有“記憶”特性，使得該網(wǎng)絡在交通流量預測方面具有特殊優(yōu)勢。

1.3.2 GRU神經(jīng)網(wǎng)絡

GRU作為LSTM的一種變體，將遺忘門和輸入門合并為一個更新門。與LSTM單元類似，隱藏單元輸出為h_t，是使用隱藏單元輸出h_t-1和當前特征X_t計算的，公式如下：

h_t=f（h_t-1，x_t） （11）

復位門的功能類似于LSTM遺忘門。由于GRU結(jié)構(gòu)與LSTM結(jié)構(gòu)相似，這里不再贅述。

1.4 軌跡規(guī)劃模型

隨機搜索算法：RRT算法通過狀態(tài)空間的隨機采樣點，把搜索導向空白區(qū)域，從而尋找到一條從起始點到目標點的軌跡。RRT-Master算法引入目標點作為隨機產(chǎn)生的引導因子，使隨機樹的生長更有效率，大大縮短了搜索時間。

啟發(fā)性搜索算法：A*算法是一種啟發(fā)性全局擇優(yōu)搜索算法，搜索過程中沒有舍棄節(jié)點，避免了最優(yōu)節(jié)點的丟失，可以找到最短路徑。A*算法估價函數(shù)可以表示為：

f（n）=g（n）+h（n） （12）

式（12）中，f（n）是節(jié)點n的估價函數(shù)，h（n）是狀態(tài)空間中從起點到終點的距離代價函數(shù)，g（n）是當前點到目標點的最優(yōu)估計代價函數(shù)，反映搜索的啟發(fā)信息。

圖2（a）是RRT-Master軌跡路線，算法的枝丫生成步長是隨機的，一般取地圖尺寸的5%-10%，從圖中可以看出軌跡曲折性很大，且可重復性小，是一種不完備搜索算法。圖2（b）是A*搜索的機器人軌跡。作為一種完備性搜索算法可以搜索出最優(yōu)路徑，但搜索地圖尺寸越大，g（n）節(jié)點信息越多，計算量就會變大，運行耗費時間相應增多。

概率性搜索算法：PRM將連續(xù)空間轉(zhuǎn)換成離散空間，再利用基于圖的規(guī)劃算法（D，A*等）在網(wǎng)絡圖上尋找路徑，算法分為兩個階段：

（1）網(wǎng)絡圖構(gòu)建。在狀態(tài)空間中隨機撤點（自定義個數(shù)），構(gòu)建路徑網(wǎng)絡圖。

（2）路徑查詢。將起始點和目標點連接到網(wǎng)絡圖中，利用A*完成路徑搜索。靜態(tài)軌跡規(guī)劃中只需進行一次搜索就可產(chǎn)生引導路徑。

圖3（a）是采樣點網(wǎng)絡圖，圖3（b）是軌跡路線圖。地圖采樣點數(shù)是隨機的，當采樣點較少時得到的是不完備地圖，當采樣點增加時得到的軌跡可以趨近于一條完備路徑，但對計算機的資源消耗也會相應增多。綜合算法效率和穩(wěn)定性考慮，本文使用PRM算法作為路徑規(guī)劃算法。

2 預測交通流量

2.1 數(shù)據(jù)描述與實驗設計

本文使用PEMS數(shù)據(jù)集。在加利福尼亞范圍內(nèi)部署了超過15000臺傳感器，多次分析數(shù)據(jù)集發(fā)現(xiàn)5分鐘的交通流量預測更合適。其中缺失數(shù)據(jù)僅占整個數(shù)據(jù)集的一小部分，所以使用歷史平均值來估算缺失數(shù)值，以下實驗基于該數(shù)據(jù)集。

實驗選擇過去30分鐘的交通流量，實際上是用6個數(shù)據(jù)點的時間序列預測未來5分鐘的交通流量。前三周用于訓練模型，第四周數(shù)據(jù)用于測試模型。由于每個路段可能都有自己的交通流模式，沒有一個通用模式可以適應所有路段，因此為每個道路口構(gòu)建唯一一個由單個傳感器收集的交通流量模型。實驗中使用均方誤差（MSE）比較算法性能。

2.2 基于參數(shù)模型的交通流量預測

首先使用傳統(tǒng)回歸模型嶺回歸（Ridge）、彈性網(wǎng)絡（Elastic Net）、支持向量回歸（SVR）。

圖4（a）中橫軸為實驗次數(shù)，縱軸為代價損失函數(shù)。為使實驗能更好地展示各算法性能優(yōu)劣，首先打散數(shù)據(jù)集，然后對每個模型進行CROSS validation=5的交叉驗證，每個模型實驗20次。可以看出Elastic Net優(yōu)于Ridge，也優(yōu)于SVR且更穩(wěn)定，從圖4（b）中看出總體偏差很大。

2.3 基于非參數(shù)模型的交通流量預測

非參數(shù)模型中，隨機森林回歸（RFR）、LSTM模型以及GRU模型預測結(jié)果如圖5所示。

從圖5（a）可以看出，非參數(shù)模型代價損失函數(shù)明顯低于參數(shù)模型。其中隨機森林回歸雖然表現(xiàn)相對穩(wěn)定但整體偏差較大，LSTM與GRU表現(xiàn)接近，但在算法運行過程中GRU耗費時間比LSTM少了近30%。不過實際應用仍選擇精度稍高的LSTM模型作為最終的交通流量預測模型。

3 仿真實驗

機器人行駛道路環(huán)境的衛(wèi)星地圖經(jīng)過二值化處理生成黑白二值圖像，道路區(qū)域由0值表示，非道路區(qū)域用l值表示，即圖7（a）中白色通道和黑色多邊形區(qū)域（只考慮主干路線，冗余的支線略去），機器人移動區(qū)域就是圖中的白色道路區(qū)域。

為了對比實驗結(jié)果，首先采用PRM在原始道路中進行路徑規(guī)劃，見圖7（b）。接著，采用深度學習模型進行道路交通流量預測，見圖7（c），圖中黃色區(qū)域為擁堵路段即車流量在未來5分鐘大于1000輛，從交通道路段集合O刪除黃色路段編號。此時重新運行PRM算法，規(guī)劃出一條時間較短且較安全的新路徑，見圖7（d）。

4 結(jié)語

為了更好地幫助機器人完成路徑規(guī)劃任務，本文對交通流量進行了預測。經(jīng)過對比參數(shù)模型和非參數(shù)模型，發(fā)現(xiàn)對于非線性的交通車流量預測，非參數(shù)模型LSTM預測效果更好，以此得到優(yōu)化的交通網(wǎng)絡圖。最后利用PRM路徑規(guī)劃算法尋找到最優(yōu)路徑。該模型算法還可進一步優(yōu)化，如加入啟發(fā)式算法優(yōu)化機器人回調(diào)路徑。