0 引言

    機器人路徑規(guī)劃（Robot Path Planning，RPP）的主要研究目的是尋找工作空間內(nèi)的一條從出發(fā)點到目標點的運動路徑，使機器人可以避開所有障礙物，且路徑長度最短。RPP問題的相關研究成果在物流、危險物資傳送、大規(guī)模集成電路設計等領域中有著廣泛的應用^[1-5]。在求解RPP問題的相關算法中，柵格法(Grid Method，GM)是一類較常用的環(huán)境建模方法^[6-8]。一些已存在的RPP算法存在計算參數(shù)過多的問題^[9-10]。例如：文獻[9]提出的算法需要設置5個計算參數(shù)，而文獻[10]提出的算法需要設置7個計算參數(shù)。計算參數(shù)是指算法模型的控制參數(shù)，不包括迭代次數(shù)等執(zhí)行參數(shù)。計算參數(shù)過多本質上增加了算法的復雜性，給算法的實際工程應用帶來困難。

    本文提出一種全新的用于求解RPP問題的自學習蟻群算法(Self-learning Ant Colony Optimization，SlACO)，該方法使用一種改進柵格法(Improved Grid Method，IGM)進行環(huán)境建模，螞蟻個體使用8-geometry行進規(guī)則。通過機器學習和多目標搜索策略，螞蟻個體一次搜索可以發(fā)現(xiàn)多條可行路徑，提高了算法計算效率。特別是該算法只需進行一個計算參數(shù)設置，簡化了算法的調試過程。

1 λ-geometry行進策略

2 自學習蟻群算法

    cell^(x，y)表示密度為X×Y的柵格地圖中的一個單元格，(x，y)代表單元格的坐標，滿足：x∈{1，2，…，X}，y∈{1，2，…，Y}，S表示機器人初始位置單元格，D代表目標位置單元格，p_k^t表示種群中第k個螞蟻個體在t時刻的單元格位置。

2.1 改進柵格法環(huán)境建模

    改進柵格法(IGM)主要用于SlACO算法的環(huán)境建模。IGM在基本柵格法的基礎上做出如下改進：

    (1)SlACO算法中，目標單元格D被看作食物。D通過食物分裂操作生成搜索目標并存放在集合搜索目標集合SA中。SA具體定義如下：

式中，l是搜索目標在集合SA中的下標，L記錄了集合SA中搜索目標的總數(shù)，tc_l表示SA中第l個搜索目標。當λ-geometry被使用時，有2λ個方向產(chǎn)生搜索目標，每個方向上可以產(chǎn)生多個搜索目標。SlACO算法具體執(zhí)行時，食物分裂操作采用的是16-geometry。在IGM地圖中，每個單元格增加兩個標記α和β。α=0表示當前單元格為障礙物單元格；α=1表示當前單元格為可行域單元格。據(jù)此，IGM地圖的單元格可以被形式化描述為cell^(x，y) (α，β)。β=1表示當前單元格為搜索目標單元格；β=0表示當前單元格不是搜索目標單元格。通過以上設計，IGM地圖中存在以下三類單元格：①障礙物單元格cell^(x，y)(0，0)；②可行域單元格cell^(x，y)(1，0)；③搜索目標單元格cell^(x，y)(1，1)。

    (2)大部分基于柵格法的RPP算法中，機器人每行進一步都要判斷是否遇到工作空間的邊界或者越界。因此，頻繁判斷邊界是RPP算法程序的一項較大的計算開銷。傳統(tǒng)的柵格地圖中，機器人判斷工作空間的邊界通常是根據(jù)單元格的坐標完成某種特殊處理。IGM在基本柵格地圖周圍增加了一層障礙物單元格。當機器人移動至工作空間的邊界時，只需做常規(guī)的障礙物判斷，無需做特別的邊界處理。此方法雖然增加了少量的存儲空間，但可以減少算法執(zhí)行時的計算開銷。

    基于以上描述，存放IGM地圖的集合GM可以被描述如下：

    以一個8×8的柵格地圖為例，增加邊界單元格后實際密度是10×10，IGM地圖的各組成部分如圖2所示。

2.2 自學習蟻群算法的主要策略

2.2.1 螞蟻個體行進策略

    SlACO中螞蟻行進策略如式(3)所示：

2.2.2 貪婪搜索策略

    式(3)中，當0＜r₀＜0.3時，ant_k執(zhí)行貪婪搜索Greedy(RF_k)。Greedy（RF_k）表示ant_k從RF_k中選擇啟發(fā)信息最小的單元格作為不同于其他仿生算法，SlACO算法的特點在于：啟發(fā)信息來源于眾多的搜索目標，而非單一的目標單元格，如圖3所示。

    從圖3可以看出：螞蟻群的規(guī)模為K，搜索目標的規(guī)模為L。參數(shù)δ記錄了SlACO中的啟發(fā)信息。啟發(fā)信息通過計算可達域中單元格與搜索目標之間的歐氏距離得到。由于每個螞蟻都對應著不同的搜索目標，在不同的時刻螞蟻個體也具有不同的可達域，因此每個螞蟻所感知的啟發(fā)信息也不同，每個螞蟻會按有不同路線移動，增加了算法解的多樣性。Ant_k螞蟻在t時刻的啟發(fā)信息可以通過如下公式計算：

2.2.3 強化搜索策略

    強化學習的計算過程為：按信息素濃度由低到高依次對可達域中的可行單元格設置權重，其中信息素濃度最低的權重設置為：θ₁=10，第二低的權值為：θ₂=20，余下的值通過斐波那契數(shù)列計算得出。排序為n的單元格權重θ_n=θ_n-1+θ_n-2。根據(jù)單元格權重，得到各自權重空間的取值區(qū)間，其中，s₁=[1，θ₁]，s₂=[θ₁+1，θ₂]，排序為n的單元格的權重空間為s_n=[θ_n-1+1，θ_n]。按權重排序，最后一個單元格的權重為θ_J，在1～δ_J之間取一個隨機整數(shù)r₂=Rand(1，δ_J)。某一時刻，如果r₂∈s_n，則s_n單元格被選擇作為下一步行進的單元格。

    進一步，當ant_k發(fā)現(xiàn)一條新的路徑TP_k時，TP_k包含的單元格的信息素按式(7)更新。

3 算法的整體描述

    當柵格地圖被初始化后，地圖內(nèi)很多單元格可能被標記為目標單元格（β=1）。t時刻，螞蟻k可行域可能包含多個搜索目標，意味著多條安全路徑被發(fā)現(xiàn)。SlACO算法的當前最優(yōu)路徑被集合BestPath記錄。算法整體描述如下：

    (1)初始化，設算法最大迭代次數(shù)為G_max，種群規(guī)模K，設置BestPath←∞用于記錄最優(yōu)路徑，設置變量k←1，l←1；

    (2)用IGM方法對工作空間建模，得到地圖GM，標記初始位置單元格S和目標位置單元格D；

    (3)生成L個搜索目標并存放在集合SA中，并在GM中做好標記；

    (4)根據(jù)式(6)，設置每個單元格初始信息素值；

    (5)根據(jù)式(3)，完成第k只螞蟻向第l個搜索目標向前爬行一步；

    (6)判斷當前可達域RFk中是否存在搜索目標，如存在，執(zhí)行步驟(7)，否則跳轉步驟(9)；

    (7)根據(jù)新發(fā)現(xiàn)的路徑更新單元格信息素；

    (8)比較BestPath與新發(fā)現(xiàn)的可行路徑，選出其中最優(yōu)的最為BestPath；

    (9)判斷當前可達域RFk中是否存在搜索目標l，如存在，則執(zhí)行步驟(10)，否則跳轉步驟(5)；

    (10)執(zhí)行k←k+1，如果k≤K，則跳轉至步驟(5)，否則執(zhí)行k←1，執(zhí)行步驟(11)；

    (11)執(zhí)行l(wèi)←l+1，如果l≤L，則跳轉至步驟(5)；否則執(zhí)行l(wèi)←1，執(zhí)行步驟(2)；

    (12)判斷是否滿足結束條件，如果滿足，則執(zhí)行步驟(13)，否則執(zhí)行步驟(5)；

    (13)輸出BestPath作為最優(yōu)路徑。

4 仿真實驗

    本節(jié)主要完成SlACO算法應用于RPP問題的實驗測試。實驗環(huán)境為:Windows 7 32位操作系統(tǒng)，Intel Core^TM i5-4300U CPU，4 GB內(nèi)存，仿真工具為Java語言。

4.1 算法效果仿真實驗

    為了檢驗算法的環(huán)境適應性和收斂速度，本文做了大量的仿真實驗，機器人工作空間為30×30柵格地圖，SlACO算法的種群規(guī)模參數(shù)設置為K=10。實驗程序用符號“□”標記了機器人的運動軌跡。在數(shù)十次實驗中SlACO均能規(guī)劃出最優(yōu)或基本最優(yōu)的路徑。SlACO算法規(guī)劃路徑的實驗結果如圖4所示。

    觀察圖4可以發(fā)現(xiàn)：行進軌跡的最后一個單元格與目標單元格D之間距離較長，產(chǎn)生這一仿真結果的原因在于多目標搜索策略使機器人可以在較遠的距離發(fā)現(xiàn)目標單元格D，進一步縮短了規(guī)劃路徑的距離。由于行進方式采用8-geometry，螞蟻個體可以1、、2、的步長行進，因此仿真實驗中兩個行進軌跡之間的距離并不統(tǒng)一，但規(guī)劃路線相較于4-geometry更為平滑。

4.2 與先進算法比較

    不失一般性，針對圖4中的3個柵格地圖，本節(jié)對SlACO、文獻[9]提出的激勵機制的改進蟻群算法(Incentive Mechanism Based Improved Ant Colony Optimization，IM-ACO)算法和文獻[10]提出的改進蛙跳算法(Improved Shuffled Frog Leaping，ISFL)算法進行了性能比較。IM-ACO和ISFL算法的參數(shù)設置參考文獻[9]和文獻[10]。圖4中的每個柵格地圖被連續(xù)運行20次，每次迭代最大次數(shù)為50次。表1展示了算法求得的平均路徑長度并使用SPSS軟件對實驗數(shù)據(jù)進行了秩和檢驗（Wilcoxon Signed-rank Test）得到秩和測試p值。表1中的“+”表示兩組實驗數(shù)據(jù)具有統(tǒng)計學差異。

    表1顯示，3個柵格地圖中SlACO算法規(guī)劃出的路徑更優(yōu)。

    相較于大部分已存在的RPP算法，SlACO算法的優(yōu)勢如下：

    (1)SlACO實現(xiàn)單計算參數(shù)控制，可控性較好；

    (2)SlACO采用的8-geometry策略，螞蟻個體可以1、、2、的步長行進，而大部分RPP算法只可以用1、的步長行進；

    (3)自學習搜索策略可以使螞蟻沿當前最優(yōu)路徑尋跡搜索，對當前最優(yōu)路徑進一步優(yōu)化，得到更優(yōu)的路徑；

    (4)多目標搜索可以保證SlACO算法解的多樣性，螞蟻個體一次搜索可以發(fā)現(xiàn)多條路徑；

    (5)多目標搜索可以使螞蟻個體在較遠距離發(fā)現(xiàn)目標單元格，提高了算法的計算效率，使得搜索的路徑更短。

    綜上所述，SlACO算法可以應用于復雜二維空間的RPP問題，而且性能穩(wěn)定。

5 結論

    本文介紹一種用于求解機器人路徑導航問題的自學習蟻群算法，算法綜合考慮了路徑規(guī)劃過程中的計算效率和所生成的可行路徑的平滑性。8-geometry行進規(guī)則的使用保證了最終規(guī)劃路線的平滑性，自學習搜索保證了算法的執(zhí)行效率。相較于已存在的蟻群算法，SlACO算法中螞蟻個體的搜索域更大，因此增加了部分計算開銷；但其對搜索目標的一次行進過程可以發(fā)現(xiàn)多條可行路徑，可以使算法的計算效率大幅增加，因此這部分計算開銷可以抵消。由于SlACO算法性能較依賴搜索目標的數(shù)量，因此，如果目標單元格附近障礙物較少，那么SLACO算法的性能通常表現(xiàn)得更好。從實驗結果來看：SlACO算法能夠處理復雜工作空間的機器人路徑規(guī)劃問題，實驗結果較為理想。

參考文獻

[1] 陳明建，林偉，曾碧.基于滾動窗口的機器人自主構圖路徑規(guī)劃[J].計算機工程，2017，43(2)：286-292.

[2] 殷路，尹怡欣.基于動態(tài)人工勢場法的路徑規(guī)劃仿真研究[J].系統(tǒng)仿真學報，2009，21(11)：3325-3341.

[3] 劉毅，車進，朱小波，等.空地機器人協(xié)同導航方法與實驗研究[J].電子技術應用，2018，44(10)：144-148.

[4] 尹新城，胡勇，牛會敏.未知環(huán)境中機器人避障路徑規(guī)劃研究[J].科學技術與工程，2016，16(33)：221-226.

[5] 唐焱，肖蓬勃，李發(fā)琴，等.避障最優(yōu)路徑系統(tǒng)研究[J].電子技術應用，2017，43(11)：128-135.

[6] ERGEZER H，LEBLEBICIOGLU K.Path planning for UAVs for maximum information collection[J].IEEE Transactions on Aerospace and Electronic Systems，2013，49(1)：502-520.

[7] PAMOSOAJI A K，HONG K S.A Path-planning algorithm using vector potential functions in triangular regions[J].IEEE Transactions on Systems，Man，and Cybernetics：Systems，2013，43(4)：832-842.

[8] WU N Q，ZHOU M C.Shortest routing of bidirectional automated guided vehicles avoiding deadlock and blocking[J].IEEE/ASME Transactions on Mechatronics，2007，12(2)：63-72.

[9] 田延飛，黃立文，李爽.激勵機制改進蟻群優(yōu)化算法用于全局路徑規(guī)劃[J].科學技術與工程，2017，17(20)：282-287.

[10] 徐曉晴，朱慶保.基于蛙跳算法的新型機器人路徑規(guī)劃算法[J].小型微型計算機系統(tǒng)，2014，35(7)：1631-1635.

[11] 朱慶保.復雜環(huán)境下的機器人路徑規(guī)劃螞蟻算法[J].自動化學報，2006，32(4)：586-593.

作者信息:

程  樂1，2，徐義晗1，卞曰瑭3

(1.淮安信息職業(yè)技術學院 計算機與通信工程學院，江蘇 淮安223003；

2.河海大學 計算機與信息學院，江蘇 南京210098；3.南京師范大學 商學院，江蘇 南京210023）