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

基于遺傳算法的完全遍歷路徑規(guī)劃研究移動(dòng)機(jī)器人遺傳算法完全遍歷路徑規(guī)劃

1引言

完全遍歷路徑規(guī)劃（CompleteCoveragePathPlanning，CCPP）是一種特別的路徑規(guī)劃，它要求移動(dòng)機(jī)器人在滿意肯定的指標(biāo)下完遍歷目標(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ū)域。根據(jù)對(duì)環(huán)境學(xué)問(wèn)的了解，在已知環(huán)境掩蓋算法中讓清潔機(jī)器人規(guī)劃出一條能走過(guò)環(huán)境中的全部地方并目.是代價(jià)最小路徑，這個(gè)時(shí)候的問(wèn)題就相當(dāng)于旅行家問(wèn)題，未知環(huán)境的掩蓋要求清潔機(jī)器人必需借助身體上攜帶的不同類型的傳感器來(lái)感知四周的環(huán)境并進(jìn)展規(guī)劃。

為克制上述路徑規(guī)劃中存在的問(wèn)題，本文比擬了基于遺傳算法的完全遍歷路徑規(guī)劃方法的優(yōu)缺點(diǎn)，提出了基于遺傳算法與單元分解法、啟發(fā)式搜尋和障礙物靠近算法結(jié)合的完全遍歷路徑規(guī)劃新方法，將該方法應(yīng)用于清潔機(jī)器人的完全遍歷路徑規(guī)劃，與基于其他算法的路徑規(guī)劃方法進(jìn)展比擬，在多共性能指標(biāo)上都得到了改善與提高。

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ū)域必需有肯定程度的重疊，明顯，

重疊區(qū)域越小越好，但因受機(jī)器人本身的系統(tǒng)誤差，定位誤差，掌握精度以及環(huán)境狀態(tài)的影響，重疊區(qū)不行能太小，假如一個(gè)機(jī)器人性能越高，則遍歷重疊率能掌握在很小的范圍內(nèi)。

從遍歷重疊率，還可以推出未遍歷面積百分率，它指機(jī)器人沿著可行軌跡線遍歷完成后，未遍歷面積與可達(dá)面積的百分比。

假如一個(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)展Boustrophedon單元分解后，地圖將由若干障礙區(qū)和若干遍歷區(qū)組成。電子地圖則表示為各個(gè)區(qū)域信息的集合，而其中單個(gè)區(qū)域的信息包括區(qū)域的屬性（障礙區(qū)屬性或遍歷區(qū)屬性）及區(qū)域頂點(diǎn)的坐標(biāo)。通過(guò)Boustrophedon單元分解，環(huán)境可以分解為如圖1所示的若干遍歷區(qū)和障礙區(qū)。

由圖2我們可以得到矩陣A

得到區(qū)域i和k的有幾條連通路徑。圖2中各區(qū)域之間的連通關(guān)系矩陣如下：

在電子地圖中兩個(gè)遍歷子區(qū)域的最近頂點(diǎn)分別為A（xi，yi）、B（xj，yj），推斷兩者之間的障礙物個(gè)數(shù)就是推斷AB連線通過(guò)的障礙物個(gè)數(shù)。障礙物頂點(diǎn)在向量AB的順時(shí)針?lè)较蜻€是在逆時(shí)針?lè)较蚩梢酝ㄟ^(guò)向量的叉乘來(lái)推斷，即

電子地圖中遍歷子區(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)展了大量的仿真試驗(yàn)。下面是對(duì)圖3的仿真地圖完全遍歷結(jié)果。

經(jīng)過(guò)大量地圖的仿真說(shuō)明，該遍歷算法的掩蓋率到達(dá)90%以上，有的甚至到達(dá)95%以上，而且重復(fù)率在10%以下。對(duì)于不同的地圖掩蓋率和重復(fù)率是不同的，不過(guò)對(duì)大多數(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ū)域