基于人工神經(jīng)網(wǎng)絡(luò)的機(jī)器人路徑規(guī)劃研究

陳麒瑞 杜少華 趙騰飛 宋瑩

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

關(guān)鍵詞：人工神經(jīng)網(wǎng)絡(luò);路徑規(guī)劃;移動(dòng)機(jī)器人

中圖分類號(hào)：TP3 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）03-0227-03

1 概述

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

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

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

2 相關(guān)工作

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

2.1 柵格法

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

2.2 人工勢(shì)場(chǎng)法

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

2.3 蟻群算法

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

3 相關(guān)算法

3.1 BP人工神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)，又稱為反向傳播網(wǎng)絡(luò)、多層前饋網(wǎng)絡(luò)，其大致結(jié)構(gòu)如圖1所示：

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

3.2 退火算法

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

3.2.1 退火法模擬

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

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

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

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

（2）獲得下一個(gè)解i+l。

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

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

（5）達(dá)到停止條件s時(shí)停止算法。

基于此我們對(duì)該算法進(jìn)行模擬的到如下圖像：

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

3.3 基于人工神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃算法

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

3.3.1 人工神經(jīng)網(wǎng)絡(luò)計(jì)算路徑罰函數(shù)

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

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

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

3.4 模擬實(shí)驗(yàn)

基于matlab我們進(jìn)行了相關(guān)模擬實(shí)驗(yàn)，對(duì)路徑可視化后到如下結(jié)果：

4 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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