基于滾動窗口的雜草優化算法的路徑規劃

中圖分類號：TP242.6 文獻標志碼：A 文章編號：1008-4657（2025）04-0001-07

0 引言

路徑規劃技術是人們研究機器人技術的一個重要方向，是完成機器人智能化的關鍵一步。路徑規劃技術是指機器人按照某些指標（如時間、耗能、距離等）自主地規劃出一條從起點到目標點的最優無碰路徑[1-2]。路徑規劃技術可分為全局路徑規劃技術與局部路徑規劃技術，全局路徑規劃技術是已知機器人的工作環境后，對機器人的工作環境進行建模得到工作的地圖，在工作的地圖中進行路徑規劃[3-4]；局部路徑規劃技術是機器人工作在未知的環境中，機器人通過傳感器等裝置探測工作環境中的障礙物信息后，一邊構建地圖，一邊采用路徑規劃算法進行路徑規劃[5-6]。

針對全局路徑規劃的研究較為成熟，常見的路徑規劃算法有 A^* 算法[7]、遺傳算法[8]、神經網絡算法[9]粒子群算法[10]等。局部路徑規劃的算法常用的算法有RRT（Rapidly-Exploring Random Tree，RRT）算法[11]、人工勢場法[12]、DWA（Dynamic Window Approach）算法[13]等。現階段局部路徑規劃算法的一個研究熱點是綜合兩種路徑規劃算法，這樣可以提升路徑規劃的效率，如文獻[14]中提出將RRT算法和滾動窗口相結合，將機器人采樣的目標限制在機器人的滾動窗口中，這樣可以大幅地減少機器人傳感器采樣的樣本，減少機器人的計算量，從而減少了機器人路徑規劃的時間。針對機器人工作環境未知這一情況，為了提高機器人路徑規劃的實時性，本文提出了基于滾動窗口的雜草優化算法的路徑規劃算法，其中機器人僅采集滾動窗口中障礙物的信息，并將滾動窗口障礙物的信息構建導航地圖，在構建的導航地圖中采用雜草優化算法進行路徑規劃，從而讓機器人規劃路徑的實時性得到有效的提升。

本文的結構如下：第一部分簡要地綜述現階段路徑規劃方面的研究;第二部分簡要地介紹了雜草優化算法和滾動窗口算法的原理;第三部分介紹了基于滾動窗口的雜草優化算法的路徑規劃算法;第四部分利用基于滾動窗口的雜草優化算法進行試驗，并與文獻[15]中提出的將RRT算法和滾動窗口相結合進行了實驗對比，通過實驗可以證明算法的可行性;最后對本文進行總結，并對未來的研究工作進行展望。

1雜草優化算法和滾動窗口算法

1.1雜草優化算法

由 Mehrabian AR等[16]提出的雜草優化算法（Invasive Weed Optimization，IWO），是一種智能的隨機搜索算法，IWO算法通過模仿自然界中雜草的種子在空間中的擴散、生長、繁殖、競爭與消亡的全部過程，通過采樣群體中的優秀個體指導雜草種群的進化。雜草優化算法采用正態分布的形式，隨機地將優秀個體生產的眾多子代個體疊加在父代個體的周圍，經過篩選獲取最優的個體。雜草優化算法具有魯棒性強、簡單等優點[17]。

雜草優化算法的步驟：

步驟1：初始化種群

將雜草隨機的散布在雜草的搜索空間中，根據實際要求設置雜草的個數。

步驟2：子代繁殖

在搜索空間中，父代根據適應值隨機地產生下一代的雜草種子，通常情況下，適應值高的個體產生的種子相對較多，反之則產生的種子少。雜草優化算法在運行時，父代產生的種子和它的適應度成比例，其產生的下一代種子的數量和適應度函數有如下關系：

式（1）中 P_n 是種子數量， f_n 是雜草的適應度函數， P_min 與 P_max 分別是雜草種子數量的最小值與最大值。如圖1所示為種子數量的原理圖。

圖1種子數量的原理圖

步驟3：空間擴散

種子的數目和適應度有關，且成正比關系，即適應度低產生的種子就少，反之產生的種子就多，子代個體按正態分布均勻地散落在父代個體的周圍，正態分布比標準偏差為：

式（2）中 σ_ini 和 σ_fu 分別是初始標準偏差與最終標準偏差， q 與 q_max 分別是系統的迭代次數與系統最大的迭代次數。

步驟4：競爭淘汰

當種群中的個體經過迭代達到群體的上限時，將父代與子代放在一起排序，淘汰適應值低的個體，即可得到想要保留的個體。

1.2 滾動窗口算法

機器人采用傳感器探測周圍的障礙物信息后，根據實際情況設定機器人的滾動窗口，根據滾動窗口中實時更新的障礙物信息，機器人通過啟發式算法優化得到優化的子目標，進而完成路徑規劃。當機器人的滾動窗口向前不停地行走時，窗口里的障礙物環境信息也在同步更新，它規劃的路徑也跟著更新，直至機器人到達目標點。因滾動窗口算法僅對滾動窗口內的環境進行路徑規劃規劃，因此它具有反應快

速、算法簡單等優點[18]

2滾動窗口的構建與雜草優化算法的路徑規劃算法

2.1 滾動窗口的構建

構建的滾動窗口示意圖如圖2所示。

圖2構建的滾動窗口示意圖

機器人在使用傳感器（如激光雷達）探測到前方的信息后，設傳感器的掃描半徑為r，其掃描的區域為 0～ （可根據實際情況進行設置）。構建直角坐標系，所得到的坐標系即為機器人工作環境的坐標系，此時朝向目標點的區域。

2.2 基于雜草優化算法的路徑規劃

機器人在前進的過程中，通過傳感器在滾動窗口進行采樣，在獲取障礙物信息后，通過雜草優化算法完成機器人的路徑規劃。基于滾動窗口的雜草優化算法的路徑規劃流程圖如圖3所示。

圖3基于滾動窗口的雜草優化算法的路徑規劃流程圖

路徑規劃的過程具體如下：

步驟1：在非障礙物區域，以機器人的起點作為父代，通過正態分布隨機地產生子代，其中子代不能落在障礙物上。

步驟：2以每個子代為父代，再隨機地產生下一代，其中距離目標點近的父代其適應值高，產生的種子較多。

步驟3：設置滾動窗口中種子的個數，當種子個數達到設定值后進行淘汰。其中淘汰的機制如下：將具體機器人目標點歐氏距離最近的子代設定為目標點，將父代與子代分別連接，直至到達目標點，此時至少可以得到一條能走到目標點的路徑。計算得到的路徑長度，長度最短的路徑即為所選路徑，在該路徑上的所有父代和子代均為所選的種子。

步驟4：重復以上步驟，直至機器人走到目標點。

機器人在滾動窗口中完成路徑規劃，并向前行走，重復上述行為直至到達目標點，從而完成機器人的工作。

3實驗

3.1 實驗平臺和實驗環境簡介

機器人（自主搭建的機器人）使用了開源機器人移動平臺來搭載機器人的相關硬件，搭載的硬件有迅為iTOP-4412開發板（對機器人進行控制）、STM32單片機（控制機器人的電機運轉）、思嵐2D雷達、超聲波傳感器等（傳感器進行障礙物數據采集）。機器人如圖4所示。

為構建試驗環境，隨機地在室內放置一些大紙盒與柵欄作為障礙物，并在設置機器人的目標點和起點后進行路徑規劃的實驗，從而驗證算法的可行性。

3.2 隨機障礙物的路徑規劃

隨機擺放的障礙物如圖5所示。

為防止機器人在行走的過程中可能會出現機器人碰撞障礙物的現象，因此需要在機器人采集到滾動窗口中障礙物的信息后，必須對障礙物進行適當的膨化處理，從而保證機器人的安全。

機器人由起點開始出發，采用雜草優化算法在機器人的滾窗內進行路徑規劃，直至走到目標點。因為機器人所在的工作環境是未知的，所以機器人只能得到滾動窗口里的障礙物信息，通過雜草優化算法的路徑規劃算法朝著目標點的方向生成新的種子，進行路徑規劃。機器人在滾動窗口中完成路徑規劃后，再采集下一個滾動窗口的信息，直至機器人到達目標點。在機器人使用雜草優化算法的路徑規劃算法走到目標點后，采用文獻[15]中的算法進行對比實驗，把結合滾動窗口和RRT算法的路徑規劃實驗作為比對實驗。在實驗過程中，分別記錄了兩種算法所規劃路徑的相關實驗數據，并通過Matlab（R2016b版本）軟件把機器人在相同的實驗環境中采用不同算法的行走軌跡在構建的地圖中標出來。其中機器人導航地圖構建的過程是采用2D激光雷達對機器人工作環境進行掃描，可以得到障礙物的雷達點云信息。為了保證機器人能安全工作，需要對障礙物的雷達點云進行膨脹處理，從而得到機器人導航用的障礙物地圖。

圖6為其中一次實驗的路徑軌跡，其中機器人的路徑軌跡信息采集是機器人在行走的過程中，每隔1秒，通過機器人的全局定位可得到機器人的位置信息，記錄機器人的位置信息后，通過Matlab繪圖，即可得到機器人的路徑軌跡。

為防止實驗的過程出現偶然性，所以在每次實驗結束后，無序地改變障礙物的數量與位置，并進行多次實驗，記錄相關的實驗數據。20次的實驗結果如表1所示。

通過表1可知基于滾動窗口的RRT算法規劃的路徑的平均長度為 439.5cm ，基于滾動窗口的雜草優化算法規劃的路徑的平均長度為 426.15cm_? 另外從圖6可以看出基于滾動窗口的雜草優化算法規劃出的路徑比基于滾動窗口的RRT算法規劃的路徑平滑一些，這樣也有利于機器人的行走。通過實驗可知，所以采用基于滾動窗口的雜草優化算法的路徑規劃具有實時性強，耗時短等特點。

4結論

基于機器人工作在未知的環境下，本文提出把滾動窗口和雜草優化算法進行結合，規劃生成機器人行走的路徑。移動機器人根據實際情況設定機器人的滾動窗口，機器人通過傳感器獲得滾動窗口中障礙物的信息，生成用于導航的地圖后，采用雜草優化算法進行路徑規劃。機器人在滾動窗口里以機器人的起點作為父代，通過正態分布隨機地產生子代，通過篩選淘汰，得到想要的種子，從而引導雜草生成的方向，使父代的種子盡可能地朝著目標點的方向生成，從而完成路徑規劃。與基于滾動窗口的RRT算法規劃的路徑相對比，本算法規劃的路徑，有較強的導向性、實時性，耗時較短，因此該算法在未知環境的路徑規劃中具有較強的實用性。后續的研究會針對復雜的障礙物環境進行實驗，探索復雜障礙物環境下算法的實用性。

參考文獻：

[1]許運鴻.基于局部和全局引導的倉儲多機器人路徑規劃算法研究[D].哈爾濱：哈爾濱工業大學，2022.

[2]邵偉偉，駱正磊.改進的可視圖法在路徑規劃中的運用[J].南陽師范學院學報，2018，17（4）：38-42.

[3]劉洋成，耿端陽，蘭玉彬，等.基于自動導航的農業裝備全覆蓋路徑規劃研究進展[J].中國農機化學報，2020，41（11）：185-192.

[4]邵偉偉.融合2D激光雷達與雙目視覺的機器人路徑規劃研究及應用[D].馬鞍山：安徽工業大學，2019.

[5]常新中，岳哲鵬，郜海超，等.基于改進粒子群的混合金豺優化算法的移動機器人路徑規劃[J].中原工學院學報，2023，34（4）：24-29.

[6]張揚，彭鵬菲，曹杰.基于改進APF算法的水面無人艇局部路徑規劃[J].兵器裝備工程學報，2023，44（9）：42-48.

[7]連興文，朱旭東，陳云海，等.基于改進 A^* 算法的變電站智能巡檢機器人路徑優化方法研究[J].電子設計工程，2023，31（18）：95-99.

[8]聶秀珍，焦迎雪，張霞.融合優化遺傳算法和變步長蟻群算法的礦山巡檢機器人路徑規劃[J].金屬礦山，2023（7）：248-253.

[9]盧玉.基于神經網絡的礦井救援機器人局部路徑規劃研究[D].濟南：山東建筑大學，2023.

[10]蔣睿，祝錫晶，馬寧，等.基于改進混合粒子群算法的智能車間無人機巡檢路徑規劃[J].機械設計與制造工程，2023，52（2）：51-57.

[11]朱紅秀，鄭權，杜闖，等.改進RRT算法用于電磁驅動機器魚路徑規劃[J].火力與指揮控制，2020，45（10）：100-105.

[12]石志剛，梅松，邵毅帆，等.基于人工勢場法的移動機器人路徑規劃研究現狀與展望[J].中國農機化學報，2021，42（12）：182-188.

[13]王旭揚，梁志偉，高翔，等.基于改進DWA算法的足球機器人局部軌跡規劃[J].國外電子測量技術，2023，42（8）：1-9.

[14]康亮，趙春霞，郭劍輝.未知環境下改進的基于RRT算法的移動機器人路徑規劃[J].模式識別與人工智能，2009（3）：337-343.

[15]張捍東，陳陽，吳玉秀.未知環境下移動機器人實時路徑規劃[J].計算機工程與應用，2018，54（19）：140-146.

[16]MehrabianAR，Lucas C.AnovelnumericaloptimizationalgorithminspiredfromweedcolonizationJ].EcologicalInfoatics，2006，1（4）：355-366.

[17]張夢坤.入侵性雜草優化算法的改進與應用[D].鎮江：江蘇科技大學，2021.

[18]康亮，趙春霞，郭劍輝.基于模糊滾動RRT算法的移動機器人路徑規劃[J].南京理工大學學報（自然科學版），2010，34（5）：642-648.