【專家點(diǎn)評(píng)】： 遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的高度并行、隨機(jī)、自適應(yīng)搜索算法。特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜的和非線性問(wèn)題。本論文采用遺傳算法對(duì)深海集礦車的避障路徑進(jìn)行規(guī)劃，思路和過(guò)程表達(dá)清晰。結(jié)果通過(guò)了計(jì)算機(jī)仿真測(cè)試初步證明了其可行性。應(yīng)該說(shuō)本論文論述的內(nèi)容是在自動(dòng)化領(lǐng)域使用先進(jìn)控制算法的一次有益和有效的嘗試。

摘要：

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

關(guān)鍵詞: 移動(dòng)機(jī)器人，遺傳算法, 避障路徑規(guī)劃

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.引言

在深海集礦車的導(dǎo)航控制中, 路徑規(guī)劃是一個(gè)很關(guān)鍵的問(wèn)題。深海集礦車路徑規(guī)劃的主要任務(wù)是在具有障礙物的環(huán)境中, 按照一定的評(píng)價(jià)標(biāo)準(zhǔn), 尋找一條從起始狀態(tài)到達(dá)目標(biāo)狀態(tài)的無(wú)碰撞路徑。

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

集礦車路徑規(guī)劃是一個(gè)困難的非線性問(wèn)題,傳統(tǒng)的尋優(yōu)策略因復(fù)雜而費(fèi)時(shí)[1],難以用于集礦車的實(shí)時(shí)導(dǎo)航。

本文提出的路徑規(guī)劃算法, 應(yīng)用簡(jiǎn)單的遺傳編碼, 并有明確物理意義的適應(yīng)度函數(shù)。

通過(guò)計(jì)算機(jī)仿真證明該方法能解決動(dòng)態(tài)環(huán)境中的深海集礦車路徑規(guī)劃問(wèn)題。

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

2.1路徑編碼方式

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

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

2.2適應(yīng)度函數(shù)的確定

適應(yīng)值函數(shù)的選取直接影響到遺傳算法收斂速度的快慢和算法的成敗。結(jié)合具體問(wèn)題的特征,該適應(yīng)度函數(shù)應(yīng)考慮以下因素：

2.2.1 路徑長(zhǎng)度

本文的路徑長(zhǎng)度指標(biāo)函數(shù)定義如下：

2.2.2 路徑的光滑度

本文的路徑光滑度指標(biāo)函數(shù)定義

規(guī)劃時(shí)必須考慮路徑光滑性對(duì)機(jī)器人運(yùn)動(dòng)性能的影響。機(jī)器人轉(zhuǎn)彎時(shí)，角度應(yīng)盡可能的小，因而要求生成的路徑盡可能變化均勻。故路徑的轉(zhuǎn)角差累積值φ(vi)較小的基因較為優(yōu)越。

2.3 路徑的安全性及相應(yīng)的懲罰策略

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

其中：Mi為機(jī)器人的某條運(yùn)動(dòng)軌跡； O指考慮安全距離條件時(shí)所有障礙物覆蓋范圍的集合。

對(duì)于進(jìn)入障礙物覆蓋范圍的隨機(jī)點(diǎn)，如下圖所示：

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

2.2.4 適應(yīng)度函數(shù)的選取

綜合以上幾點(diǎn)，可得到適應(yīng)度函數(shù)為：

其中α,β,γ為相應(yīng)的加權(quán)系數(shù)。

該適應(yīng)度函數(shù)把3個(gè)約束條件有機(jī)的結(jié)合到一起，物理意義明了，計(jì)算簡(jiǎn)單。

2.3 交叉方法

采用算術(shù)交叉法產(chǎn)生新的個(gè)體。這里將兩個(gè)染色體中的各元素以如下的方式組合，得到新染色體的相應(yīng)元素，方法如下：

2.4 變異操作算子的選擇

2.4.1 修復(fù)操作算子：

移動(dòng)一個(gè)點(diǎn)。依照一定的概率，對(duì)位于障礙區(qū)域內(nèi)的點(diǎn)重新取值，使其獲得避開障礙物的機(jī)會(huì)。

2.4.2 優(yōu)化操作算子：

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

2.5遺傳算法操作步驟

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

1.編碼：生成一組隨機(jī)數(shù)，以一維數(shù)組的形式轉(zhuǎn)化成染色體vi。

2.評(píng)估及選擇：

3.以一定的概率，對(duì)新種群進(jìn)行交叉，變異。

4.進(jìn)行遺傳迭代操作，經(jīng)過(guò)若干代的搜索，即可得到一條最佳路徑。

3. 仿真實(shí)驗(yàn)

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

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

4. 結(jié)論

本文設(shè)計(jì)了一套基于遺傳算法的路徑

規(guī)劃的方法，通過(guò)適當(dāng)?shù)倪m應(yīng)度函數(shù)引導(dǎo)遺傳搜索，得到了集礦車避障的最佳路徑。仿真實(shí)驗(yàn)證明了該方法的穩(wěn)定性和有效性。它的應(yīng)用將使深海集礦車具備一定的自主導(dǎo)航、避障的能力，為其智能化研究提供了一條有益的思路。

參考文獻(xiàn)：

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

[2]玄光男(日)，程潤(rùn)偉。遺傳算法與工程設(shè)計(jì)?？茖W(xué)出版社, 2000: 64-66.

[3]仲欣,呂恬生?；谶z傳算法的汽車式移動(dòng)機(jī)器人路徑規(guī)劃方法。上海交通大學(xué)學(xué)報(bào)，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.