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

王 浩 方 露 莊 奎 周欣沅

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

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

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

1 路徑規(guī)劃算法

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

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

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

1.2 環(huán)境編碼

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

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

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

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

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

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

（2）求解極大值問題時(shí)，令：

其中Cmin為的最小值估計(jì)。

求解極小值問題時(shí)，令：

其中Cmin為的最大值估計(jì)。

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

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

1.4 算法步驟

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

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

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

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

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

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

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

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

1.5 編碼運(yùn)算

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

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

圖1 初始種群示意圖

圖2 終止種群示意圖

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

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

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

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

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

3 結(jié)論

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

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