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

張濤+李繼生+王鳳萍

摘 要：隨著智能控制的快速發(fā)展，移動機器人都被賦予了一定的智能自主能力。本文以靜態(tài)環(huán)境路徑規(guī)劃為研究重點，通過對路徑規(guī)劃方法和遺傳算法相關(guān)工作進行了研究，設計了一套基于遺傳算法的靜態(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 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3（a）（b）對應變異概率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]王小平，曹立明.遺傳算法理論和應用與軟件實現(xiàn)[M].西安交通大學出版社，2002.

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

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

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

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

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

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

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