基于智能算法的多目標路徑規(guī)劃

李傳發(fā) ，楊舒音 ，李 末 ，孟 妤

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

1 研究背景

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

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

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

2 智能算法

2.1 問題模型

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

圖1 示例目標點

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

圖2 按序號遍歷

圖3 按蟻群算法優(yōu)化后遍歷

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

2.2 算法思路

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

圖4 流程框圖

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

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

圖5 橫向搜索

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

圖7 計算路徑長度算法

3 超參數(shù)測定

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

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

圖8 蟻群算法規(guī)劃目標點順序流程圖

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

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

圖921 目標點收斂曲線

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

圖1051 目標點收斂曲線

4 模擬實驗

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

圖1121 目標點路徑尋優(yōu)

圖1221 目標點路徑

圖1351 目標點路徑尋優(yōu)

圖1451 目標點隨機路徑

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

圖15 路徑規(guī)劃

5 結(jié)語

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