陳麒瑞 杜少華 趙騰飛 宋瑩

摘要：隨著科學技的發(fā)展，機器人技術得到了飛速的進步，如今機器人已經成為我們生產生活的一部分，從工業(yè)制造，衛(wèi)星導航到無人駕駛技術等。而作為機器人技術重要的課題之一，路徑規(guī)劃算法也得到了學者們的重視，先后相繼提出了各種各樣的算法。

關鍵詞：人工神經網絡;路徑規(guī)劃;移動機器人

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

文章編號：1009-3044（2020）03-0227-03

1 概述

自古以來人們一直夢想制造一種像人一樣的機器，來代替人類做工作，來完成各種危險而復雜的任務，使人類從繁重的體力勞動中解放出來。早在1920年，捷克斯洛伐克的作家卡雷爾·恰佩克就在他的小說中提出了機器人的概念，但直到1961年美國才真正制造出世界上第一臺工業(yè)機器人。隨著科技的不斷發(fā)展，機器人技術也迎來了迅猛的進步，從20世紀70年代的傳感技術、現(xiàn)代控制技術再到如今的人工智能，機器人的研究一直是一個熱點話題。

在移動機器人導航技術應用過程中，其核心就是路徑規(guī)劃算法，路徑規(guī)劃要求機器人可以自己判定障礙物，主決定路徑，避開障礙物。因此，研究出一種算法使得機器能夠在最短的時間內，規(guī)劃出一條路徑長度最短、沒有障礙物碰撞的路徑，就成了學者們研究的重點課題。

本文基于人工神經網絡提出一種路徑規(guī)劃算法，利用人工智能神經網絡求出路徑中障礙物的罰函數(shù)并由此得到路徑能量函數(shù)，再利用退火算法對該函數(shù)求極小值，從而得到最優(yōu)路徑。

2 相關工作

路徑規(guī)劃經過幾十年的發(fā)展已經涌現(xiàn)出了許多有效的求解方法，目前移動機器人路徑規(guī)劃算法主要有以下幾類。

2.1 柵格法

柵格法是目前應用最為廣泛的路徑規(guī)劃算法之一，它將機器人周邊空間分解為相互連接但不重疊的空間單元，由這些單元構成一個連通圖，依據(jù)障礙物占有情況，從圖上搜索一條從起始單元格到終止單元格的最優(yōu)路徑。由柵格法規(guī)劃出的自由柵格多少直接影響路徑的長度，柵格越多則路徑越長。然而由于柵格法能將空間中的關系抽象為一個個柵格，大大簡化了計算，因此柵格法也是目前最主流的路徑規(guī)劃算法之一。

2.2 人工勢場法

人工勢場法來源于物理學，它將機器所處環(huán)境定義為一個勢場，所有障礙物描述為一個對機器人存在斥力的物體，而機器人目的地是一個存在引力的點。引力和斥力的合力為機器人的加速力，來控制機器人的運動方向和運動位置。該算法簡單，易于底層控制，但存在局部最優(yōu)解的問題，容易產生死鎖現(xiàn)象。在使用人工勢場法時可能使機器人在到達目的地之前就停留在局部最優(yōu)點。

2.3 蟻群算法

蟻群算法是一種模擬螞蟻覓食行為的智能算法，研究發(fā)現(xiàn)，螞蟻在覓食的過程中會在經過的路徑上留下一種物質，稱為信息素，其他的螞蟻能夠感知信息素是否存在以及強度的高低，并會傾向于爬向信息素濃度高的地方。這種方法主要用于解決最優(yōu)化問題，路徑長度越短，經過的螞蟻越多，則信息強度也就越高，這是一個正向反饋的過程，從而逼近直至找到全局最優(yōu)解。

3 相關算法

3.1 BP人工神經網絡

BP神經網絡，又稱為反向傳播網絡、多層前饋網絡，其大致結構如圖1所示：

由圖可知，該網絡一般由三層構成：輸入層、隱藏層、輸出層。同一層神經元之間沒有交互，隱藏層可以有多個。由實驗可知，該網絡可以逼近任意非線性函數(shù)。它是一種利用反向傳播算法進行訓練的多層前饋網絡，它的核心是利用梯度下降法，使輸出值和期望值的均方誤差最小。

3.2 退火算法

退火算法來源于物體退火過程。所謂的退火就是指物體降溫的過程，在降溫的過程中物體的內能會降低，當溫度降低至某一最低值時物體的溫度和內能會趨于穩(wěn)定。在最優(yōu)化算法中，該算法從起始點開始向周圍各個遍歷，如果周圍某個點的值比當前點小，則選擇更優(yōu)點。如果該點比當前點更大，則依據(jù)概率接受該點。

3.2.1 退火法模擬

退火法其實是一種貪心算法的變形，即每次選擇時都會選擇當前最優(yōu)點作為下一個擴展點，不同的是退火算法在獲得一個比當前解更差的解時并不會選擇拋棄，而是會以一個概率來使該解成為當前解進行下一次遍歷，因此退火算法可以避免陷入局部最優(yōu)解，從而達到全局最優(yōu)解。

根據(jù)蒙特卡洛定理，當高溫物體降溫的過程中，溫度穩(wěn)定的概率為，其中E為溫度為T時物體的能量，為固體降溫前后的溫度改變量，k為Boltzmann常數(shù)。對于上述定理可轉化為數(shù)學公式：

在解決優(yōu)化問題時可以對上述公式進行變更，得到的算法流程為：

（1）由初始解i和控制參數(shù)t開始。

（2）獲得下一個解i+l。

（3）對解i+l和i進行比較，如果解i+l優(yōu)于解i，則接受解i+l;否則便以一個概率來接受解i+l。

（4）每次迭代衰減t值。

（5）達到停止條件s時停止算法。

基于此我們對該算法進行模擬的到如下圖像：

圖像中綠色線條為模擬函數(shù)，藍色點為起始點，紅色點為算迭代得到的解，從圖像可以看出該解為全局最優(yōu)解。

3.3 基于人工神經網絡的路徑規(guī)劃算法

本課題主要利用BP神經網絡并結合退火法來進行路徑規(guī)劃，在路徑規(guī)劃問題中，難點在于如何將所求問題轉化為一個數(shù)學問題。本文基于環(huán)境已知的條件下，將機器人通過某一路徑所需要的代價定義為能量函數(shù)，其中能量函數(shù)包括兩個部分，一個部分表示路徑長度，另一個部分定義為碰撞懲罰，表示通過該路徑需要經過的障礙物，以此來表示機器人通過該路徑所需要的能量損耗。并通過退火算法來對該函數(shù)求極小值，由于退火算法概率選取差于當前解的次優(yōu)解，所以在迭代過程中可以避免陷入局部最小值，達到局部最優(yōu)的結果

3.3.1 人工神經網絡計算路徑罰函數(shù)

在環(huán)境已知的條件下，可以構建笛卡爾坐標系，將問題中對障礙物和路徑的表述轉化為數(shù)學表示。其中路徑為各個相鄰點之間的歐式距離的和，而用不等式組來表示相應的障礙物。我們使用三層BP神經網絡，第一層為輸入層，輸入層包含兩個神經元，表示坐標的x、v輸入;第二層為隱藏層，隱藏層中所包含的神經元數(shù)量為表述相應不等式的個數(shù)，隱藏層和輸入層之間連接的權數(shù)為不等式坐標的系數(shù)，使用的激活函數(shù)為sigmoid函數(shù);輸出層輸出相應障礙物的罰函數(shù)，輸出層結點的閾值取不等式結點個數(shù)減去0.5的負數(shù)。

我們建立下圖所示坐標系，坐標系中黑色塊表示為障礙物：

由于構建的能量函數(shù)可能在某一領域內存在多個最小值，故我們采用退火算法來逼近最小值。

3.4 模擬實驗

基于matlab我們進行了相關模擬實驗，對路徑可視化后到如下結果：

4 總結

本文基于人工神經網絡，討論了一種機器人路徑規(guī)劃算法，利用人工神經網絡計算路徑中障礙物的懲罰值，利用結點的歐式距離的和表示路徑長度，并將這兩部分的和表示為路徑的能量函數(shù)，利用退火算法求出能量函數(shù)的最小值，其結點構成的路徑便是全局最優(yōu)路徑。

參考文獻：

[1]耿煥同，陳正鵬，陳哲，等，基于平衡搜索策略的多目標粒子群優(yōu)化算法[J].模式識別與人工智能，2017，30（3）：224-234.

[2]劉祖兵，袁亮，蔣偉.基于模糊邏輯的移動機器人避障研究[J].機械設計與制造，2017（3）：101-104.

[3]劉曉磊，蔣林，金祖飛，等.非結構化環(huán)境中基于柵格法環(huán)境建模的移動機器人路徑規(guī)劃[J]機床與液壓，2016，44（17）：1-7.

[4]謝紅俠，馬曉偉，陳曉曉，等.基于多種群的改進粒子群算法多模態(tài)優(yōu)化[J].計算機應用，2016，36（9）：2516-2520.

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

[6]黃磊，蘇義鑫.基于神經網絡的移動機器人路徑規(guī)劃方法研究[J]控制理論與控制工程，2008（5）.

[7]崔建軍，魏娟.基于遺傳算法的移動機器人路徑規(guī)劃研究[J]測試計量技術及儀器，2008（9）.

[8]劉傳頌，楊靜宇.基于勢場法和遺傳算法的機器人路徑規(guī)劃技術研究[J].計算機應用技術，2012（3）.

[9]劉亮，曾明如.基于勢蟻群算法的機器人路徑規(guī)劃研究[J].控制理論與控制工程，2013（5）.