基于遺傳算法掃地機器人設(shè)計路徑規(guī)劃

王 浩 方 露 莊 奎 周欣沅

（江蘇海事職業(yè)技術(shù)學院,江蘇 南京 211170）

近年來，國家相關(guān)部門不斷加大對機器人產(chǎn)業(yè)的扶持力度。作為服務(wù)機器人領(lǐng)域中的新產(chǎn)品，掃地機器人可在無人看守的情況下輕松完成室內(nèi)環(huán)境的吸塵等清潔工作。路徑規(guī)劃對機器人的工作至關(guān)重要，不僅能提高其清掃效率，還能將機器人的工作原理廣泛應(yīng)用于各個場景，具有一定研究價值。路徑規(guī)劃是智能掃地機器人導航的關(guān)鍵技術(shù)，實時、快捷及安全的運動方式能夠事半功倍。因此，本文將對掃地機器人的路徑規(guī)劃進行深入探討[1]。

全覆蓋路徑規(guī)劃即在工作范圍內(nèi)，清掃機器人從初始點開始，找到一條可覆蓋全部位置的連續(xù)路徑，以使機器人的某種性能指標達到最優(yōu)。全覆蓋路徑規(guī)劃算法目前已有很多，主要有隨機方法、單元分解法、規(guī)劃式覆蓋算法、模板模型法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法等。其中遺傳算法在路徑規(guī)劃中具有很強的全局尋優(yōu)性、環(huán)境適應(yīng)性及運算準確性。

1 路徑規(guī)劃算法

遺傳算法（Genetic Algorithm）的基本思想是參照生物界自然遺傳機制和自然選擇的隨機化搜索算法。通過模擬人工種群的進化過程，在選擇、交叉及變異中進行迭代，直至其適應(yīng)度達到近似最優(yōu)狀態(tài)[2]。另外，GA作為一種智能優(yōu)化算法，相對一些普通的優(yōu)化算法，可以較快獲取最佳的結(jié)果，其關(guān)鍵步驟為：初始化種群、計算適應(yīng)度、選擇、交叉和變異。

1.1 環(huán)境模型的建立

在對掃地機器人的路徑規(guī)劃前，首先建立其工作區(qū)域的環(huán)境地圖。柵格法是地圖建模的常用方法，定義0代表自由區(qū)域，1代表障礙區(qū)域。柵格大小的設(shè)定會直接決定規(guī)劃算法的性能。柵格越小，環(huán)境信息分辨率越高，但數(shù)據(jù)量及噪聲會增大，并會降低規(guī)劃速度及算法性能；反之，柵格較大，存儲信息量越少，提高了算法速度，但降低了環(huán)境信息分辨率。

1.2 環(huán)境編碼

將數(shù)學中的微元化處理思想應(yīng)用于掃地機器人的路徑規(guī)劃中，機器人的運動軌跡T就被劃分成由直線段擬合而成，轉(zhuǎn)換成數(shù)學表達式即為：

由于掃地機器人在運動過程中是具有方向性的，那么在實際運算中應(yīng)將基本距離單位適量化處理，假設(shè)起點為O，終點為P，則數(shù)學表達式為：

掃地機器人經(jīng)過的每一個位點被運算后，就能獲取到其所工作環(huán)境的路徑，建立掃地機器人在工作空間中位置的集合，即：

將路徑軌跡T利用坐標點數(shù)據(jù)進行儲存，利用二維平面坐標確定當前路徑軌跡中掃地機器人的具體位置，再依據(jù)遺傳學原理將路徑進行確定的方式稱為染色體的編碼。在實際的路徑規(guī)劃中，機器人的路徑統(tǒng)計可以通過多次操作和運算來完成。

1.3 適應(yīng)度函數(shù)的選擇

個體適應(yīng)度函數(shù)值的大小是遺傳算法中區(qū)分個體優(yōu)劣的重要指標，從生物學層面來講，相當于“適者生存”的能力，而此能力正是由個體適應(yīng)度的大小來決定的。所以，算法的收斂性及收斂速度取決于適應(yīng)度函數(shù)的選取。常見的適應(yīng)度函數(shù)如下：

（2）求解極大值問題時，令：

其中Cmin為的最小值估計。

求解極小值問題時，令：

其中Cmin為的最大值估計。

（3）求解極大值問題，適應(yīng)度函數(shù)通過轉(zhuǎn)換得到：

求解極小值問題，適應(yīng)度函數(shù)通過轉(zhuǎn)換得到：

1.4 算法步驟

掃地機器人的路徑規(guī)劃可以歸納為：按照某種優(yōu)化指標，在起始點和目標點規(guī)劃出一條與環(huán)境障礙無碰撞的路徑，并且實現(xiàn)所需清掃區(qū)域的合理完全路徑覆蓋。遺傳算法的運算過程如下：

（1）初始化：群體的初始化由隨機方式產(chǎn)生；

（2）個體評價：通過個體適應(yīng)度函數(shù)值來評價；

（3）選擇運算：在個體適應(yīng)度評估的基礎(chǔ)上，對群體建立選擇算子運算；

（4）交叉運算：在個體適應(yīng)度評估的基礎(chǔ)上，對群體建立交叉算子運算；

（5）變異運算：為防止出現(xiàn)未成熟收斂現(xiàn)象，對群體建立變異算子運算；

（6）迭代終止判定：滿足終止條件時，產(chǎn)生的最大適應(yīng)度個體即為最優(yōu)解，計算結(jié)束，否則返回至第二步。

在整個進化過程中，個體在選擇運算中是否被選中是由個體適應(yīng)度的大小來決定的[3]。適應(yīng)度大的個體被遺傳的概率也就越大，反之亦然。通過比例選擇來判定個體是否被遺傳，而目標數(shù)值與個體適應(yīng)度之間的轉(zhuǎn)換規(guī)則需要提前設(shè)定好[4]。尤其是要提前設(shè)定好當目標數(shù)值是負數(shù)時的解決辦法。執(zhí)行遺傳算法時，需要提前設(shè)定四個參數(shù)，即：群體大小、變異概率、交叉概率和終止代數(shù)。

1.5 編碼運算

在路徑規(guī)劃的過程中，遺傳算法的染色體其實是一條從起點到終點的最優(yōu)路徑。染色體的編碼可使用變長度的符號編碼方式來精確地表達路徑信息，地圖模型中的柵格序號可對應(yīng)于染色體中的每個基因。為保證路徑的可靠性，可規(guī)定染色體中不得出現(xiàn)重復序號和障礙序號[5]。代碼示例如下：

在這里先設(shè)定一個積累方向，再通過適應(yīng)度函數(shù)一代代地選擇，最終得到合適的結(jié)果。從許多點并行操作，一直找到最合適的解。如圖1、圖2即為函數(shù)尋優(yōu)圖。

圖1 初始種群示意圖

圖2 終止種群示意圖

2 路徑規(guī)劃算法仿真模擬

為驗證算法的有效性，應(yīng)基于Matlab軟件進行仿真模擬，采用柵格地圖法建立掃地機器人運動環(huán)境。按公式（4）的適應(yīng)度函數(shù)對柵格地圖模型進全覆蓋路徑規(guī)劃仿真，其中黑色表示環(huán)境中的障礙物，紅色曲線表示機器人清掃的路徑。基于遺傳算法在已知環(huán)境下的簡單避障路徑與復雜全遍歷路徑規(guī)劃見圖3和圖4。

由圖3和圖4可知，遺傳算法是一種具有良好智能性和隨機尋優(yōu)性的算法，在簡單避障路徑及復雜障礙物已知環(huán)境中的全覆蓋路徑尋優(yōu)中展現(xiàn)出了簡易性和通用性，并有較好的魯棒性，適于并行處理。

圖3 遺傳算法簡單避障路徑規(guī)劃

圖4 遺傳算法全遍歷路徑規(guī)劃

3 結(jié)論

本文重點探討了智能掃地機器人在已知環(huán)境下的路徑規(guī)劃遺傳算法，采用柵格地圖建立了機器人的工作環(huán)境地圖模型，構(gòu)造了適應(yīng)度函數(shù)，并通過實驗和仿真對算法的效果進行了驗證，證明了在已知環(huán)境中對掃地機器人的路徑規(guī)劃的遺傳算法是可行、準確且符合實際的。

在實際應(yīng)用中，除了加入基本的交叉、變異等基因操作，也可根據(jù)自己的需求，按照掃地機器人路徑規(guī)劃的特征，加入尋找捷徑、避讓障礙等基因優(yōu)化操作符，進一步改進路徑規(guī)劃算法，提升其高效性和可靠性。