基于遺傳算法的完全遍歷路徑規(guī)劃研究

1、基于遺傳算法的完全遍歷途徑規(guī)劃研究比較了基于遺傳算法的完全遍歷途徑規(guī)劃方法的優(yōu)缺點(diǎn)，提出了基于遺傳算法與單元分解法Boustrophedon算法結(jié)合的完全遍歷途徑規(guī)劃新方法。采用 Boustrophedon單元分解法將全部遍歷區(qū)域分解為假設(shè)干子區(qū)域，在實(shí)現(xiàn)單個(gè)子區(qū)域的遍歷根底上，利用遺傳算法確定子區(qū)域的遍歷順序。將該方法應(yīng)用于清潔機(jī)器人的完全遍歷途徑規(guī)劃，與基于其他算法的途徑規(guī)劃方法進(jìn)展比較，在多個(gè)性能指標(biāo)上都得到了改善與進(jìn)步。該方法綜合了于遺傳算法與單元分解法Boustrophedon算法的優(yōu)點(diǎn) ，簡(jiǎn)單有效 ，還通過(guò)仿真研究說(shuō)明 ，該方法在多個(gè)性能指標(biāo)上都得到了改善與進(jìn)步。挪動(dòng)機(jī)器人遺傳算法

2、完全遍歷途徑規(guī)劃1引言完全遍歷途徑規(guī)劃 Complete Coverage Path Planning， CCPP是一種特殊的途徑規(guī)劃，它要求挪動(dòng)機(jī)器人在滿足一定的指標(biāo)下完遍歷目的環(huán)境中的可達(dá)區(qū)域。在機(jī)器人的許多應(yīng)用領(lǐng)域，大都需要用到遍歷途徑規(guī)劃算法，例如軍事用的地雷探測(cè)、家居及辦公環(huán)境的地面清潔、不同應(yīng)用領(lǐng)域地圖的創(chuàng)立等。在這些應(yīng)用中要求機(jī)器人覆蓋環(huán)境中所有未被障礙物占據(jù)的區(qū)域。按照對(duì)環(huán)境知識(shí)的理解，在環(huán)境覆蓋算法中讓清潔機(jī)器人規(guī)劃出一條能走過(guò)環(huán)境中的所有地方并目.是代價(jià)最小途徑，這個(gè)時(shí)候的問(wèn)題就相當(dāng)于旅行家問(wèn)題，未知環(huán)境的覆蓋要求清潔機(jī)器人必須借助身體上攜帶的不同類型的傳感器來(lái)感知周圍的環(huán)

3、境并進(jìn)展規(guī)劃。為抑制上述途徑規(guī)劃中存在的問(wèn)題，本文比較了基于遺傳算法的完全遍歷途徑規(guī)劃方法的優(yōu)缺點(diǎn)，提出了基于遺傳算法與單元分解法、啟發(fā)式搜索和障礙物逼近算法結(jié)合的完全遍歷途徑規(guī)劃新方法，將該方法應(yīng)用于清潔機(jī)器人的完全遍歷途徑規(guī)劃，與基于其他算法的途徑規(guī)劃方法進(jìn)展比較，在多個(gè)性能指標(biāo)上都得到了改善與進(jìn)步。2完全遍歷規(guī)劃性能指標(biāo)挪動(dòng)機(jī)器人的完全遍歷途徑規(guī)劃常用的性能評(píng)價(jià)指標(biāo)有遍歷面積百分率，遍歷重疊率。1遍歷覆蓋率，是指機(jī)器人沿可行軌跡線遍歷完成后，己遍歷面積與可達(dá)區(qū)域面積的百分比。2遍歷重疊率，指所有遍歷重疊面積之和與可達(dá)區(qū)域面積的之比的百分?jǐn)?shù)。為了保證相鄰區(qū)域之間不留有遍歷盲區(qū)，相鄰遍歷區(qū)域

4、必須有一定程度的重疊，顯然，重疊區(qū)域越小越好，但因受機(jī)器人本身的系統(tǒng)誤差，定位誤差，控制精度以及環(huán)境狀態(tài)的影響，重疊區(qū)不可能太小，假設(shè)一個(gè)機(jī)器人性能越高，那么遍歷重疊率能控制在很小的范圍內(nèi)。從遍歷重疊率，還可以推出未遍歷面積百分率，它指機(jī)器人沿著可行軌跡線遍歷完成后，未遍歷面積與可達(dá)面積的百分比。假設(shè)一個(gè)機(jī)器人性能越高，那么遍歷覆蓋率越高，遍歷重疊率越低，遍歷效果越好，本文中主要結(jié)合遍歷重疊率和未遍歷面積來(lái)綜合評(píng)價(jià)完全遍歷途徑規(guī)劃。3基于遺傳算法的完全遍歷途徑規(guī)劃本文的環(huán)境地圖采用幾何表示法表示，即用點(diǎn)、線及其組合來(lái)表示環(huán)境中的特征，并用參數(shù)來(lái)說(shuō)明各個(gè)特征在環(huán)境中的詳細(xì)位置。將地圖進(jìn)展Bous

5、trophedon單元分解后，地圖將由假設(shè)干障礙區(qū)和假設(shè)干遍歷區(qū)組成。電子地圖那么表示為各個(gè)區(qū)域信息的集合，而其中單個(gè)區(qū)域的信息包括區(qū)域的屬性障礙區(qū)屬性或遍歷區(qū)屬性及區(qū)域頂點(diǎn)的坐標(biāo)。通過(guò) Boustrophedon單元分解，環(huán)境可以分解為如圖 1所示的假設(shè)干遍歷區(qū)和障礙區(qū)。由圖2我們可以得到矩陣A得到區(qū)域i和k的有幾條連通途徑。圖2中各區(qū)域之間的連通關(guān)系矩陣如下：在電子地圖中兩個(gè)遍歷子區(qū)域的最近頂點(diǎn)分別為 A x i ， y i 、 B x j ， y j ，判斷兩者之間的障礙物個(gè)數(shù)就是判斷AB連線通過(guò)的障礙物個(gè)數(shù)。障礙物頂點(diǎn)在向量AB的順時(shí)針?lè)较蜻€是在逆時(shí)針?lè)较蚩梢酝ㄟ^(guò)向量的叉乘來(lái)判斷，即電

6、子地圖中遍歷子區(qū)域之間的障礙物數(shù)矩陣 N如下：為了只保存對(duì)角線元素為 0，將矩陣 N的非對(duì)角線元素加1，得到規(guī)格化后的障礙物矩陣N。間隔 矩陣 D表示遍歷子區(qū)域之間的實(shí)際間隔 ，其元素dij為子區(qū)域i和j的最近頂點(diǎn)之間的間隔 ，對(duì)于毗鄰區(qū)域的間隔 值定為a，非毗鄰區(qū)域的間隔 值由電子地圖根據(jù)區(qū)域坐標(biāo)定出。圖 1區(qū)域之間間隔 矩陣 D實(shí)測(cè)如下：通過(guò)對(duì)障礙物矩陣、間隔 矩陣、連通矩陣的一樣位置的元素相乘，再對(duì)非一次連通的區(qū)域間隔 乘以系數(shù)b，得到一個(gè)重新定義的綜合間隔 矩陣D'，其中圖1區(qū)域綜合間隔 矩陣D'如下：4仿真研究基于本章提出的完全遍歷途徑規(guī)劃算法，進(jìn)展了大量的仿真實(shí)驗(yàn)。

7、下面是對(duì)圖3的仿真地圖完全遍歷結(jié)果。經(jīng)過(guò)大量地圖的仿真說(shuō)明，該遍歷算法的覆蓋率到達(dá)90%以上，有的甚至到達(dá)95%以上，而且重復(fù)率在10%以下。對(duì)于不同的地圖覆蓋率和重復(fù)率是不同的，不過(guò)對(duì)大多數(shù)地圖而言，該算法是高效的、實(shí)用的，具有很強(qiáng)的適應(yīng)性。該完全遍歷算法特點(diǎn)是系統(tǒng)要處理的信息量很少，機(jī)器人實(shí)時(shí)性控制更強(qiáng)。特別是提出了基點(diǎn)這一重要概念，使得在未知環(huán)境中實(shí)現(xiàn)完全遍歷更有效、更方便。5結(jié)論本文根據(jù)遍歷環(huán)境內(nèi)區(qū)域關(guān)系和區(qū)域連通圖，將已有的連通圖補(bǔ)充為完全連通圖，并根據(jù)區(qū)域信息和連通信息定義一個(gè)區(qū)域之間的間隔 矩陣，賦予區(qū)域之間的連接權(quán)值。根據(jù)間隔 矩陣，采用遺傳算法對(duì)區(qū)域的遍歷順序進(jìn)展優(yōu)化。仿真研究說(shuō)明，該方法用于