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

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

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

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

（忻州師范學院 電子信息科學與技術系，山西 忻州 035000）

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

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

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

智能掃地機器人作為一種智能服務型的機器人得到了快速的發展和推廣，對掃地機器人進行路徑規劃，

不僅能夠對掃地機器人的工作效率進行提升，同時還能將掃地機器人的工作原理向地質勘探等多個領域進行推廣，有助于人工智能的發展．智能掃地機器人的關鍵性技術[1]要求之一就是路徑規劃，合理、高效及可行的路徑規劃能夠有效完成任務．因此，本文將對掃地機器人的路徑規劃進行研究．

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

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

1.1 遺傳算法概述

遺傳算法是在達爾文進化論和孟德爾遺傳定律的基礎上，通過分析數學和數論的基礎建模理論實現的算法．通過生物體在遺傳的過程中出現的基因重組和基因變異的遷移，能夠有效地實現遺傳算法在實現過程中對實際問題的高度適應性[6]，對于遺傳算法來說，主要由7個參數構成（見表1）．

表1 遺傳算法中的參數

1.2 基于遺傳算法對路徑規劃的環境建模

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

圖1 掃地機器人的工作環境模擬

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

結合圖1中對掃地機器人的工作環境進行模擬編碼（見表2）．

表2 工作環境的二進制編碼

1.2.3 群體初始化 種群的初始化依靠隨機選取的方式產生，而在遺傳算法的實現過程中，種群的隨機產生表現為出發點和目標點的隨機性[8]．具體表示為，在涵蓋出發點和目標點的空間范圍內，預設節點，在出發點和目標點之間所有路徑構成的集合構成初始化種群．

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

1.3 遺傳算法算子

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

結合適應度函數的有關概念，將交叉算子應用于適應度函數中，得到表達式

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

因此，利用式（12）對變異算法進行適應度的約束，即表明在適應度的條件下，每次變異產生的新路徑都能實現對當前路徑的優化．

1.3.4 刪除算子 刪除算子[11]指的是在空間范圍內隨機選擇無數條路徑中，在適應度函數的約束條件下，進行對障礙物的搜索，結合2個條件，可以確定對障礙物進行碰撞的路徑，將所有的可能出現碰撞事件的位點以及對應的算子在適應度模型中進行刪除，而剩余的路徑即為能夠實現工作需求的待選擇路徑．

2 基于遺傳算法的智能掃地機器人路徑規劃仿真實現

基于遺傳算法已知路徑的仿真實驗分為兩大部分：單點到單點的最優路徑規劃和全覆蓋路徑尋優．同時為了簡單，本文采用靜態環境進行路徑規劃．

2.1 最優路徑規劃仿真模擬

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

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

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

2.2 全覆蓋路徑規劃仿真模擬

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

圖4 遺傳算法簡單全局路徑規劃

圖5 遺傳算法更復雜環境全局路徑規劃

由圖3可知，遺傳算法可以實現單點到單點的最短路徑尋優．由圖4和圖5可知，由于遺傳算法的智能性和隨機尋優性，可以實現在簡單和復雜障礙物的靜態環境中的全覆蓋路徑尋優，具有良好的魯棒性．

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

[1] 郭梟鵬．基于改進人工勢場法的路徑規劃算法研究[D]．哈爾濱：哈爾濱工業大學，2017：4-12

[2] 呂后勇．室內機器人全覆蓋路徑規劃方法研究[D]．咸陽：西北農林科技大學，2016：7-13

[3] 李麗蘭，葉雙清．清潔機器人路徑規劃專利技術綜述[J]．科技經濟導刊，2019，27（23）：21

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

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

[6] 張志遠，趙幸，靳曄．基于生物激勵神經網絡的清潔機器人遍歷路徑規劃算法的改進[J]．輕工學報，2018，33（4）：73-78，85

[7] 朱博．移動機器人完全遍歷路徑規劃研究[D]．天津：天津職業技術師范大學，2015：11-15

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

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

[10] 張堂凱．己知環境下智能清潔機器人路徑規劃研究[D]．南京：南京郵電大學，2017：10-22

[11] 洪云波．多功能清潔機器人研究[D]．蘇州：蘇州大學，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

忻州師范學院科研項目（2018KY22，2018KY15）；山西省高等學校科技創新項目（2019L0830）；山西省高等學校教學改革創新項目（J2018162，J2019174）

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