基于遺傳算法的機器人在全局靜態(tài)環(huán)境中路徑規(guī)劃研究

張濤+李繼生+王鳳萍

摘 要：隨著智能控制的快速發(fā)展，移動機器人都被賦予了一定的智能自主能力。本文以靜態(tài)環(huán)境路徑規(guī)劃為研究重點，通過對路徑規(guī)劃方法和遺傳算法相關(guān)工作進行了研究，設(shè)計了一套基于遺傳算法的靜態(tài)全局路徑規(guī)劃算法，運用MATLAB對該路徑規(guī)劃算法進行了仿真研究，并分析了相關(guān)參數(shù)對路徑規(guī)劃效果的影響，以及參數(shù)合理調(diào)整的基本思路；最后也初步研究并仿真了動態(tài)環(huán)境下的路徑規(guī)劃算法。

關(guān)鍵詞：移動機器人；路徑規(guī)劃；遺傳算法； MATLAB仿真

DOI：10.16640/j.cnki.37-1222/t.2017.04.192

1 引言

遺傳算法是國際上廣泛應(yīng)用的一種新型參數(shù)優(yōu)化方法，傳統(tǒng)的優(yōu)化方法在解決路徑規(guī)劃這類復(fù)雜非線性問題中缺乏足夠的魯棒性，因此研究遺傳算法對于移動機器人全局路徑規(guī)劃的發(fā)展也起到了推動作用。

根據(jù)對環(huán)境的了解情況，路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃，從靜態(tài)或動態(tài)地獲取障礙物信息角度看，全局路徑規(guī)劃屬于靜態(tài)規(guī)劃，而局部路徑規(guī)劃則是動態(tài)規(guī)劃，在移動機器人的應(yīng)用中需要精確的位置信息，是機器人在執(zhí)行任務(wù)時首先應(yīng)具備導(dǎo)航和定位能力。

2 基于遺傳算法的全局路徑規(guī)劃研究

遺傳算法的各個部分是相互作用的，這些參數(shù)組合起來的情況非常多，通過手工調(diào)節(jié)找到最佳的參數(shù)組合很困難。如果能在演化過程中，使程序自行調(diào)節(jié)這些參數(shù)，就能使算法適用于更多類型的問題。

仿真運動環(huán)境為二維平面空間，已知靜態(tài)障礙物信息，動態(tài)障礙物（數(shù)量為1個）可以進行探測。我們的目標(biāo)是要在已知的靜態(tài)環(huán)境里，讓移動機器人自主找到一條從當(dāng)前位置到目標(biāo)位置的行動路線，要求這條路徑不與障礙物發(fā)生沖突并盡可能短，且該路徑應(yīng)與障礙物保持一定的安全距離。

主要從以下幾個方面描述：（1）環(huán)境及染色體的表示。因為是已知環(huán)境下的路徑規(guī)劃，因此機器人的運動環(huán)境用一個矩形的黑白二值位圖表示，其中黑色區(qū)域表示障礙區(qū)域，而白色區(qū)域表示可自由通行的區(qū)域。（2）初始種群的生成。對于基本遺傳算法來說，初始種群的產(chǎn)生是通過隨機的方式產(chǎn)生的。在路徑上隨機選擇n個節(jié)點構(gòu)成一條路徑作為一個染色體。這樣形成的初始種群進化效率明顯高于隨機生成的方法，且不喪失遺傳算法的全局搜索能力。（3）路徑評估。對路徑優(yōu)劣程度的評估作為遺傳算法中染色體的適應(yīng)值。因此要將規(guī)劃路徑時的要求包含進去，并用數(shù)值的形式體現(xiàn)出來，以便進行比較和衡量。由于染色體是可行路徑或不可行路徑，因此對這兩種情況分別進行處理：對于可行路徑的適應(yīng)值我們考慮安全性、路徑長度、平滑性這三個因素。不可行路徑的適應(yīng)值計算需考慮不可行線段數(shù)與總線段數(shù)的比、不可行線段與障礙物的交叉深度和路徑的總長度等因素。

（4）遺傳操作。根據(jù)路徑規(guī)劃問題的實際情況，主要使用了3種遺傳操作算子：選擇、交叉、變異。由于選擇方式采用排序選擇，所以無需考慮個體適應(yīng)度是否取正值或負(fù)值以及個體適應(yīng)度之間的數(shù)值差異程度，這樣可以避免因優(yōu)秀個體充斥種群空間導(dǎo)致的早熟。本次采用單點交叉的方法，且首先作用在不可行路徑片段上，再按隨機方式選擇交叉點。本文中采用的變異方式有增加一個點、減少一個點、移動一個點3種方式，在程序執(zhí)行時隨機選擇任意一種作為某一父代個體的變異操作。將判斷算法收斂的條件設(shè)為：若連續(xù)進化500次，最優(yōu)解均未發(fā)生變化，且種群的平均適應(yīng)值提高不足1%，則算法進化代數(shù)已達(dá)到了設(shè)定的最大值。本次實驗通過定義一種簡單又不影響遺傳算法隨機性的環(huán)境，在該環(huán)境下運行9次比較其結(jié)果。

3 靜態(tài)（全局）環(huán)境仿真

本次對環(huán)境進行仿真的路徑規(guī)劃是尋找滿足安全和路線平滑條件下的最短路徑也就是求最小值，因此以下各圖中適應(yīng)值越小，則該路徑越好。對于靜態(tài)環(huán)境仿真，本次設(shè)定的任務(wù)，即：遍歷N個已知節(jié)點，找到最優(yōu)路徑，最后返回起點，類似于旅行商問題。

（1）改變進化代數(shù)K（Pc=0.9，Pm=0.2），連續(xù)仿真9次，其數(shù)據(jù)分析表1如下。

圖1（a）（b）對應(yīng)進化代數(shù)為K=500，2000的仿真結(jié)果。

從仿真結(jié)果分析，當(dāng)交叉和變異的概率都不變時，進化代數(shù)K越大，規(guī)劃出來的路徑越優(yōu)。

（2）改變交叉概率Pc（K=500， Pm=0.2），連續(xù)仿真9次，其數(shù)據(jù)分析表2如下。

圖2（a）（b）對應(yīng)交叉概率為Pc =0.00009，0.9的仿真結(jié)果。表2是進化代數(shù)不同連續(xù)仿真9次對應(yīng)的時間和路徑長度。

（3）改變變異概率Pm（K=500，Pc=0.9）連續(xù)仿真9次，分析如表3所示。

圖3（a）（b）對應(yīng)變異概率Pm =0.00002，0.7的仿真結(jié)果。

從以上仿真結(jié)果分析，經(jīng)過調(diào)整參數(shù)后，可以看到本搜索算法成功地找到了近似最優(yōu)的可行路徑。另外可以看到算法的計算時間稍長，還需要進一步優(yōu)化，在以后的研究中將運用MATLAB對動態(tài)路徑規(guī)劃算法進一步仿真研究，并分析了相關(guān)參數(shù)對路徑規(guī)劃效果的影響，以及參數(shù)合理調(diào)整的基本思路。

參考文獻：

[1]王小平，曹立明.遺傳算法理論和應(yīng)用與軟件實現(xiàn)[M].西安交通大學(xué)出版社，2002.

[2]薛毅.最優(yōu)化原理與方法[M].北京工業(yè)大學(xué)出版社，2001.

[3]吳曉濤，孫曾沂.用遺傳算法進行路徑規(guī)劃[J].清華大學(xué)學(xué)報，1995：14-19.

[4]陳剛.復(fù)雜環(huán)境下路徑規(guī)劃問題的遺傳路徑規(guī)劃方法.機器人[J]，2001：230-233.

[5]龔進峰.數(shù)字勢場和遺傳算法的機器人路徑規(guī)劃的方法[J].天津大學(xué)學(xué)報，2002：525-529.

[6] 孫樹棟，曲嚴(yán)賓.遺傳算法在機器人路徑規(guī)劃中的應(yīng)用研究[J].西北工業(yè)大學(xué)學(xué)報，1998：79-82.

[7] 周明，孫樹棟.遺傳算法原理及應(yīng)用[M].國防工業(yè)出版社，1999.

作者簡介：張濤（1987-），碩士研究生，天津職業(yè)技術(shù)師范大學(xué)國有資產(chǎn)管理處管理員，研究方向：智能控制、機電一體化。