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

荀燕琴，田竹梅，任國(guó)鳳，鹿嘉航

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

荀燕琴，田竹梅，任國(guó)鳳，鹿嘉航

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

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

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

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

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

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

在對(duì)掃地機(jī)器人路徑規(guī)劃的方法研究中，全局路徑規(guī)劃實(shí)現(xiàn)對(duì)工作環(huán)境信息的提前儲(chǔ)存，局部路徑規(guī)劃對(duì)于未知環(huán)境具有的高度適應(yīng)性，兩者結(jié)合在實(shí)現(xiàn)掃地機(jī)器人工作取得較好的成果[2-3]．具體分為：?jiǎn)卧纸夥ā⒛０迥Ｐ头ā⑼負(fù)浞ā鸥穹ā⑦z傳算法、蟻群算法、啟發(fā)式算法等，其中遺傳算法在路徑規(guī)劃中的應(yīng)用體現(xiàn)出了較高的環(huán)境適應(yīng)性，運(yùn)算高效性以及結(jié)果可靠性，因此遺傳算法成為目前掃地機(jī)器人路徑規(guī)劃中的主要方法．例如：朱寶艷[4]具體說(shuō)明A*算法和柵格法，李明[5]在2017年提出基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃研究．

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

1.1 遺傳算法概述

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

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

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

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

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

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

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

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

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

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

1.3 遺傳算法算子

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[11] 洪云波．多功能清潔機(jī)器人研究[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é)院科研項(xiàng)目（2018KY22，2018KY15）；山西省高等學(xué)校科技創(chuàng)新項(xiàng)目（2019L0830）；山西省高等學(xué)校教學(xué)改革創(chuàng)新項(xiàng)目（J2018162，J2019174）

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