<acronym id="owqss"><center id="owqss"></center></acronym>
<acronym id="owqss"></acronym>
<acronym id="owqss"><center id="owqss"></center></acronym>

基于對角障礙檢測和優化蟻群算法的路徑規劃

徐興毅 付麗霞 張勇 毛劍琳 郭寧

引用本文:
Citation:

基于對角障礙檢測和優化蟻群算法的路徑規劃

    作者簡介: 徐興毅(1995?),男,云南人,碩士生,研究方向為智能優化與控制. E-mail: 2550157276@qq.com;
    通訊作者: 付麗霞, 905771625@qq.com
  • 中圖分類號: TP312

Path planning based on diagonal obstacle detection and optimized ant colony algorithm

    Corresponding author: FU Li-xia, 905771625@qq.com ;
  • CLC number: TP312

  • 摘要: 針對大部分算法在多對角障礙環境中求解最短路徑時會穿過對角障礙形成實際不可行路徑的問題,提出一種結合對角障礙檢測的優化蟻群算法用于移動機器人路徑規劃. 首先采用對角障礙檢測標記出條件障礙,然后使用三角選擇法準確篩選出可通行和不可通行的條件障礙,最后提出自調整期望啟發因子和信息素更新策略. 實驗結果表明:該算法具有環境適應性強、收斂速度快和尋優能力強的特點,并能有效避免所規劃路徑穿過對角障礙.
  • 圖 1  地圖優化前后對比

    Figure 1.  Comparison before and after map optimization

    圖 2  條件柵格的篩選

    Figure 2.  Selection of condition grid

    圖 3  多對角障礙環境中不同算法結果對比

    Figure 3.  Comparison of algorithms under multi-diagonal obstacles

    圖 4  無對角障礙環境中算法對比

    Figure 4.  Comparison of algorithms without diagonal barrier

    表 1  對角障礙環境下的實驗結果對比

    Table 1.  Comparison?of?experimental?results?in?multi-diagonal?obstacle?environment

    算法平均收斂迭代次數規劃路徑長度平均收斂時間/s算法平均總耗時/s
    傳統蟻群 30 28.6274 2.965221 9.719562
    對角障礙檢測 20 30.9706 1.959106 9.576410
    對角加條件障礙 17 28.2563 1.680547 9.660051
    本文算法 11 28.2563 1.054999 6.563211
    下載: 導出CSV

    表 2  無對角障礙環境中實驗結果對比

    Table 2.  Comparison of experimental results in an environment without diagonal obstacles

    算法(柵格環境)收斂迭代
    次數(20×20)
    規劃路徑
    長度(20×20)
    收斂迭代
    次數(30×30)
    路徑長度(30×30)
    文獻[11]算法1928.043143.36
    本文算法1228.042543.36
    下載: 導出CSV
    鸿禾娱乐
  • [1] Patle B K ,Ganesh B L , PandeyA, et al. A review: On path planning strategies for navigation of mobile robot[J]. Defence Technology, 2019, 15(4): 582-606. DOI:  10.1016/j.dt.2019.04.011.
    [2] 霍鳳財, 遲金, 黃梓健, 等. 移動機器人路徑規劃算法綜述[J]. 吉林大學學報: 信息科學版, 2018, 36(6): 639-647. Huo F C, Chi J, Huang Z J, et al. Review of path planning for mobile robots[J]. Journal of Jilin University: Information Science Edition, 2018, 36(6): 639-647.
    [3] 史恩秀, 陳敏敏, 李俊, 等. 基于蟻群算法的移動機器人全局路徑規劃方法研究[J]. 農業機械學報, 2014, 45(6): 53-57. DOI:  10.6041/j.issn.1000-1298.2014.06.009. Shi N X, Chen M M, Li J, et. al. Research on method of global path-planning for mobile robot based on ant-colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(6): 53-57.
    [4] 王曉燕, 楊樂, 張宇, 等. 基于改進勢場蟻群算法的機器人路徑規劃[J]. 控制與決策, 2018, 33(10): 1 775-1 781. Wang X Y, Yang L, Zhang Y, et al. Robot path planning based on improved ant colony algorithm with potential field heuristic[J]. Control and Decision, 2018, 33(10): 1 775-1 781.
    [5] 王雷, 李明, 蔡勁草, 等. 改進遺傳算法在移動機器人路徑規劃中的應用研究[J]. 機械科學與技術, 2017, 36(5): 711-716. Wang L, Li M, Cai J C, et al. Research on mobile robot path planning by using improved genetic algorithm[J]. Mechanical Science and Technology for Aerospace Engineering, 2017, 36(5): 711-716.
    [6] 賈會群, 魏仲慧, 何昕, 等. 基于改進粒子群算法的路徑規劃[J]. 農業機械學報, 2018, 49(12): 371-377. DOI:  10.6041/j.issn.1000-1298.2018.12.044. Jia H Q, Wei Z H, He X, et al. Path planning based on improved particle swarm optimization algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2018, 49(12): 371-377.
    [7] Bharadwaj H , Vinodh K E. Comparative study of neural networks in path planning for catering robots[J]. Procedia Computer Science, 2018, 133: 417-423. DOI:  10.1016/j.procs.2018.07.051.
    [8] Dorigo M, Gambardella L M . Ant colonies for the travelling salesman problem[J]. BioSystems, 1997, 43(2): 73-81. DOI:  10.1016/S0303-2647(97)01708-5.
    [9] 朱艷, 游曉明, 劉升. 基于啟發式機制的改進蟻群算法[J]. 信息與控制, 2019, 48(3): 265-271. Zhu Y, You X M, Liu S. Improved ant colony algorithm based on Heuristic mechanism[J]. Information and Control, 2019, 48(3): 265-271.
    [10] 江明, 王飛, 葛愿, 等. 基于改進蟻群算法的移動機器人路徑規劃研究[J]. 儀器儀表學報, 2019, 40(2): 113-121. Wang M, Wang F, Ge Y, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Chinese Journal of Scientific Instrument, 2019, 40(2): 113-121.
    [11] 朱顥東, 孫振, 吳迪, 等. 基于改進蟻群算法的移動機器人路徑規劃[J]. 重慶郵電大學學報:自然科學版, 2016, 28(6): 849-855. Zhu H D, Sun Z, Wu D, et al. Path planning for mobile robot based on improved ant colony algorithm[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2016, 28(6): 849-855.
    [12] 劉新宇, 譚力銘, 楊春曦, 等. 未知環境下的蟻群-聚類自適應動態路徑規劃[J]. 計算機科學與探索, 2019, 13(5): 846-857. DOI:  10.3778/j.issn.1673-9418.1811015. Liu X Y, Tan L M, Yang C X, et al. Self-adjustable dynamic path planning of unknown environment based on ant colony-clustering algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(5): 846-857.
    [13] 劉梅. 基于柵格化視覺的機器人路徑優化研究[J]. 計算機與數字工程, 2018, 46(8): 1 548-1 552. DOI:  10.3969/j.issn.1672-9722.2018.08.014. Liu M. Research on robot path optimization based on rasterized vision[J]. Computer & Digital Engineering, 2018, 46(8): 1 548-1 552.
    [14] 程向紅, 祁藝. 基于柵格法的室內指示路徑規劃算法[J]. 中國慣性技術學報, 2018, 26(2): 236-240. Cheng X H, Qi Y. Indoor indicator path planning algorithm based on grid method[J]. Journal of Chinese Inertial Technology, 2018, 26(2): 236-240.
    [15] 朱慶保, 張玉蘭. 基于柵格法的機器人路徑規劃蟻群算法[J]. 機器人, 2005(2): 132-136. DOI:  10.3321/j.issn:1002-0446.2005.02.008. Zhu Q B, Zhang Y L. An ant colony algorithm based on grid method for mobile robot path planning[J]. Robot, 2005(2): 132-136.
  • [1] 黃冰倩杜慶治龍華 . 面向WSN的移動錨節點路徑規劃算法. 云南大學學報(自然科學版), 2018, 40(1): 29-35. doi: 10.7540/j.ynu.20170249
    [2] 王康碧蔣作和曉萍周衛紅 . 一種基于蟻群算法的電梯群節能調度算法. 云南大學學報(自然科學版), 2013, 35(S2): 39-. doi: 10.7540/j.ynu.2013b5
    [3] 李祖欣張榆鋒施心陵 . 基于論域自調整模糊規則切換的雙??刂破? 云南大學學報(自然科學版), 2003, 25(4): 313-316.
    [4] 岳昆李維華蘇茜劉惟一 . XML查詢中的頻繁路徑選擇. 云南大學學報(自然科學版), 2007, 29(3): 241-246.
    [5] 曾超李娜王維周曙白陳朝陽 . 群搜索算法與Powell法結合的醫學圖像配準. 云南大學學報(自然科學版), 2013, 35(5): 603-. doi: 10.7540/j.ynu.20120464
    [6] 陳暢陳麗李佳李云德 . 玻色-愛因斯坦凝聚體中的三角渦旋格子. 云南大學學報(自然科學版), 2004, 26(3): 238-240.
    [7] 杜凡杜小浪羅柏青赫尚麗 . 瀕危特有植物毛蕊三角車(Rinorea erianthera)在云南發現. 云南大學學報(自然科學版), 2009, 31(3): 300-301 .
    [8] 石國姣王公正黃帥鳳飛龍張保存 . 二維內質量結構三角形晶格聲子晶體的帶隙研究. 云南大學學報(自然科學版), 2019, 41(3): 545-550. doi: 10.7540/j.ynu.20180748
    [9] 楊子生 . 論土地生態規劃設計. 云南大學學報(自然科學版), 2002, 24(2): 114-124,129.
    [10] . Excel Solver的線性規劃模型. 云南大學學報(自然科學版), 2011, 33(S2): 239-242.
    [11] 鄒力鵾王麗珍何婧 . 基于圖的空間例外檢測算法研究. 云南大學學報(自然科學版), 2003, 25(5): 398-400.
    [12] 何樹紅董志偉李如兵 . 常利率影響下調整下限風險模型的破產概率. 云南大學學報(自然科學版), 2006, 28(2): 103-107.
    [13] 胡宗達吳兆錄閆海忠周元清張志明 . 滇西南燈臺樹種植適宜區規劃研究. 云南大學學報(自然科學版), 2005, 27(1): 86-92.
    [14] 周云松裴以建余江池宗琳 . 雙足行走機器人步態軌跡規劃. 云南大學學報(自然科學版), 2006, 28(1): 20-26.
    [15] 劉國志 . 基于信賴域技術的局部收縮的微粒群算法. 云南大學學報(自然科學版), 2008, 30(1): 21-26.
    [16] 趙柳顏光前吳俊羅華友孫亮舒若 . 基于ABUS冠狀面圖像的乳頭位置自動檢測算法. 云南大學學報(自然科學版), 2019, 41(3): 464-469. doi: 10.7540/j.ynu.20180318
    [17] 楊仁青柏正堯尹立國高皜張濤 . 基于分數傅里葉變換的數字圖像復制-粘貼篡改檢測算法. 云南大學學報(自然科學版), 2016, 38(1): 18-22. doi: 10.7540/j.ynu.20150058
    [18] 楊雨薇張亞萍 . 一種改進的SIFT圖像檢測與特征匹配算法. 云南大學學報(自然科學版), 2017, 39(3): 376-384. doi: 10.7540/j.ynu.20160731
    [19] 代志濤蘇寒松劉高華張倩芳 . 基于改進非局部均值濾波算法的顯著性區域檢測*. 云南大學學報(自然科學版), 2018, 40(3): 440-450. doi: 10.7540/j.ynu.20170351
    [20] 獨智序王曉峰 . 基于穩健關鍵點的圖像Copy-Move篡改檢測算法. 云南大學學報(自然科學版), 2019, 41(1): 61-67. doi: 10.7540/j.ynu.20170629
  • 加載中
圖(4)表(2)
計量
  • 文章訪問數:  738
  • HTML全文瀏覽量:  718
  • PDF下載量:  12
  • 被引次數: 0
出版歷程
  • 收稿日期:  2019-10-21
  • 錄用日期:  2020-02-19
  • 網絡出版日期:  2020-04-23
  • 刊出日期:  2020-07-01

基于對角障礙檢測和優化蟻群算法的路徑規劃

    作者簡介:徐興毅(1995?),男,云南人,碩士生,研究方向為智能優化與控制. E-mail: 2550157276@qq.com
    通訊作者: 付麗霞, 905771625@qq.com
  • 昆明理工大學 信息工程與自動化學院,云南 昆明 650500

摘要: 針對大部分算法在多對角障礙環境中求解最短路徑時會穿過對角障礙形成實際不可行路徑的問題,提出一種結合對角障礙檢測的優化蟻群算法用于移動機器人路徑規劃. 首先采用對角障礙檢測標記出條件障礙,然后使用三角選擇法準確篩選出可通行和不可通行的條件障礙,最后提出自調整期望啟發因子和信息素更新策略. 實驗結果表明:該算法具有環境適應性強、收斂速度快和尋優能力強的特點,并能有效避免所規劃路徑穿過對角障礙.

English Abstract

  • 在移動機器人的研究領域當中,路徑規劃[1]一直是人們研究的熱點問題,即移動機器人根據已知的環境信息或者自身攜帶的傳感器感知外界環境,在復雜的環境中尋找一條無碰撞的路線,并完成指定任務. 隨著國內外學者的深入研究,機器人路徑規劃不僅僅局限于準確找到一條無碰撞的路線,同時還要求根據多個綜合指標來選出最優路線,比如充分考慮到能耗最低、路線最短和收斂速度快等問題[2]. 因此,大量的智能算法得到了很好的運用,如:蟻群算法[3-4]、遺傳算法[5]、粒子群算法[6]和神經網絡[7]等已運用于機器人的路徑規劃當中.

    蟻群算法最初是由意大利的學者Dorigo[8]等提出的一種模擬螞蟻覓食行為,解決旅行商問題的算法. 由于其具有并發性、自組織性、強魯棒性等特點,在路徑規劃中具有很大的優勢,從而被廣泛地用于機器人路徑規劃,但蟻群算法存在搜索效率較低、容易陷入局部最優解等缺點,一些學者針對這些問題進行了改進. 文獻[9]引入了一種啟發式機制的思想,在蟻群算法的基礎上,通過候選節點到目標點的距離動態調整啟發函數,提高收斂速度;文獻[10]通過自適應調節信息素揮發因子和優化避障的策略,有效地解決了傳統蟻群算法容易陷入局部最優解及收斂速度較慢等問題;文獻[11]改進了節點間的狀態轉移規則,提出自適應調整啟發函數,使不同復雜環境下的路徑規劃都具有良好的尋優能力;文獻[12]通過生成虛擬障礙物,避免規劃的路徑穿過對角障礙,同時加入聚類算法,自適應地調整搜索半徑,提升了蟻群算法的環境適應能力.

    在上述對蟻群算法改進的研究中,除文獻[12]外,都沒有考慮到實際環境中存在對角障礙的問題,導致這些改進蟻群算法在出現對角障礙的環境中規劃出的路線會穿過對角障礙,使規劃出的路線實際不可行. 文獻[12]雖然采用生成虛擬障礙的方法避免了穿過對角障礙,但其中某些實際可通過的區域被作為虛擬障礙而不可通行,無形中增加了障礙物區域,使得規劃出的路徑并不是最短. 為此,本文提出了如下的改進:①基于文獻[12]對角障礙檢測的基礎上,將地圖中對角障礙附近的自由柵格標記為條件障礙,使得柵格地圖得到進一步的簡化,減少算法的計算時間;②采用三角選擇法篩選出可穿越和不可穿越的條件障礙,提高地圖的準確性,既保證規劃的路徑不穿過對角障礙物,又能縮短路徑長度;③對蟻群算法中的期望啟發因子β和信息素更新采用參數自調整策略,克服蟻群算法自身缺陷,獲得最短路徑,并提升算法的收斂速度.

    • 柵格法是目前路徑規劃中最常用的仿真環境建模方法[13],它能夠將實際場景按照一定比例量化成若干個面積相等的柵格. 其中,不規則的障礙物通過腐蝕或膨脹處理,按照其在整個實際場景中的大小和位置,等比例劃分為多個柵格,并標記為障礙柵格. 其余無障礙的地方所劃分的柵格標記為自由柵格. 可用一個M×N的數組矩陣來表示柵格地圖中障礙物的分布情況[14],如式(1)所示:

      $ G\left( {M,N} \right) = \left\{ {\begin{array}{*{20}{c}} 1\!\!\!\!\!\!&\!{,{\text{障礙柵格;}}}\\ 0\!\!\!\!\!\!&\!{,{\text{自由柵格,}}} \end{array}} \right. $

      式中,$ G\left( {M,N} \right) = 1$ 時表示柵格地圖上MN列存在障礙物,不可通行;$ G\left( {M,N} \right) = 0$ 時表示柵格地圖上MN列沒有障礙物,可自由通行.

      為了方便在計算中能夠迅速找到對應的柵格,對每一個柵格進行編號,建立一個直角坐標系,以x為橫軸,y為縱軸,每個柵格對應的編號為i,每個柵格的中心點坐標為($ {x_i},{y_i}$),柵格編號與中心點坐標的對應關系為:

      $ \left\{ {\begin{array}{*{20}{l}} {{x_i} = a\left( {{\rm{mod}}\left( {i,M_{\max}} \right) - 0.5} \right),}\\ {{y_i} = a\left( {M_{\max} + 0.5 - {\rm{ceil}}\left( {\dfrac{i}{{M_{\max}}}} \right)} \right),} \end{array}} \right. $

      式中,a表示每個柵格的邊長,Mmax表示柵格圖中橫縱軸柵格數的最大值,mod是求余符號,ceil是舍余求整符號.

    • 將實際環境轉化為柵格地圖,通常會出現大量的對角障礙,所謂對角障礙就是如圖1(a)所示形成對角的障礙柵格B1B2,為機器人的安全考慮,應避免機器人穿越B1B2相交的對角點,在本文中敘述為避免機器人穿過對角障礙B1B2. 由此,本文針對柵格地圖中出現多個對角障礙的問題提出了基于對角障礙檢測的地圖優化,目的是找到地圖中的對角障礙,并將其附近的自由柵格標記為條件柵格,從而避免機器人穿越對角障礙,對角障礙檢測的實現步驟如下,圖1所示為柵格地圖優化前后的對比.

      圖  1  地圖優化前后對比

      Figure 1.  Comparison before and after map optimization

      步驟 1 通過鄰接矩陣尋找障礙柵格,并判斷柵格編號ij之間的關系,找出對角障礙. 鄰接矩陣表征每個柵格與其8個領域柵格的關系,通過創建一個i×j的二維方陣D,ij為柵格的編號,$ D\left( {i,j} \right)$ 代表柵格i與柵格j之間的關系,其滿足如下的關系:

      $ D\left({i,j} \right) = \left\{ {\begin{array}{*{20}{l}} 1\!\!\!&\!\!\!\!{,{\text{柵格}}{{i}}{\text{、}}\!\!\!\!{{j}}{\text{為障礙柵格且相鄰}}};\\ {0}\!\!\!&\!\!\!\!{,{\text{其它}}}. \end{array}} \right. $

      式中,$ D\left( {i,j} \right) = 1$ 表示柵格ij為相鄰的障礙柵格.

      根據對角障礙的特征,搜索矩陣D中值為1的元素所對應的ij的數值,記編號i的障礙柵格編號為B1,編號j的障礙柵格編號為B2,則滿足式(4)的B1B2互為對角障礙.

      $ {B_2} - {B_1} = M \pm 1,\;\;\;\;\;\; {{B_1} < {B_2}}. $

      式中,M為柵格圖中橫向柵格最大值.

      步驟 2 在對角障礙附近標記條件障礙. 當判斷柵格B1B2互為對角障礙后,將滿足式(5)的自由柵格Cg1、Cg2標記為條件障礙(也稱為條件柵格).

      $ \left\{ {\begin{array}{*{20}{c}} {C{{\rm{g}}_1} = {B_1} + M},C{{\rm{g}}_1}{\text{為自由柵格}};\\ {C{{\rm{g}}_2} = {B_2} - M},C{\rm{g}}_2{\text{為自由柵格}}. \end{array}} \right. $

    • 通過對角障礙檢測標記出條件障礙,文獻[12]中將標記出的條件柵格全部虛擬為障礙柵格,雖然避免了規劃出的路徑穿越對角障礙,但是會使得部分實際可通行的條件柵格變為障礙,從而無形中增加了所規劃出的路徑長度. 例如:圖2中當機器人從節點S1行進至節點S3時,如果條件柵格Cg1可穿越,則機器人行進的最短路徑為S1Cg1S3,但用文獻[12]的方法得到機器人行進的路徑將是S1S4S3,顯然不是最短路徑. 為解決這一問題,本文對條件障礙采用三角選擇法進行篩選,準確篩選出可通行和不可通行的條件柵格. 具體步驟如下:

      圖  2  條件柵格的篩選

      Figure 2.  Selection of condition grid

      步驟 1 計算當前機器人所處位置到八鄰域節點的距離,并用鄰接矩陣G記錄.

      創建一個M×M的鄰接矩陣 $ {{G}}\left( {{S_1},{S_2}} \right)$,設機器人所處節點S1的坐標為 $ \left( {{x_1},{y_1}} \right)$,且柵格S1不為障礙柵格,下一鄰接節點S2坐標為 $ \left( {{x_2},{y_2}} \right)$,則將S1S2的距離 $ G\left( {{S_1},{S_2}} \right)$ 按式(6)進行計算.

      $\begin{split} &G\left( {{S_1},{S_2}} \right) =\\ &\left\{ {\begin{array}{*{20}{c}} {\sqrt {{{\left| {{x_1} - {x_2}} \right|}^2} + {{\left| {{y_1} - {y_2}} \right|}^2}} } {,\;\;{S_2}{\text{為自由柵格}}};\\ {0.9} {,\;\;{S_2}{\text{為條件柵格}}};\\ 0 {,\;\;{S_2}{\text{為障礙柵格.}}} \end{array}} \right.\end{split} $

      表示式(6)中將機器人所處位置到條件障礙的距離范圍設置為 $ \left( {0,1} \right)$,目的是使條件障礙能夠更大概率地被選中,通過多次實驗可得最優值為0.9.

      步驟 2 對條件柵格采用三角選擇法進行篩選,將滿足穿越條件的條件柵格加入到待選節點,其余不可穿越的條件柵格加入禁忌表.

      設機器人當前位于節點S1,選擇與S1鄰接的條件柵格Cg,通過式(7)計算得到S3,如S3為自由柵格,則根據式(8)進行條件障礙篩選分類,將不可穿越的條件柵格放入禁忌表,其它可穿越的條件障礙放入待選節點表. 如此,可使地圖得到進一步優化.

      $ {S_3} = 2C{\rm{g}} - {S_1}, $

      $ \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} G\left( {{\rm{Cg}},{S_1}} \right) = 0.9{\text{或}}G\left( {{\rm{Cg}},{S_3}} \right) = 0.9{\text{或}}; \\ G\left( {{\rm{Cg}},{S_3}} \right) = 0,{\rm{Cg}}{\text{不可穿越表}}; \\ \end{array}\; \\ {{{\text{否則}},\;{\rm{Cg}}{\text{可穿越表}}}.} \end{array}} \right. $

      圖2所示,機器人從S1移動到S3時,經步驟1的對角障礙檢測后標記出的條件柵格Cg1Cg2,再經步驟2篩選出實際可穿越的Cg1作為待選節點,其規劃路徑為S1Cg1S3,則可得到S1S3的最短路徑,既能避免機器人穿越對角障礙,又能獲得最短路徑.

    • 蟻群算法模擬了自然界中螞蟻外出覓食的過程,每只螞蟻在其通過的路徑上會釋放出信息素,使得一定范圍內的螞蟻能夠察覺并影響他們以后的路徑選擇. 當路徑上的螞蟻越來越多時,該路徑上的信息素強度將得到增強,螞蟻選擇該路徑的概率增加[15],從而促使整個蟻群最終找到一條最短的路徑.

    • 蟻群算法是一種正反饋機制,其實質是調整算法轉移概率公式中信息素和啟發信息在公式中的占比,使得最優解能夠得到更大概率地被選擇. 狀態轉移概率決定著被選為下一節點的可能性大小,螞蟻由當前節點i選擇下一節點j的轉移概率為:

      $ P_{ij}^k\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {\dfrac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^\beta }}}{{ \displaystyle\sum \nolimits_{j \in {a_k}} {{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^\beta }}}},j \in {a_k};\\ {0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\text{其它}}}. \end{array}} \right. $

      $ {\eta _{ij}}\left( t \right) = 1/{d_{je}}, $

      式中ak表示螞蟻k可以到達的節點,α為信息素啟發因子,β為期望啟發因子,$ {\tau _{ij}}\left( t \right)$t時刻螞蟻從ij的信息素濃度,$ {\eta _{ij}}\left( t \right)$t時刻螞蟻從ij的啟發信息,dje表示節點j到終點e的歐式距離.

      信息素更新策略影響各節點信息素的揮發和積累,引導螞蟻群能找到一條最優的路徑達到目標點,信息素更新公式為:

      $ {\tau _{ij}} = \left( {1 - \rho } \right){\tau _{ij}}\left( t \right) + {\rm{\Delta }}{\tau _{ij}}\left( {t,t + 1} \right), $

      $ {\rm{\Delta }}{\tau _{ij}}\left( {t,t + 1} \right) = \left\{ {{\rm{}}\begin{array}{*{20}{l}} {\dfrac{Q}{{{L_k}}},\;\;\;{\text{螞蟻本次迭代經過}}\left( {i,j} \right)};\\ {0,\;\;\;\;\;\;{\text{其它}}}. \end{array}} \right. $

      式中ρ為信息素揮發因子,$ \varDelta {\tau _{ij}}\left( {t,t + 1} \right)$ 表示本次螞蟻在路徑上的信息素增量,Q為信息素強度,Lk表示第k只螞蟻所走的路徑總長度.

    • 蟻群算法在初期的搜索中,信息素濃度較低,啟發信息對下一節點的選擇占主導作用;而后期隨著迭代次數的增加,信息素濃度逐漸增強,啟發信息的影響應該得到減弱,以提高算法收斂速度. 由此,本文提出了一種自調整策略動態更新期望啟發因子,其基本思想是引入一個可自調整的期望啟發因子,隨著螞蟻迭代次數的增加來減弱啟發信息對節點選擇的影響,將傳統蟻群算法的式(9)改進為式(13)和式(14):

      $ P_{ij}^k\left( t \right) = \left\{ {\begin{array}{*{20}{l}} {\dfrac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^{\left[ {\beta '} \right]}}}}{{\displaystyle \sum \nolimits_{s \in {a_k}} {{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\eta _{ij}}\left( t \right)} \right]}^{\left[ {\beta '} \right]}}}}\;\;\;,j \in {a_k}};\\ {0,{\text{其它}}}. \end{array}} \right. $

      $ \beta ' = \beta K - k + 1/K, $

      式中k為當前螞蟻迭代次數,K為螞蟻總的迭代次數.

      由(14)式可知,當前螞蟻迭代次數k從0逐漸增加至總的迭代次數K,隨著k的增加,期望啟發因子 $ \beta '$ 逐漸變小,滿足了對期望啟發因子前期強、后期弱的自調整策略,使得啟發信息逐漸削弱,間接促使信息素的作用得到增強,加快了蟻群算法的收斂速度.

    • 信息素更新的作用是為了減弱陷入死鎖螞蟻所通過路徑上的信息素濃度,同時增強每次迭代后最優螞蟻路徑上的信息素濃度. 傳統蟻群算法使用固定的信息素增量進行更新,雖然能夠使得一些路徑上的信息素迅速積累,得到較快的收斂速度,但導致算法搜索范圍小,容易陷入到局部最優. 另外,使用2.2節的啟發因子自調整策略,隨迭代次數的增加會間接促使信息素作用增強,如果仍沿用傳統蟻群算法的信息素更新策略,將導致信息素的作用過強. 針對這一問題,本文提出信息素自調整策略,使信息素隨迭代次數緩慢增加,將傳統蟻群算法的式(11)改進為式(15).

      $ {\tau _{ij}}\left( {t + 1} \right) = \left( {1 - \rho } \right){\tau _{ij}}\left( t \right) + \frac{k}{K}\varDelta {\tau _{ij}}\left( {t,t + 1} \right), $

      $ \varDelta {\tau _{ij}}\left( {t,t + 1} \right) = \left\{ {\begin{array}{*{20}{l}} {\dfrac{Q}{{{L_k}}},\;\;\;{\text{螞蟻本次迭代經過}}\left( {i,j} \right)};\\ {0,\;\;\;\;\;\;{\text{其它}}}. \end{array}} \right. $

      式中k為當前螞蟻迭代次數,K為螞蟻總的迭代次數.

      改進后的蟻群算法前期 $ \dfrac{k}{K}$ 比較小,信息素增量小,保持了路徑選擇的多樣性,使搜索范圍擴大,不容易陷入局部最優;在算法后期,參數 $ \dfrac{k}{K}$ 增大,信息素增量大,最優路徑的信息素濃度增大,且1.3節中期望啟發因子β的減小進一步促使信息素對節點的選擇占主導地位,使得算法的收斂速度得到提高.

    •   步驟 1 利用對角障礙檢測將地圖中對角障礙附近的自由柵格標記為條件柵格;

      步驟 2 初始化蟻群算法中的各個參數,即信息素啟發因子α、期望啟發因子β、信息素揮發系數ρ、螞蟻迭代次數k和螞蟻數M;

      步驟 3 對機器人當前所處柵格的八鄰域進行搜索,記錄下自由柵格和條件柵格的編號并存入矩陣,作為下一步可選節點,將障礙柵格加入到禁忌表中;

      步驟 4 對下一步可選節點中的條件柵格采用本文1.3節的三角選擇法進行篩選,根據式(8)篩選出可穿越的條件柵格并保留在待選節點表中,將不可穿越的條件柵格加入到禁忌表中;

      步驟 5 將待選節點逐一帶入公式(13)中計算選擇概率所占的比重,通過輪盤賭決定下一步可行進的柵格,并判斷螞蟻數量是否達到最大值,如達到則繼續下一步,否返回步驟3繼續搜索;

      步驟 6 所有螞蟻完成一次搜索以后,找出本次迭代中的最優路徑,根據公式(15)進行信息素更新,更新完成后將螞蟻數清零,迭代次數加1;

      步驟 7 判斷迭代次數是否達到最高次數Kmax,達到則輸出螞蟻的最優路徑長度并繪制收斂曲線,否則跳轉至步驟3繼續進行搜索.

    • 在Matlab R2019a的軟件中進行仿真實驗,計算機為Windows10 64 bit的操作系統,CPU為Core i7-9750H,計算機內存為8.00 GB. 為了驗證算法的環境適應性和優越性,在多對角障礙環境和無對角障礙環境中分別進行仿真實驗.

    • 為了驗證多對角障礙的環境中,本文所提出的算法能夠有效地避免穿過對角障礙,同時得到最優路徑. 仿真環境設置為存在多對角障礙的20×20柵格環境,進行4種不同策略下的規劃路徑結果比較,同時將收斂曲線、算法運行時間進行對比. 設置初始參數α值為1、β值為7、ρ值為0.5、螞蟻數目m為50,最大迭代次數Kmax為100,共進行10次實驗,取10次實驗結果的平均值進行分析.

      圖3(a)可以看出,傳統蟻群算法在多對角障礙的環境中,雖然規劃出了一條抵達目標點的路徑,但是所規劃的路徑穿過了對角障礙,無法在實際場景中運用;圖3(b)中采用加入對角障礙檢測的傳統蟻群算法,通過標記條件障礙,并將條件障礙全部虛擬為障礙柵格,標記后障礙柵格在地圖中占比37.25%,比未標記前增加了15%,整個地圖環境變得簡潔,減少了計算量,同時規劃出的路徑能成功避免穿過地圖中所有的對角障礙. 但可以看出在地圖中一些拐角的地方,部分可通過的條件柵格被虛擬為障礙柵格而無法穿越,導致所規劃的路徑并不是最短;圖3(c)中在圖3(b)中算法的基礎上加入了三角優化算法實現條件障礙的篩選,篩選出可穿越的條件障礙并將其加入待選節點表,比單純采用對角障礙檢測增加了搜索的范圍,更有利于得到最優路徑. 如此,既避免了穿過對角障礙,又克服了圖3(b)中存在的缺陷,尋得了最優路徑;圖3(a)、(b)、(c)均采用傳統蟻群算法,為解決傳統蟻群算法存在的缺陷,圖3(d)中對圖3(c)中的傳統蟻群算法進行了改進,加入參數自調整策略,動態調整期望啟發因子和信息素更新機制,形成本文最終的算法,規劃出的路徑避免穿過對角障礙,且能尋得最優路徑.圖3(e)繪制了4種不同算法的收斂曲線,從圖中可以清晰地看出本文算法在尋到最優路徑時的迭代次數明顯少于其它算法,并且收斂曲線較為平緩,表明本文算法收斂速度更快,且能穩定地收斂于最優解.

      圖  3  多對角障礙環境中不同算法結果對比

      Figure 3.  Comparison of algorithms under multi-diagonal obstacles

      此外,從表1中的實驗結果數據可以看出,本文算法中相比其它3種算法,在準確躲避對角障礙得到最優路徑的同時,平均收斂迭代次數和收斂時間均為最少,說明了對條件障礙的篩選使地圖得到簡化,算法計算量減少,提高了算法的收斂速度,同時算法總耗時(即:算法達到最大迭代次數Kmax為100時的耗時)縮短.

      算法平均收斂迭代次數規劃路徑長度平均收斂時間/s算法平均總耗時/s
      傳統蟻群 30 28.6274 2.965221 9.719562
      對角障礙檢測 20 30.9706 1.959106 9.576410
      對角加條件障礙 17 28.2563 1.680547 9.660051
      本文算法 11 28.2563 1.054999 6.563211

      表 1  對角障礙環境下的實驗結果對比

      Table 1.  Comparison?of?experimental?results?in?multi-diagonal?obstacle?environment

      通過上面的實驗數據分析,本文的改進算法用于多對角障礙環境中機器人路徑規劃,能夠準確避免穿過對角障礙的同時尋得最優路徑,且算法的效率有所提升.

    • 為不失一般性,證明本文的改進算法在無對角障礙的環境中也具有較好的性能,在與文獻[11]相同的柵格地圖環境中,將本文算法的仿真實驗結果與文獻[11]的仿真實驗結果進行對比分析. 設置初始參數α值為1.3、β值為8、ρ值為0.4、螞蟻數目m為50,最大迭代次數Kmax為100,在20×20和30×30的柵格地圖中分別進行仿真實驗.

      通過對比圖4(a)4(b)可以看出在無對角障礙的環境中,兩種算法在20×20和30×30的地圖中都能夠尋到一條最優路徑,但結合表2的實驗結果對比可知,本文算法加入參數自調整策略后,在相同的環境下收斂迭代次數少于文獻[11],收斂速度更快. 如此,驗證了本文所采用的算法在無對角障礙的環境下同樣能獲得最優路徑,并具有較好的收斂性.

      算法(柵格環境)收斂迭代
      次數(20×20)
      規劃路徑
      長度(20×20)
      收斂迭代
      次數(30×30)
      路徑長度(30×30)
      文獻[11]算法1928.043143.36
      本文算法1228.042543.36

      表 2  無對角障礙環境中實驗結果對比

      Table 2.  Comparison of experimental results in an environment without diagonal obstacles

      圖  4  無對角障礙環境中算法對比

      Figure 4.  Comparison of algorithms without diagonal barrier

    • (1)大多數論文并沒有在仿真環境中考慮到對角障礙的存在,而實際運用場景中往往會存在大量的對角障礙. 本文基于文獻[12]對角障礙檢測的基礎上,提出通過三角選擇法實現條件障礙的篩選,準確區分可穿越和不可穿越的條件障礙. 仿真結果表明使用加入了對角障礙檢測和條件障礙篩選的蟻群算法能夠簡化地圖,并提升地圖的準確性,縮短算法運行時間,準確避免穿過對角障礙,并得到最優路徑.

      (2)針對傳統蟻群算法存在收斂速度慢、搜索范圍小而易陷入局部最優等問題,本文提出了一種參數自調整策略,期望啟發因子和信息素更新能夠隨迭代次數的增加得以動態調整,使算法前期擴大搜索范圍,后期快速收斂,從而保證在全局搜索中算法的全局性和收斂性都能夠得以兼顧,規劃出的路線較快地收斂到全局最優路徑.

      (3)在多對角障礙和無對角障礙的仿真環境中進行實驗和算法對比,實驗結果表明,本文算法具有環境適應性強、收斂速度快和尋優能力強的特點,有一定的優越性.

      論文中主要針對環境信息已知的靜態路徑規劃,沒有考慮動態環境下算法的適應性,這也是文章的不足之處和后續研究的重點.

參考文獻 (15)

目錄

    /

    返回文章
    返回