【專家點評】： 遺傳算法是一種借鑒生物界自然選擇和進化機制發展起來的高度并行、隨機、自適應搜索算法。特別適合于處理傳統搜索算法解決不好的復雜的和非線性問題。本論文采用遺傳算法對深海集礦車的避障路徑進行規劃，思路和過程表達清晰。結果通過了計算機仿真測試初步證明了其可行性。應該說本論文論述的內容是在自動化領域使用先進控制算法的一次有益和有效的嘗試。

摘要：

本文主要研究了利用遺傳算法實現深海集礦車避障路徑規劃的方法與途徑。將連續的路徑離散化，并用隨機數模擬各路徑種群。把二維的路徑轉化為一維，生成簡單的路徑基因。提出了物理意義明確的適應度函數和相應的變異算子，從而引導遺傳算法快速收斂于最優解。實驗仿真表明，該算法能夠快速，穩定的搜尋到所需的最佳路徑。

關鍵詞: 移動機器人，遺傳算法, 避障路徑規劃

Abstract: A kind of path planning method based on genetic algorithm for mobile robot with the consideration of the obstacles in the environment is analyzed and worked out. In this paper the continuous path is simulated by scatter point, and uses the random number to represent the path. The path of two dimensions is reduced into one dimension to produce simple path gene. In the method, the fitness function contains explicit physic means and corresponding mutation operator is provided, so that GA can be lead to an optimized result rapidly. The experiment shows that: this algorithm can get a optimal path fast and steadily. Key word: Mobile Robot, Genetic Algorithm, Path Planning;

1.引言

在深海集礦車的導航控制中, 路徑規劃是一個很關鍵的問題。深海集礦車路徑規劃的主要任務是在具有障礙物的環境中, 按照一定的評價標準, 尋找一條從起始狀態到達目標狀態的無碰撞路徑。

一般來說有許多路徑可供集礦車行走,可事實上需要集礦車必須找到一個最優路徑,既能避開障礙物，又能以最小的消耗(如時間)返回預定路徑。

集礦車路徑規劃是一個困難的非線性問題,傳統的尋優策略因復雜而費時[1],難以用于集礦車的實時導航。

本文提出的路徑規劃算法, 應用簡單的遺傳編碼, 并有明確物理意義的適應度函數。

通過計算機仿真證明該方法能解決動態環境中的深海集礦車路徑規劃問題。

2.基于遺傳算法的深海集礦車路徑規劃方法

2.1路徑編碼方式

如何將問題的解轉換為編碼表達的染色體，并利于后續約束條件下的優化操作是遺傳算法的關鍵問題。在遺傳算法中，編碼串的長度以及查找空間對于系統的運行速度是非常重要的[2], 因此必須設計一種簡潔實用的編碼技術,才能縮短規劃時間，實現實時控制。在現實運動中，路徑點是二維的，如果能對路徑坐標點進行降維處理，必將大大提高計算速度。本文中，令當前坐標系為XOY,其中原點與起始點重合，X軸位于起始點與目標點的連線上。將連接起點與目標點的線段 等分,取等分點Xj(j=1,2,…n-2),過Xj點作直線Lj與X軸正交，在每個Lj上隨機地選擇一點Pj ,共得到n-2個點,再令Po, Pn-1分別為起點，終點，如下圖所示：路徑編碼示意圖

記各點縱坐標為yi,j,從而形成一條隨機路徑Rj。這樣路徑就轉化為一維的Y坐標編碼。具體編碼采用浮點數方式，如下圖所示：圖中的yi,o即移動機器人的當前位置縱坐標,yi,n-1即是機器人的目標點縱坐標,路徑就是：

2.2適應度函數的確定

適應值函數的選取直接影響到遺傳算法收斂速度的快慢和算法的成敗。結合具體問題的特征,該適應度函數應考慮以下因素：

2.2.1 路徑長度

本文的路徑長度指標函數定義如下：

2.2.2 路徑的光滑度

本文的路徑光滑度指標函數定義

規劃時必須考慮路徑光滑性對機器人運動性能的影響。機器人轉彎時，角度應盡可能的小，因而要求生成的路徑盡可能變化均勻。故路徑的轉角差累積值φ(vi)較小的基因較為優越。

2.3 路徑的安全性及相應的懲罰策略

在設計安全保障策略前，首先假設障礙物的個數,位置信息已由安裝在機器人上的聲納傳感器獲得。那么懲罰策略的目的是在機器人規劃路徑與障礙物覆蓋范圍進行比較的基礎上, 形成安全、無碰撞可行路徑。一條可行的路徑必須保證機器人任何部位都不與障礙物發生碰撞, 即機器人與障礙物邊緣的距離必須大于最小安全距離，即： Mi∩O=0

其中：Mi為機器人的某條運動軌跡； O指考慮安全距離條件時所有障礙物覆蓋范圍的集合。

對于進入障礙物覆蓋范圍的隨機點，如下圖所示：

（注：圖中陰影部分為障礙物范圍，Pi,j為隨機路徑點, P,i,j為該點對應的障礙物邊緣點；） 本文設計了一個罰函數φ(vi)令：

2.2.4 適應度函數的選取

綜合以上幾點，可得到適應度函數為：

其中α,β,γ為相應的加權系數。

該適應度函數把3個約束條件有機的結合到一起，物理意義明了，計算簡單。

2.3 交叉方法

采用算術交叉法產生新的個體。這里將兩個染色體中的各元素以如下的方式組合，得到新染色體的相應元素，方法如下：

2.4 變異操作算子的選擇

2.4.1 修復操作算子：

移動一個點。依照一定的概率，對位于障礙區域內的點重新取值，使其獲得避開障礙物的機會。

2.4.2 優化操作算子：

刪除一個點。同樣，在一定的概率下，如果三個連續點皆在障礙物覆蓋范圍外部，且首尾點連線的中間點還位于障礙物覆蓋范圍外部，則刪除中間點。 兩種變異操作分別如下圖所示：

2.5遺傳算法操作步驟

綜上所述，該算法可描述如下：

1.編碼：生成一組隨機數，以一維數組的形式轉化成染色體vi。

2.評估及選擇：

3.以一定的概率，對新種群進行交叉，變異。

4.進行遺傳迭代操作，經過若干代的搜索，即可得到一條最佳路徑。

3. 仿真實驗

本文在VC++6.0環境下進行了仿真，用兩個橢圓物體代表障礙物，用遺傳算法求得避障路徑，效果圖如下：

（注：P o為起點，P n-1為目標點，障礙物的標記分別為BLOCK1,BLOCK2）

4. 結論

本文設計了一套基于遺傳算法的路徑

規劃的方法，通過適當的適應度函數引導遺傳搜索，得到了集礦車避障的最佳路徑。仿真實驗證明了該方法的穩定性和有效性。它的應用將使深海集礦車具備一定的自主導航、避障的能力，為其智能化研究提供了一條有益的思路。

參考文獻：

[1]孫明，孫樹棟。遺傳算法原理及應用。國防工業出版社,1999: 45-47.

[2]玄光男(日)，程潤偉。遺傳算法與工程設計。科學出版社, 2000: 64-66.

[3]仲欣,呂恬生。基于遺傳算法的汽車式移動機器人路徑規劃方法。上海交通大學學報，1999年7月。

[4]Bauer,R. Genetic Algorithms and Investment Strategies. John Wiley&Sons,New York. 1994: 102-105. [5]Allbrecht,R.,C. Reeves, and N. Steele,editors, Artificial Neural Nets and Genetic Algorithms. Springer-Verlag,New York,1993: 88-91.