李 立,魏曉晨

(1.上海震旦職業(yè)學(xué)院智能工程學(xué)院,上海 201900) (2.山東科技大學(xué)機(jī)械電子工程學(xué)院,山東 青島 266590)

近年來,電子商務(wù)業(yè)務(wù)呈爆炸性增長,隨之增加的包裹數(shù)量對倉儲物流系統(tǒng)的作業(yè)效率提出了更高的要求。為適應(yīng)現(xiàn)代生產(chǎn)需求,物流正朝著智能化方向發(fā)展[1]。隨著云計算和人工智能等新一代技術(shù)與機(jī)械設(shè)計制造技術(shù)的深度融合,智能倉儲機(jī)器人應(yīng)運(yùn)而生,而路徑規(guī)劃就是智能倉儲的關(guān)鍵技術(shù)[2]。因此,研究基于云計算的路徑規(guī)劃方法具有重要的現(xiàn)實意義。

目前,國內(nèi)外對倉儲物流機(jī)器人路徑規(guī)劃方法的研究主要集中在A*算法、動態(tài)窗口法、蟻群算法、人工勢場法等[3-4]。文獻(xiàn)[5]提出一種改進(jìn)蟻群算法用于倉儲機(jī)器人路徑規(guī)劃,結(jié)果表明,相比于常規(guī)路徑規(guī)劃方法,所提方法有效縮短了倉儲物流機(jī)器人路徑長度,且更穩(wěn)定,具有較強(qiáng)的適應(yīng)性。文獻(xiàn)[6]將人工蜂群和自適應(yīng)遺傳算法相結(jié)合用于倉儲機(jī)器人法的路徑規(guī)劃,結(jié)果表明,與常規(guī)路徑方法相比,所提方法有效降低了能耗,且規(guī)劃路徑更加平滑,更適用于倉儲機(jī)器人的路徑規(guī)劃。文獻(xiàn)[7]提出一種基于線性時序邏輯理論的倉儲機(jī)器人路徑規(guī)劃,結(jié)果表明,與常規(guī)A*算法相比,所提方法不僅能夠滿足復(fù)雜的任務(wù)要求,而且能夠保證路徑規(guī)劃的最優(yōu)性。文獻(xiàn)[8]提出一種改進(jìn)A*算法用于倉儲機(jī)器人路徑規(guī)劃,結(jié)果表明,相比于常規(guī)方法,所提方法有效地縮短了規(guī)劃時間,得到了最優(yōu)的規(guī)劃路徑。但上述方法在規(guī)劃中存在規(guī)劃路徑長和效率低等問題,適應(yīng)性有待進(jìn)一步提高。在此基礎(chǔ)上,本文結(jié)合改進(jìn)A*算法和改進(jìn)人工勢場法用于倉儲機(jī)器人的路徑規(guī)劃。其中通過蟻群算法優(yōu)化A*算法,完成全局路徑規(guī)劃;通過修正勢場函數(shù)和加入逃逸因子優(yōu)化人工勢場法,完成局部路徑調(diào)整。

1 基于云計算的路徑規(guī)劃系統(tǒng)

智能倉儲物流機(jī)器人路徑規(guī)劃需要結(jié)合倉儲實際環(huán)境,本文通過建立環(huán)境拓?fù)淠Ｐ秃吐窂揭?guī)劃方法確保智能倉儲物流機(jī)器人安全有效地執(zhí)行任務(wù)[9-10]。智能倉儲物流機(jī)器人原型采用開放式結(jié)構(gòu)和控制系統(tǒng),可搭載多種執(zhí)行器。圖1所示為基于云計算網(wǎng)絡(luò)的智能倉儲物流機(jī)器人路徑規(guī)劃系統(tǒng),由云服務(wù)器和機(jī)器人本體兩部分組成。云服務(wù)器主要功能是規(guī)劃實際場景內(nèi)倉儲物流機(jī)器人的運(yùn)行路徑和顯示實時數(shù)據(jù)。機(jī)器人由主控器、作業(yè)部分和行走部分組成。本文基于開源Hadoop框架,通過云計算解決大規(guī)模環(huán)境中的路徑規(guī)劃問題。

圖1 系統(tǒng)結(jié)構(gòu)

2 混合路徑規(guī)劃方法

本文以最小化所有機(jī)器人運(yùn)行總時間為目標(biāo)函數(shù),通過蟻群算法對A*算法進(jìn)行優(yōu)化,完成全局路徑規(guī)劃。但在實際行進(jìn)中會存在各種障礙物,因此引入改進(jìn)的人工勢場法,完成局部路徑調(diào)整。

2.1 目標(biāo)函數(shù)

倉儲物流機(jī)器人路徑規(guī)劃最終目標(biāo)是找到一條無障礙路徑,因為機(jī)器人以勻速行走,所以用時最少即路徑最短。目標(biāo)函數(shù)如式(1)所示:

(1)

1)一個任務(wù)只有一臺機(jī)器人完成,如式(2)所示。

(2)

2)在當(dāng)前節(jié)點下執(zhí)行任務(wù)mq的機(jī)器人時間不能位于之前執(zhí)行任務(wù)mb的機(jī)器人保留時間窗中,避免路徑發(fā)生沖突。如式(3)所示。

(3)

2.2 全局規(guī)劃方法

A*算法通過啟發(fā)式函數(shù)估計路徑代價,選擇最低的代價節(jié)點作為下一擴(kuò)展點。代價函數(shù)如式(4)所示:

f(n)=g(n)+h(n)

(4)

式中:f(n)為搜索節(jié)點的代價函數(shù),g(n)為實際代價,h(n)為評估代價。

站在企業(yè)發(fā)展的角度上看，企業(yè)資金是實現(xiàn)一切運(yùn)行發(fā)展的重要基礎(chǔ)前提，只有確保資金充足，才能為企業(yè)創(chuàng)造更多的機(jī)遇，進(jìn)而推進(jìn)企業(yè)規(guī)模的不斷擴(kuò)大。由此，當(dāng)代企業(yè)在實施資金管理的過程中，必須健全相關(guān)績效考核體系，以此實現(xiàn)對工作人員積極性的有效調(diào)動。在實施績效考評體系的同時，加強(qiáng)對資源消耗的考核力度，深入分析資金的使用是否存在合理性。與此同時，通過不斷完善績效考評體系，實現(xiàn)對資金管理的有效完善。

在A*算法中有兩個列表(打開和關(guān)閉)。未訪問的節(jié)點在打開列表中,已訪問的節(jié)點則在關(guān)閉列表中。

A*算法雖然簡單,便于操作,但存在路徑長、折線多、平滑性不足的問題,不適合輪式機(jī)器人的實際應(yīng)用需要。針對上述問題,進(jìn)行了啟發(fā)式函數(shù)優(yōu)化和蟻群算法結(jié)合兩個方面的改進(jìn)。

A*算法啟發(fā)式函數(shù)的改進(jìn)如式(5)所示。

f(n)=g(n)+(1+d/D)h(n)

(5)

式中:d和D分別為機(jī)器人的當(dāng)前位置和從起點位置到目標(biāo)點的距離。

為了提高A*算法的性能,本文通過蟻群算法對其進(jìn)行優(yōu)化,蟻群算法在本質(zhì)上是一種啟發(fā)式全局優(yōu)化算法,可以使改進(jìn)后A*算法規(guī)劃的全局路徑長度更短、更加平滑。

2.3 局部規(guī)劃方法

人工勢場法使用虛擬力場移動機(jī)器人,局部路徑實時性好,路徑更平滑?；驹硎峭ㄟ^虛擬勢場,機(jī)器人在力的作用下運(yùn)動。如圖2所示,障礙物對機(jī)器人施加排斥力,目標(biāo)點對機(jī)器人施加吸引力,機(jī)器人在這些作用力下移動。

圖2 人工勢場法簡圖

機(jī)器人在空間中的坐標(biāo)和目標(biāo)點的坐標(biāo)分別為Xg=[xg,yg]T和X=[x,y]T,機(jī)器人受力如

式(6)所示:

Fh=Fa(x)+Fr(x)=

(6)

式中:Fh、Fa、Fr分別為機(jī)器人所受合力、吸引力和排斥力;ρ為機(jī)器人與障礙物的相對距離,ρ=|Xg-X|;ρ0為斥力場的作用范圍;k1、η為增益系數(shù)。

理論上,整個空間勢場的最小值點是目標(biāo)點,但在障礙物分布復(fù)雜的區(qū)域,因機(jī)器人受到的合力為0而無法識別,勢場下降到最小點。在實際應(yīng)用中,擁擠的障礙物會改變機(jī)器人移動時施加在機(jī)器人上的力,導(dǎo)致路徑振動、搖晃或無法向前移動。本文從勢場修正和引入逃逸因子兩個方面進(jìn)行優(yōu)化。

斥力勢場修正函數(shù)如式(7)所示:

(7)

式中:Urg為修正后斥力勢場,m為實數(shù)(0

機(jī)器人所受斥力如式(8)所示:

(8)

式中:Fr1和Fr2分別為Fr的斥力和引力分力。

為了使輪式機(jī)器人脫離局部最小值到達(dá)目標(biāo)點,引入逃逸力,逃逸力如式(9)所示:

(9)

式中:Fesc為逃逸力的大小,方向指向目標(biāo)點,確保其在陷入局部最小值后,合力方向指向目標(biāo)位置;a、λ1和λ2為正比例系數(shù);a0為障礙物的影響范圍;aobs為局部最小值,即距離機(jī)器人最近的障礙物距離。為了將逃逸力控制在合理的范圍內(nèi),在引力方向上添加角度偏移量+mπ/2。

3 結(jié)果與分析

3.1 試驗參數(shù)

為了驗證算法的可行性和優(yōu)越性,通過試驗對全局優(yōu)化算法和混合優(yōu)化算法性能進(jìn)行分析。試驗在Linux下搭建的Hadoop實驗平臺上進(jìn)行。測試環(huán)境為10臺聯(lián)想PC機(jī)(Intel i52450m CPU、2.5 GHz主頻,8 GB內(nèi)存,512 GB硬盤)組成的集群系統(tǒng)。為了保證結(jié)果的精度,結(jié)果均為10次運(yùn)行平均值。在100 m×100 m的倉儲環(huán)境進(jìn)行仿真,試驗參數(shù)見表1。

表1 試驗參數(shù)

3.2 試驗分析

為了驗證全局規(guī)劃方法的優(yōu)越性,對文中改進(jìn)的A*算法與A*算法進(jìn)行了比較分析。設(shè)置隨機(jī)訂單數(shù)分別為100、200、500、1 000,物流機(jī)器人數(shù)為1。不同方法全局規(guī)劃隨訂單數(shù)變化的路徑長度和搜索時間結(jié)果曲線如圖3所示。

圖3 全局規(guī)劃方法結(jié)果曲線

由圖3可以看出,隨著訂單數(shù)量越來越大,需求越來越高,改進(jìn)A*算法的路徑總長和運(yùn)行時間均優(yōu)于A*算法,當(dāng)訂單數(shù)量為1 000時,改進(jìn)前后的路徑總長度和運(yùn)行時間差異達(dá)到最大,與改進(jìn)前相比,優(yōu)化后分別降低了11.28%和12.37%。這時因為只有1臺物流機(jī)器人,改進(jìn)A*算法基于云計算的分布式計算優(yōu)勢無法充分體現(xiàn)。

用本文所提方法從全局算法得到的關(guān)鍵網(wǎng)格節(jié)點序列生成全局最優(yōu)路徑節(jié)點,并加入改進(jìn)的人工勢場法進(jìn)行局部路徑的調(diào)整。將本文混合路徑規(guī)劃方法與A*算法+改進(jìn)人工勢場法進(jìn)行比較分析,設(shè)置隨機(jī)訂單數(shù)分別為100、200、500、1 000,物流機(jī)器人數(shù)為1,不同方法的混合規(guī)劃結(jié)果曲線如圖4所示。

圖4 混合路徑規(guī)劃方法結(jié)果曲線

由圖4可以看出,本文的混合路徑規(guī)劃方法隨著訂單數(shù)量的增加,路徑長度和搜索時間均優(yōu)于A*算法+改進(jìn)人工勢場法。訂單數(shù)量越多,兩種方法差異越大,訂單數(shù)量為1 000時,與改進(jìn)前相比,本文混合計劃方法在路徑長度和搜索時間上分別降低了13.05%和10.49%。雖然混合路徑規(guī)劃方法相比于全局規(guī)劃方法運(yùn)行時間長了很多,但是混合規(guī)劃方法可以降低路徑長度并提高平滑度。證明混合規(guī)劃方法是合理和有效的。

為了進(jìn)一步驗證云計算平臺對大規(guī)模物流機(jī)器人路徑規(guī)劃問題的影響,對本文所提方法與基于云計算平臺的改進(jìn)A*算法+改進(jìn)人工勢場法進(jìn)行了比較分析。選擇機(jī)器人數(shù)為1、20、60、100,對于每個機(jī)器人運(yùn)行10次,采用隨機(jī)方法,生成機(jī)器人的起點和終點,取10次的均值。根據(jù)機(jī)器人數(shù)量的不同,不同混合規(guī)劃方法運(yùn)行結(jié)果見表2。

表2 不同混合規(guī)劃方法隨機(jī)器人數(shù)量變化的運(yùn)行結(jié)果

由表4可知,在機(jī)器人數(shù)量小于20的情況下,本文方法與不加云計算的混合路徑規(guī)劃方法的性能相差不大。當(dāng)機(jī)器人數(shù)量超過20時,本文方法與不加云計算的混合路徑規(guī)劃方法相比在路徑平均長度和搜索平均時間方面的優(yōu)勢越來越明顯,當(dāng)機(jī)器人數(shù)量為100時,路徑平均長度和搜索平均時間分別降低了25.71%和8.54%。這表明,在大規(guī)模應(yīng)用機(jī)器人時,運(yùn)用分布式計算的云計算平臺可以提高本文混合路徑規(guī)劃方法的執(zhí)行效率,降低規(guī)劃路徑長度,具有一定的應(yīng)用價值。

4 結(jié)束語

本文給出的倉儲物流機(jī)器人路徑規(guī)劃方法具有較強(qiáng)的實用性,不僅加快了執(zhí)行效率,而且降低了規(guī)劃路徑長度,為倉儲物流智能化提供了一定的技術(shù)支持。但本文研究也有一定的局限性,如僅對規(guī)劃方法進(jìn)行研究,未對機(jī)器人和云計算平臺進(jìn)行深入研究。因而下一步工作的重點是不斷優(yōu)化和完善整個系統(tǒng),盡快進(jìn)行實際應(yīng)用。