0 引言

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

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

1 λ-geometry行進(jìn)策略

2 自學(xué)習(xí)蟻群算法

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

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

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

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

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

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

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

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

2.2 自學(xué)習(xí)蟻群算法的主要策略

2.2.1 螞蟻個(gè)體行進(jìn)策略

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

2.2.2 貪婪搜索策略

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

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

2.2.3 強(qiáng)化搜索策略

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

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

3 算法的整體描述

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

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

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

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

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

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

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

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

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

    (9)判斷當(dāng)前可達(dá)域RFk中是否存在搜索目標(biāo)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 仿真實(shí)驗(yàn)

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

4.1 算法效果仿真實(shí)驗(yàn)

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

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

4.2 與先進(jìn)算法比較

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

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

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

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

    (2)SlACO采用的8-geometry策略,，螞蟻個(gè)體可以1、,、2,、的步長(zhǎng)行進(jìn)，而大部分RPP算法只可以用1,、的步長(zhǎng)行進(jìn),；

    (3)自學(xué)習(xí)搜索策略可以使螞蟻沿當(dāng)前最優(yōu)路徑尋跡搜索，對(duì)當(dāng)前最優(yōu)路徑進(jìn)一步優(yōu)化,，得到更優(yōu)的路徑,；

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

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

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

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

[4] 尹新城,，胡勇，牛會(huì)敏.未知環(huán)境中機(jī)器人避障路徑規(guī)劃研究[J].科學(xué)技術(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] 田延飛,，黃立文，李爽.激勵(lì)機(jī)制改進(jìn)蟻群優(yōu)化算法用于全局路徑規(guī)劃[J].科學(xué)技術(shù)與工程,，2017,，17(20)：282-287.

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

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

作者信息:

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

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

2.河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京210098,；3.南京師范大學(xué) 商學(xué)院,，江蘇 南京210023）