







摘要:針對粒子群優化算法在全局路徑規劃時存在容易陷入局部最優的問題,依據粒子群算法和鴿群算法的相關理論,分析了導致粒子群算法陷入局部最優的影響因素,根據AGV小車的最小轉向半徑確定二維柵格地圖中單元格的大小,改進粒子群算法并結合鴿群算法的快速收斂能力進行全局路徑規劃,給出了一種融合改進粒子群與鴿群算法的二階段混合優化算法。對比傳統的粒子群算法,新方法能有效防止算法陷入局部最優,規劃的全局最優路徑長度比傳統的粒子群算法縮短了約3.8%并減少了路徑規劃時長。
關鍵詞:路徑規劃;改進粒子群算法;鴿群算法;二維柵格地圖;AGV小車
DOI:10.15938/j.jhust.2022.03.011
中圖分類號: TP242文獻標志碼: A文章編號: 1007-2683(2022)03-0082-08
A Path Planning Method for AGV Based
on Improved PSO-PIO Algorithm
QIN Chang-li1,ZHANG Hua-qiang1,LIU Lin1,CHEN Yu2,SU Qing-hua3
(1.School of Mechanical Engineering, Shandong University of Technology, Zibo 255049, China;
2.Military Representative Office of Rocket Army in 211 Factory, Beijing 100076, China;
3.School of Information Engineering, Beijing Wuzi University, Beijing 101149, China)
Abstract:In order to solve the problem of particle swarm optimization algorithm easily falling into local optimum in global path planning, according to the related theories of particle swarm optimization algorithm and pigeon-inspired optimization algorithm, the influencing factors that lead to particle swarm optimization algorithm falling into local optimum are analyzed, and the size of raster in two-dimensional raster map is determined according to the minimum turning radius of automatic guided vehicle. The particle swarm optimization is improved and combined with the fast convergence ability of pigeon-inspired optimization algorithm, and a two-stage hybrid optimization algorithm based on improved particle swarm optimization and pigeon-inspired optimization algorithm is proposed for global path planning. Compared with the traditional particle swarm optimization algorithm, the new method can effectively avoid falling into local optimum. The global optimal path length is shortened by about 3.8% and the path planning time is reduced.
Keywords:path planning; improved particle swarm optimization; pigeon-inspired optimization; two-dimensional raster map; automatic guided vehicle
0引言
隨著智能無人技術的發展,移動機器人在工業、農業和物流運輸等領域發揮著越來越重要的作用。但當機器人周圍環境中出現障礙物時,可能會阻礙其正常工作。因此如何建立一條在機器人工作平臺上的避障路徑,幫助移動機器人實現自主避障是自動導航行駛過程中避免碰撞的關鍵,一直以來被國內外諸多專家學者所研究。
自主避障的核心是路徑規劃,其主要任務是通過傳感器獲取周圍的環境信息,按照一定的算法實時更新路徑,從而繞開障礙物到達目標點。目前已有許多相對成熟的路徑規劃算法,其中可視圖法是一種障礙空間法,算法靈活并且易實現,但對環境的適應性及實時性較差。文[1]提出了一種基于多尺度可視圖的長航路徑規劃方法,降低了模型的復雜度,縮短了搜索時間。人工勢場法假設機器人在一種虛擬力場中運動,但存在因環境對機器人的虛擬合力為零而導致機器人陷入局部最優,無法繼續行駛的問題。文[2]提出一種融合模擬電勢場的人工勢場法,解決了人工勢場法在面對連續型障礙時規劃路徑存在不可行的問題。遺傳算法是根據大自然中生物體進化規律而設計提出的,由于其固定的結構和大量的離線訓練,導致其運算速度慢,進化規則多。文[3]在傳統遺傳算法中引入了4種新的基于領域知識的算子用于多目標的路徑規劃問題,增強了傳統遺傳算法的性能。粒子群算法是通過模擬鳥群覓食行為而發展起來的一種基于群體協作的隨機搜索算法,但易陷入局部最優從而導致路徑精度降低。文[4]提出一種基于神經網絡的改進粒子群優化算法,在提高算法收斂速度的同時保證路徑精度。文[5]提出一種具有時變機制慣性權重因子的粒子群優化算法來進行最優路徑規劃,但在路徑規劃時均未將機器人的運動學約束考慮在內。文[6]在傳統粒子群優化算法中引入自適應的分數階速度來解決局部陷落和早熟收斂問題,但算法的執行時間仍有待提高。文[7]提出了一種基于人工神經網絡的Q-learning 算法,以此來解決AGV在靜態未知環境中的路徑規劃問題。AGV 能夠在未知環境下成功找到一條無碰撞路徑,由于在實際智能倉儲環境中往往需要多臺 AGV 共同運作,因此,該方法仍存在一定的局限性。文[8]結合模擬退火算法和蟻群算法對立體貨架的貨物揀選路徑進行規劃。該算法有效解決了模擬退火算法無法有效利用系統中的反饋信息、精確解以及效率低的問題,同時解決了蟻群算法求解速度慢的問題。但所研究的只是倉儲活動中單一的揀貨路徑問題,僅對有關要素進行了適當的簡化處理。
針對上述問題,本文對AGV(automatic guided vehicle)避障路徑規劃問題展開研究。建立AGV小車的運動學模型,根據最小轉向半徑來確定環境柵格地圖中單元格的大小。將粒子群算法和鴿群算法相融合實現AGV小車運行環境中的全局路徑規劃,該方法將2種算法按照優點規避缺點的原則相結合,能快速有效地規劃出一條安全合理,可以準確執行的避障路徑。
1AGV小車運動學建模分析
由于AGV小車轉彎是一個低速行駛的過程,將其簡化為二輪模型進行運動學分析[9-12],即假設小車在平滑路面行駛,輪胎為剛性輪且與地面只產生縱向壓力,不產生側向滑動。二輪模型示意圖如圖1所示。圖1中,A(xs,ys)表示前輪軸心坐標,B(xd,yd)表示后輪軸心坐標,α為小車的航向角,δs為前輪轉向角,α和δs逆時針為正、順時針為負,vs和vd分別表示前后輪的速度,R為轉向半徑,L為小車的軸距。
由二輪模型可得前輪轉向角為
δs=arctan(L/R)(1)
前文已假設AGV小車轉彎過程中車速極慢,因此將后輪的軸向速度近似為0。根據前后輪幾何約束可得AGV小車運動學模型為
d=vd·cosα
d=vd·sinα
=vd·tanδs/L(2)
根據AGV小車的最小轉向半徑與作業寬幅之間的關系來選擇轉彎形式,設定柵格地圖中單元格的寬度大于等于AGV小車的最小轉向半徑以滿足運動學約束,因此選擇半圓弧轉彎形式,如圖2所示。
其中:W為轉向直徑,是單元格寬度的2倍。
2周邊環境建模
2.1柵格地圖模型
在AGV小車路徑規劃中,需要對運行空間周邊環境進行分析,采用柵格地圖法[13]對周邊環境進行建模。假設AGV小車在二維平面中工作,任何運行空間上的點都可以表示為(xn,yn)。在二維空間中,障礙物及讓小車無法通過的區域都是實時獲取的,且可知這些區域的具體位置。AGV小車運行環境柵格地圖,如圖3所示。
其中,每個正方形的方塊都是一個單元柵格,柵格大小設定的不同對算法性能影響較大。由于AGV小車有一定的最小轉向半徑,對可通行寬度有一定要求,因此根據小車的運動學約束來確定單元柵格的大小。黑色表示這個單元柵格上有障礙物,小車無法通行,將其屬性定義為1,對不滿一個柵格的障礙物進行“膨脹處理”,近似成一個柵格;反之表示其為自由柵格,小車可以自動通行,將其屬性定義為0。
2.2路徑評價模型
按照圖3所示順序將地圖中每一個柵格都進行編號。將模型中每一個柵格所包含的信息定義為數組Mn={xn,yn,tn},其中n=1,2,…,400為柵格編號,{xn,yn}為柵格的坐標信息,{tn}為柵格的屬性信息。出發點D到目標點T的最優路徑表示為path=(D,…,Mn,…,T),有效路徑的判定標準為Mn在柵格地圖的十字相鄰位置且不包含障礙物。
對于所有可行解,主要將路徑長度作為指標建立路徑評價模型來評估路徑好壞[14],其計算公式如下:
L(path)=∑N-1i=1‖Pn+1-Pn‖(3)
式中:Pn為柵格地圖上路徑點的坐標{xn,yn};‖Pn+1-Pn‖為Pn+1與其上一路徑點Pn之間的歐氏距離;N為路徑點總數。
3PSO-PIO路徑規劃算法
提出的AGV小車避障路徑規劃算法二階段尋優過程為:第一階段,種群先按照改進后的PSO(particle swarm optimization)算法進行迭代,同時采用多樣性函數實時監控種群的多樣性。設定種群多樣性閾值作為第一階段終止,第二階段開始的界限;第二階段,此時種群將目的地鎖定在較小范圍內,利用PIO(pigeon-inspired optimization)算法的地圖羅盤算子和地標算子分別迭代更新鴿群的速度和位置。當滿足終止條件時,終止算法。改進PSO-PIO路徑規劃算法流程如圖4所示。
3.1PSO算法搜索路徑
PSO算法具有初期收斂速度快的優點,但在解決實際問題時容易陷入局部最優。本文中用粒子表示可行解,一個粒子表示一條路徑[15-17]。
3.1.1PSO算法路徑搜索原理
假設粒子群規模為m,每個微粒是沒有質量和體積的個體,在二維空間中以一定的速度進行飛行搜索,第t輪迭代粒子群的位置、速度如式(4)和式(5)所示[18]:
Xt=[Xt1Xt2…Xtm]T(4)
Vt=[Vt1Vt2…Vtm]T(5)
因此,第t輪迭代中粒子i在柵格地圖中的位置坐標和速度向量分別為(xti,yti)和(vtxi,vtyi)。PSO算法的基本進化公式為
Vt+1di=ωVtdi+c1r1[pti,d-Xtdi]+c2r2[ptg,d-Xtdi](6)
Xt+1di=Xtdi+Vt+1di(7)
式中:t為迭代次數;ω為動態慣性因子;pi為個體極值;pg為全局極值;c1、c2為學習因子;r1、r2為[0,1]之間的隨機數;d為空間維度,0lt;d≤2。其中,動態慣性因子ω由搜索范圍的大小來確定。迭代初期為避免陷入局部最優,種群適合在較大范圍內搜索;迭代后期為提高收斂速度,種群適合在小范圍內精確搜索[19-20]。ω隨著迭代過程以凹函數遞減,變化公式為
ω=e-s/smax(8)
式中:smax為最大迭代次數。根據式(8)得到凹函數與線性函數的動態慣性因子ω變化對比圖,如圖5所示。
由圖5可知,當迭代次數s增大時,凹函數的動態慣性因子比線性函數降低的更快,因此采用凹函數遞減方法能夠提高粒子群算法的計算效率,減少計算時間。
3.1.2適應度函數
由于在AGV小車路徑規劃系統中變量、約束較多,因此采用懲罰函數γ來處理變量的不等式約束。本文主要針對AGV小車的運行時間提出一種適應度函數計算方法,用適應度函數來評價各粒子的性能優劣,其計算公式為:
f=∑n-1i=1l(pj,pj+1)V+γntj(9)
式中:l(pj,pj+1)為一個粒子中pj和pj+1連接形成線段的距離;n為一個粒子上所代表路徑的轉彎次數;tj為轉一個彎所需的時間。
3.2帶線性變異策略的鴿群算法
PIO算法主要由地圖羅盤算子和地標算子組成,具有收斂速度快,計算精度高的優點[21]。算法的設計如下:
假設鴿子種群大小為mnew,第k時刻第i(0lt;i≤mnew)個鴿子在二維搜索空間中的速度和位置為Xki=(xk1i,xk2i)和Vki=(vk1i,vk2i)。在k+1時刻,該鴿子的速度和位置更新如式(10)和式(11)所示:
vk+1di=vk1di·eR×(k+1)+rand·(gBest-xkdi)(10)
xk+1di=xkdi+vkdi,0lt;i≤m,0lt;d≤2(11)
式中:R為地圖羅盤算子,在0~1之間取值;rand為[0,1]之間的隨機數;gBest為全局最優解。
地圖羅盤算子R值越小,搜索速度越快,開發能力越強[22]。采用線性變異策略對地圖羅盤算子R進行動態改進。
R=(Rmin+RmaxNkmax)(1+pr(rand-1))(12)
式中:Rmax和Rmin分別為地圖羅盤算子的最大值和最小值;pr表示變異概率。
當算法迭代到一定次數時,地圖羅盤算子的運算結束,進入地標算子運算階段。該階段每次迭代都會種群數量減半并舍棄遠離目標的鴿子。鴿子種群中心位置和各鴿子的更新如式(14)和式(15)所示:
mk+1new=mknew2(13)
xkcenter=∑mknewi=1xkdi·fitness(xkdi)mknew∑mki=1fitness(xkdi)(14)
xk+1di=xkdi+rand·(xkcenter-xkdi)(15)
式中:xkcenter為中心位置的鴿子;fitness(x)為適應度函數。
3.3種群多樣性監控
在PSO算法中,所有粒子都根據個體極值pi和全局極值pg來改變自己的飛行方向。如果種群跟隨pg在局部極值所在的較小區域內搜索,粒子將很難跳出這個局部極值。因此采用一種衡量種群多樣性的函數[23]進行實時檢測,種群多樣性隨著迭代的進行而下降,將種群多樣性是否達到閾值作為開始第二階段鴿群算法尋徑的標準。
divt=1mL∑mi=1∑2j=1(ptdi-pdcenter)2(16)
式中:m為群體規模;L為搜索空間最大對角線長度的一半;pdcenter為粒子群第d維的中心。量化后的種群多樣性為[0,1]的實數。
4仿真及實驗
4.1仿真及分析
為了驗證改進PSO-PIO算法規劃路徑的有效性,利用 MatlabR2018b進行仿真測試,其運行環境為:Windows 10,CPU為Intel Core i5-9300H CPU 2.40GHz,8.00GB RAM,64位操作系統。將其與傳統的PSO算法進行對比分析,其中AGV運行環境各參數如表1所示。
圖6為2種算法在仿真測試中的收斂曲線。由圖6可知,傳統的PSO算法規劃的路徑在120次迭代時找到第一條完整路徑并且已經陷入局部最優;改進PSO-PIO算法尋徑能力明顯提高,在61次迭代時就能找到第一條完整路徑,其穩定性和可靠性也更高。
圖7為分別采用傳統的PSO算法和改進PSO-PIO算法規劃路徑的趨勢線。由圖7可知,路徑長度隨迭代次數的增加而減小,2種算法都在第180次迭代附近時收斂,改進PSO-PIO算法在第35次迭代之后規劃路徑的長度小于傳統的PSO算法。傳統的PSO算法在收斂時規劃的路徑長度為157m;改進PSO-PIO算法在收斂時規劃的路徑長度為151m。
圖8為分別采用2種算法對不同出發點到目標點的路徑規劃,其中實線段為傳統的PSO算法規劃出的最優路徑,虛線段為改進PSO-PIO算法的路徑規劃。由圖8可知,改進PSO-PIO算法規劃的路徑為全局最優路徑,與傳統的PSO算法規劃的路徑相比,小車的轉彎次數大大降低。表2為2種算法所規劃路徑的轉彎次數。
圖9為在柵格地圖中新增障礙物時采用改進PSO-PIO算法對不同出發點到目標點的路徑規劃。圖9表明,該算法生成的路徑轉彎次數較少,算法的穩定性較高。
4.2路徑規劃實驗
為驗證本文提出的改進PSO-PIO算法能否在實際應用中按要求完成全局路徑規劃,以基于ROS系統開發的AGV小車為對象進行實驗,小車的轉向直徑為90cm。實驗環境為實驗室外布置好障礙物的一段走廊,寬度為200cm,如圖10(a)所示。采用激光雷達對實驗環境進行掃描并在ROS系統中建立柵格地圖,根據前文單元格寬度大于等于小車轉向半徑的原則進行柵格劃分。圖10(b)為采用改進PSO-PIO算法規劃的全局最優路徑,實驗結果驗證了本文改進PSO-PIO算法在AGV小車路徑規劃方面的可行性和有效性。
5結論
1)對AGV運行空間環境進行柵格地圖建模,并根據小車的運動學約束來確定單元柵格的大小,保證了AGV小車可以安全避障。
2)PSO算法中動態慣性因子ω采用凹函數遞減,PIO算法中采用線性變異策略對地圖羅盤算子R進行動態改進,根據種群多樣性指標進行二階段尋優,提高算法的計算效率,避免陷入局部最優。
3)仿真結果表明,本文提出的改進PSO-PIO算法與傳統的PSO算法相比,規劃的全局最優路徑長度縮短了約3.8%并減少了路徑規劃時長。該算法生成最優路徑的轉彎次數較少,在全局尋優的性能上有著較大的提升,并且實驗證明了本文算法的可行性。
參 考 文 獻:
[1]WU G X, ATILLA I, TAHSIN T, et al. Long-voyage Route Planning Method Based on Multi-scale Visibility Graph for Autonomous Ships[J]. Ocean Engineering,2021,219.
[2]唐嘉寧,潘蓉,周思達,等.融合模擬電勢場的改進人工勢場法研究[J].電光與控制,2020,27(12):69.
TANG Jianing, PAN Rong, ZHOU Sida, et al. An Improved Artificial Potential Field Method Integrating Simulated Electric Potential Field[J]. Electronics Optics amp; Control,2020,27(12):69.
[3]SARKAR R, BARMAN D, CHOWDHURY N. Domain Knowledge Based Genetic Algorithms for Mobile Robot Path Planning Having Single and Multiple Targets[J]. Journal of King Saud University-Computer and Information Sciences,2020(prepublish):doi:10.1016/j.jksuci.2020.10.010.
[4]陳秋蓮,鄭以君,蔣環宇,等.基于神經網絡改進粒子群算法的動態路徑規劃[J].華中科技大學學報(自然科學版),2021,49(2):51.
CHEN Qiulian, ZHENG Yijun, JIANG Huanyu, et al. Improved Particle Swarm Optimization Based on Neural Network for Dynamic Path Planning[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition) ,2021,49(2):51.
[5]TAHSEEN F A, ABAAS T F, SHABEEB A H. Autonomous Mobile Robot Navigation Based on PSO Algorithm with Inertia Weight Variants for Optimal Path Planning[J]. IOP Conference Series: Materials Science and Engineering,2020,928(2):022005.
[6]SONG Baoye, WANG Zidong, ZOU Lei. An Improved PSO Algorithm for Smooth Path Planning of Mobile Robots Using Continuous High-degree Bezier Curve[J]. Applied Soft Computing,2021,100:106960.
[7]王鼎新.基于改進Q-learning算法的AGV路徑規劃[J].電子設計工程,2021,29(4):7.
WANG Dingxin.AGV Path Planning Based on Improved Q-learning Algorithm[J].Electronic Design Engineering,2021,29(4):7.
[8]胡治鋒,陳冬方,李慶奎,等.基于模擬退火蟻群算法的揀貨路徑規劃[J].電子設計工程,2021,29(24):80.
HU Zhifeng,CHEN Dongfang,LI Qingkui,et al.Picking Path Planning Based on Simulated Annealing Ant Colony Algorithm[J].Electronic Design Engineering,2021,29(24):80.
[9]張華強,王國棟,呂云飛,等.基于改進純追蹤模型的農機路徑跟蹤算法研究[J].農業機械學報,2020,51(9):18.
ZHANG Huaqiang, WANG Guodong, L Yunfei, et al. Agricultural Machinery Automatic Navigation Control System Based on Improved Pure Tracking Model[J]. Transactions of the Chinese Society for Agricultural Machinery,2020,51(9): 18.
[10]馬曉敏,劉丁,辛菁,等.移動機器人生物啟發式變結構軌跡跟蹤控制[J].電機與控制學報,2018,22(7):97.
MA Xiaomin, LIU Ding, XIN Jing, et al. Biologically Inspired Variable Structure Trajectory Tracking Control for A Mobile Robot[J]. Electric Machines and Control, 2018,22(7):97.
[11]尤波,田朋,丁亮,等.星球探測車運行方式選擇策略[J].哈爾濱理工大學學報,2018,23(2):40.
YOU Bo, TIAN Peng, DING Liang, et al. Planet Rover Operation Mode Selection Strategy[J]. Journal of Harbin University of Science and Technology, 2018,23(2):40.
[12]尤波,丁寧,李佳鈺,等.載人六足機器人駕駛決策[J].電機與控制學報,2020,24(8):150.
YOU Bo, DING Ning, LI Jiayu, et al. Driving Decision of Manned Hexapod Robot[J]. Electric Machines and Control, 2020,24(8):150.
[13]丁承君,王鑫,馮玉伯,等.基于粒子群優化算法的AGV路徑規劃[J].傳感器與微系統,2020,39(8):123.
DING Chengjun, WANG Xin, FENG Yubo, et al. AGV Path Planning Based on PSO Algorithm[J]. Transducer and Microsystem Technologies,2020,39(8):123.
[14]羅陽陽,彭曉燕.基于改進PSO的四輪移動機器人全局路徑規劃[J].計算機仿真,2020,37(7):373.
LUO Yangyang, PENG Xiaoyan. Global Path Planning of Four-wheel Mobile Robot Based on Improved PSO[J]. Computer Simulation,2020,37(7):373.
[15]郭廣寒,王志剛.一種改進的粒子群算法[J].哈爾濱理工大學學報,2010,15(2):31.
GUO Guanghan, WANG Zhigang. A Modified Particle Swarm Optimization[J]. Journal of Harbin University of Science and Technology, 2010,15(2):31.
[16]朱佳瑩,高茂庭.融合粒子群與改進蟻群算法的AUV路徑規劃算法[J].計算機工程與應用,2021,57(6):267.
ZHU Jiaying, GAO Maoting. AUV Path Planning Based on Particle Swarm Optimization and Improved Ant Colony Optimization[J]. Computer Engineering and Applications, 2021,57(6):267.
[17]劉書池,楊維.礦井環境下無人機視覺PSOFastSLAM算法的實現[J].哈爾濱理工大學學報,2018,23(4):75.
LIU Shuchi, YANG Wei. Implementation of Vision PSOFastSLAM Algorithm for Unmanned Aerial Vehicles in Mine Environment[J]. Journal of Harbin University of Science and Technology, 2018,23(4):75.
[18]滿春濤,劉博,曹永成.粒子群與遺傳算法優化支持向量機的應用[J].哈爾濱理工大學學報,2019,24(3):87.
MAN Chuntao, LIU Bo, CAO Yongcheng. The Application Based on Support Vector Machine Optimized by Particle Swarm Optimization and Genetic Algorithm[J]. Journal of Harbin University of Science andTechnology, 2019,24(3):87.
[19]于桂芹,李劉東,袁永峰.一種結合自適應慣性權重的混合粒子群算法[J].哈爾濱理工大學學報,2016,21(3):49.
YU Guiqin, LI Liudong, YUAN Yongfeng. A Hybrid Particle Swarm Optimization Algorithm with Adaptive Inertia Weight[J]. Journal of Harbin University of Science and Technology,2016,21(3):49.
[20]劉細平,胡衛平,鄒永玲,等.改進粒子群算法的永磁同步電機多參數辨識[J].電機與控制學報,2020,24(7):112.
LIU Xiping, HU Weiping, ZOU Yongling, et al. Multi-parameter Identification of Permanent Magnet Synchronous Motor Based on Improved Particle Swarm Optimization[J]. Electric Machines and Control, 2020,24(7):112.
[21]李杰,莫宏偉,孫堯.基于鴿群決策機制的群體系統協同控制方法[J].電機與控制學報,2015,19(12):88.
LI Jie, MO Hongwei, SUN Yao. Cooperative Swarm System Control Method Based on Pigeons Decision-making Mechanism[J]. Electric Machines and Control, 2015,19(12):88.
[22]馬龍,盧才武,顧清華,等.引入改進鴿群搜索算子的粒子群優化算法[J].模式識別與人工智能,2018,31(10):909.
MA Long, LU Caiwu, GU Qinghua, et al. Particle Swarm Optimization with Search Operator of Improved Pigeon-inspired Algorithm[J]. Pattern Recognition and Artificial Intelligence,2018,31(10):909.
[23]彭樂,張立民,鄧向陽.基于種群多樣性模糊控制的粒子群算法[J].計算機仿真,2012,29(4):255.
PENG Le, ZHANG Limin, DENG Xiangyang. Particle Swarm Optimization Based on Fuzzy Control of Population Diversity[J]. Computer Simulation,2012,29(4):255.
(編輯:溫澤宇)