基于神經網絡的無人車越障規(guī)劃算法

鄭以君 陳秋蓮 蔣環(huán)宇

摘要：研究一種基于神經網絡的無人車越過障礙自動抵達指定地點的路徑規(guī)劃算法。神經網絡具有高度并行的結構且適用于提高無人車路徑規(guī)劃算法的運行速度，神經網絡結構算法成了避過障礙、規(guī)劃全局與局部較優(yōu)路徑過程必不可少的重要部分。理論表明該算法可以快速地規(guī)劃無碰撞的較優(yōu)路徑。

關鍵詞：神經網絡；越障；路徑規(guī)劃

中圖分類號：TP393 文獻標識碼：A

文章編號：1009-3044（2019）10-0181-03

開放科學（資源服務）標識碼（OSID）：

1 引言

無人車路徑規(guī)劃是智能導航過程中必不可少的重要部分，它除了需要對在具有障礙物的環(huán)境中規(guī)劃出一條從起始點至終點的無碰撞的路徑，還應該對整體路徑長度進行最短方案的優(yōu)化。

無人車的行進環(huán)境空間可以利用前向型神經網絡進行描述，將構成環(huán)境空間中的障礙物約束條件依次輸入該神經網絡結構中依照輸出的結果即可判別此路徑點是否在障礙物內。神經網絡作為一個具有高度非線性并行處理的運算結構，同時具備網絡的全局作用及高度魯棒性，為無人車系統(tǒng)路徑規(guī)劃實時性提供了很高的可行性。在此研究中，神經網絡的運算相當于一個代價約束函數，首先是因為在神經網絡結構中障礙物是以凸多邊形模型數值表示的，當行進向下一個路徑點時只需要使用該路徑點與環(huán)境中的障礙物信息[1]。神經網絡將運動物體視作一個質點進行模擬。最后，運用模擬退火法對局部極值問題進行優(yōu)化。

無人車路徑規(guī)劃可劃分為環(huán)境全部或者部分未知的局部路徑規(guī)劃與已知環(huán)境的全局路經規(guī)劃。環(huán)境已知的全局路徑規(guī)劃算法主要有人工勢場法、粒子群算法等，但該類普遍用于二維運動環(huán)境中。人工勢場法的應用于此類問題中的工作方式為構建目標點、環(huán)境障礙物與無人車的勢場模型，無人車只需要順延著勢場能量的梯度方向行進方向就可以找到避開障礙物的路徑，其好處是快速、高效，然而該算法有局部極小值的問題并且不適用于尋求最優(yōu)結果[2]。本文主要介紹前向型神經網絡路徑規(guī)劃為主，禹建麗等[3，4，5，6]給出的基于神經網絡的路徑規(guī)劃算法，得出結果收斂快、運算簡便，并且可以避免某些局部極小值問題并規(guī)劃出最短路徑，并且經過改良以后可以用于未知環(huán)境下的機器人路徑規(guī)劃問題[7，8]。同時易于從二維擴展到三維的情況中。

2 基于神經網絡的越障路徑規(guī)劃算法

2.1 無人車行進環(huán)境障礙物的神經網絡描述

前向型神經網絡的作用之一是用于描述無人車行進至終點過程中所在的障礙物，通過神經網絡對所在路徑點與多邊形障礙的約束條件的關系即可完整的描述障礙物信息，具體關系如下所述：無人車所在路徑點[pi（xi，yi）]作為神經網絡輸入層的輸入數據，每個多邊形障礙物可以使用一個不等式組描述，每個不等式中變量的系數為輸入層與隱藏之間的權值，常數項為隱層的閾值，示例如下：

圖1描述的是長方形的障礙物和描述相應的障礙物不等式組。由圖得知，通過判別某個路徑點是否符合并同時符合該不等式組的條件即可了解該路徑點是否位于障礙物里，通過規(guī)劃出來的路徑點與障礙物空間對比即可知路徑點直接按是否經過障礙物，環(huán)境空間的點集[pi（xi，yi）]與凸多邊形障礙物所坐落位置可用圖2所示的神經網絡結構模型來描述。

輸入層的2個底層節(jié)點分別是計算路徑點[pi]的[xi]，[yi]坐標，輸入層節(jié)點到中間層節(jié)點的連接權值系數去為每個不等式中[x]，[y]的系數，中間層為神經網絡隱層節(jié)點的閾值，用不等式中的常數項表示，隱層到頂層節(jié)點的連接權值系數均為常數1，頂層節(jié)點的輸出值為環(huán)境中路徑點對障礙物的碰撞罰函數，表示路徑點對于障礙物的碰撞程度，頂層節(jié)點的閾值取每個不等式的個數減去0.5后的相反數。

式中，[IMm]為中間層第m個節(jié)點的輸入；[Wxm]，[Wym]，為第m個不等式限制條件的系數；[θMm]為神經網絡隱層第m個節(jié)點的閾值，G為該層的節(jié)點數；[OMm]為中間層第m個節(jié)點的輸出值；T1為各個中間層結構與閾值的求和值作為頂層節(jié)點輸入值；[θo]為頂層節(jié)點的閾值；[C]為輸出層節(jié)點輸出，數值范圍為（0，1），數值越大表明越接近障礙物，其罰函數形狀則相對于非障礙物位置越陡峭；選擇S型函數[f（x）=1（exp（-xT））]為激活函數，參數T影響罰函數的形狀，T（t）=[βlog（1+t）]，是模擬退火算法中的“溫度”，其含義是，隨著時間[t]路徑點將向著盡可能避開障礙物并且使得整體路徑比較短的位置移行進。但由于模擬退火位于在起始時溫度比較高，無人車的路徑點行進到遠遠避開障礙物的位置，隨著該溫度降低，無人車路徑的長度將逐步減小，最終，將其路徑收斂到避障的狀態(tài)。

2.2 基于神經網絡碰撞罰能量的最優(yōu)路徑規(guī)劃

無人車路徑規(guī)劃需要處理兩個優(yōu)化問題：首先是無人車避開障礙物避免任何程度的碰撞；其次是規(guī)劃的路徑是最短的。這兩個要求得以滿足，則無人車規(guī)劃的路徑則可為最優(yōu)路徑規(guī)劃。

3 結論

基于神經網絡的路徑規(guī)劃算法的實現過程：首先根據已知障礙物環(huán)境的約束方程，建立障礙物模型；確定起點和終點，連接這兩點，并取路徑上若干點集均分線段作初始迭代路徑點；利用神經網絡對應其參數與激發(fā)函數運算出各個路徑點的偏導數以作為下一個路徑點的運算基礎，經過完整的迭代過程后如果符合終止條件[x'<Δ]，[y'<Δ]，則退出運算。最后對最終結果進行保存與繪制仿真圖形。

基于神經網絡的路徑規(guī)則算法可規(guī)劃出最短路徑，而且收斂較快，計算方式簡便。該算法除了適用于環(huán)境中障礙物為凸多邊形構成的形狀外， 同時還適用于環(huán)境中障礙物是圓形的情形，并可以簡單地避免某些情況下的局部極小值，為無人車的最優(yōu)化行進路徑規(guī)劃提供了一個簡便有效的算法。

參考文獻：

[1] 孫增圻.智能控制理論與技術[M].北京：清華大學出版社，2000.

[2] 戴博，肖曉明，蔡自興.移動機器人路徑規(guī)劃技術的研究現狀與展望[J].控制工程， 2005， 12 （3） ： 113- 116 .

[3] 禹建麗，V.Kromov，孫增圻，成久洋之. 一種快速神經網絡路徑規(guī)劃算法[J].機器人Robot ， 2001， 23 （3） ：201-205.

[4] 禹建麗，程思雅，孫增圻，V.Kromov.一種移動機器人三維路徑規(guī)劃優(yōu)化算法[J].中南大學學報（自然科學版），2009， 40 （2） ：471-477.

[5] 魏冠偉，付夢印.基于神經網絡的機器人路徑規(guī)劃算法[J].計算機仿真，2010，7：112-116.

[6] 陳志華，謝存禧，曾德懷.基于神經網絡的移動機器人路徑規(guī)劃算法的仿真[J].華南理工大學（自然科學版），2003，6：56-59.

[7] 宮孟孟.基于神經網絡的移動機器無人車路徑規(guī)劃方法研究[D].哈爾濱工業(yè)大學，2017.

[8] AnminZhu，Simon X. Yang.A Neural Network Approach to Dynamic Task Assignment of Multirobots[J].IEEE Transactions On Neural Networks，2006，9（17）：471-477.

【通聯編輯：代影】