基于深度學習改進的機器人軌跡規劃算法
「在公路環境巡邏機器人軌跡規劃問題中，實時準確的交通流量預測對機器人軌跡規劃尤為重要。然而由于車流量的隨機非線性，使得機器人軌跡規劃任務仍然充滿挑戰。提出一種深度神經網絡與軌跡規劃算法相結合的融合算法。通過深度學習預測短期交通流量，優化交通網絡圖并運用軌跡規劃算法完成路徑規劃。實驗表明，改進的機器人能夠更快、更安全地完成道路巡邏任務。(2023-2-25)」
關鍵詞：機器人;深度學習;融合算法;優化網絡圖;軌跡規劃
DOI：10.11907/rjdk.192115開放科學（資源服務）標識碼（OSID）：
中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）006-0015-04
0 引言
巡邏機器人是一種自動、半自動或由人類控制完成安防工作的機器人，其主要技術之一就是軌跡規劃。蔣偉等通過拉格朗日插入值優化A*運動軌跡點找尋最短軌跡;魏玉等提出偏向目標的改進RRT算法優化機器人行駛時間;孫欽鵬等通過動態設置機器人最小轉彎半徑和最小安全距離以確保機器人安全導航。對于傳統軌跡規劃算法的優化，雖然能得到一條較優的規劃軌跡，但當道路發生擁堵、事故、人流量暴增等情況時，實用性會很差。
智能交通是智慧城市的重要組成部分。Tian等采用基于長短期記憶（LSTM）算法分析不規則采樣和丟失的交通流量數據;程健等通過基于狀態的過濾模塊優化交通物理對象（TPO）與交通信息空間（TIS）的人工智能算法;Chen等提出模糊深度學習方法FDCN預測交通流量。
這些交通流量預測研究為機器人軌跡規劃提供了較好的基礎。本文提出一種基于深度學習的改進機器人軌跡規劃算法。首先，使用深度學習算法對交通流量進行預測;其次，通過交通流量的預測結果優化交通網絡圖;最后，采用軌跡規劃算法獲得行駛路徑。
1 系統模型
交通流量預測在城市交通管理中非常重要，目前產生了很多交通流量預測方法，一般將其分為參數模型和非參數模型兩類。
1.1 模型介紹
參數模型：此類算法通常由簡單模型實現并能夠明確理解，因此建模實現相對容易。常見的有嶺回歸算法（Ridge Regression）、彈性網絡（Elastic Net）、支持向量回歸（Support Vector Regression）等。但由于交通流的隨機性，參數模型無法很好地描述這種隨機特性。
非參數模型：指沒有固定結構且沒有固定參數的模型。流行的非參數模型有k近鄰算法（k nearest neigh.bor，KNN）、隨機森林（Random Forest）、人工神經網絡（Artificial Neural Network，ANN）等�；谏窠浘W絡的非參數模型具有優越的映射能力，幾乎可以使所有函數適應任意精度。
對于公路環境路徑規劃問題，本文通過分析隨機性搜索算法（Rapidly exploring random Trees，RRT）、概率性搜索算法（Probabilistic Roadmap，PRM）和啟發性搜索算法A*（A-Star），尋找最優規劃算法。
1.2 參數模型
Ridge回歸，即在線性回歸損失函數上直接加入一個正則項，使模型不但可以擬合數據，并且能夠使參數權重盡量小。這個正則項只需在訓練進程中加入損失函數。
Lasso回歸是另一種正則化的線性回歸。與嶺回歸相似，在損失函數上增加了一個正則化項，但是使用權重向量的L1范數而不是權重向量L2范數平方的一半。
Elastic Net彈性網絡介于Ridge回歸與Lasso回歸之間，它的正則項是Ridge回歸和Lasso回歸正則項的混合。該模型能夠調控它們的混合率，當r=0時，彈性網絡就是Ridge回歸，當r=1時，其就是Lasso回歸。
式（1）-式（3）分別是Ridge回歸、Lasso回歸和ElasticNet回歸的代價損失函數，其中Ridge回歸應用L2范數，Lasso回歸應用Ll范數，Elastic Net回歸應用L1+L2的混合范數，實現正則化。
SVM模型中邊界上的點以及兩條邊界內部違反margin的點被當作支持向量，在后續預測中起作用。在SVR模型中邊界上的點以及兩條邊界以外的點被當作支持向量在預測中起作用。從圖1可以看到，在margin內部的這些點誤差都為0，只有超出margin的點才會計算error。
1.3 非參數模型
1.3.1 LSTM神經網絡
RNN神經網絡最初用于語言模型，因為它具有長期記憶能力。但隨著時間增長，RNN的梯度可能會隨著網絡層數增加變為非常深的前饋神經網絡。為了解決梯度消失問題，提出了具有遺忘門的RNN結構（LSTM）。
LSTM神經網絡的典型結構由輸入門、存儲單元、遺忘門和輸出門4個門組成。輸入門從外部獲取新數據，存儲單元接收輸入數據最后一次迭代結果，遺忘門決定何時遺忘輸出結果，輸出門計算所有的輸出單元為LSTM的輸出結果。
輸入的時間序列特征表示為X=（x1，x2，…，xn），隱藏層記憶細胞的狀態H=（h1，h2，…，hn），輸出時間序列結果為Y=（Y1，Y2，…，Yn），LSTM網絡計算如下：
其中，y代表實際交通流量，p代表預測交通流量。為了最小化訓練誤差，同時防止局部最優出現，使用Adam梯度下降法。神經網絡容易出現過擬合問題。常用正則化配合dropout的方法解決過擬合問題。由于LSTM神經細胞的傳遞具有“記憶”特性，使得該網絡在交通流量預測方面具有特殊優勢。
1.3.2 GRU神經網絡
GRU作為LSTM的一種變體，將遺忘門和輸入門合并為一個更新門。與LSTM單元類似，隱藏單元輸出為ht，是使用隱藏單元輸出ht-1和當前特征Xt計算的，公式如下： ht=f（ht-1，xt） （11）
復位門的功能類似于LSTM遺忘門。由于GRU結構與LSTM結構相似，這里不再贅述。
1.4 軌跡規劃模型
隨機搜索算法：RRT算法通過狀態空間的隨機采樣點，把搜索導向空白區域，從而尋找到一條從起始點到目標點的軌跡。RRT-Master算法引入目標點作為隨機產生的引導因子，使隨機樹的生長更有效率，大大縮短了搜索時間。
啟發性搜索算法：A*算法是一種啟發性全局擇優搜索算法，搜索過程中沒有舍棄節點，避免了最優節點的丟失，可以找到最短路徑。A*算法估價函數可以表示為：
f（n）=g（n）+h（n） （12）
式（12）中，f（n）是節點n的估價函數，h（n）是狀態空間中從起點到終點的距離代價函數，g（n）是當前點到目標點的最優估計代價函數，反映搜索的啟發信息。
圖2（a）是RRT-Master軌跡路線，算法的枝丫生成步長是隨機的，一般取地圖尺寸的5%-10%，從圖中可以看出軌跡曲折性很大，且可重復性小，是一種不完備搜索算法。圖2（b）是A*搜索的機器人軌跡。作為一種完備性搜索算法可以搜索出最優路徑，但搜索地圖尺寸越大，g（n）節點信息越多，計算量就會變大，運行耗費時間相應增多。
概率性搜索算法：PRM將連續空間轉換成離散空間，再利用基于圖的規劃算法（D，A*等）在網絡圖上尋找路徑，算法分為兩個階段：
�。�1）網絡圖構建。在狀態空間中隨機撤點（自定義個數），構建路徑網絡圖。
�。�2）路徑查詢。將起始點和目標點連接到網絡圖中，利用A*完成路徑搜索。靜態軌跡規劃中只需進行一次搜索就可產生引導路徑。
圖3（a）是采樣點網絡圖，圖3（b）是軌跡路線圖。地圖采樣點數是隨機的，當采樣點較少時得到的是不完備地圖，當采樣點增加時得到的軌跡可以趨近于一條完備路徑，但對計算機的資源消耗也會相應增多。綜合算法效率和穩定性考慮，本文使用PRM算法作為路徑規劃算法。
2 預測交通流量
2.1 數據描述與實驗設計
本文使用PEMS數據集。在加利福尼亞范圍內部署了超過15000臺傳感器，多次分析數據集發現5分鐘的交通流量預測更合適。其中缺失數據僅占整個數據集的一小部分，所以使用歷史平均值來估算缺失數值，以下實驗基于該數據集。
實驗選擇過去30分鐘的交通流量，實際上是用6個數據點的時間序列預測未來5分鐘的交通流量。前三周用于訓練模型，第四周數據用于測試模型。由于每個路段可能都有自己的交通流模式，沒有一個通用模式可以適應所有路段，因此為每個道路口構建唯一一個由單個傳感器收集的交通流量模型。實驗中使用均方誤差（MSE）比較算法性能。
2.2 基于參數模型的交通流量預測
首先使用傳統回歸模型嶺回歸（Ridge）、彈性網絡（Elastic Net）、支持向量回歸（SVR）。
圖4（a）中橫軸為實驗次數，縱軸為代價損失函數。為使實驗能更好地展示各算法性能優劣，首先打散數據集，然后對每個模型進行CROSS validation=5的交叉驗證，每個模型實驗20次�？梢钥闯鯡lastic Net優于Ridge，也優于SVR且更穩定，從圖4（b）中看出總體偏差很大。
2.3 基于非參數模型的交通流量預測
非參數模型中，隨機森林回歸（RFR）、LSTM模型以及GRU模型預測結果如圖5所示。
從圖5（a）可以看出，非參數模型代價損失函數明顯低于參數模型。其中隨機森林回歸雖然表現相對穩定但整體偏差較大，LSTM與GRU表現接近，但在算法運行過程中GRU耗費時間比LSTM少了近30%。不過實際應用仍選擇精度稍高的LSTM模型作為最終的交通流量預測模型。
3 仿真實驗
機器人行駛道路環境的衛星地圖經過二值化處理生成黑白二值圖像，道路區域由0值表示，非道路區域用l值表示，即圖7（a）中白色通道和黑色多邊形區域（只考慮主干路線，冗余的支線略去），機器人移動區域就是圖中的白色道路區域。
為了對比實驗結果，首先采用PRM在原始道路中進行路徑規劃，見圖7（b）。接著，采用深度學習模型進行道路交通流量預測，見圖7（c），圖中黃色區域為擁堵路段即車流量在未來5分鐘大于1000輛，從交通道路段集合O刪除黃色路段編號。此時重新運行PRM算法，規劃出一條時間較短且較安全的新路徑，見圖7（d）。
4 結語
為了更好地幫助機器人完成路徑規劃任務，本文對交通流量進行了預測。經過對比參數模型和非參數模型，發現對于非線性的交通車流量預測，非參數模型LSTM預測效果更好，以此得到優化的交通網絡圖。最后利用PRM路徑規劃算法尋找到最優路徑。該模型算法還可進一步優化，如加入啟發式算法優化機器人回調路徑。
(蔬車)
DOI：10.11907/rjdk.192115開放科學（資源服務）標識碼（OSID）：
中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）006-0015-04
0 引言
巡邏機器人是一種自動、半自動或由人類控制完成安防工作的機器人，其主要技術之一就是軌跡規劃。蔣偉等通過拉格朗日插入值優化A*運動軌跡點找尋最短軌跡;魏玉等提出偏向目標的改進RRT算法優化機器人行駛時間;孫欽鵬等通過動態設置機器人最小轉彎半徑和最小安全距離以確保機器人安全導航。對于傳統軌跡規劃算法的優化，雖然能得到一條較優的規劃軌跡，但當道路發生擁堵、事故、人流量暴增等情況時，實用性會很差。
智能交通是智慧城市的重要組成部分。Tian等采用基于長短期記憶（LSTM）算法分析不規則采樣和丟失的交通流量數據;程健等通過基于狀態的過濾模塊優化交通物理對象（TPO）與交通信息空間（TIS）的人工智能算法;Chen等提出模糊深度學習方法FDCN預測交通流量。
這些交通流量預測研究為機器人軌跡規劃提供了較好的基礎。本文提出一種基于深度學習的改進機器人軌跡規劃算法。首先，使用深度學習算法對交通流量進行預測;其次，通過交通流量的預測結果優化交通網絡圖;最后，采用軌跡規劃算法獲得行駛路徑。
1 系統模型
交通流量預測在城市交通管理中非常重要，目前產生了很多交通流量預測方法，一般將其分為參數模型和非參數模型兩類。
1.1 模型介紹
參數模型：此類算法通常由簡單模型實現并能夠明確理解，因此建模實現相對容易。常見的有嶺回歸算法（Ridge Regression）、彈性網絡（Elastic Net）、支持向量回歸（Support Vector Regression）等。但由于交通流的隨機性，參數模型無法很好地描述這種隨機特性。
非參數模型：指沒有固定結構且沒有固定參數的模型。流行的非參數模型有k近鄰算法（k nearest neigh.bor，KNN）、隨機森林（Random Forest）、人工神經網絡（Artificial Neural Network，ANN）等�；谏窠浘W絡的非參數模型具有優越的映射能力，幾乎可以使所有函數適應任意精度。
對于公路環境路徑規劃問題，本文通過分析隨機性搜索算法（Rapidly exploring random Trees，RRT）、概率性搜索算法（Probabilistic Roadmap，PRM）和啟發性搜索算法A*（A-Star），尋找最優規劃算法。
1.2 參數模型
Ridge回歸，即在線性回歸損失函數上直接加入一個正則項，使模型不但可以擬合數據，并且能夠使參數權重盡量小。這個正則項只需在訓練進程中加入損失函數。
Lasso回歸是另一種正則化的線性回歸。與嶺回歸相似，在損失函數上增加了一個正則化項，但是使用權重向量的L1范數而不是權重向量L2范數平方的一半。
Elastic Net彈性網絡介于Ridge回歸與Lasso回歸之間，它的正則項是Ridge回歸和Lasso回歸正則項的混合。該模型能夠調控它們的混合率，當r=0時，彈性網絡就是Ridge回歸，當r=1時，其就是Lasso回歸。
式（1）-式（3）分別是Ridge回歸、Lasso回歸和ElasticNet回歸的代價損失函數，其中Ridge回歸應用L2范數，Lasso回歸應用Ll范數，Elastic Net回歸應用L1+L2的混合范數，實現正則化。
SVM模型中邊界上的點以及兩條邊界內部違反margin的點被當作支持向量，在后續預測中起作用。在SVR模型中邊界上的點以及兩條邊界以外的點被當作支持向量在預測中起作用。從圖1可以看到，在margin內部的這些點誤差都為0，只有超出margin的點才會計算error。
1.3 非參數模型
1.3.1 LSTM神經網絡
RNN神經網絡最初用于語言模型，因為它具有長期記憶能力。但隨著時間增長，RNN的梯度可能會隨著網絡層數增加變為非常深的前饋神經網絡。為了解決梯度消失問題，提出了具有遺忘門的RNN結構（LSTM）。
LSTM神經網絡的典型結構由輸入門、存儲單元、遺忘門和輸出門4個門組成。輸入門從外部獲取新數據，存儲單元接收輸入數據最后一次迭代結果，遺忘門決定何時遺忘輸出結果，輸出門計算所有的輸出單元為LSTM的輸出結果。
輸入的時間序列特征表示為X=（x1，x2，…，xn），隱藏層記憶細胞的狀態H=（h1，h2，…，hn），輸出時間序列結果為Y=（Y1，Y2，…，Yn），LSTM網絡計算如下：
其中，y代表實際交通流量，p代表預測交通流量。為了最小化訓練誤差，同時防止局部最優出現，使用Adam梯度下降法。神經網絡容易出現過擬合問題。常用正則化配合dropout的方法解決過擬合問題。由于LSTM神經細胞的傳遞具有“記憶”特性，使得該網絡在交通流量預測方面具有特殊優勢。
1.3.2 GRU神經網絡
GRU作為LSTM的一種變體，將遺忘門和輸入門合并為一個更新門。與LSTM單元類似，隱藏單元輸出為ht，是使用隱藏單元輸出ht-1和當前特征Xt計算的，公式如下： ht=f（ht-1，xt） （11）
復位門的功能類似于LSTM遺忘門。由于GRU結構與LSTM結構相似，這里不再贅述。
1.4 軌跡規劃模型
隨機搜索算法：RRT算法通過狀態空間的隨機采樣點，把搜索導向空白區域，從而尋找到一條從起始點到目標點的軌跡。RRT-Master算法引入目標點作為隨機產生的引導因子，使隨機樹的生長更有效率，大大縮短了搜索時間。
啟發性搜索算法：A*算法是一種啟發性全局擇優搜索算法，搜索過程中沒有舍棄節點，避免了最優節點的丟失，可以找到最短路徑。A*算法估價函數可以表示為：
f（n）=g（n）+h（n） （12）
式（12）中，f（n）是節點n的估價函數，h（n）是狀態空間中從起點到終點的距離代價函數，g（n）是當前點到目標點的最優估計代價函數，反映搜索的啟發信息。
圖2（a）是RRT-Master軌跡路線，算法的枝丫生成步長是隨機的，一般取地圖尺寸的5%-10%，從圖中可以看出軌跡曲折性很大，且可重復性小，是一種不完備搜索算法。圖2（b）是A*搜索的機器人軌跡。作為一種完備性搜索算法可以搜索出最優路徑，但搜索地圖尺寸越大，g（n）節點信息越多，計算量就會變大，運行耗費時間相應增多。
概率性搜索算法：PRM將連續空間轉換成離散空間，再利用基于圖的規劃算法（D，A*等）在網絡圖上尋找路徑，算法分為兩個階段：
�。�1）網絡圖構建。在狀態空間中隨機撤點（自定義個數），構建路徑網絡圖。
�。�2）路徑查詢。將起始點和目標點連接到網絡圖中，利用A*完成路徑搜索。靜態軌跡規劃中只需進行一次搜索就可產生引導路徑。
圖3（a）是采樣點網絡圖，圖3（b）是軌跡路線圖。地圖采樣點數是隨機的，當采樣點較少時得到的是不完備地圖，當采樣點增加時得到的軌跡可以趨近于一條完備路徑，但對計算機的資源消耗也會相應增多。綜合算法效率和穩定性考慮，本文使用PRM算法作為路徑規劃算法。
2 預測交通流量
2.1 數據描述與實驗設計
本文使用PEMS數據集。在加利福尼亞范圍內部署了超過15000臺傳感器，多次分析數據集發現5分鐘的交通流量預測更合適。其中缺失數據僅占整個數據集的一小部分，所以使用歷史平均值來估算缺失數值，以下實驗基于該數據集。
實驗選擇過去30分鐘的交通流量，實際上是用6個數據點的時間序列預測未來5分鐘的交通流量。前三周用于訓練模型，第四周數據用于測試模型。由于每個路段可能都有自己的交通流模式，沒有一個通用模式可以適應所有路段，因此為每個道路口構建唯一一個由單個傳感器收集的交通流量模型。實驗中使用均方誤差（MSE）比較算法性能。
2.2 基于參數模型的交通流量預測
首先使用傳統回歸模型嶺回歸（Ridge）、彈性網絡（Elastic Net）、支持向量回歸（SVR）。
圖4（a）中橫軸為實驗次數，縱軸為代價損失函數。為使實驗能更好地展示各算法性能優劣，首先打散數據集，然后對每個模型進行CROSS validation=5的交叉驗證，每個模型實驗20次�？梢钥闯鯡lastic Net優于Ridge，也優于SVR且更穩定，從圖4（b）中看出總體偏差很大。
2.3 基于非參數模型的交通流量預測
非參數模型中，隨機森林回歸（RFR）、LSTM模型以及GRU模型預測結果如圖5所示。
從圖5（a）可以看出，非參數模型代價損失函數明顯低于參數模型。其中隨機森林回歸雖然表現相對穩定但整體偏差較大，LSTM與GRU表現接近，但在算法運行過程中GRU耗費時間比LSTM少了近30%。不過實際應用仍選擇精度稍高的LSTM模型作為最終的交通流量預測模型。
3 仿真實驗
機器人行駛道路環境的衛星地圖經過二值化處理生成黑白二值圖像，道路區域由0值表示，非道路區域用l值表示，即圖7（a）中白色通道和黑色多邊形區域（只考慮主干路線，冗余的支線略去），機器人移動區域就是圖中的白色道路區域。
為了對比實驗結果，首先采用PRM在原始道路中進行路徑規劃，見圖7（b）。接著，采用深度學習模型進行道路交通流量預測，見圖7（c），圖中黃色區域為擁堵路段即車流量在未來5分鐘大于1000輛，從交通道路段集合O刪除黃色路段編號。此時重新運行PRM算法，規劃出一條時間較短且較安全的新路徑，見圖7（d）。
4 結語
為了更好地幫助機器人完成路徑規劃任務，本文對交通流量進行了預測。經過對比參數模型和非參數模型，發現對于非線性的交通車流量預測，非參數模型LSTM預測效果更好，以此得到優化的交通網絡圖。最后利用PRM路徑規劃算法尋找到最優路徑。該模型算法還可進一步優化，如加入啟發式算法優化機器人回調路徑。
(蔬車)