基于智能算法的多目標路徑規劃

李傳發 ，楊舒音 ，李 末 ，孟 妤

（1.大連理工大學機械工程學院，遼寧 大連 116024；2.中機科（北京）車輛檢測工程研究院有限公司，北京102100；3.大連益利亞科技發展有限公司，遼寧 大連116000）

1 研究背景

隨著著互聯網技術的發展，物聯網應運而生，其用途十分廣泛，遍及智能交通、倉儲物流、環境保護、工業檢測等多個領域。隨著快遞等服務業的快速發展，物聯網在倉儲物流中的應用也是起著非常大的作用，比如中國的一些大型港口已經實現無人化，一些快遞的中轉地依靠機器人進行快遞的分揀。在實際的應用場景中機器人有時需要從起點出發去不同的地點完成多個任務再回到起點，而為了減少機器人在路徑上花費的時間，需要算法來規劃其路徑，使機器人在執行任務時經過最短路徑。

本文所提出的算法所要解決的問題即當機器人需要從起點出發，路經多個需要停留作業的地點（目標點），然后回到起點時，規劃出機器人所走過的最短路徑。此類問題在現實中有很多應用的場景，因為我們有時需要的不只是從起點到終點兩點之間的路徑尋優，而是從起點到多個目標點的路徑尋優。比如外賣的配送、快遞的郵寄等，他們都是從一個起點出發，需要經過多個目標點再回到起點。而目前的路徑尋優基本是單目標點的尋優即從起點到終點的路徑規劃，比如經典的A*算法、D*算法以及本文用到的JPS算法[3]等，在這些算法的基礎上進行改進后，使得路徑的規劃更加高效，比如在A*的基礎上進行改進的算法如：吳鵬等人[4]提出的雙向 A*算法對比 A*算法效率上最大提升了73.4%，對A*算法的尋路策略進行優化，在保證原有算法路徑平滑性和安全性的基礎上，同時提升了機器人的尋路效率和實時規劃能力；李沖等人[5]提出了一種單邊矩形擴展 A*算法，通過受迫擴展規則，簡化了終止條件，提高了尋路效率和路徑質量；趙曉等人[6]提出跳點搜索方式以改進A*算法，降低對不必要節點的計算，從而使得尋路效率得以提升；Goldberg等[7]在啟發函數的精準度方面加以改進，以提高尋路效率，但由于過于側重速度提升使得空間復雜度增加。以上研究工作都是在路徑規劃的效率和路徑平滑性上進行了研究。

在規劃多個目標點之間的最短路徑時，機器人經過目標點之間的先后順序也是影響因素之一，根據上述算法的原理，這些算法只能規劃出兩個目標點之間的最短路徑，所以在解決多目標路徑規劃問題時，上述算法就無法單獨解決此類問題。為此，本文提出了在多目標路徑規劃時，可以先求解兩兩目標點之間的最短距離，再求出多個目標點在最短路徑中所處的次序，即以JPS算法求解出兩兩目標點之間的最短距離，再使用蟻群算法求解出依次經過各個目標點的順序，這樣就可以實現由算法規劃出一條經過多個目標點的最短路徑。經驗證可以很好的應用于多目標路徑規劃，在不同的環境下使用不同的超參數從而使算法整體的效率和準確性都大大提高。

2 智能算法

2.1 問題模型

本文的問題模型示例如圖1所示，此實際環境中常為機器人需要從點1出發，在遍歷其余四個目標點后，再回到起始點1，為了提高機器人的工作效率，要規劃出一條最優路徑。為了直觀的顯示未優化的路徑與優化后的路徑的效果對比，將由點1、4、5組成的三角形設為等邊三角形，由點1、2、5組成的三角形為鈍角三角形，且位于點5處的角為鈍角。

圖1 示例目標點

如圖2所示，所采用的策略為按照目標點序號的大小進行遍歷，采用這種方法時所經過路徑的沒有進行優化，與圖3經過蟻群算法優化后的路徑進行對比可知，后者的路徑長度減少了3.5，當目標點增多時，經過在第四章的對比，這個結果會更加顯著，所以對路徑進行優化可以顯著的提高機器人的工作效率。

圖2 按序號遍歷

圖3 按蟻群算法優化后遍歷

在實際的環境中，可能還會有障礙物的存在，不能直接得知兩兩目標點之間的最短距離，所以兩個目標點之間的距離和路徑也需要進行規劃。而JPS是Daniel Harabor與Alban Grastien提出的一種基于A*的算法，它在柵格無權地圖的搜索性能要強于A*算法，本文選用了JPS算法來降低整體算法的時間復雜度，因為在目標較多時，路徑搜索的運算量也是呈指數級上升，所以找到一個低時間復雜度的算法顯得尤為重要。

2.2 算法思路

（1）算法的整體思路為：輸入所有目標點的坐標，利用JPS算法快速的計算出將兩兩目標點之間的最優路徑，將這些路徑的具體信息（如柵格地圖中，路徑所經過方格時，所有方格的中心坐標的集合即為具體信息）和路徑的長度分別存儲在各自的列表中，然后將存有各個目標點之間路徑長度的列表，輸入到蟻群算法中，計算出最優的路徑中目標點的排列順序，并返回到一個列表中，結合存有兩兩目標點之間路徑具體信息的列表。就可以得出一次遍歷所有目標點的具體路徑。算法的總體流程框圖如圖4所示。

圖4 流程框圖

JPS的實現方式如下：從起點先隨機尋找一個方向進行搜索，在搜索時為兩個循環嵌套，在斜向上前進一個單位后，分別在此方向的橫向和豎向進行搜索，比如選擇（1，1）方向進行搜索時，那么在橫向與豎向的搜索方向分別為（1，0）、（0，1），當在橫向搜索與豎向搜索結束時，進行下一循環，即進入下一個狀態的斜向搜索。當橫向、豎向的下一位置為障礙物、邊界或終點時停止橫向與豎向的搜索，即停止循環進入斜向搜索循環，同樣的，當斜向搜索下一位置為障礙物或邊界時，一個循環至此結束，并將所有的強制臨點，與強制臨點的父節點加入到openset列表中，然后再在起點選擇一個與之不同的方向進行循環，這樣就可以遍歷所有圖的節點并最終可已找到一條起點與終點之間的最優路徑。

強制臨點的判斷：如圖5所示為直線方向在判斷強制臨點時，需要判斷在p（x）上下兩個位置，如果有障礙物則將其斜上方的點當做強制臨點加入openset列表中，并將斜上方節點的父節點設為當前節點，一同加入openset列表中、diagonal方向在判斷強制臨點時，需要判斷當前節點的下方與左方是否為障礙物，如x點下方有障礙物，則x的強制臨點為左下方的節點，同樣的將其加入到openset列表中，并將其設為x的子節點，這些節點再加入到openset列表中。

圖5 橫向搜索

將JPS與蟻群算法相結合的計算路徑長度算法為計算由JPS規劃出兩兩目標點之間的幾何距離，因為蟻群算法需要在給定了兩兩目標點的距離后，才能開始優化，所以需要一個函數將JPS中各個目標點的具體路徑（儲存在圖7的列表l1中）進行計算得出兩兩目標點之間的距離（儲存在圖7的列表l2中），再傳入蟻群算法中。流程圖中的第二個循環內的判斷中點i與點j的距離L加1或加1.4（圖6）當機器人沿柵格的斜邊走時是其沿直角邊走大約是距離的1.4倍，是根據點i與點j之間路徑中相鄰兩點位于水平線或在對角線的位置為判斷依據。經過其流程圖為：

圖7 計算路徑長度算法

3 超參數測定

蟻群算法（ant colony optimization，ACO），又稱螞蟻算法，是一種用來在圖中尋找優化路徑的機率型算法，它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發現路徑的行為，蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優良的性質[1-2]。

將計算出的各個目標點的路徑長度傳入蟻群算法中，然后利用蟻群算法進行計算。首先將參數進行初始化，然后開始使螞蟻分別對一條路徑進行探索，首先隨機選擇一個目標點，然后計算此目標點到其他未到達過得目標點的轉移概率，選擇下一城市的方式為輪盤賭的方式，然后在所有目標點之間進行循環，直到一只螞蟻將所有的城市都遍歷完畢，并將其所路經的距離進行計算，記為totle-distance，在所有螞蟻循環完畢以后，將路過路徑最短的螞蟻記為best-ant，用于返回最優路徑，在所有螞蟻遍歷過所有路徑一次后，更新路徑上的信息素，并進入下一次循環。流程圖如圖8所示。

圖8 蟻群算法規劃目標點順序流程圖

在蟻群算法中需要對超參數進行預先設定，而一般人們對超參數的設定往往根據經驗進行設定，但是對于不同的問題，不同的超參數會影響算法的整體效率，所以作者對本算法用到的模型進行了超參數的測定，使算法可以在特定的環境下更有效率。

圖9中縱坐標為路徑的最短距離，橫坐標為迭代次數，從上到下，從左到右依次分別為10、20、30只螞蟻進行優化的曲線。由圖9中可以看出當目標點的數目在20個左右時，螞蟻的數量為20左右時，路徑就可以達到最優，當螞蟻的數目再增加只是減少了迭代次數，但是目標點數目的增加對會使算法的效率降低，所以21目標點設置20螞蟻進行迭代最優。

圖921 目標點收斂曲線

圖10從上到下，從左到右依次分別為30、50、70只螞蟻進行優化的曲線，可以看出當目標點數為51時，螞蟻數量為50時，就能找到最優路徑。由上面兩組圖我們可以看出目標點的數目和螞蟻的數量相當時，算法就可以達到一個很好的效果。

圖1051 目標點收斂曲線

4 模擬實驗

為了驗證本算法的可行性，在python3.7的平臺環境下進行了仿真實驗，分別仿真了21個目標點和51個目標點，通過實驗驗證了本文所提出的算法的可行性。實驗結果如圖11-14所示：其中灰色的方塊代表機器人[智能體]要到達的目標點，灰色實心格子為障礙物，灰色空心格子為可移動路徑，灰色的實線為智能體的移動路徑。

圖1121 目標點路徑尋優

圖1221 目標點路徑

圖1351 目標點路徑尋優

圖1451 目標點隨機路徑

由圖11與圖12和圖13與圖14對比可以看出經過優化后的路徑比沒有優化的路徑要短，經過計算得知圖11的路徑總長為75.8，圖12的路徑長度為76.2；圖13的路徑總長為182.4，圖14的路徑長度為279，圖12的路徑經過了簡單的目標點順序規劃，如圖15所示，左右兩圖目標點的坐標相同，但是兩圖中點2與點3的順序不同，兩圖的遍歷順序都為點1到點2到點3到點4，這時可以看出右圖的路徑長度明顯小于左邊的長度。這是因為當遍歷路徑時當由交叉線時，路徑的長度就會變大，所以可以在連接各個目標點時盡量避免路徑重疊可以縮短路徑，但是此方法費時費力，所以需要蟻群算法來幫助規劃，當沒有進行任何規劃時，如果只是讓機器人隨機的遍歷目標點，由14圖可以看出路徑明顯的增多。所以經過對比可以看出此算法可以很好的應用于多目標點的路徑尋優。

圖15 路徑規劃

5 結語

本文所選用的蟻群算法和JPS算法很好的解決了所目標路徑規劃的問題，作者對整體的算法進行了設計，對蟻群算法中的超參數進行了仿真，使得算法的效率進一步提升。要想將算法應用到現實情況中，還需要對算法進一步優化，因為算法的路徑的拐點過于曲折，所以作者下一步將會對路徑進行優化，使其可以應用到實際情況中。