0 引言

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

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

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在基本柵格法的基礎(chǔ)上做出如下改進：

    (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表示當前單元格不是搜索目標單元格。通過以上設(shè)計，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ā)信息通過計算可達域中單元格與搜索目標之間的歐氏距離得到。由于每個螞蟻都對應(yīng)著不同的搜索目標，在不同的時刻螞蟻個體也具有不同的可達域，因此每個螞蟻所感知的啟發(fā)信息也不同，每個螞蟻會按有不同路線移動，增加了算法解的多樣性。Ant_k螞蟻在t時刻的啟發(fā)信息可以通過如下公式計算：

2.2.3 強化搜索策略

    強化學習的計算過程為：按信息素濃度由低到高依次對可達域中的可行單元格設(shè)置權(quán)重，其中信息素濃度最低的權(quán)重設(shè)置為：θ₁=10，第二低的權(quán)值為：θ₂=20，余下的值通過斐波那契數(shù)列計算得出。排序為n的單元格權(quán)重θ_n=θ_n-1+θ_n-2。根據(jù)單元格權(quán)重，得到各自權(quán)重空間的取值區(qū)間，其中，s₁=[1，θ₁]，s₂=[θ₁+1，θ₂]，排序為n的單元格的權(quán)重空間為s_n=[θ_n-1+1，θ_n]。按權(quán)重排序，最后一個單元格的權(quá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è)算法最大迭代次數(shù)為G_max，種群規(guī)模K，設(shè)置BestPath←∞用于記錄最優(yōu)路徑，設(shè)置變量k←1，l←1；

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實驗

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

4.1 算法效果仿真實驗

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

    觀察圖4可以發(fā)現(xiàn)：行進軌跡的最后一個單元格與目標單元格D之間距離較長，產(chǎn)生這一仿真結(jié)果的原因在于多目標搜索策略使機器人可以在較遠的距離發(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ù)設(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算法可以應(yīng)用于復(fù)雜二維空間的RPP問題，而且性能穩(wěn)定。

5 結(jié)論

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

參考文獻

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

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

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

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

[5] 唐焱，肖蓬勃，李發(fā)琴，等.避障最優(yōu)路徑系統(tǒng)研究[J].電子技術(shù)應(yīng)用，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].科學技術(shù)與工程，2017，17(20)：282-287.

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

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

作者信息:

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

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

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