荀燕琴，田竹梅，任國鳳，鹿嘉航

基于遺傳算法的智能掃地機器人路徑規(guī)劃研究

荀燕琴，田竹梅，任國鳳，鹿嘉航

（忻州師范學(xué)院 電子信息科學(xué)與技術(shù)系，山西 忻州 035000）

隨著現(xiàn)代科技的發(fā)展，移動機器人隨之產(chǎn)生．清潔機器人作為特殊應(yīng)用的機器人，為人們的生活提供便利，路徑規(guī)劃作為智能掃地機器人的關(guān)鍵技術(shù)之一，其算法的性能是影響機器人工作效率的重要因素．遺傳算法作為新興智能算法，具有強魯棒性、并行性、高效性等特點，因此研究了遺傳算法并實現(xiàn)掃地機器人的路徑規(guī)劃．分析了掃地機器人的基本理論，遺傳算法的原理、實現(xiàn)及應(yīng)用，將遺傳算法應(yīng)用于掃地機器人路徑規(guī)劃中，并在VS中進(jìn)行仿真實驗，實現(xiàn)單點到單點的路徑規(guī)劃，同時實現(xiàn)全覆蓋式路徑規(guī)劃．

掃地機器人；路徑規(guī)劃；遺傳算法；全覆蓋路徑

掃地機器人的路徑規(guī)劃是機器人學(xué)科的一個重要的研究領(lǐng)域，研究的范圍涉及人工智能學(xué)、機器人學(xué)、數(shù)學(xué)分析以及計算機編程等多個領(lǐng)域和學(xué)科．在人工智能快速發(fā)展的背景下，掃地機器人的使用獲得了空前的發(fā)展，并且機器人的路徑規(guī)劃及研究引發(fā)了各界的廣泛重視．本文基于掃地機器人及其路徑規(guī)劃理論，通過詳細(xì)介紹遺傳算法原理、算子介紹及編碼操作，將遺傳算法用于求解智能掃地機器人的路徑規(guī)劃，并在VS中實現(xiàn)最優(yōu)路徑及全覆蓋路徑的仿真．

智能掃地機器人作為一種智能服務(wù)型的機器人得到了快速的發(fā)展和推廣，對掃地機器人進(jìn)行路徑規(guī)劃，

不僅能夠?qū)叩貦C器人的工作效率進(jìn)行提升，同時還能將掃地機器人的工作原理向地質(zhì)勘探等多個領(lǐng)域進(jìn)行推廣，有助于人工智能的發(fā)展．智能掃地機器人的關(guān)鍵性技術(shù)[1]要求之一就是路徑規(guī)劃，合理、高效及可行的路徑規(guī)劃能夠有效完成任務(wù)．因此，本文將對掃地機器人的路徑規(guī)劃進(jìn)行研究．

在對掃地機器人路徑規(guī)劃的方法研究中，全局路徑規(guī)劃實現(xiàn)對工作環(huán)境信息的提前儲存，局部路徑規(guī)劃對于未知環(huán)境具有的高度適應(yīng)性，兩者結(jié)合在實現(xiàn)掃地機器人工作取得較好的成果[2-3]．具體分為：單元分解法、模板模型法、拓?fù)浞?、柵格法、遺傳算法、蟻群算法、啟發(fā)式算法等，其中遺傳算法在路徑規(guī)劃中的應(yīng)用體現(xiàn)出了較高的環(huán)境適應(yīng)性，運算高效性以及結(jié)果可靠性，因此遺傳算法成為目前掃地機器人路徑規(guī)劃中的主要方法．例如：朱寶艷[4]具體說明A*算法和柵格法，李明[5]在2017年提出基于改進(jìn)遺傳算法的移動機器人路徑規(guī)劃研究．

1 基于遺傳算法的智能掃地機器人路徑規(guī)劃

1.1 遺傳算法概述

遺傳算法是在達(dá)爾文進(jìn)化論和孟德爾遺傳定律的基礎(chǔ)上，通過分析數(shù)學(xué)和數(shù)論的基礎(chǔ)建模理論實現(xiàn)的算法．通過生物體在遺傳的過程中出現(xiàn)的基因重組和基因變異的遷移，能夠有效地實現(xiàn)遺傳算法在實現(xiàn)過程中對實際問題的高度適應(yīng)性[6]，對于遺傳算法來說，主要由7個參數(shù)構(gòu)成（見表1）．

表1 遺傳算法中的參數(shù)

1.2 基于遺傳算法對路徑規(guī)劃的環(huán)境建模

1.2.1 環(huán)境建模 智能掃地機器人在工作范圍中的障礙物信息應(yīng)為三維信息，而工作環(huán)境信息是二維信息，應(yīng)將機器人自身看作點，并將障礙物信息由三維信息向平面化進(jìn)行轉(zhuǎn)化，規(guī)定障礙物的尺寸向外擴(kuò)展半個機器人半徑，便于機器人對障礙物的識別和判斷[7]．設(shè)定掃地機器人實際工作環(huán)境中的二維柵格模型見圖1．

圖1 掃地機器人的工作環(huán)境模擬

在此基礎(chǔ)上，對掃地機器人的每一個位置點進(jìn)行運算后，即可得出掃地機器人在工作過程中的路徑，建立掃地機器人在工作空間中的位置集合

結(jié)合圖1中對掃地機器人的工作環(huán)境進(jìn)行模擬編碼（見表2）．

表2 工作環(huán)境的二進(jìn)制編碼

1.2.3 群體初始化 種群的初始化依靠隨機選取的方式產(chǎn)生，而在遺傳算法的實現(xiàn)過程中，種群的隨機產(chǎn)生表現(xiàn)為出發(fā)點和目標(biāo)點的隨機性[8]．具體表示為，在涵蓋出發(fā)點和目標(biāo)點的空間范圍內(nèi)，預(yù)設(shè)節(jié)點，在出發(fā)點和目標(biāo)點之間所有路徑構(gòu)成的集合構(gòu)成初始化種群．

由此可知，掃地機器人在工作空間中移動的障礙物排斥函數(shù)

1.3 遺傳算法算子

1.3.1 算子的交叉算法 交叉算法在2個親代的個體中，以每一個親本個體的一部分結(jié)構(gòu)進(jìn)行保留而將剩余的一部分進(jìn)行替換，排除當(dāng)前2個親本之后的其他所有剩余個體．從交叉算法的實現(xiàn)過程來說，無論是親本的選擇，還是替換目標(biāo)的選擇，親本中保留部分和替換部分的選擇都依據(jù)隨機性的原則[10]，以個體作為實現(xiàn)單位，進(jìn)行兩兩配對．

結(jié)合適應(yīng)度函數(shù)的有關(guān)概念，將交叉算子應(yīng)用于適應(yīng)度函數(shù)中，得到表達(dá)式

而在實際的運動過程中，變異現(xiàn)象的產(chǎn)生是隨機的，也就是說變異現(xiàn)象在產(chǎn)生的過程中，不具有定向性，可能存在有利于個體的變異性狀和不利于個體生存發(fā)展的變異性狀．結(jié)合實際問題，則表現(xiàn)為，對于掃地機器人路徑規(guī)劃的變異運算可能使掃地機器人的路徑更為合理，也有可能使規(guī)劃的路徑不能滿足最短原則

因此，利用式（12）對變異算法進(jìn)行適應(yīng)度的約束，即表明在適應(yīng)度的條件下，每次變異產(chǎn)生的新路徑都能實現(xiàn)對當(dāng)前路徑的優(yōu)化．

1.3.4 刪除算子 刪除算子[11]指的是在空間范圍內(nèi)隨機選擇無數(shù)條路徑中，在適應(yīng)度函數(shù)的約束條件下，進(jìn)行對障礙物的搜索，結(jié)合2個條件，可以確定對障礙物進(jìn)行碰撞的路徑，將所有的可能出現(xiàn)碰撞事件的位點以及對應(yīng)的算子在適應(yīng)度模型中進(jìn)行刪除，而剩余的路徑即為能夠?qū)崿F(xiàn)工作需求的待選擇路徑．

2 基于遺傳算法的智能掃地機器人路徑規(guī)劃仿真實現(xiàn)

基于遺傳算法已知路徑的仿真實驗分為兩大部分：單點到單點的最優(yōu)路徑規(guī)劃和全覆蓋路徑尋優(yōu)．同時為了簡單，本文采用靜態(tài)環(huán)境進(jìn)行路徑規(guī)劃．

2.1 最優(yōu)路徑規(guī)劃仿真模擬

基于對當(dāng)前模型的多次仿真，得出基于遺傳算法的對智能掃地機器人路徑規(guī)劃的方式具有穩(wěn)定性和可靠性．因此，將研究的成果進(jìn)行運行模擬．結(jié)合Visual Studio對此模型進(jìn)行實際模擬，模擬的環(huán)境見圖2，白色部分表示智能掃地機器人能夠進(jìn)行移動的空間范圍．模擬的結(jié)果見圖3．

圖2 遺傳算法智能掃地機器人自動尋路環(huán)境模擬

圖3 基于遺傳算法的最短路徑模擬

2.2 全覆蓋路徑規(guī)劃仿真模擬

基于Visual Studio對遺傳算法求解全覆蓋路徑規(guī)劃進(jìn)行仿真，其中綠色標(biāo)識表示路徑規(guī)劃起點，紅色標(biāo)識表示路徑規(guī)劃的終點，黑色標(biāo)識表示環(huán)境障礙．基于遺傳算法的已知環(huán)境下的較簡單與較復(fù)雜的全局性路徑規(guī)劃見圖4和圖5．

圖4 遺傳算法簡單全局路徑規(guī)劃

圖5 遺傳算法更復(fù)雜環(huán)境全局路徑規(guī)劃

由圖3可知，遺傳算法可以實現(xiàn)單點到單點的最短路徑尋優(yōu)．由圖4和圖5可知，由于遺傳算法的智能性和隨機尋優(yōu)性，可以實現(xiàn)在簡單和復(fù)雜障礙物的靜態(tài)環(huán)境中的全覆蓋路徑尋優(yōu)，具有良好的魯棒性．

遺傳算法作為智能掃地機器人路徑規(guī)劃的典型算法之一，最近幾年得到了廣泛的研究和發(fā)展，其應(yīng)用廣泛．本文通過實驗和仿真對算法的有效性、可行性、實踐性進(jìn)行了驗證，證明了遺傳算法在已知環(huán)境下的路徑規(guī)劃是有效可行的．

[1] 郭梟鵬．基于改進(jìn)人工勢場法的路徑規(guī)劃算法研究[D]．哈爾濱：哈爾濱工業(yè)大學(xué)，2017：4-12

[2] 呂后勇．室內(nèi)機器人全覆蓋路徑規(guī)劃方法研究[D]．咸陽：西北農(nóng)林科技大學(xué)，2016：7-13

[3] 李麗蘭，葉雙清．清潔機器人路徑規(guī)劃專利技術(shù)綜述[J]．科技經(jīng)濟(jì)導(dǎo)刊，2019，27（23）：21

[4] 朱寶艷．移動機器人全覆蓋遍歷路徑規(guī)劃算法研究[D]．淄博：山東理工大學(xué)，2017：3-9

[5] 李明．基于改進(jìn)遺傳算法的移動機器人路徑規(guī)劃研究[D]．蕪湖：安徽工程大學(xué)，2017：22-35

[6] 張志遠(yuǎn)，趙幸，靳曄．基于生物激勵神經(jīng)網(wǎng)絡(luò)的清潔機器人遍歷路徑規(guī)劃算法的改進(jìn)[J]．輕工學(xué)報，2018，33（4）：73-78，85

[7] 朱博．移動機器人完全遍歷路徑規(guī)劃研究[D]．天津：天津職業(yè)技術(shù)師范大學(xué)，2015：11-15

[8] 李偉莉，趙東輝．基于柵格法與神經(jīng)元的機器人全區(qū)域覆蓋算法[J]．機械設(shè)計與制造，2017（8）：240-242，246

[9] 陳光明，楊建峰．智能洗地機器人區(qū)域遍歷覆蓋策略的研究[J]．機床與液壓，2018，46（9）：78-80，85

[10] 張?zhí)脛P．己知環(huán)境下智能清潔機器人路徑規(guī)劃研究[D]．南京：南京郵電大學(xué)，2017：10-22

[11] 洪云波．多功能清潔機器人研究[D]．蘇州：蘇州大學(xué)，2015：2-13

Research on path planning of intelligent floor sweeping robot based on genetic algorithm

XUN Yanqin，TIAN Zhumei，REN Guofeng，LU Jiahang

（Department of Electronic Information Science and Technology，Xinzhou Normal University，Xinzhou 035000，China）

Mobile robots have also evolved along with the development of human science and technology．Cleaning robots，as special-purpose robots，are therefore widely studied．Path planning is one of the key technologies of intelligent robots for sweeping．The performance of the algorithm affects the important factors of the efficiency of robots．As a new intelligent algorithm，genetic algorithm has the characteristics of strong robustness，parallelism，high efficiency．Therefore，mainly studies genetics algorithms and path planning for sweeping robots．The principle，implementation and application of genetic algorithm are analyzed in detail．More and more，the simulation experiment is carried out in the VS to realize the single point to single point path planning and the full coverage path planning．

floor sweeping robot；path planning；genetic algorithm；full coverage path

TP242

A

10.3969/j.issn.1007-9831.2020.03.010

1007-9831（2020）03-0056-05

2019-11-04

忻州師范學(xué)院科研項目（2018KY22，2018KY15）；山西省高等學(xué)?？萍紕?chuàng)新項目（2019L0830）；山西省高等學(xué)校教學(xué)改革創(chuàng)新項目（J2018162，J2019174）

荀燕琴（1988-），女，山西臨汾人，助教，碩士，從事信號處理、智能算法研究．E-mail：361942664@qq.com