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

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

1 遺傳算法

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

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

障礙物的描述：

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

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

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

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

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

路徑長度啟發(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個路徑點所連兩條路徑的夾角。

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

[f=f2+f3-f1]

1.3遺傳操作

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

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

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

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

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

2人工勢場算法

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

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

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

機器人受力分析圖如圖4。

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

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

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

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

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

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

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

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

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

4實驗結(jié)果

4.1實驗平臺與環(huán)境

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

4.2實驗結(jié)果

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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