熊昕霞， 何利力

(浙江理工大學(xué) 信息學(xué)院， 杭州 310018)

0 引 言

在當(dāng)今的制造業(yè)中，戰(zhàn)略已從制造大量單個(gè)產(chǎn)品轉(zhuǎn)移到了一系列產(chǎn)品，并改善了質(zhì)量和交貨時(shí)間。許多物流和制造流程都依賴于多AGV系統(tǒng)的使用[1]，系統(tǒng)中的每輛車都執(zhí)行運(yùn)輸任務(wù)，包括在給定的初始位置提取貨物并在所需的目的地進(jìn)行運(yùn)輸和卸載[2]。多AGV系統(tǒng)運(yùn)行效率直接影響整個(gè)制造車間的高效運(yùn)轉(zhuǎn)。為了改善多AGV系統(tǒng)的運(yùn)行效率和安全性，要解決的主要問題是正確規(guī)劃多AGV的路徑[3]。多AGV路徑最優(yōu)軌跡是實(shí)現(xiàn)基于多AGV智能生產(chǎn)車間的關(guān)鍵。

從初始位置到目標(biāo)位置通過檢測并避開障礙物是自動導(dǎo)引小車在無人倉庫中的最重要功能。因此，在簡單或復(fù)雜的環(huán)境中工作時(shí)，正確選擇導(dǎo)航技術(shù)是機(jī)器人路徑規(guī)劃中最重要的步驟。多AGV路徑規(guī)劃是當(dāng)前研究的一個(gè)熱點(diǎn)和難點(diǎn)[3]。張丹露等提出一種基于預(yù)約表和動態(tài)加權(quán)地圖的改進(jìn)A*算法，應(yīng)用在多機(jī)器人路徑規(guī)劃、避障和擁堵問題上[4]，改進(jìn)的A*算法提出預(yù)約表與交通規(guī)則結(jié)合的方式解決了多機(jī)器人的碰撞問題，根據(jù)生成的動態(tài)加權(quán)地圖解決了擁堵問題；袁洋等研究多AGV在運(yùn)行時(shí)單個(gè)AGV的路徑規(guī)劃問題，提出了使用負(fù)載均衡改進(jìn)的A*算法進(jìn)行路徑規(guī)劃的方法，解決多AGV運(yùn)行路網(wǎng)的局部擁塞、防止和負(fù)載均衡問題，將路網(wǎng)負(fù)載引入到A*算法的評價(jià)函數(shù)中，避免多AGV路徑規(guī)劃時(shí)產(chǎn)生局部車流量過大[5]；張毅等根據(jù)AGVs剩余電量分配優(yōu)先級，協(xié)調(diào)AGVs路徑，以提高小車的使用效率，再使用改進(jìn)的蟻群算法計(jì)算AGVs的最優(yōu)路徑[3]。

在實(shí)際應(yīng)用中，大多數(shù)多AGV路徑規(guī)劃研究都是以無障礙、AGV之間的協(xié)調(diào)、車間不堵塞等路線調(diào)整為研究目標(biāo)，很少將路徑偏差和能源消耗視作關(guān)鍵因素。本文提出了一種改進(jìn)粒子群蟻群融合算法，使每個(gè)AGV的路徑長度到達(dá)時(shí)間最小化。以解決倉庫環(huán)境中的多AGV路徑規(guī)劃問題。

本文的主要工作如下：第一階段設(shè)立目標(biāo)函數(shù)，使每個(gè)小車的路徑成本、路徑偏差和能耗最小化。利用混合算法為每個(gè)移動機(jī)器人規(guī)劃出一條最佳路徑；第二階段，障礙物檢測，使每個(gè)機(jī)器人都避免與障礙物和其他機(jī)器人發(fā)生碰撞，解決充滿障礙物的倉庫環(huán)境中多AGV路徑規(guī)劃問題；第三階段，仿真實(shí)驗(yàn)，將獲得的結(jié)果與改進(jìn)的粒子群優(yōu)化(IPSO)、ACO算法進(jìn)行比較。

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

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

在無人倉庫中，為達(dá)到目標(biāo)位置完成運(yùn)輸任務(wù)，要求各個(gè)機(jī)器人從起點(diǎn)出發(fā)，繞過靜態(tài)障礙物，并且避免與其他機(jī)器人相撞，到達(dá)目標(biāo)位置完成運(yùn)輸任務(wù)。從倉庫中的當(dāng)前位置計(jì)算每個(gè)機(jī)器人的下一個(gè)位置目標(biāo)。 該路徑的目標(biāo)是在不與問題沖突的情況下找到最優(yōu)或接近最優(yōu)的路徑(最安全、最短和最光滑)。在制定多機(jī)器人路徑規(guī)劃問題時(shí)要考慮以下約束條件。假設(shè)：

(1)倉庫地圖已知；

(2)已知機(jī)器人的起始位置和目標(biāo)位置；

(3)每個(gè)機(jī)器人逐步規(guī)劃動作，直到到達(dá)各自的目標(biāo)位置；

(4)機(jī)器人到達(dá)下一個(gè)位置時(shí)可能會與倉庫中其他機(jī)器人/障礙物相撞。

因此，機(jī)器人前進(jìn)方向?qū)⒁砸欢ń嵌认蜃蠡蛳蛴肄D(zhuǎn)，從而確定其下一個(gè)位置。本文提出的混合算法通過假設(shè)機(jī)器人的當(dāng)前位置和速度作為優(yōu)化給定的多目標(biāo)函數(shù)的參數(shù)，來評估每個(gè)機(jī)器人的下一個(gè)位置。其確定了動態(tài)和靜態(tài)環(huán)境中從每個(gè)狀態(tài)到目標(biāo)狀態(tài)的最佳路徑，機(jī)器人借助配備的傳感器來測量其到障礙物的距離。

1.2 模型建立

(1)

(2)

當(dāng)Δt=1時(shí)，式(1)、(2)為式(3)、(4)：

(3)

(4)

該多機(jī)器人路徑規(guī)劃問題將作為路徑和能耗都得到優(yōu)化的問題提出。優(yōu)化問題被表述為基于約束的多目標(biāo)函數(shù)。目標(biāo)函數(shù)用于表示最小化每個(gè)機(jī)器人當(dāng)前位置到其目的地之間的路徑長度，避免與其他機(jī)器人和靜態(tài)障礙物碰撞的同時(shí)優(yōu)化生成路徑的平滑度。

1.2.1 路徑長度

路徑長度影響機(jī)器人的運(yùn)輸時(shí)間，為更快完成任務(wù)，通過形成約束f1使得機(jī)器人從當(dāng)前位置到目標(biāo)位置總路徑長度最小，并且避開障礙物。約束公式為(5)：

(5)

將式(3)(4)帶入得到式(6)：

(6)

1.2.2 與障礙物的安全距離

為防止機(jī)器人與障礙物碰撞，定義了每個(gè)障礙物的排斥場，式(7)：

(7)

其中，η0是障礙物的影響范圍；k是常數(shù)；γ≥2形成電位的徑向輪廓；dmin(Xp)為Xp到障礙物的最小距離。

1.2.3 預(yù)測動態(tài)障礙物(其他機(jī)器人)位置

動態(tài)障礙物將動態(tài)出現(xiàn)在機(jī)器人的路徑軌跡中。因此，在決定下一位置前，機(jī)器人需預(yù)測動態(tài)障礙物的軌跡，式(8)：

(8)

其中，(xp,yp)是動態(tài)障礙物的預(yù)計(jì)位置。

1.2.4 路徑平滑度

最小化直線(目標(biāo)點(diǎn)到建議點(diǎn))之間的角度差，使得路線平滑度最大，減少機(jī)器磨損，提升機(jī)器人運(yùn)行穩(wěn)定性。路徑平滑度目標(biāo)函數(shù)為式(9)：

(9)

第一個(gè)函數(shù)f1使得每個(gè)機(jī)器人當(dāng)前位置到目標(biāo)位置的歐幾里得距離最?。坏诙偷谌齻€(gè)懲罰函數(shù)f2、f3用于避免移動機(jī)器人與動態(tài)障礙物之間的碰撞；第四個(gè)懲罰函數(shù)f4是平滑路徑?？偰繕?biāo)(適應(yīng)度)函數(shù)為式(10)：

fit=λ1f1+λ2f2+λ3f3+λ4f4.

(10)

其中，λ1、λ2、λ3、λ4是4個(gè)函數(shù)的權(quán)重，滿足條件式(11)：

λ1+λ2+λ3+λ4=1.

(11)

這些權(quán)重在仿真實(shí)驗(yàn)中做出調(diào)整，λ1=0.3、λ2=0.3、λ3=0.3、λ4=0.1，通過使用適應(yīng)度函數(shù)最小化來獲取最優(yōu)路徑。

2 通過蟻群機(jī)制中信息素使用改進(jìn)的粒子群優(yōu)化

2.1 粒子群優(yōu)化

粒子的速度更新：

(12)

粒子的位更新：

(13)

為了更好地控制開發(fā)和探索，Shi和Eberhated提出了有關(guān)慣性權(quán)重的PSO，其中更新了每個(gè)粒子的速度，為全局搜索提供更大的慣性權(quán)重值，而較小該值將提供局部搜索。為提高PSO的收斂速度，本文將在自適應(yīng)權(quán)重調(diào)整和加速度系數(shù)方面改進(jìn)PSO。根據(jù)以式(14)和(15)修改：

(14)

(15)

2.2 改進(jìn)的粒子群優(yōu)化

PSO的收斂速度借助多種技術(shù)對其參數(shù)微調(diào)而得到了改善。為了避免群里發(fā)散而引入慣性權(quán)重w，通過調(diào)節(jié)先前迭代中速度對粒子的定義來控制粒子的速度。因此，當(dāng)慣性權(quán)重值較大時(shí)，將實(shí)現(xiàn)全局搜索；當(dāng)慣性權(quán)重值較小時(shí)，將進(jìn)行局部搜索。多項(xiàng)研究表明，通過動態(tài)改變慣性權(quán)重可以提高PSO的搜索能力，而線性遞減慣性權(quán)重已經(jīng)顯示出更好的結(jié)果[7]。因此，這里采用慣性權(quán)重的自適應(yīng)方法，如式(16)所示。過去已有實(shí)驗(yàn)驗(yàn)證，采用組合wmax=0.9，wmin=0.4可以達(dá)到最佳性能。

(16)

(17)

max_dist=argmax(disti).

(18)

其中，disti為粒子i與全局最佳粒子之間的歐幾里得距離，如式(17)所示；xgbestd為第d次迭代的全局最優(yōu)位置；max_dist是一代中粒子與全局最佳粒子之間的最大距離，如式(18)所示。

由于混沌行為類似于隨機(jī)性，但具有更好的動力學(xué)和統(tǒng)計(jì)學(xué)特性，與隨機(jī)搜索相比，混沌搜索可以更容易地從局部最優(yōu)解中逃脫[8]。因此，將隨機(jī)參數(shù)r1、r2替換成一維混沌圖，使得算法收斂速度更快。已有實(shí)驗(yàn)驗(yàn)證，將隨機(jī)參數(shù)r1替換成混沌圖獲得的結(jié)果最佳，并且Singer映射用于該算法的結(jié)果最優(yōu)[9]。替換后為式(19)：

(19)

Singer映射定義為式(20)：

(20)

其中，μ是一個(gè)0.9到1.08之間的參數(shù)。

2.3 蟻群算法

蟻群算法(ACO)是一個(gè)受實(shí)際蟻群行為啟發(fā)的人工系統(tǒng)。在螞蟻搜索路徑過程中，會留下信息素蹤跡，該信息素會隨時(shí)間和距離消散。當(dāng)螞蟻經(jīng)過下一個(gè)位置時(shí)，或當(dāng)更多的螞蟻經(jīng)過該位置時(shí)，該位置上的信息素強(qiáng)度會更高。因此，遵循信息素尾跡的螞蟻將更具以下情況聚集：信息素“濃度”隨著更隨尾跡的每增加一個(gè)螞蟻而增加。

在標(biāo)準(zhǔn)ACO中，螞蟻每一步位置轉(zhuǎn)移按照輪盤賭的方式做出概率選擇，再將信息素沿其蹤跡更新食物來源。t時(shí)刻螞蟻k由位置i轉(zhuǎn)移到j(luò)的轉(zhuǎn)移概率為(21)：

(21)

每只螞蟻完成一次搜索后，更新信息素跡線。首先以恒定的蒸發(fā)速率降低它們，然后依次使每只螞蟻在其經(jīng)過的一部分弧上沉積信息素，如式(22)：

(22)

(23)

其中，Lk(t)是行程的長度，Q是固定參數(shù)。

2.4 融合改進(jìn)粒子群優(yōu)化和蟻群優(yōu)化算法

由于依賴于外部參數(shù)(例如：慣性權(quán)重和加速度參數(shù))，傳統(tǒng)的PSO算法難以生成最優(yōu)解，收斂速度較慢。為了解決優(yōu)化問題，擺脫局部最小值，最大化探索粒子的搜索范圍，通過引入蟻群算法中的信息素協(xié)同粒子群優(yōu)化，如式(24)。

(24)

其中，C3為加速度系數(shù)，用于調(diào)整IPSO-ACO上的PSO速度。如果C3設(shè)置為零，則IPSO-ACO成為獨(dú)立的IPSO；如果C3設(shè)置為1，則會受到ACO的一半的隨機(jī)影響。

信息素軌跡是轉(zhuǎn)遞到構(gòu)造圖邊緣的真實(shí)值，被視為過程強(qiáng)信息的存儲器，這些信息涉及單個(gè)解決方案組件在先前的迭代中的效果。τi-1,i是從點(diǎn)i-1到點(diǎn)i的信息素，對應(yīng)于一個(gè)由吸引力的線連接的兩個(gè)點(diǎn)。因此，在混合過程中，IPSO使用內(nèi)存來保存迄今為止找到的最佳解決方案，通過信息素確認(rèn)該粒子將被加速。當(dāng)所有粒子接近良好的解決方案時(shí)，移動都非常緩慢，并且gbest可以幫助其充分利用全局最佳方法。每個(gè)粒子都觀察到最佳解并向其移動。

3 仿真實(shí)驗(yàn)

3.1 路徑求解流程

本文使用混合算法IPSO-ACO對充滿障礙物的無人倉庫中多AGV進(jìn)行路徑規(guī)劃。在該算法中，從每個(gè)AGV的現(xiàn)有位置計(jì)算每個(gè)AGV的連續(xù)最佳位置，同時(shí)滿足所有約束并提高收斂速度。使用本文提出的混合算法進(jìn)行多AGV路徑規(guī)劃流程，如圖1所示。

圖1 IPSO-ACO算法流程圖

3.2 靜態(tài)障礙物下多機(jī)器人路徑規(guī)劃

仿真實(shí)驗(yàn)使用Python語言實(shí)現(xiàn)，使用圖2作為模擬環(huán)境來實(shí)現(xiàn)AGV路徑規(guī)劃問題。模擬環(huán)境中，不同顏色的圓形為每個(gè)AGV，正方形為每個(gè)AGV對應(yīng)的目標(biāo)位置。障礙物隨機(jī)分布在模擬環(huán)境中。

圖2 仿真環(huán)境圖

實(shí)驗(yàn)時(shí)障礙物和環(huán)境是靜止的，其他優(yōu)先級AGV可以移動。在仿真實(shí)驗(yàn)中設(shè)置的算法相關(guān)參數(shù)見表1。每個(gè)GAV根據(jù)定義的適應(yīng)度值來決定其下一個(gè)位置。使用IPSO-ACO算法使每個(gè)AGV到達(dá)其相應(yīng)位置，虛線表示每個(gè)AGV的路徑，如圖3所示。從圖3中可知，6臺AGV都分別到達(dá)了目標(biāo)位置，第3臺和第5臺AGV在第13步時(shí)距離非常接近，在路段上可能發(fā)生沖突，第3臺將第5臺AGV視作動態(tài)障礙物，重新計(jì)算其路徑，避開動態(tài)障礙物。

3.3 算法比較

為評估IPSO-ACO的性能，運(yùn)用IPSO和ACO算法在上述環(huán)境中對6臺AGV進(jìn)行路徑規(guī)劃，算法相關(guān)參數(shù)設(shè)置與IPSO-ACO相同。AGV通過三種不同算法到達(dá)其對應(yīng)目標(biāo)位置所需的時(shí)間進(jìn)行了比較，其折線圖如圖4所示。由圖4可知使用本文算法為所有機(jī)器人到達(dá)目標(biāo)規(guī)劃的路徑比其他兩種算法每步所需時(shí)間更短。圖5顯示了三種不同的啟發(fā)式算法的每一步的目標(biāo)距離對比，與IPSO和ACO相比，使用IPSO-ACO算法到達(dá)目標(biāo)位置的距離最短，且最終的路徑長度以及所需步數(shù)都較小。

表1 算法相關(guān)參數(shù)

(a) 第7步結(jié)果 (b) 第13步結(jié)果 (c) 第19步結(jié)果

圖4 三種算法迭代次數(shù)和運(yùn)行時(shí)間

圖5 三種算法的步數(shù)和平均目標(biāo)距離

4 結(jié)束語

本文提出了一種改進(jìn)粒子群蟻群融合算法，以提高粒子群優(yōu)化算法的搜索能力，避免陷入局部最小值，實(shí)現(xiàn)更好的收斂性。使用該混合算法解決充滿障礙物的無人倉庫中多AGV路徑規(guī)劃。通過軟件模擬，并與IPSO和ACO算法對比，該方法的效率更高，優(yōu)化效果更好。