周 晟，酈佳燕

(武警士官學(xué)校a.基層后勤管理系；b.基礎(chǔ)部，杭州 310000)

0 引言

近年來，高速發(fā)展下的物流行業(yè)對(duì)倉儲(chǔ)機(jī)器人的高效工作性能需求日益突顯，在庫房內(nèi)迅速找尋物資并移動(dòng)至出庫工位或操作工位的時(shí)間節(jié)制了物流工作的整體效率，因此，倉儲(chǔ)機(jī)器人路徑規(guī)劃研究具有十分重要的意義，亦是現(xiàn)代機(jī)器人研究的重要方向。

趙克新等[1]引入混沌算子改良算法中螞蟻的隨機(jī)游走后，有效結(jié)合蟻獅構(gòu)造全局搜索和局部搜索并行的雙線模式，面對(duì)復(fù)雜環(huán)境下的航線最優(yōu)化設(shè)計(jì)具有良好的應(yīng)用，有效提升算法尋優(yōu)能力。張煥龍等[2]將模擬退火算法與蟻獅優(yōu)化算法有機(jī)結(jié)合，合理利用邊界收縮機(jī)制和螞蟻與蟻獅之間的聯(lián)系，以提升圖像匹配效率、匹配精度。后采用局部嵌入準(zhǔn)則進(jìn)行評(píng)估，切換搜索策略，實(shí)驗(yàn)驗(yàn)證，改進(jìn)算法優(yōu)化效率高、匹配速度快、匹配精度高。趙小國等[3]采用動(dòng)態(tài)隨機(jī)搜索策略并改良搜索半徑的收縮機(jī)制后，應(yīng)用于T-S模糊辨識(shí)中含噪聲的非線性系統(tǒng)問題，仿真驗(yàn)證時(shí)噪聲被有效抑制，改進(jìn)方法具優(yōu)良效用。

針對(duì)物流行業(yè)倉儲(chǔ)機(jī)器人工作效率問題，文中提出一種改進(jìn)蟻獅算法，將傳統(tǒng)的時(shí)間最優(yōu)化設(shè)計(jì)轉(zhuǎn)換為倉儲(chǔ)機(jī)器人運(yùn)行中，路徑最短且轉(zhuǎn)彎次數(shù)最少的多目標(biāo)路徑規(guī)劃問題，以保證工作運(yùn)行效率的同時(shí)，使得倉儲(chǔ)機(jī)器人運(yùn)行更加平穩(wěn)[4-5]。文中采用柵格法劃分工作環(huán)境，合理設(shè)定目標(biāo)函數(shù)、約束條件后，通過優(yōu)化算法實(shí)現(xiàn)路徑規(guī)劃，結(jié)合MATLAB進(jìn)行仿真分析，驗(yàn)證算法的有效性，為后續(xù)研究提供理論支撐。

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

1.1 問題描述

設(shè)定在智能庫房中，倉儲(chǔ)機(jī)器人在接受任務(wù)后，從初始點(diǎn)出發(fā)規(guī)避障礙物后到達(dá)任務(wù)點(diǎn)完成工作任務(wù)，在完成過程中要求行徑路線實(shí)現(xiàn)路徑最短且轉(zhuǎn)彎次數(shù)最少，并假定：

(1)智能庫房平面地圖已知；

(2)柵格分為可通過柵格和不可通過柵格；

(3)倉儲(chǔ)機(jī)器人工況良好；

(4)任務(wù)初始點(diǎn)和結(jié)束點(diǎn)位置已知。

1.2 模型構(gòu)建

文中設(shè)定庫房內(nèi)工作環(huán)境為靜態(tài)，障礙物靜止不動(dòng)不存在外界干擾，以倉儲(chǔ)機(jī)器人在庫房工作時(shí)，轉(zhuǎn)彎次數(shù)最少和路徑最短為目標(biāo)，結(jié)合柵格法構(gòu)建工作環(huán)境模型和多目標(biāo)路徑規(guī)劃求解函數(shù)式。

1.2.1 環(huán)境模型構(gòu)建

柵格法可以將路徑規(guī)劃問題轉(zhuǎn)變?yōu)槁窂酵緩近c(diǎn)的集合，利用相應(yīng)算法在柵格中找尋最優(yōu)解的方法。由于柵格法建模簡單，能夠最大程度地反映庫房內(nèi)實(shí)際障礙物情況，因此文中采用柵格法構(gòu)建工作環(huán)境模型示意圖，如圖1所示。

圖1 工作環(huán)境模型示意圖

倉儲(chǔ)機(jī)器人在柵格中的運(yùn)行方向如圖2所示。

圖2 倉儲(chǔ)機(jī)器人運(yùn)行方向示意圖

為降低計(jì)算量、優(yōu)化柵格模型，設(shè)定柵格的每一個(gè)長度為一個(gè)單位長度，黑色柵格為障礙柵格，白色柵格為可通過柵格，S為柵格序號(hào)，L為柵格邊長，柵格序號(hào)與柵格中心坐標(biāo)對(duì)應(yīng)關(guān)系如式(1)：

(1)

1.2.2 轉(zhuǎn)彎次數(shù)最少目標(biāo)函數(shù)

設(shè)dn表示第n個(gè)節(jié)點(diǎn)上的轉(zhuǎn)彎次數(shù)，N(d)表示路徑轉(zhuǎn)彎次數(shù)的求和，k為斜率，n為路徑途徑的柵格中心坐標(biāo)順序序列號(hào)，(xn,yn)，(xn+1,yn+1)分別為路徑通過的相鄰柵格中心點(diǎn)的坐標(biāo)[6-7]。倉儲(chǔ)機(jī)器人運(yùn)行穩(wěn)定性由轉(zhuǎn)彎次數(shù)決定，轉(zhuǎn)彎次數(shù)越少，運(yùn)行越平穩(wěn)，目標(biāo)函數(shù)如式(2)所示。

(2)

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

倉儲(chǔ)機(jī)器人運(yùn)行路徑的距離決定工作效率的高低，為提升物流工作的整體效率，設(shè)定起、止點(diǎn)條件下，求解最短行進(jìn)路徑，其目標(biāo)函數(shù)如式(3)：

(3)

式中，L(P)表示最短路徑之和，L(Pi,Pi+1)為點(diǎn)Pi至Pi+1之間的距離，(xi,yi)，(xi+1,yi+1)分別為轉(zhuǎn)向點(diǎn)在空間中，當(dāng)前柵格中心點(diǎn)的坐標(biāo)和下一個(gè)點(diǎn)的坐標(biāo)，N(d)為轉(zhuǎn)向的次數(shù)。

1.2.4 效用函數(shù)

文中通過線性加權(quán)與效用函數(shù)Z(L,N)將轉(zhuǎn)彎次數(shù)最少目標(biāo)函數(shù)與路徑最短目標(biāo)函數(shù)建立聯(lián)系，轉(zhuǎn)換為傳統(tǒng)的多目標(biāo)求解問題，使得求解結(jié)果同時(shí)滿足路徑最短和轉(zhuǎn)彎次數(shù)最少。其中，效用函數(shù)公式如式(4)：

Z(L,N)=ω1L(P)+ω2N(d)

(4)

式中，ω1是路徑長度權(quán)重系數(shù)，ω2是轉(zhuǎn)彎次數(shù)權(quán)重系數(shù)，L(P)表示最短路徑的求和，N(d)為轉(zhuǎn)向次數(shù)的求和。

2 蟻獅算法

蟻獅優(yōu)化算法是通過觀察自然界中蟻獅的捕獵行為所提出的一種新型智能優(yōu)化算法，算法中包含蟻獅、精英蟻獅和螞蟻3個(gè)個(gè)體[8-11]。首先，蟻獅和螞蟻的位置以隨機(jī)方式初始化，再通過輪盤賭和隨機(jī)游走的策略確定螞蟻的位置，算法優(yōu)化過程中，螞蟻的游走會(huì)受到邊界和蟻獅陷阱的影響并采用適應(yīng)度函數(shù)對(duì)所有的游走螞蟻進(jìn)行評(píng)估、迭代。設(shè)定每一輪迭代中最優(yōu)解的蟻獅稱為精英蟻獅，優(yōu)化過程中將精英蟻獅不斷與最優(yōu)解的蟻獅進(jìn)行比較，循環(huán)計(jì)算求解最優(yōu)個(gè)體。

文中采用式(5)模擬螞蟻的隨機(jī)游走。

X(t)=[0，cs(2r(t1)-1)，…，cs(2r(tn)-1)]

(5)

式中，cs表示計(jì)算累計(jì)和，n表示最大迭代次數(shù)，t表示隨機(jī)游走的步驟，r(t)表示隨機(jī)函數(shù)。

算法優(yōu)化中，螞蟻依據(jù)隨機(jī)游走更新迭代位置參數(shù)，但是搜索空間存在邊界限制，所以式(5)無法直接更新螞蟻的位置參數(shù)，需采用式(6)對(duì)其進(jìn)行歸一化處理。

(6)

文中采用式(7)和式(8)計(jì)算蟻獅陷阱對(duì)螞蟻隨機(jī)游走狀態(tài)的影響。

(7)

(8)

為規(guī)避局部最優(yōu)解，在優(yōu)化過程中，蟻獅算法采用輪盤賭算子和適應(yīng)度函數(shù)相結(jié)合進(jìn)行蟻獅選擇，精英蟻獅的設(shè)定是算法優(yōu)化的重要設(shè)定，確保優(yōu)化的任意階段均可獲取最優(yōu)解。鑒于精英蟻獅對(duì)螞蟻迭代時(shí)隨機(jī)游走的干擾，文中假定任意一只螞蟻在選定蟻獅周圍隨機(jī)地通過輪盤賭或隨機(jī)游走進(jìn)行行走，如式(9)所示。

(9)

當(dāng)螞蟻陷入陷阱時(shí)，蟻獅將自主減少陷阱，此時(shí)螞蟻隨機(jī)游走搜索半徑將自適應(yīng)地縮小，隨著迭代次數(shù)的持續(xù)增加，蟻獅陷阱和精英蟻獅的設(shè)定將不斷收縮邊界條件，逐漸求解全局最優(yōu)解。

(10)

(11)

式中，I隨迭代次數(shù)的增加分線段性遞增。

(12)

式中，t表示當(dāng)前迭代次數(shù)，T表示最大迭代次數(shù)，w取決于當(dāng)前代數(shù)。

最后階段，當(dāng)螞蟻具有更優(yōu)位置參數(shù)時(shí)，蟻獅捕獲螞蟻并依據(jù)等式(13)進(jìn)行位置參數(shù)更新。

(13)

3 改進(jìn)的蟻獅算法

針對(duì)傳統(tǒng)算法的局限性，文中引入混沌序列增強(qiáng)種群的均勻性和遍歷性，依據(jù)螞蟻的游走行為采用隨機(jī)分形搜索策略，增強(qiáng)算法探索能力，采用自適應(yīng)邊界策略改善螞蟻游走時(shí)邊界趨同情況，提高算法開發(fā)能力。

3.1 混沌序列種群初始化

螞蟻的位置信息保存在位置矩陣MAnt中，Ai,j表示第i個(gè)螞蟻第j維的位置值，適度值fi保存在矩陣MOA中，蟻獅的位置信息保存在矩陣MAntlion中，ALi,j為第i個(gè)蟻獅第j維的位置值，蟻獅的適應(yīng)度fLi保存在矩陣MOAL中。

(14)

(15)

(16)

(17)

算法優(yōu)化設(shè)計(jì)時(shí)考慮到立方映射產(chǎn)生混沌變量的均勻性優(yōu)良，為規(guī)避算法陷入早熟獲取結(jié)果為局部最優(yōu)，文中采用立方映射方法進(jìn)行螞蟻和蟻獅的初始位置信息設(shè)置。初期階段，先產(chǎn)生一個(gè)隨機(jī)初始序列x，元素范圍均在[0,1]之間，代入立方映射式(18)生成混沌序列。

(18)

式(18)在初始值不為零時(shí)求解序列真實(shí)有效，且既能求解螞蟻位置信息Ai,j，又可以求解蟻獅的位置信息ALi,j，求解計(jì)算后由式(19)映射返回求解空間。

(19)

式中，x*表示返回求解空間后賦給螞蟻或蟻獅個(gè)體的數(shù)值；ub、lb表示求解空間的上、下邊界。

隨機(jī)游走更新目標(biāo)數(shù)值時(shí)，以當(dāng)前最優(yōu)個(gè)體與全局最優(yōu)個(gè)體為目標(biāo)進(jìn)行求解，計(jì)算公式如式(20)所示。

(20)

(21)

(22)

3.2 隨機(jī)分形搜索方程

萊維飛行是服從萊維分布的隨機(jī)搜索方法，其位置更新如式(23)所示。

(23)

式中，Levy(λ)表示服從萊維分布的路徑，1<λ≤3；xi(t)表示第t代的第i個(gè)解；l表示控制步長的權(quán)重，xb表示當(dāng)前的最優(yōu)解。

目前常采用Mantegan算法模擬求解過程，降低萊維分布計(jì)算難度，步長計(jì)算公式如式(24)所示，仿真結(jié)果如圖3所示。

(24)

圖3 萊維飛行仿真結(jié)果示意圖

文中將萊維飛行與螞蟻的搜索策略相結(jié)合，構(gòu)建隨機(jī)分形搜索方程，如式(25)所示。

(25)

式中，q表示種群數(shù)量；a表示比例因子；Ai表示最初的螞蟻位置。

3.3 自適應(yīng)邊界策略

結(jié)合式(10)～式(12)可知，螞蟻圍繞蟻獅的邊界由I值決定且同一輪迭代時(shí)趨同的邊界降低了算法的多樣性，不利于全局最優(yōu)解的獲取，文中提出自適應(yīng)邊界策略用以提升螞蟻圍繞蟻獅游走的多樣性，計(jì)算公式如式(26)所示。

(26)

式中，rand為(0,1)內(nèi)均勻分布的隨機(jī)數(shù)。

3.4 改進(jìn)的蟻獅算法流程

步驟1：設(shè)定最大迭代次數(shù)為M；螞蟻個(gè)體數(shù)目與蟻獅個(gè)體數(shù)目均為N，維數(shù)為D；求解空間的上界為ub與下界為lb；

步驟2：根據(jù)式(18)～式(20)混沌初始化螞蟻和蟻獅的位置數(shù)值，由矩陣MAnt和MAntlion分別儲(chǔ)存，矩陣MOA和MOAL分別儲(chǔ)存螞蟻與蟻獅的適應(yīng)度值；

步驟3：排序適應(yīng)度值，選取初代精英蟻獅；

步驟4：根據(jù)式(10)、式(11)更新當(dāng)前迭代次數(shù)中，所有螞蟻隨機(jī)游走的最大值和最小值ci、di；

步驟6：根據(jù)式(9)、式(25)采用隨機(jī)分形搜索策略更新螞蟻個(gè)體位移數(shù)值并求出所有個(gè)體的適應(yīng)度值；

步驟7：判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到，則循環(huán)結(jié)束并輸出精英個(gè)體，若未達(dá)到，返回步驟3。

改進(jìn)的蟻獅算法流程圖如圖4所示。

圖4 改進(jìn)算法流程圖

4 仿真驗(yàn)證

為測試算法的尋優(yōu)性能，文中設(shè)定螞蟻和蟻獅的種群規(guī)模數(shù)均為50，最大迭代次數(shù)為200，搜索維度D=10,20，c1=0.4，c2=0.6，起始點(diǎn)、終止點(diǎn)等初始參數(shù)值后，對(duì)多個(gè)障礙物位置不同的庫房環(huán)境進(jìn)行仿真驗(yàn)證，其結(jié)果如圖5所示。

(a) 狹小空間路徑規(guī)劃 (b) 有一定空間的路徑規(guī)劃

(c) 收斂曲線變化趨勢圖5 倉儲(chǔ)機(jī)器人路徑規(guī)劃仿真

圖5a中倉儲(chǔ)機(jī)器人能夠穿過狹小的軌跡空間找尋目的地，其收斂曲線趨于平穩(wěn)的迭代次數(shù)少，均表明改進(jìn)蟻獅算法具有良好的優(yōu)化性能，適用于庫房內(nèi)的狹小空間，高效地完成物資堆垛工作。圖5b中倉儲(chǔ)機(jī)器人能夠避免在上部區(qū)域內(nèi)以較長的路徑軌跡運(yùn)行到目的地，有效在下部區(qū)域通過較短的路徑軌跡，找尋目的地完成物資堆垛工作，其收斂變化曲線在初始階段經(jīng)過一定的震蕩后，能夠迅速穩(wěn)定趨于一定的空間范圍，表明改進(jìn)算法具有迅速的判斷、尋優(yōu)能力，迅速找尋路徑運(yùn)行方向，有效節(jié)約時(shí)間，提高算法的工作效率。

5 結(jié)論

文中以倉儲(chǔ)機(jī)器人物資堆垛為例，借助MATLAB軟件結(jié)合柵格法，構(gòu)造物資堆垛運(yùn)行軌跡示意圖，提出一種改進(jìn)蟻獅算法，以轉(zhuǎn)彎次數(shù)最少、路徑最短為目標(biāo)函數(shù)，得到結(jié)論如下：

文中根據(jù)螞蟻的游走行為，采用隨機(jī)分形自適應(yīng)搜索策略，增強(qiáng)算法的探索能力。根據(jù)螞蟻游走的邊界都完全相同，降低了算法的多樣性，不利于算法尋找全局最優(yōu)解，提出自適應(yīng)邊界策略，提高游走的隨機(jī)性和多樣性，增強(qiáng)算法的開發(fā)能力和全局搜索能力，有利于找到全局最優(yōu)解。