基于深度學(xué)習(xí)改進(jìn)的機(jī)器人軌跡規(guī)劃算法

劉玉 鄧琛 李文帥 韓寶磊

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

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

DOI：10.11907/rjdk.192115開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）006-0015-04

0 引言

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

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

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

1 系統(tǒng)模型

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

1.1 模型介紹

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

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

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

1.2 參數(shù)模型

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

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

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

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

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

1.3 非參數(shù)模型

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

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

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

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

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

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

GRU作為L(zhǎng)STM的一種變體，將遺忘門和輸入門合并為一個(gè)更新門。與LSTM單元類似，隱藏單元輸出為h_t，是使用隱藏單元輸出h_t-1和當(dāng)前特征X_t計(jì)算的，公式如下：

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

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

1.4 軌跡規(guī)劃模型

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

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

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

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

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

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

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

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

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

2 預(yù)測(cè)交通流量

2.1 數(shù)據(jù)描述與實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

圖4（a）中橫軸為實(shí)驗(yàn)次數(shù)，縱軸為代價(jià)損失函數(shù)。為使實(shí)驗(yàn)?zāi)芨玫卣故靖魉惴ㄐ阅軆?yōu)劣，首先打散數(shù)據(jù)集，然后對(duì)每個(gè)模型進(jìn)行CROSS validation=5的交叉驗(yàn)證，每個(gè)模型實(shí)驗(yàn)20次?？梢钥闯鯡lastic Net優(yōu)于Ridge，也優(yōu)于SVR且更穩(wěn)定，從圖4（b）中看出總體偏差很大。

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

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

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

3 仿真實(shí)驗(yàn)

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

為了對(duì)比實(shí)驗(yàn)結(jié)果，首先采用PRM在原始道路中進(jìn)行路徑規(guī)劃，見圖7（b）。接著，采用深度學(xué)習(xí)模型進(jìn)行道路交通流量預(yù)測(cè)，見圖7（c），圖中黃色區(qū)域?yàn)閾矶侣范渭窜嚵髁吭谖磥?lái)5分鐘大于1000輛，從交通道路段集合O刪除黃色路段編號(hào)。此時(shí)重新運(yùn)行PRM算法，規(guī)劃出一條時(shí)間較短且較安全的新路徑，見圖7（d）。

4 結(jié)語(yǔ)

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