基于多算法結(jié)合的機(jī)器人路徑規(guī)劃算法

邱浩++楊為民++鮮子霆

摘要： 機(jī)器人的路徑規(guī)劃目前已有多種解決方案，如模擬物理學(xué)中場概念的人工勢場算法，以及智能算法中的遺傳算法。但每一種算法都有一定的局限性，每一種算法只在一定條件下才能達(dá)到最好的效果。本文著眼于對各個(gè)算法適應(yīng)的條件進(jìn)行分類，在相應(yīng)的條件下使用相應(yīng)的算法，開發(fā)出CPP（Combination Path Planning）算法，從而克服的各個(gè)算法的缺點(diǎn)，讓每種算法的優(yōu)點(diǎn)得到充分發(fā)揮。

關(guān)鍵詞：路徑規(guī)劃；條件適應(yīng)；遺傳算法；人工勢場算法

中圖分類號：TP242 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）17-0174-03

Abstract： There are variety of solutions of Robot path planning， such as the algorithm called artificial potential field algorithm， which simulation the potential form physics concept and genetic algorithm. But some limitations with these algorithm， which only gets the best result under certain conditions. So it is necessary for us to use one algorithm under the conditions match it best， by which every algorithm can work more effective.

Key words： path planning； condition match；genetic algorithm； artificial potential algorithm

為了更加深入的學(xué)習(xí)多智能體系統(tǒng)，開創(chuàng)了RoboCup項(xiàng)目，即機(jī)器人世界杯。近幾年來，機(jī)器人足球的國際賽事越來越普及。RoboCup是其中影響最大的。而路徑規(guī)劃問題又是RoboCup3D項(xiàng)目中的一個(gè)熱點(diǎn)研究領(lǐng)域。所謂路徑規(guī)劃，就是在仿真環(huán)境中找到一條從起點(diǎn)到終點(diǎn)的最優(yōu)，即最短路徑。不僅要考慮到路徑長度，還要考慮到障礙物的干擾。這樣，路徑規(guī)劃問題就涉及了實(shí)時(shí)避障問題，這兩個(gè)問題是反映智能雙足機(jī)器人的自主能力的關(guān)鍵性問題。如何在各種復(fù)雜的環(huán)境中找到無碰撞的最優(yōu)路徑本身就是一個(gè)高度智能的過程?；诖藛栴}的算法近年來也是層見疊出，新的算法和對傳統(tǒng)算法的改進(jìn)算法不斷涌現(xiàn)出來。有以模擬退火算法，人工勢場算法和模糊邏輯算法為代表的傳統(tǒng)算法；還有圖形化的算法，如C空間圖形法，自由空間法，以及柵欄法；而最新研究的智能仿生學(xué)算法從生物處的得到啟示，從蟻群覓食中得到的蟻群算法，從動物神經(jīng)網(wǎng)絡(luò)行為中學(xué)到的神經(jīng)網(wǎng)絡(luò)算法，還有模擬達(dá)爾文遺傳選擇和自然淘汰的遺傳算法。以上的每種算法都有其優(yōu)缺點(diǎn)，柵欄算法在一定的條件下可以得到最優(yōu)解，但是解的質(zhì)量取決于柵欄大小的選擇，柵欄越小，所需要的儲存空間也更大。而可視圖法每經(jīng)過一定周期，就需要重新計(jì)算路徑，尋找效率較低，以上兩種方法求得的路徑為折線，不適于機(jī)器人的運(yùn)動控制；人工勢場算法雖然克服了上述算法的缺點(diǎn)，但是存在局部最優(yōu)解的問題，即規(guī)劃路徑非全局最優(yōu)。而發(fā)展火熱的智能仿生學(xué)算法卻因?yàn)槠湫枰罅康拇鎯臻g以及相當(dāng)高的時(shí)空復(fù)雜度而不能在實(shí)時(shí)避障問題中大顯身手，還需要我們不斷地研究發(fā)展才能應(yīng)用到實(shí)際問題中。既然每種算法都有其適用范圍和不適用范圍，那我們可以就環(huán)境條件進(jìn)行分類，在每種環(huán)境下使用其適用的算法，可以讓每種算法的缺點(diǎn)得到最大程度的縮小，而優(yōu)點(diǎn)得到充分放大。本文就采用能夠得到全局最優(yōu)解的遺傳算法和存在局部最優(yōu)問題的人工勢場算法。兩種方法結(jié)合，在RoboCup3D的仿真平臺上測試。3D仿真平臺是采用C/S模式設(shè)計(jì)的機(jī)器人足球比賽平臺，平臺實(shí)現(xiàn)對真實(shí)的物理三維世界模型的模擬，該系統(tǒng)主要用于研究服務(wù)器的通信，基本動作及決策系統(tǒng)，對球員的感知等基本功能模塊。

1 遺傳算法

1.1遺傳算法路徑規(guī)劃的具體方法

遺傳算法（Genetic Algorithm，GA）啟發(fā)于自讓進(jìn)化的模型， 是一種在自然選擇和遺傳基礎(chǔ)上發(fā)展來的全局優(yōu)化算法。編碼、適應(yīng)度函數(shù)、初始群體、控制參數(shù)和遺傳操作過程是遺傳算法的五個(gè)基本要素；而遺傳操作又包括選擇、交叉復(fù)制、變異。

障礙物的描述：

在綜合考慮障礙物的搜索范圍和搜索效率等條件的情況下，以機(jī)器人的起始點(diǎn)S與目標(biāo)點(diǎn)D的連線長度|SD|為長，以|SD|/2位寬確定障礙物區(qū)域α，則區(qū)域α為障礙物搜索范圍。用集合Obstacle{}表示障礙物集合，元素為On，如第一個(gè)元素為O1，第二個(gè)元素為O2。且α內(nèi)On的表示為On（xn，yn）∈α，其中xn和yn分別為第n個(gè)元素在球傳平面的橫坐標(biāo)和縱坐標(biāo)。

將區(qū)域α的長分為m+1等分，寬分為n+1等分，這樣α內(nèi)就有了m*n個(gè)路徑點(diǎn)，在每一條平行于寬線的線（我們暫且稱之為橫線，m條）上有n個(gè)路徑點(diǎn)，在每一條橫線上取一個(gè)路徑點(diǎn)，這樣便形成了一條由各個(gè)橫線上的路徑點(diǎn)連成的一條路徑線β，我們這樣表示β：

其中Ln表示從開始點(diǎn)S開始第n條橫線上的一個(gè)路徑點(diǎn)P，xn、yn表示相應(yīng)的二維坐標(biāo)。

1.2建立啟發(fā)函數(shù)

啟發(fā)函數(shù)關(guān)系到遺傳迭代的方向，在最優(yōu)路徑的規(guī)劃中，我們要考慮到路徑長短，距離障礙物距離以及路徑平滑度三個(gè)因素。

路徑長度啟發(fā)函數(shù)為：

[f1=|LiLi+1|] （其中i從1到m-1）

距離障礙物啟發(fā)函數(shù) ：

[f2=DistanceL，Oi]（其中i從1到m-1），其中Distance表示障礙物集合中的任一障礙物到路徑的垂直距離。

路徑平滑度啟發(fā)函數(shù) ?3=∑∠LPi（其中i從1到m-1），其中∠LPi為第i個(gè)路徑點(diǎn)所連兩條路徑的夾角。

綜上，得出啟發(fā)函數(shù)為 ：

[f=f2+f3-f1]

1.3遺傳操作

編碼，采用二進(jìn)制編碼表示出路徑點(diǎn)，可將每一條橫線上的點(diǎn)編號，并用二進(jìn)制編碼，這樣每條路徑都可以用相應(yīng)的二進(jìn)制序列表示出來。

選擇合適的初始化參數(shù)，確定群體的大小、交叉概率以及最大遺傳代數(shù)。

隨機(jī)產(chǎn)生初始種群，即隨機(jī)產(chǎn)生一條路徑。

算出當(dāng)前種群中各個(gè)個(gè)體的適應(yīng)度，并記錄最優(yōu)個(gè)體。

通過交叉復(fù)制和變異操作產(chǎn)生新的種群，并用新種群替換舊種群，此處要注意防止種群退化現(xiàn)象的出現(xiàn)。

2人工勢場算法

人工勢場算法最先是由Khatib博士在1986年提出，他采用這種方法來實(shí)現(xiàn)機(jī)器臂移動的避障規(guī)劃，而后眾多科研工作者對該方法進(jìn)行了深入的研究，并應(yīng)用到了機(jī)器人路徑規(guī)劃的問題中。

這種算法的基本思想來自于物理上的場的概念，在物理學(xué)的電場中，同種電荷之間作用為斥力，異種電荷間作用為引力。類比于這種思想，在機(jī)器人的運(yùn)動空間中建立一個(gè)引力和斥力共存的勢場，因?yàn)槟繕?biāo)是要到達(dá)目的地D，故在D點(diǎn)加入一個(gè)引力場，對機(jī)器人起吸引作用，且這個(gè)引力場的有效范圍是機(jī)器人的運(yùn)動空間；在障礙物點(diǎn)加入一個(gè)斥力場，對機(jī)器人起排斥作用，應(yīng)注意的是，該斥力場的作用范圍并不是機(jī)器人的全部運(yùn)功空間，而是以障礙物所在點(diǎn)為圓心，以一定距離為半徑的圓。機(jī)器人在自起始點(diǎn)向目標(biāo)點(diǎn)運(yùn)動的過程中，全程受到目標(biāo)點(diǎn)的引力作用，每當(dāng)進(jìn)入障礙物斥力作用范圍，便會受到斥力作用而偏離障礙物。圖3是人工勢場算法模型圖。

在其他介紹人工勢場算法的文獻(xiàn)中，都將勢函數(shù)與距離關(guān)聯(lián)起來，即勢函數(shù)是關(guān)于距離的函數(shù)。下面給出一種勢函數(shù)形式，作為介紹。

機(jī)器人受力分析圖如圖4。

3結(jié)合路徑規(guī)劃算法

上面介紹了遺傳算法和人工勢場算法的基本方法。在遺傳算法，m和n的取值直接影響到遺傳結(jié)果的優(yōu)劣，當(dāng)m和n取較大時(shí)，搜索區(qū)域α分的足夠精細(xì)，會取得較好的路徑結(jié)果，但算法的時(shí)空復(fù)雜度會很高，無法達(dá)實(shí)時(shí)避障的要求；反之，若取值較小，雖然計(jì)算速度會得到提升，但計(jì)算的結(jié)果卻不盡如人意。再來看看人工勢場算法，該算法是一個(gè)傳統(tǒng)算法，能夠很好地實(shí)現(xiàn)實(shí)時(shí)避障，但該算法有局部性問題，常常會陷入局部最優(yōu)的路徑中，很難計(jì)算出全局最優(yōu)的路徑。

作者嘗試一種新的思路，對環(huán)境條件進(jìn)行分析，根據(jù)環(huán)境來選擇不同的路徑規(guī)劃算法，可以最大程度的發(fā)揮各算法的優(yōu)勢。如何判斷環(huán)境條件，成了問題了的關(guān)鍵。人工勢場算法具有很好的實(shí)時(shí)性，在時(shí)間相對較為急迫，或者說，從開始點(diǎn)到目標(biāo)點(diǎn)的直線距離較近時(shí)，人工勢場算法更加適合。作為嘗試，作者在這里只選取了遺傳算法和人工勢場算法，讀者可以自行嘗試加入其他算法。

我們設(shè)置兩個(gè)環(huán)境條件參數(shù)，這兩個(gè)參數(shù)將幫助我們在相應(yīng)的環(huán)境下合理地選擇路徑規(guī)劃算法。

Dis：起始點(diǎn)到出發(fā)點(diǎn)的直線距離；

OB_N：在搜索區(qū)域α中，每單位面積中障礙物的個(gè)數(shù)。

其中，Dis的值我們可以直接根據(jù)S點(diǎn)和D點(diǎn)的二維空間坐標(biāo)直接得出，而求OB_N需要知道搜索空間α中障礙物的總數(shù)以及搜索空間α的面積。搜索空間α的面積為Dis與Dis/2的乘積，即Dis2/2；搜索空間中障礙物的總數(shù)可以通過窮舉障礙物集合中的所有元素，并一一判斷是否在搜索空間中得出。在3D平臺中，對方球員和我方球員均為障礙物，故除去自身，最多有21個(gè)障礙物。

在計(jì)算出這兩個(gè)參數(shù)的值以后，便可以使用這兩個(gè)參數(shù)來參考決定應(yīng)該使用的路徑規(guī)劃算法。在Dis大于一定值得情況下，我們需要取得偏向全局最優(yōu)的結(jié)果，應(yīng)使用遺傳算法進(jìn)行計(jì)算；在Dis小于一定值得情況下，時(shí)間較為緊迫，應(yīng)當(dāng)采用實(shí)時(shí)性較強(qiáng)的避障算法，故采用人工勢場算法；當(dāng)Dis在一定區(qū)間時(shí)，參考OB_N的值，OB_N較大，搜索區(qū)間較為擁擠，采用人工勢場算法；反之OB_N較小，采用遺傳算法。算法選擇圖如圖5。

其中的a，b，c人為確定，可以多次試驗(yàn)以取得較優(yōu)值。

4實(shí)驗(yàn)結(jié)果

4.1實(shí)驗(yàn)平臺與環(huán)境

本實(shí)驗(yàn)在RoboCup3D平臺下進(jìn)行，系統(tǒng)為Ubuntu14.04，rcssserver3d版本0.6.9，Roboviz可視化監(jiān)視器。

4.2實(shí)驗(yàn)結(jié)果

設(shè)定多組參數(shù)（a，b，c），經(jīng)實(shí)驗(yàn)分析后選擇較優(yōu)組合，其中a為12；b為20；c為10/128。將結(jié)合算法與遺傳算法和人工勢場算法分別應(yīng)用在Dreamwing3D隊(duì)伍代碼中，并進(jìn)行多次實(shí)時(shí)對抗，觀察到避障效果明顯優(yōu)化，同時(shí)記錄相應(yīng)數(shù)據(jù)，如圖6所示。

經(jīng)實(shí)驗(yàn)得出，基于遺傳算法和人工勢場算法的結(jié)合路徑規(guī)劃算法，路徑規(guī)劃效果明顯優(yōu)于單獨(dú)應(yīng)用上述兩種算法之一。

參考文獻(xiàn)：

[1] 吳晨光.基于改進(jìn)人工勢場法的機(jī)器人路勁規(guī)劃及其在RoboCup中的應(yīng)[D].南京：南京郵電大學(xué)，2012：16-20.

[2] 宿魯艷，梁志偉.RoboCup3D仿真平臺中足球機(jī)器人的避障規(guī)劃[D].南京：南京郵電大學(xué)，2013：1-5.

[3] 樊明濤，楊宜民.基于遺傳算法的雙足足球機(jī)器人路徑規(guī)劃[J]. 現(xiàn)代計(jì)算機(jī)：專業(yè)版，2012（36）.

[4] 鄭重虎.RoboCup3D仿真中雙足機(jī)器研究與開發(fā)[D].南京：南京郵電大學(xué)，2012：1-5.

[5] 人的運(yùn)動規(guī)劃與智能決策[D].南京：南京郵電大學(xué)，2013：8-19.

[6] 肖南峰.智能機(jī)器人[M].廣州：華南理工大學(xué)出版社，2008.

[7] 蔡自興.機(jī)器人學(xué)[M].北京：清華大學(xué)出版社，2009.

[8] 吳青松.基于遺傳算法的移動機(jī)器人路徑規(guī)劃研究[D].西安：電子科技大學(xué)圖書館，2005.

[9] 王于，林良明，顏國正.動態(tài)避障物環(huán)境下移動機(jī)器人路徑規(guī)劃[J].上海交通大學(xué)學(xué)報(bào)，2002，10（10）：1430-1434.

[10] 李智也.移動機(jī)器人路徑規(guī)劃問題的解決方案[J].計(jì)算機(jī)工程，2006，32（1）：189-192.