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

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

1引言

完全遍歷路徑規(guī)劃（CompleteCoveragePathPlanning，CCPP）是一種特別的路徑規(guī)劃，它要求移動機器人在滿意肯定的指標下完遍歷目標環(huán)境中的可達區(qū)域。在機器人的很多應(yīng)用領(lǐng)域，大都需要用到遍歷路徑規(guī)劃算法，例如軍事用的地雷探測、家居及辦公環(huán)境的地面清潔、不同應(yīng)用領(lǐng)域地圖的創(chuàng)立等。在這些應(yīng)用中要求機器人掩蓋環(huán)境中全部未被障礙物占據(jù)的區(qū)域。根據(jù)對環(huán)境學(xué)問的了解，在已知環(huán)境掩蓋算法中讓清潔機器人規(guī)劃出一條能走過環(huán)境中的全部地方并目.是代價最小路徑，這個時候的問題就相當(dāng)于旅行家問題，未知環(huán)境的掩蓋要求清潔機器人必需借助身體上攜帶的不同類型的傳感器來感知四周的環(huán)境并進展規(guī)劃。

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

2完全遍歷規(guī)劃性能指標

移動機器人的完全遍歷路徑規(guī)劃常用的性能評價指標有遍歷面積百分率，遍歷重疊率。

（1）遍歷掩蓋率，是指機器人沿可行軌跡線遍歷完成后，己遍歷面積與可達區(qū)域面積的百分比。

（2）遍歷重疊率，指全部遍歷重疊面積之和與可達區(qū)域面積的之比的百分數(shù)。

為了保證相鄰區(qū)域之間不留有遍歷盲區(qū)，相鄰遍歷區(qū)域必需有肯定程度的重疊，明顯，

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

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

假如一個機器人性能越高，則遍歷掩蓋率越高，遍歷重疊率越低，遍歷效果越好，本文中主要結(jié)合遍歷重疊率和未遍歷面積來綜合評價完全遍歷路徑規(guī)劃。

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

本文的環(huán)境地圖采納幾何表示法表示，即用點、線及其組合來表示環(huán)境中的特征，并用參數(shù)來說明各個特征在環(huán)境中的詳細位置。將地圖進展Boustrophedon單元分解后，地圖將由若干障礙區(qū)和若干遍歷區(qū)組成。電子地圖則表示為各個區(qū)域信息的集合，而其中單個區(qū)域的信息包括區(qū)域的屬性（障礙區(qū)屬性或遍歷區(qū)屬性）及區(qū)域頂點的坐標。通過Boustrophedon單元分解，環(huán)境可以分解為如圖1所示的若干遍歷區(qū)和障礙區(qū)。

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

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

在電子地圖中兩個遍歷子區(qū)域的最近頂點分別為A（xi，yi）、B（xj，yj），推斷兩者之間的障礙物個數(shù)就是推斷AB連線通過的障礙物個數(shù)。障礙物頂點在向量AB的順時針方向還是在逆時針方向可以通過向量的叉乘來推斷，即

電子地圖中遍歷子區(qū)域之間的障礙物數(shù)矩陣N如下：

為了只保存對角線元素為0，將矩陣N的非對角線元素加1，得到規(guī)格化后的障礙物矩陣N。

距離矩陣D表示遍歷子區(qū)域之間的實際距離，其元素dij為子區(qū)域i和j的最近頂點之間的距離，對于毗鄰區(qū)域的距離值定為a，非毗鄰區(qū)域的距離值由電子地圖依據(jù)區(qū)域坐標定出。圖1區(qū)域之間距離矩陣D實測如下：

通過對障礙物矩陣、距離矩陣、連通矩陣的一樣位置的元素相乘，再對非一次連通的區(qū)域距離乘以系數(shù)b，得到一個重新定義的綜合距離矩陣D”，其中

圖1區(qū)域綜合距離矩陣D”如下：

〓〓4仿真討論

基于本章提出的完全遍歷路徑規(guī)劃算法，進展了大量的仿真試驗。下面是對圖3的仿真地圖完全遍歷結(jié)果。

經(jīng)過大量地圖的仿真說明，該遍歷算法的掩蓋率到達90%以上，有的甚至到達95%以上，而且重復(fù)率在10%以下。對于不同的地圖掩蓋率和重復(fù)率是不同的，不過對大多數(shù)地圖而言，該算法是高效的、有用的，具有很強的適應(yīng)性。該完全遍歷算法特點是系統(tǒng)要處理的信息量很少，機器人實時性掌握更強。特殊是提出了基點這一重要概念，使得在未知環(huán)境中實現(xiàn)完全遍歷更有效、更便利。

5結(jié)論

本文依據(jù)遍歷環(huán)境內(nèi)區(qū)域關(guān)系和區(qū)域連通圖，將已有的連通圖補充為完全連通圖，并依據(jù)區(qū)域信息和連通信息定義一個區(qū)域之間的距離矩陣，給予區(qū)域之間的連接權(quán)值。依據(jù)距離矩陣，采納遺傳算法對區(qū)域