基于遺傳算法的機器人在全局靜態環境中路徑規劃研究

張濤+李繼生+王鳳萍

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

關鍵詞：移動機器人；路徑規劃；遺傳算法； MATLAB仿真

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

1 引言

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

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

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

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

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

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

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

3 靜態（全局）環境仿真

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

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

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

從仿真結果分析，當交叉和變異的概率都不變時，進化代數K越大，規劃出來的路徑越優。

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

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

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

圖3（a）（b）對應變異概率Pm =0.00002，0.7的仿真結果。

從以上仿真結果分析，經過調整參數后，可以看到本搜索算法成功地找到了近似最優的可行路徑。另外可以看到算法的計算時間稍長，還需要進一步優化，在以后的研究中將運用MATLAB對動態路徑規劃算法進一步仿真研究，并分析了相關參數對路徑規劃效果的影響，以及參數合理調整的基本思路。

參考文獻：

[1]王小平，曹立明.遺傳算法理論和應用與軟件實現[M].西安交通大學出版社，2002.

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

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

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

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

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

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

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