一種啟發式自優化的紫外線消毒機器人路徑規劃方法

余一聰，駱紹燁，許城濤，張勇敢，蔡榮貴，2

（1.莆田學院 新工科產業學院， 福建 莆田 351100，2.廈門金龍聯合汽車工業有限公司，福建 廈門 361006）

1 研究背景

新冠病毒的全球蔓延，對我國產業產生許多負面影響，疫情讓大家對公共環境衛生問題尤為關注。目前有許多殺毒技術被提出，如紫外線殺毒已被證實有效，不污染環境。紫外線殺毒需滿足一定要求，即特定的紫外線波長、照射劑量和時間等[1]。大部分紫外線殺毒裝置采用定點方式安置，機動性不足、耗費人力等。通過在移動式機器人上裝載紫外線消毒裝置，能夠讓機器人在特定的區域范圍內自主移動進行殺毒，充當疫情“志愿者”，降低人力成本，提高公共衛生應急響應能力。

在實際復雜環境特定區域下，往往消毒區域復雜且存在諸多障礙物，移動式紫外線消毒機器人常因移動軌跡未優化，使得消毒區域的全覆蓋目標難以實現。因此，如何實現在給定區域利用路徑規劃算法給出最佳的移動軌跡，同時根據移動中出現的障礙物情況實時調整移動軌跡，獲得最佳的消毒移動軌跡，已成為紫外線消毒機器人當前的研究熱點。本研究中，首先把特定的消毒區域切割成許多小網格，并考慮每一個網格需達到全覆蓋，當滿足這個條件時，則整個消毒區域能達到全覆蓋。

傳統的路徑規劃算法并不能保證全區域的殺毒，雖然使用移動式機器人可克服部分環境的限制，但仍面臨著殺毒區域不夠全面，包括由障礙物造成的小范圍死角和殺毒點位不夠精準的問題。此外，需考慮移動機器人電力不足，須返回充電站進行充電任務。為了解決上述問題，本研究提出了一種啟發式自優化的路徑規劃（Heuristic Self-optimizing Path Planning，HSPP）算法。該算法旨在實現消毒區域的全覆蓋，優化機器人的路徑長度并確保回到起點。HSPP 分為2 個程序：路徑生成與路徑優化程序。在路徑生成程序中，機器人試圖基于SCAN 算法，生成一種路徑的可行解，能夠覆蓋全區域的消毒軌跡。在路徑優化程序中，采用貪心策略優化機器人的移動路徑軌跡，減少機器人重復的移動軌跡。本研究的貢獻有以下3 點：

（1）提出了HSPP 算法，設計并實現了路徑生成與路徑優化程序用于移動式紫外線消毒機器人。

（2）在路徑生成程序中，HSPP 基于SCAN算法，達到全區域覆蓋的目標，實現全區域消毒任務。

（3）通過路徑優化程序尋求最小環的策略縮短機器人的總移動路徑長度，提高消毒效率。

2 相關研究

國內外學者針對移動機器人的路徑規劃做了大量相關研究。Liu 等[2]提出一種基于Delaunay的測量算法，通過標定Voronoi 節點作為改進的A*算法尋路節點，并融合了動態融合尋路算法，提高了路徑規劃算法效率，但并未充分考慮路徑規劃中的全覆蓋及安全性等。Hou 等[3]提出了一種基于蟻群算法的修正策略，能夠減少移動路徑中曲折路線信息造成的干擾，該方法能提升算法收斂速度和結果。王豪等[4]提出一種改進自適應遺傳算法應用于機器人路徑規劃，將移動路徑長度和拐點數量選為評估指標，并設計了自適應交叉算子等，提高了算法收斂速度等問題。陸向龍等[5]針對復雜的果園環境，提出了一種融合A*算法與DWA 算法路徑規劃算法，可實現果園復雜環境下噴霧機器人的作業需求。劉子豪等[6]針對室內移動中存在過多的冗余拐點等現象，提出一種改進的A*算法，結合跳躍點搜索理論,通過選取特定關鍵點的方法用于室內環境的機器人移動，結果表明在相同環境下，運行時間及總長度等均有明顯的提高。秦濤等[7]設計一款集成紫外線消毒及噴霧功能的移動消毒防疫機器人，通過移動底盤進行地圖構建和自主導航，能夠在仿真地圖環境下自主導航，可實現室內空間區域地面及較高位置消毒的需求。徐建萍等[8]設計一款可移動自動消殺機械控制系統，該機器人可攜帶不同的機械臂，通過即時定位與地圖構建（Simultaneous Localization and Mapping，SLAM）技術進行導航操作，可滿足對狹窄空間等進行無接觸自動消殺作業需求。

3 紫外線消毒機器人路徑規劃

3.1 問題概述

為了實現對公共環境區域消毒的效果，可通過紫外線照射的方式，破壞和改變病毒微生物的結構，使病毒立即死亡或無法增殖，從而實現對環境消毒的目標。不妨通過設定待消毒的環境區域，按照前面所述，將整個環境區域（圖1）切割成多個小網格，其中LG為小網格的大小，為紫外線照射半徑。通過勾股定理，能夠很容易得出網格長度LG與的關系式，如式（1）所示：

圖1 紫外線照射半徑與網格大小的關系

因此，機器人在小網格的中心位置，即代表該網格被機器人的紫外線所覆蓋。本研究期望機器人在移動中以以最短路徑遍歷所有的小網格，確保每個小網格僅被訪問一次，并最終返回到出發點，在這個設計中，借鑒了掃地機器人回到原點充電的思路[9]。此外，基于分治法的原理，通過遍歷所有小區域的方式，當每個小區域都能被覆蓋到，則整個區域都實現全覆蓋的目標。在路徑移動的問題上，為了節能與省時，同時期望遍歷的路徑越短越好，這個問題可轉化為商旅問題(Travelling Salesman Problem, TSP) 的一個實例。假設在環境中，存在個小網格，這些網格可用集合來表示，機器人從起點L0出發后，然后沿著移動路徑逐一訪問每個網格，確保每個網格都能夠被遍歷1 次，最終再回到起點L0，因此，機器人的遍歷路徑Z 可描述為式（2）所示：

其中式（3）受限于式（4）：

那么，機器人的移動軌跡的最短路徑SP，可用式（5）表示：

為了滿足HSPP 中的路徑生成與路徑優化程序，機器人必須記錄的每一個小網格的相關屬性。假設整個區域Area 被切割成n 個網格，每一個網格gi∈Area，1 ﹤i ﹤n 都有唯一的ID、機器人網格的遍歷路徑滿足，它們負責記錄機器人需遍歷網格的順序。同時將區域的左上角網格g1設置為起點，機器人會遍歷所有的網格，最終再回到起點g1。在機器人移動中，定義網格權值Wi用于記錄網格g1被走訪的次數，若某一個網格被機器人訪問過多次，則權重值Wi越高，其初始值設置為0。另外，在遍歷路徑Z中設置標簽ti標記，當tagi=1 代表可被刪除，當tagi=0 代表不能被刪除。

3.2 路徑生成程序

設定機器人具有上下左右及其45°方向等8種移動方向，如圖2 所示。

圖2 機器人移動的8 個方向

HSPP 的路徑生成程序是基于SCAN 產生移動網格路徑軌跡（圖3），并記錄該網格的ID、遍歷的次序及權值。假定機器人從左上角的網格中心點出發，沿著X 軸遍歷每一個小網格，當同一行的網格都被遍歷過后，沿著Y 軸向下移動一個小網格的距離，繼續沿著X 軸的反方向遍歷，直到遍歷過所有網格，實現特定區域的全覆蓋。在真實的環境中，機器人需避開移動路徑上的障礙物。為此采用一種簡單而有效的策略來繞過障礙物，即在機器人上安裝激光雷達，讓機器人在遇到障礙物時能夠自主靈活地調整路徑進行繞行。如圖4 所示，當探測到左側障礙物面積大于右側時，機器人將向右側的網格遍歷，并沿著障礙物周圍的網格繞行，反之則相反；如果障礙物太大，機器人無法判定左右兩邊面積的大小時，機器人隨機選擇一個方向的網格遍歷并繞過障礙物。

圖3 機器人SCAN 的路徑軌跡

圖4 機器人遇障礙物繞行策略

3.3 路徑優化程序

由路徑生成程序生成的路徑有時可能導致機器人在繞過障礙物時遍歷了冗余重復路徑，本研究要設法去除多余的路徑，因此被訪問超過1 次的節點必須去除。除此之外，去除的原則必須保證機器人的路徑是不間斷的。由于簡單的SCAN并不總能生成一個最小環，為了避免過長重復路徑，在路徑生成程序執行后，啟動路徑優化程序。路徑優化程序采用貪心法的策略，試圖縮短機器人的遍歷的路徑。假設某路徑生成程序所生成的序列Z={gi, gi+1, gi+2, gi+3,…, gn, gi}，對應的權值為wi, 1 ≤i ≤n。由于機器人必須從原點出發，最終返回原點，故路徑優化程序只需從序列第2 個節點開始依次檢查，以下為路徑優化程序的步驟：

步驟1：設置檢查起點位置，逐一向后檢查每一個節點的權值，若節點的權值大于1 且位置與的鄰接距離大于1 時，則繼續向后檢查，式（6）為位置i 與位置j 的初始化。

定義鄰接距離Adj 為2 個相鄰的節點，即在序列中位置的距離之差，如式（7）所示。

步驟2：當某節點的權值為1 時且位置i 與j的鄰接距離等于1 時, 則該節點設置為檢查終止位置j。刪除起點位置i 與終止位置j 之間的節點。由于權值大于1 則代表該節點被遍歷超過1 次，因此，可以刪去權值大于1 的節點。假設原始序列Z 中，元素個數有n 個，SS 為位置i+1 至位置j-1的元素所構成的集合，元素有m 個，因此可以表示為式（8）：

步驟3：由于將權值大于1 的刪除，所以權值wk必須減1（更新）成為新的權值，如式（9）所示。

步驟4：若尚未達到序列的最后節點，則將終止位置設置為新的起點位置并返回第1 步，否則整個程序結束。以圖5 為例，在序列中增加許多重復路徑，以此證明如何通過優化路徑程序來優化路徑長度。假設路徑軌跡Z(0)={g1, g2, g3, g6,g5, g4, g7, g8, g9, g8, g5, g6, g3, g2, g1}，序列長度為15。由于序列頭尾節點是不能夠被刪除的節點，故先將檢查起點位置設置為第2 個節點g2，由第二個結點逐步向后檢查，發現到第6 個節點g4與第2 個節點相鄰（相鄰距離為1），同時第6 個節點的權值為1，因此將第6 個節點設置為檢查終止位置j。因此，能夠將節點g3、g6和g5刪除。緊接著，將檢查起點位置i 設為j，再將設置為新的檢查起點,逐步向后檢查。直到第9 個節點為i，第11 個節點為j 時，其第10 個節點g8符合被刪除的條件，因此將第14 個節點刪除。經過優化程序后的結果為Z(1)={g1, g2, g4, g7, g8, g9, g5, g6, g3, g2,g1}，如表1 所示。接著再將優化過1 輪的序列整理后繼續進入第2 輪的路徑優化程序。從序列Z(1)中，發現Z(1)已無法再優化，故路徑優化程序結束。

圖5 機器人經路徑程序優化后的路徑長度示例

表1 經過一輪路徑優化程序案例

4 仿真實驗設計及結果

4.1 實驗環境與參數設置

在仿真開發方面，使用Windows 10 系統，利用Java 語言、MATLAB 以及Gnuplot 作為繪圖及輔助工具。通過設定3 組對比實驗來比較HSPP、隨機法和SCAN 的平均路徑長度比和平均覆蓋率等內容。

隨機法要達到全覆蓋需花費很長的時間，假設機器人移動1 個小網格耗費1 個單位時間，S定義為總路徑長度與2 倍的網格總數的比率，其中Atotal為整個區域的網格總數，而平均路徑長度APL 等于SPLR 除以總執行次數，如式（10）所示：

當遍歷序列S 中的網格Gj與Gk存在路徑時，xij為1 否則為0，其中exe 為總執行的次數。此外，為了評估紫外線消毒機器人的消毒效率并實現全區覆蓋的目標，定義Acovered為被覆蓋的網格總數，那么覆蓋率的計算方式如式（11），平均覆蓋率CR 可用式（12）表示：

每組實驗進行如下：（A）改變區域大小；（B）改變障礙物數量；（C）改變障礙物大小。實驗設置的參數見表2。

表2 實驗參數設置

4.2 改變區域大小的影響

在本實驗中，通過改變區域的大小，比較3 種方法的平均路徑長度與覆蓋率的效能。其中區域邊長從100 單位網格數遞增至500 單位網格數，每組實驗的區域邊長每次遞增50 個單位網格，障礙物的大小為1 個單位網格，障礙物的數量固定為1 500 個。從圖6 可看出，區域大小的改變對于HSPP 與SCAN 法在覆蓋率上并無明顯區別，原因在于SCAN 是以全區域覆蓋目標所設計，HSPP 的路徑生成程序是基于SCAN 改進的。在平均路徑長度比表現方面，SCAN 的路徑長度約為隨機法的0.6 倍，而HSPP 約為隨機法的0.4 倍，效果最佳。這是由于隨機算法未考慮到覆蓋與路徑的問題，SCAN雖考慮了移動路徑，但當環境中存在較多障礙物時，SCAN 未對路徑進行優化，會生成許多重復的路徑；而HSPP 考慮了重復路徑問題，針對路徑長度進行了優化。

圖6 區域大小對路徑長度的影響

4.3 改變障礙物數量的影響

在本實驗中，設法改變障礙物的數量，比較3 種方法的平均路徑長度比與覆蓋率的效能。區域的大小固定為單位網格，障礙物的大小固定為1 個單位網格，隨機生成的障礙物數量從600 個遞增至1 500 個，每組實驗的障礙物數量依次遞增100 個。從圖7 可看出，障礙物數量的改變對于HSPP 與SCAN 法的覆蓋率有一定影響。當障礙物數量達到1 500 個，HSPP 的平均路徑長度比為0.36，SCAN 的平均路徑長度比為0.58。隨著障礙物數量的增加，SCAN 的重復路徑增加，HSPP 使用優化程序進行優化，使得其平均路徑長度比明顯優于SCAN 與隨機法。

圖7 障礙物的數量對路徑長度的影響

4.4 改變障礙物大小的影響

為了營造不規則區域場景的環境，在實驗中，通過改變障礙物的大小，形成各種不同形狀大小的障礙物，并使得障礙物間可能相鄰。本組實驗同樣比較3 種方法的平均路徑長度比與覆蓋率的效能。區域的大小固定為 單位網格，障礙物的數量固定為500 個，障礙物的大小從1 個單位網格大小遞增至10 個單位網格大小，每組實驗的障礙物的大小遞增1 個單位網格。從圖8 可看出，障礙物大小的改變對于HSPP 與SCAN 法的覆蓋率都達到100%。當障礙物大小為10 時，HSPP 的平均路徑長度比為0.363，SCAN 的平均路徑長度比為0.41。隨著障礙物大小的增加，SCAN 的重復路徑隨之增加，經過優化程序的HSPP 算法在平均路徑長度比明顯優于隨機法，且比SCAN 表現更好。

圖8 障礙物的大小對路徑長度的影響

5 結論

移動式紫外線殺毒機器人是一種高效且實用的公共環境消毒技術應用，但現實中移動機器人未能完全滿足復雜環境區域的任務需求，常因移動軌跡未優化、消毒區域不全面等問題而未能發揮出最大效能。而在本研究中裝載HSPP 算法的移動式紫外線消毒機器人能夠通過SCAN 生成一種可行的移動軌跡進而優化的方法，能很好地滿足全區域高效全面的消毒任務，具有很好的應用價值。