郭興海，計明軍，劉雙福

(大連海事大學(xué) 交通運輸工程學(xué)院，遼寧 大連 116023)

0 引言

作為無人倉庫運營的關(guān)鍵設(shè)備，自動導(dǎo)引車(Automated Guided Vehicle, AGV)的工作效率直接影響無人倉庫的整體運營效率。合理的AGV行駛路徑不僅能提升無人倉庫內(nèi)產(chǎn)品的流通效率與工作效率，還能減少AGV派發(fā)數(shù)量并節(jié)約能耗，增加其有效工作時間。為此，本文將AGV在無人倉庫的路徑規(guī)劃作為研究重點。

路徑規(guī)劃思想于20世紀(jì)60年代由Lozano等[1]提出，其以最合理的方式躲避障礙物來完成運輸任務(wù)，在很多領(lǐng)域都有廣泛的應(yīng)用，其中在高新技術(shù)領(lǐng)域主要有無人機的突防避障飛行路徑規(guī)劃、無纜水下機器人的救援與勘探路徑規(guī)劃、陸上機器人的自主行為無碰的路徑規(guī)劃等。AGV屬于陸上機器人的一種，其路徑規(guī)劃包括運動規(guī)劃和軌跡規(guī)劃。現(xiàn)階段國內(nèi)外的AGV路徑規(guī)劃問題研究主要有李軍軍等[2]以行駛時間為考量解決多AGV路徑?jīng)_突問題，并將蟻群算法與粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法相結(jié)合，使計算結(jié)果更加精準(zhǔn)；卜新蘋等[3]對復(fù)雜環(huán)境下的大型工裝的物料運輸與維修的路徑規(guī)劃進行研究，將蟻群算法與Bezier曲線相結(jié)合得到曲率連續(xù)的路徑；夏揚坤等[4]研究訂單拆分多AGV物料配送路徑規(guī)劃，考慮距離、載重、需求等因素，提出自適應(yīng)性的禁忌搜索算法，使路徑規(guī)劃更加符合實際需求；Rund等[5]根據(jù)工業(yè)倉庫的任務(wù)量，利用協(xié)同數(shù)據(jù)制定實時AGV路徑；Zheng等[6]對水上AGV的路徑規(guī)劃進行研究，其與工業(yè)倉庫中AGV路徑規(guī)劃的研究方法相似；He等[7]研究了四輪車輛在三維環(huán)境下的路徑約束，給出了平滑路徑和速度控制規(guī)則，再利用Bezier修正三維約束的曲率不連續(xù)的路徑；Elhoseny等[8]利用遺傳算法求解移動機器人在動態(tài)場地的路徑規(guī)劃，利用Bezier曲線使路徑連續(xù)平滑；Wang等[9]融合切線加速度與速度約束的Bezier曲線路徑規(guī)劃，能確保無人車輛穩(wěn)定通過某一特定點，且不會造成不良振動與側(cè)滑。

現(xiàn)在大多數(shù)路徑規(guī)劃研究都是以距離最短、時間最少、任務(wù)最多等外部因素作為研究目標(biāo)，很少考慮運行設(shè)備的機械能耗與速度限制等內(nèi)部因素，而且多數(shù)文獻僅給出行走路徑，卻沒有綜合考慮設(shè)備的平穩(wěn)性、快速性及節(jié)能性要求。

基于以上分析與研究，本文從以下幾方面開展工作：

(1)將路徑規(guī)劃分為兩階段，第一階段先考慮路徑最短與平滑度最大的因素，產(chǎn)生初始路徑；第二階段利用Bezier曲線與平滑度最大的約束，求解出能耗最少且符合速度限制的AGV行走路徑。

(2)基于3階Bezier曲線特性，連接任意方向兩點的轉(zhuǎn)彎單元，使曲率不連續(xù)的路徑幾何連續(xù)，再結(jié)合平滑度約束調(diào)整Bezier曲線路徑的弧度，生成最終路徑。

(3)設(shè)計了混沌變化系數(shù)的量子粒子群優(yōu)化(Quantum Particle Swarm Optimization, QPSO)算法求解多目標(biāo)路徑規(guī)劃問題，并與常規(guī)算法進行對比，證明該算法收斂速度快，所得解具有良好的精確度與前沿性。

1 問題描述與模型構(gòu)建

1.1 問題描述與假設(shè)

在無人倉庫內(nèi)，為到達預(yù)設(shè)地點完成運輸任務(wù)，要求AGV從起點出發(fā)，繞過障礙物到達目標(biāo)點完成運輸任務(wù)；行走時盡量使路徑最短、平滑度最大，同時還要確保AGV行走路徑曲率的連續(xù)性。該路徑可減少AGV行走時間，降低機械磨損，而且使運行更穩(wěn)定、能耗更少，從而提升無人倉庫的整體工作效率。

假設(shè)：①倉庫平面地圖已知；②貨架(障礙物)位置以坐標(biāo)的形式分布；③AGV車況良好且通過外部計算機控制與監(jiān)測運行狀態(tài)。

1.2 模型的建立

本節(jié)為路徑規(guī)劃的第一階段。該階段以路徑最短與平滑度最大為約束，建立多目標(biāo)模型并用改進的QPSO算法求解，所得解能最大程度上滿足這兩個約束的要求，目標(biāo)函數(shù)模型如下：

(1)路徑最短目標(biāo)函數(shù)

路徑最短能夠節(jié)約工作時間，確保更快完成運輸任務(wù)，則目標(biāo)函數(shù)為

(1)

式中：L(P)為最短路徑求和；L(Pi,Pi+1)為點Pi和Pi+1之間的距離；(xi，yi)，(xi+1，yi+1)分別為轉(zhuǎn)向點在空間D上的當(dāng)前點坐標(biāo)與下一個點坐標(biāo)；d為AGV轉(zhuǎn)向點的數(shù)量。

(2)平滑度最大目標(biāo)函數(shù)

路徑平滑度最大即行走路徑轉(zhuǎn)角總和最小，該約束可減少機械磨損，保證良好的機械狀態(tài)；另外，平滑度越大，轉(zhuǎn)彎的速度變化越小，AGV運行的穩(wěn)定性越高。其目標(biāo)函數(shù)為

(2)

式中：θ(P)為直線Pi-1Pi和PiPi+1的角正切值求和；atan 2為轉(zhuǎn)向角的正切值；(xi，yi)，(xi-1，yi-1)，(xi+1，yi+1)分別為轉(zhuǎn)向點的當(dāng)前坐標(biāo)及其上一個點和下一個點的坐標(biāo)。

通過建立與求解式(1)和式(2)兩個模型，能夠得到AGV在行駛空間內(nèi)直線相連但曲率不連續(xù)的初始路徑，該路徑在一定程度上滿足了路徑最短與平滑度最大兩個約束。

1.3 求解算法設(shè)計

基于多目標(biāo)問題對算法的遍歷性要求，本文通過改進QPSO算法來增強算法的全局搜索能力，提升求解的準(zhǔn)確性與精度，并結(jié)合仿真部分的三角分割法來減少計算時間。

三角分割法是將行走空間劃分為多個連續(xù)的三角區(qū)域，粒子在三角空間內(nèi)搜索能夠增大粒子搜索的有效步長，減小搜索范圍；同時，與啟發(fā)式算法結(jié)合后能夠使搜索具有方向性，從而縮短計算時間，具體操作見第4.3節(jié)。

QPSO算法由孫俊等[10]提出，該算法是將量子運動思想運用到粒子行為上的一種啟發(fā)式算法，標(biāo)準(zhǔn)的QPSO算法狀態(tài)更新公式如下：

(3)

(4)

(5)

(6)

式中：Vk+1為下一時刻粒子的速度，c1，c2為學(xué)習(xí)因子且為非負(fù)常數(shù)；r1，r2為[0,1]間的隨機數(shù)，P(k)為個體最優(yōu)值，Pg(k)為全局最優(yōu)值；Xk+1為粒子下一時刻的位置，Xk為粒子當(dāng)前位置，u為[0,1]間的隨機數(shù)；mbest為全局最優(yōu)平均值，M為種群個數(shù)；a為權(quán)重系數(shù)，maxgen為最大迭代次數(shù)，iter為當(dāng)前迭代次數(shù)，常數(shù)ρ1=ρ2=0.5。

經(jīng)檢驗發(fā)現(xiàn)，在離散和多維問題上QPSO算法的搜索遍歷性表現(xiàn)不佳，需進一步改進來增強算法的尋優(yōu)能力；同時無論對連續(xù)還是離散問題，式(4)中慣性權(quán)重a在收斂速度與尋優(yōu)的遍歷性方面顯示出非常重要的作用[11]。為此，考慮通過改進a達到提升算法求解能力的目的。

式(6)中的a隨著迭代次數(shù)的增加而線性減小，從而降低了QPSO算法的收斂速度和遍歷性。然而，混沌映射具有很強的遍歷性、非重復(fù)性、敏感性等[12]，它能以更高的速度進行全面搜索，比依靠均勻變化的搜索方式(式(6))更具優(yōu)勢。因此，引入混沌映射來調(diào)整慣性權(quán)重a，改進后的QPSO算法命名為混沌量子粒子群優(yōu)化(Chaotic Quantum Particle Swarm Optimization, CHQPSO)算法。選擇正弦函數(shù)式的混沌變化來調(diào)整慣性權(quán)重[13]，式(6)改進為

a=A×sin(πaiter-1)，0

iter=1,2,…,maxgen。

(7)

式中：A為(0,1)間的隨機數(shù)。

1.4 多目標(biāo)Pareto解集篩選

本文的路徑規(guī)劃求解需同時考慮路徑最短與平滑度最大兩個因素，故該問題可視為具有離散特性的多目標(biāo)優(yōu)化問題(Multi-Objective Optimization Problem, MOP)[14]。CHQPSO算法在求解MOP模型時會產(chǎn)生多個非劣解，但AGV只選擇一條路線行走，為減少人為的隨機性，需要對Pareto解集進行評價，即引入擁擠距離方法描述非劣解的優(yōu)劣[15]，將目標(biāo)函數(shù)fm按升序排列，定義邊界個體的擁擠距離Lk=∞，其余個體的擁擠距離

(8)

2 路徑生成與Bezier曲線

本章為路徑規(guī)劃的第二階段。首先利用能耗約束速度與加速度變化產(chǎn)生不同形式的Bezier曲線；然后對速度進行控制，確保AGV穩(wěn)定運行；最后利用Bezier曲線與平滑度的約束得到曲率連續(xù)的路徑。

2.1 最小耗能目標(biāo)函數(shù)

速度與加速度的乘積定義為偽功率[16]，減少偽功率會顯著降低能耗與峰值功率，則目標(biāo)函數(shù)為：

J=maxLk，?k∈(1,2,…,k)；

(9)

(10)

式中：J為最大擁擠距離函數(shù)，Lk為擁擠距離；P為最小耗能目標(biāo)函數(shù)，vl為運行速度，al為加速度，m為AGV的質(zhì)量，N為AGV速度變化的次數(shù);k為擁擠距離的數(shù)量，l為功率變化點的次數(shù)。式(10)說明速度和加速度變化與能耗存在線性關(guān)系。

2.2 速度規(guī)劃與控制

類似于小型車輛，AGV在轉(zhuǎn)彎過程中要對轉(zhuǎn)向速度進行控制，若速度過大，則AGV將產(chǎn)生側(cè)滑，車上物體易掉落；若速度過慢，則會影響工作效率。因此約束速度的公式如下：

(11)

(12)

(13)

其中：式(11)表示曲率與半徑之間的關(guān)系以及AGV不發(fā)生側(cè)滑的速度約束，ψ為曲率，R為轉(zhuǎn)向半徑，φ為前輪轉(zhuǎn)向角度，T為軸距，u和g為靜態(tài)摩擦系數(shù)與重力加速度，m為AGV的質(zhì)量，vmax為最大轉(zhuǎn)向速度；式(12)表示AGV在不同曲率ψB的運行速度，vB為根據(jù)Bezier曲線曲率計算的速度；式(13)表示計算速度與實際運行速度之間的約束，v為當(dāng)前的實際運行速度。圖1所示為AGV的轉(zhuǎn)向結(jié)構(gòu)圖。

2.3 多階Bezier曲線與平滑度約束

Bezier曲線是一種參數(shù)曲線，由伯次斯坦基n次多項式組成[17-18]，可以定義為

P(t)=P0(1-t)3+3P1(1-t)2t+

3P2(1-t)t2+P3t3，t∈(0,1);

(14)

(15)

將每次轉(zhuǎn)彎過程中的控制點與轉(zhuǎn)向點相連，如圖2三角形△p1p2q1中，在三角區(qū)生成Bezier曲線后引入平滑度約束，利用鄰域搜索機制增強路徑的連續(xù)性，減少轉(zhuǎn)向角度，則控制軌跡方程為：

(16)

式中:L?為當(dāng)前位置點；U?為下一個位置點；T為軸距；Rand為介于當(dāng)前與下一個點的隨機函數(shù)。根據(jù)AGV軸距與轉(zhuǎn)向角的關(guān)系[17]，確定路徑曲率變化在[-0.77,0.77]內(nèi)可以減少AGV的速度變化，使轉(zhuǎn)向更加平穩(wěn)。

在圖2中連接任意兩點的轉(zhuǎn)向單元，點(p1,p2,…,p6)為CHQPSO算法生成的路徑點，點(q1,q2,…,q5)為Bezier曲線控制點，擬合出的軌跡如圖2所示。

3 仿真實驗

本章首先介紹路徑求解流程，并對CHQPSO算法的尋優(yōu)性能進行測試與對比；然后，模擬AGV在100 m×100 m倉庫內(nèi)進行路徑規(guī)劃，以S(0,10)為起點、T(70,85)為終點進行多目標(biāo)建模，采用CHQPSO算法求解，并與常用多目標(biāo)算法進行對比；最后，生成路徑后利用Bezier曲線與平滑度進行擬合修正，并給出與路徑相關(guān)的變量變化情況。計算環(huán)境均為Window7、i5CPU、8 GB內(nèi)存，編程語言為MATLAB2017b。

3.1 路徑求解流程

路徑求解的具體步驟如下：

步驟1將無人倉庫與障礙物位置映射到坐標(biāo)系中進行三角分割，建立路徑最短與平滑度最大的多目標(biāo)函數(shù)模型。

步驟2用CHQPSO算法求解多目標(biāo)模型，根據(jù)擁擠距離評價Pareto解集，選擇符合約束的路徑。

步驟3若計算結(jié)果未達到預(yù)定終止條件，則清空存儲器Q，返回步驟2；否則，終止輸出結(jié)果。

步驟4以耗能最少為目標(biāo)，利用Beizer曲線擬合修正步驟2生成的路徑，使路徑幾何連續(xù)，并計算AGV輸出的運行速度和加速度范圍，即可確定其功率的變化情況。

步驟5通過采用CHQPSO算法求解MOP問題和連續(xù)函數(shù)的極值，來測試算法的搜索性能，并與其他算法進行對比。

步驟6結(jié)束。

3.2 改進算法性能測試

為驗證CHQPSO算法的尋優(yōu)性能，采用5個常用的基準(zhǔn)函進行測試，函數(shù)名稱如表1所示[13]。將測試結(jié)果與PSO，Levy+PSO，QPSO算法進行對比。算法參數(shù)設(shè)置為：初始種群為30，最大迭代次數(shù)為500，粒子速度為[-1,1]，學(xué)習(xí)因子c1=c2=2，維數(shù)d=50。每個測試函數(shù)各運行50次，記錄每次的平均值Mean和標(biāo)準(zhǔn)差S.d，結(jié)果如表2所示。

表1 基本測試函數(shù)及其取值范圍

表2 函數(shù)在不同算法下的最小平均值和方差

由表2可知，采用CHGPSO算法求解時，5個基準(zhǔn)函數(shù)的平均數(shù)與方差最小，說明每次求得的最佳適應(yīng)度值波動小，算法求解的穩(wěn)定性好。

3.3 路徑生成與修正

(1)第一階段：初始路徑生成與算法對比

本階段先采用三角分割法劃分行走空間，再利用CHQPSO算法求解多目標(biāo)模型，并與常用的帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)和改進的強度Pareto進化算法(Improving the Strength Pareto Evolutionary Algorithm, SPEA2)[19]進行對比，突出CHQPSO算法在多目標(biāo)問題求解的有效性。

利用三角分割法將AGV行走空間劃分為多個連續(xù)的三角區(qū)域，分割后的效果如圖3所示；再使算法粒子從起始點出發(fā)，到生成的三角行邊緣與終點所在的三角區(qū)域內(nèi)進行搜索，確定最終路徑。CHQPSO算法參數(shù)設(shè)置為：maxgen=1 000，M=300，c1=c2=1.499 5，a采用混沌變化，Pareto解集存儲器Q=5(即5條路徑)。結(jié)果如圖3和表3所示。

表3 CHQPSO算法生成的路徑及相關(guān)信息

路徑長度/m角度/(°)擁擠距離前沿計算時間/sS1116.8610526.29否S2115.4810626.18否S3114.1911026.29否S4110.4311326.09否S5109.8811626.36是55

將圖3路徑的非劣解導(dǎo)入表3，利用式(8)計算擁擠距離，舍去邊緣擁擠距離無窮大的解，可知路徑S5的擁擠距離最大，因此將其作為AGV行駛路徑。

NSGA-Ⅱ算法參數(shù)設(shè)置為：最大迭代次數(shù)為1 000，種群規(guī)模為300，交叉概率為0.8，變異概率為0.8。SPEA2參數(shù)與NSGA-Ⅱ相同。兩個算法各執(zhí)行5次，產(chǎn)生的結(jié)果如圖4和圖5所示，其路徑的詳細(xì)數(shù)據(jù)如表4所示。

表4 NSGA-Ⅱ與SPEA2算法生成的路徑及相關(guān)信息

算法路徑長度/m角度/(°)擁擠距離前沿計算時間/sNSGA-ⅡS1131.601259.57否S2130.051389.84否S3127.2915610.18是S4127.181439.56否S5110.651639.11否150

續(xù)表4

對比3種算法發(fā)現(xiàn)，CHQPSO算法求出的5個解擁擠距離較大，說明解的質(zhì)量好，其解更前沿，且計算時間少；NSGA-Ⅱ與SPEA2算法出現(xiàn)被困在搜索區(qū)域中間和邊緣情況，其路徑平滑度減小，轉(zhuǎn)向角變大，計算時間更長。因此，本文所提算法在求解多目標(biāo)問題上更加有效，能夠搜索到較好的Pareto前沿解。

(2)第二階段：路徑擬合修正

該階段以降低總功率為目標(biāo)函數(shù)，利用Bezier曲線與平滑度約束對表3中的最優(yōu)路徑S5進行擬合修正。先在可行走方向生成多條曲率連續(xù)的無碰撞Bezier曲線路徑，再利用平滑度約束的鄰域搜索控制曲線產(chǎn)生的弧度，使弧度變化符合速度限制，所生成曲線的數(shù)量與控制單元計算機的能力相關(guān)，如圖6和圖7所示。

圖6中帶有標(biāo)記箭頭的直線為修正后的Beizer曲線路徑，圖7為引入平滑度調(diào)整弧度后的Bezier曲線。

當(dāng)已知空間內(nèi)出現(xiàn)未知障礙物時，若其坐標(biāo)信息未及時更新，則AGV應(yīng)躲避?，F(xiàn)實中多數(shù)企業(yè)使用的為具有感應(yīng)功能的激光AGV，感應(yīng)距離至少為4 m。當(dāng)遇到動態(tài)或靜態(tài)障礙物時，AVG的路徑采用Bezier曲線與平滑度約束重新生成，其繞過障礙物后回到原來修正后的路徑上繼續(xù)行走。仿真過程如圖8所示。

(3)兩階段路徑求解與關(guān)系的說明

對圖6和圖7的路徑進行參數(shù)分析，其計算方式如下：

1)CHQPSO路徑 平滑度通過式(2)計算求得，路徑距離通過兩點間距離公式計算。

2)Bezier路徑 平滑度是先對轉(zhuǎn)向的起點和完成轉(zhuǎn)向的終點做切線相交，如圖2中線段L(p1p2)與L(q1p2)相交，然后根據(jù)式(2)計算求得，路徑距離利用Bezier曲線方程積分運算得到。

3)Bezier+平滑度 路徑采用式(13)鄰域搜索的方法，以保證曲線與直線連接處的曲率連續(xù)，再利用式(2)計算平滑度，路徑距離利用Bezier曲線方程進行積分運算得到，數(shù)據(jù)如表5所示。

表5 第一階段與第二階段獲得的路徑數(shù)據(jù)對比

由表5可知，Bezier路徑與平滑度約束共同擬合修正后的路徑轉(zhuǎn)向正切值之和最小，總體平滑度變大，而且保證了路徑曲率的連續(xù)性，確保了AGV的速度變化小、能耗低，可作為路徑規(guī)劃的最終路徑，雖然總路徑有一定增加，但是根據(jù)式(10)計算的偽功率，其總能耗與運行時間均為最低。

路徑求解分為兩階段的原因主要是，多數(shù)離散化路徑規(guī)劃問題計算出的解并不一定是最優(yōu)解，通常需要進一步調(diào)整或者二次優(yōu)化，因此本文的路徑規(guī)劃也采用這種分階段優(yōu)化的思想。

在路徑生成過程中，第一階段考慮路徑最短與平滑度最大，目的是產(chǎn)生符合多目標(biāo)要求的初始路徑，該路徑是曲率不連續(xù)的折線，不適合AGV行駛；第二階段求解的目的是對第一階段的初始路徑進行Bezier曲線修正，修正過程中引入平滑度約束，產(chǎn)生速度變化小且能耗低的曲率連續(xù)路徑，以符合AGV運行。這兩個階段路徑是依次建模并求解的，第一階段為第二階段的計算基礎(chǔ)，第二階段是對第一階段生成路徑的擬合修正，兩個階段為逐層遞進的關(guān)系。

另外，因為第一階段的路徑從多個Pareto解集中篩選，滿足路徑最短和平滑度的要求，已經(jīng)相對較優(yōu)，所以第二階段的路徑產(chǎn)生后，不會再調(diào)整上一階段的路徑。

3.4 實驗變量分析

本文實驗的車輛為激光感應(yīng)式AGV，對AGV行駛的相關(guān)變量和自身參數(shù)描述如表6所示。

由于PID控制器擾動、坡道角、內(nèi)耗等問題，加速度與速度存在波動，很難達到勻速運動的狀態(tài)。利用CHQPSO算法與Beizer曲線擬合方式產(chǎn)生的行走路徑，其AGV的速度、功率變化如圖9所示。

表6 AGV車體參數(shù)設(shè)計

由圖9a可見，Bezier曲線擬合后的路徑速度變化少，可以推導(dǎo)出加速度變化減小，再根據(jù)式(10)可知偽功率降低。由圖9可知，當(dāng)目標(biāo)地點相同時，Bezier曲線路徑能耗由4.95 kW降低到4.14 kW，同比節(jié)約17%；工作時間由110 s降至92 s，工作效率提升16%；AGV平均每天完成任務(wù)約16 h，新路徑的工作時間降至13.28 h，工作效率明顯提升。

4 結(jié)束語

本文結(jié)合多目標(biāo)約束與CHQPSO算法求解出AGV的行走路徑，再利用Bezier曲線進行擬合修正，并有以下結(jié)論：

(1)第一階段通過多目標(biāo)建模并對Pareto最優(yōu)解集路徑進行篩選，得到能夠綜合長度最短與平滑度最大的路徑，與僅考慮路徑最短的情況相比，在該路徑下行走時AGV的磨損程度更小，穩(wěn)定更高，初始路徑?jīng)Q策更科學(xué)。

(2)第二階段結(jié)合Bezier曲線與平滑度對第一階段的路徑進行修正，所產(chǎn)生的路徑曲率平滑，速度與加速度的變化減少，耗能降低。仿真結(jié)果表明，雖然路徑變長，但是工作時間減少，說明該方法的實用性較好。

(3)對比所提CHQPSO算法與經(jīng)典NSGA-Ⅱ和SPEA2算法可知，CHQPSO算法能夠快速準(zhǔn)確地求解多目標(biāo)問題，其Pareto最優(yōu)解集更前沿；利用基準(zhǔn)函數(shù)對CHQPSO算法進行測試，并與同類型改進算法對比，可知本文所提算法的尋優(yōu)性能更好，能夠保證解在時間和質(zhì)量上具有可行性。

本文只給出2個目標(biāo)約束的路徑規(guī)劃，下一步將對更多目標(biāo)約束及路徑跟蹤問題進行研究，編程方式將采用MATLAB與C++的混合編程，以提高計算速度。