久久精品国产69国产精品亚洲_日韩欧美亚洲一区_免费观看污网站_欧美在线一

隨著電子商務(wù)的快速發(fā)展，其對倉儲業(yè)提出了更高的要求。中國物資儲運(yùn)協(xié)會會長姜浩峰指出，電商對倉儲業(yè)的需求主要體現(xiàn)在倉儲和配送兩個(gè)方面，要求倉儲實(shí)現(xiàn)快速響應(yīng)，準(zhǔn)確地入倉、完成貨位管理，快速準(zhǔn)確分揀[1]。作為智能倉儲的重要組成部分，物流機(jī)器人主要完成倉儲包裹分揀、傳輸?shù)裙ぷ鳌Ｂ窂揭?guī)劃是物流機(jī)器人導(dǎo)航過程中的一個(gè)重要環(huán)節(jié)，而物流機(jī)器人屬于移動機(jī)器人中的一種，移動機(jī)器人的路徑規(guī)劃是指機(jī)器人基于環(huán)境信息規(guī)劃出一條從起點(diǎn)到終點(diǎn)的無碰、安全的可行路徑，并盡可能地優(yōu)化路徑[2]。機(jī)器人路徑規(guī)劃的常用方法有可視圖法、人工勢場法、A*算法、人工智能算法等。智能倉儲環(huán)境下的物流機(jī)器人路徑規(guī)劃方法主要有A*算法[3]、遺傳算法[4]、蟻群算法[5,6]、強(qiáng)化學(xué)習(xí)算法[7]及算法融合[8,9,10]。其中，文獻(xiàn)[4]分別基于人工魚群算法、遺傳算法、A*算法解決倉儲系統(tǒng)中多機(jī)器人小車路徑規(guī)劃問題，結(jié)果表明，在多機(jī)器人倉儲系統(tǒng)路徑規(guī)劃中，改進(jìn)A*算法完成所有任務(wù)的時(shí)間最短，總的路徑步數(shù)也最少。

A*算法是Dijikstra算法的一個(gè)擴(kuò)展，它利用等代價(jià)搜索和啟發(fā)式搜索來有效地計(jì)算最佳優(yōu)先搜索，使用的時(shí)間更少[11]。文獻(xiàn)[12]針對倉儲物流中移動機(jī)器人的多任務(wù)調(diào)度問題，提出復(fù)雜對角線距離算法，改進(jìn)A*算法的啟發(fā)函數(shù)，實(shí)現(xiàn)調(diào)度系統(tǒng)中移動機(jī)器人的總?cè)蝿?wù)完工時(shí)間最短，但規(guī)劃之后的路徑仍存在冗余節(jié)點(diǎn)。針對A*算法規(guī)劃出的移動機(jī)器人路徑存在折線多、轉(zhuǎn)折次數(shù)多、累計(jì)轉(zhuǎn)折角度大等問題，研究者們主要提出了平滑路徑的解決方案。例如，文獻(xiàn)[13]在A*算法的初始路徑規(guī)劃的基礎(chǔ)上，遍歷路徑中的所有節(jié)點(diǎn)，刪除冗余節(jié)點(diǎn)，建立平滑A*模型，以極低的計(jì)算時(shí)間損失有效地降低移動機(jī)器人規(guī)劃路徑的長度、轉(zhuǎn)折次數(shù)和轉(zhuǎn)折角度,適用于復(fù)雜環(huán)境的路徑規(guī)劃。而文獻(xiàn)[14]在A*算法的初始路徑的基礎(chǔ)上，通過劃分路徑步長、刪除冗余路徑節(jié)點(diǎn)的方法，有效地減小路徑長度和轉(zhuǎn)折角度，適合多任務(wù)點(diǎn)、高障礙率環(huán)境下的移動機(jī)器人路徑規(guī)劃。但智能倉儲環(huán)境與一般機(jī)器人的工作環(huán)境大不相同，倉儲環(huán)境中布滿貨架，物流機(jī)器人的可行空間有限，障礙物形狀規(guī)則，因此，智能倉儲環(huán)境下的物流機(jī)器人的路徑規(guī)劃有別于一般移動機(jī)器人。對于智能倉儲物流機(jī)器人而言，不僅要求規(guī)劃的路徑最短，同時(shí)，也要求轉(zhuǎn)折角度小，轉(zhuǎn)折次數(shù)少，從而便于物流機(jī)器人的運(yùn)行控制和安全作業(yè)。文獻(xiàn)[15]在A*算法的基礎(chǔ)上進(jìn)行改進(jìn)，在代價(jià)函數(shù)中加入轉(zhuǎn)向代價(jià)和路徑?jīng)_突代價(jià)，實(shí)現(xiàn)多物流機(jī)器人的路徑規(guī)劃，但具體的代價(jià)值比較難確定。

綜上，針對A*算法規(guī)劃的路徑存在轉(zhuǎn)折點(diǎn)和冗余點(diǎn)過多的問題，現(xiàn)有的研究主要采用刪除冗余節(jié)點(diǎn)的路徑平滑方法，較少考慮智能倉儲環(huán)境的特殊性。因此，本文首先探索了A*算法中不同啟發(fā)式距離函數(shù)對智能倉儲環(huán)境下路徑規(guī)劃的適用性；其次，針對A*算法在路徑規(guī)劃中存在較多轉(zhuǎn)折的問題，提出一種適用于智能倉儲環(huán)境路徑規(guī)劃的L型路徑趨勢的改進(jìn)A*算法。

智能倉儲系統(tǒng)一般由揀選工作臺、貨架、物流機(jī)器人等組成，對于物流機(jī)器人而言，揀選工作臺、貨架、其他物流機(jī)器人等都是障礙物。

為便于研究且不失一般性，本文在智能倉儲系統(tǒng)的環(huán)境建模時(shí)做出以下合理假設(shè)：

(1)揀選工作臺、貨柜等障礙物邊界是在實(shí)際邊界的基礎(chǔ)上加一個(gè)物流機(jī)器人安全距離；

(2)把物流機(jī)器人看做是一個(gè)質(zhì)點(diǎn)，暫不考慮其高度，且物流機(jī)器人可以在任意方向移動；

(3)在路徑規(guī)劃過程中，倉儲環(huán)境信息不變。

常用的環(huán)境建模方法有幾何法、可視圖法和柵格法等。柵格法是將環(huán)境分割成大小相等的方格單元的一種建模方法，被廣泛用于描述二維信息，具有簡單有效的特點(diǎn)，因此，本文采用柵格法進(jìn)行智能倉儲環(huán)境的建模，同時(shí)以經(jīng)典物流系統(tǒng)———KIVA系統(tǒng)中的倉儲布局模式為參考，建立了一個(gè)51×16的柵格化智能倉儲環(huán)境（如圖1所示，在實(shí)際應(yīng)用中，可以根據(jù)實(shí)際需要設(shè)定智能倉儲環(huán)境的規(guī)模和貨架布局）。其中，紫色矩形為揀選工作臺，黑色矩形為貨架，青色小方格為障礙物（其他物流機(jī)器人等），紅色為起始位置，藍(lán)色為目標(biāo)位置（目標(biāo)貨架），白色為通道。

本文設(shè)計(jì)基于改進(jìn)A*算法求解智能倉儲環(huán)境下，物流機(jī)器人從起始位置到目標(biāo)位置的無碰撞最優(yōu)路徑。

圖1 智能倉儲環(huán)境的模型  下載原圖

A*算法由Dijkstra算法演變而來，是一種啟發(fā)式算法。A*算法通過估價(jià)函數(shù)引導(dǎo)和決定路徑的搜索方向。從起點(diǎn)開始搜索當(dāng)前位置相鄰的8個(gè)周圍節(jié)點(diǎn)，由估價(jià)函數(shù)表示每個(gè)節(jié)點(diǎn)的價(jià)值，選擇價(jià)值最低的節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn)，循環(huán)這一過程直到到達(dá)終點(diǎn)停止搜索，從而獲得最終的路徑規(guī)劃結(jié)果。因?yàn)槊看嗡阉鞫歼x擇價(jià)值最低的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，因此，最終獲得的路徑代價(jià)是最低的。

A*算法的估價(jià)函數(shù)f(n)表示如式（1):

其中:f(n)表示從起始位置經(jīng)過節(jié)點(diǎn)n到達(dá)終點(diǎn)的估價(jià)函數(shù)；g(n)表示從起始位置到節(jié)點(diǎn)n的實(shí)際代價(jià)函數(shù)；h(n)表示從節(jié)點(diǎn)n到終點(diǎn)的估計(jì)代價(jià)函數(shù)。

通常，估計(jì)代價(jià)函數(shù)h(n)可以使用歐幾里得距離或曼哈頓距離作為啟發(fā)函數(shù)，因?yàn)槁D距離只涉及加、減法，和歐式距離相比較，節(jié)約算法的運(yùn)行時(shí)間，提高算法效率。相比于一般移動機(jī)器人的工作環(huán)境，智能倉儲環(huán)境中布滿貨架，曼哈頓距離顯然更適用。因此，本文采用曼哈頓距離作為節(jié)點(diǎn)間的啟發(fā)函數(shù)，即

其中：（xd,yd）為目標(biāo)位置的坐標(biāo)；（xn,yn）是節(jié)點(diǎn)n的坐標(biāo)。

A*算法在搜索路徑過程中，需要不斷更新兩個(gè)列表，一個(gè)是開啟列表，另一個(gè)是關(guān)閉列表。開啟列表存儲所有周圍的節(jié)點(diǎn)。A*算法從開啟列表中選擇估價(jià)值最小的節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn)。關(guān)閉列表存儲所有經(jīng)過的節(jié)點(diǎn)和環(huán)境中的障礙物所在節(jié)點(diǎn)。

通過A*算法計(jì)算，得到智能倉儲物流機(jī)器人的初始路徑規(guī)劃。

傳統(tǒng)A*算法計(jì)算的路徑類似“鋸齒形”路徑，存在轉(zhuǎn)折過多，轉(zhuǎn)彎過多的問題。智能倉儲環(huán)境不同于一般的移動機(jī)器人所處的環(huán)境，智能倉儲環(huán)境中障礙物主要是貨架、揀選工作臺、隨機(jī)障礙物等，這些障礙物都是規(guī)則、有序且相對固定，輪廓近似矩形。與此同時(shí)，智能倉儲環(huán)境中的通道規(guī)則且狹窄，可行空間相對有限，因此，“鋸齒形”路徑主要出現(xiàn)在揀選工作臺附近的局部區(qū)域。從起始位置S到目標(biāo)位置T形成的最終路徑可以近似看做是L趨勢，當(dāng)各部分路徑都和該L趨勢一致時(shí)，則該路徑的轉(zhuǎn)彎節(jié)點(diǎn)最少。

本文根據(jù)起始位置S與目標(biāo)位置T的幾何關(guān)系，構(gòu)造4種L型路徑趨勢的標(biāo)識，分別為L1（實(shí)線）、L2（實(shí)線）、L3（實(shí)線）和L4（實(shí)線）。

圖2 L型路徑趨勢的標(biāo)識示意圖  下載原圖

路徑趨勢標(biāo)識的構(gòu)建方法。以L1型路徑趨勢標(biāo)識為例，起始位置S在目標(biāo)位置T的左下方，延長S、T所在直線構(gòu)成直角（D），構(gòu)建L1型路徑趨勢標(biāo)識。同樣地，S在T左上方時(shí)，構(gòu)建L2型路徑趨勢標(biāo)識；S在T右上方時(shí)，構(gòu)建L3型路徑趨勢標(biāo)識；S在T右下方時(shí)，構(gòu)建L4型路徑趨勢標(biāo)識。

路徑趨勢標(biāo)識的使用方法。在A*算法規(guī)劃出初始路徑之后，依據(jù)“盡可能使局部路徑與S、T構(gòu)成的路徑趨勢一致”的原則，通過路徑趨勢標(biāo)識進(jìn)行優(yōu)化。具體規(guī)則如下：局部路徑中，鄰近的3個(gè)節(jié)點(diǎn)（k-1、k、k+1）構(gòu)成L型鏈路時(shí)，判斷其與當(dāng)前L型路徑趨勢標(biāo)識是否匹配（依據(jù)：局部鏈路的L型與S、T構(gòu)成的路徑趨勢標(biāo)識L剛好組成一個(gè)回路）；如果匹配，判斷局部鏈路中間節(jié)點(diǎn)k的對角節(jié)點(diǎn)D（組成回路的對角）是否為障礙物，如果不是障礙物，則將對角節(jié)點(diǎn)D替換該節(jié)點(diǎn)k。

以L1型路徑趨勢標(biāo)識的優(yōu)化為例。當(dāng)前，S與T構(gòu)成L1型路徑趨勢，初始路徑中局部路徑k-1、k、k+1三個(gè)節(jié)點(diǎn)構(gòu)成的鏈路（綠色點(diǎn)劃線所示），呈現(xiàn)出L型形狀，（從S、k-1、k、k+1、T路徑出現(xiàn)了鋸齒形狀，存在3個(gè)轉(zhuǎn)彎），因此需要進(jìn)行優(yōu)化。現(xiàn)判斷D節(jié)點(diǎn)是否為障礙物（揀選工作臺、貨架、其他障礙物等），如果是，則不處理；如果否，則節(jié)點(diǎn)k替換成節(jié)點(diǎn)D。此時(shí)，鏈路變成S、k-1、D、k+1、T，該鏈路中，只有1個(gè)轉(zhuǎn)彎，從而，減少了轉(zhuǎn)彎的節(jié)點(diǎn)，使路徑變得平滑。其他L型路徑趨勢標(biāo)識的優(yōu)化方法以此類推。

基于A*算法的智能倉儲物流機(jī)器人的L型路徑優(yōu)化流程如圖3。

本文通過MATLAB2015軟件（Math Works公司）對所提出的基于改進(jìn)A*算法的智能倉儲物流機(jī)器人的路徑規(guī)劃進(jìn)行仿真驗(yàn)證。首先設(shè)置智能倉儲環(huán)境，包括倉儲邊界、貨架、揀選工作臺、物流機(jī)器人初始位置和目標(biāo)位置、隨機(jī)障礙物位置等信息。其中，起始位置S的柵格坐標(biāo)為（5,6），目標(biāo)位置的柵格坐標(biāo)為（25,11）。其次，設(shè)計(jì)A*算法求解從起始位置到目標(biāo)位置的初始規(guī)劃路徑。

為探索曼哈頓距離與文獻(xiàn)[12]提出的復(fù)雜對角線距離對智能倉儲環(huán)境路徑規(guī)劃的適應(yīng)性，本文分別求解基于以上兩種距離公式的A*算法初始路徑。結(jié)果如圖4～5所示。

圖3 基于改進(jìn)A*算法的智能倉儲物流機(jī)器人的路徑規(guī)劃流程圖  下載原圖

圖4 基于復(fù)雜對角線距離A*算法的智能倉儲物流機(jī)器人的初始路徑規(guī)劃結(jié)果  下載原圖

圖5 基于曼哈頓距離A*算法的智能倉儲物流機(jī)器人的初始路徑規(guī)劃結(jié)果  下載原圖

圖中灰色表示已訪問的柵格，灰白色代表在訪問列表中。圖4中點(diǎn)實(shí)線表示基于文獻(xiàn)[12]提出的復(fù)雜對角線距離公式獲得的A*算法初始路徑，圖5中點(diǎn)實(shí)線表示基于曼哈頓距離公式獲得的A*算法初始路徑。觀察發(fā)現(xiàn)，兩種距離公式最終規(guī)劃出的路徑一致，均成功避免了與貨架等障礙物相碰，并且找到了從起始位置到目標(biāo)位置的規(guī)劃路徑。

表1 基于不同距離A*算法的智能倉儲物流機(jī)器人的初始路徑規(guī)劃結(jié)果  下載原圖

表1 基于不同距離A*算法的智能倉儲物流機(jī)器人的初始路徑規(guī)劃結(jié)果

表1的數(shù)據(jù)說明，基于文獻(xiàn)[12]中的復(fù)雜對角線距離公式獲得的A*算法初始路徑與基于曼哈頓距離獲得的A*算法初始路徑總長度一致，都是25單位長度，但前者算法運(yùn)行時(shí)間為7.46 s，后者運(yùn)行時(shí)間為7.23 s。這個(gè)結(jié)果表明，對于智能倉儲環(huán)境，曼哈頓距離在算法運(yùn)行時(shí)間上更有優(yōu)勢。因此，本文在改進(jìn)A*算法時(shí)采用曼哈頓距離公式。

進(jìn)一步觀察以上兩條初始路徑，可以發(fā)現(xiàn)，A*算法求解的初始路徑中有5個(gè)轉(zhuǎn)折，路徑不夠平滑。

在實(shí)驗(yàn)中，分別用平滑A*算法和本文提出的L型路徑趨勢標(biāo)識對A*算法獲得的初始路徑進(jìn)行優(yōu)化。首先參考文獻(xiàn)[13]的平滑A*算法，在A*算法初始規(guī)劃路徑的基礎(chǔ)上，遍歷所有節(jié)點(diǎn)，若某一節(jié)點(diǎn)的前一節(jié)點(diǎn)與后一節(jié)點(diǎn)連線未經(jīng)過障礙物，則剔除本中間節(jié)點(diǎn)，從而減少轉(zhuǎn)折節(jié)點(diǎn)和轉(zhuǎn)彎過多的問題。結(jié)果如圖6所示。

圖6 基于平滑A*算法的智能倉儲物流機(jī)器人的路徑規(guī)劃結(jié)果  下載原圖

其中o-實(shí)線表示采用平滑A*算法獲得的從起始位置S到目標(biāo)貨架T的優(yōu)化路徑。

其次，采用本文構(gòu)造的L型路徑趨勢標(biāo)識對A*算法初始路徑中的局部路徑進(jìn)行優(yōu)化，結(jié)果如圖7所示。

圖7 基于L型路徑趨勢改進(jìn)A*算法的智能倉儲物流機(jī)器人的路徑規(guī)劃結(jié)果  下載原圖

其中*線表示采用L型路徑趨勢標(biāo)識優(yōu)化后的從起始位置S到目標(biāo)貨架T的優(yōu)化路徑。

A*算法改進(jìn)前后智能倉儲物流機(jī)器人的路徑規(guī)劃結(jié)果比較見表2。

表2 A*算法改進(jìn)前后智能倉儲物流機(jī)器人的路徑規(guī)劃結(jié)果比較  下載原圖

表2 A*算法改進(jìn)前后智能倉儲物流機(jī)器人的路徑規(guī)劃結(jié)果比較

與A*算法規(guī)劃的初始路徑比較可以發(fā)現(xiàn)，平滑A*算法中，路徑長度較初始路徑減少8.7%；轉(zhuǎn)折節(jié)點(diǎn)減少2個(gè)，減少率為40%；累計(jì)轉(zhuǎn)彎角度減少225°，減少率為50%，即在一定程度上達(dá)到了減少路徑總長度、轉(zhuǎn)折節(jié)點(diǎn)數(shù)和累計(jì)轉(zhuǎn)彎角度的效果。與A*算法初始路徑比較，L型路徑趨勢改進(jìn)A*算法，其路徑總長度沒有減少，但轉(zhuǎn)折節(jié)點(diǎn)減少3個(gè)，減少率為60%；累計(jì)轉(zhuǎn)彎角度減少270°，減少率為60%。L型路徑趨勢改進(jìn)A*算法減少轉(zhuǎn)彎節(jié)點(diǎn)率較平滑A*算法高20%,L型路徑趨勢改進(jìn)A*算法減少轉(zhuǎn)彎角度率較平滑A*算法高10%，對于布滿貨架、可行空間有限的智能倉儲系統(tǒng)環(huán)境而言，相較于路徑總長度的減少，對減少轉(zhuǎn)彎次數(shù)和轉(zhuǎn)彎角度的需求更迫切，一方面便于控制物流機(jī)器人的轉(zhuǎn)向，另一方面，更有利于作業(yè)安全。與此同時(shí)，L型路徑趨勢改進(jìn)A*算法的運(yùn)行時(shí)間較平滑A*算法運(yùn)行時(shí)間短，在大規(guī)模智能倉儲環(huán)境的路徑規(guī)劃中，算法運(yùn)行時(shí)間短顯然更有優(yōu)勢。

本文建立了柵格化的智能倉儲環(huán)境。采用A*算法求解智能倉儲物流機(jī)器人的路徑規(guī)劃，獲得了一條從起始位置到終點(diǎn)位置的無碰撞安全路徑。仿真實(shí)驗(yàn)結(jié)果表明，與文獻(xiàn)[12]提出的復(fù)雜對角線距離比較，曼哈頓距離更適用于智能倉儲環(huán)境的路徑規(guī)劃。針對A*算法求解最優(yōu)路徑時(shí)存在轉(zhuǎn)折點(diǎn)過多和轉(zhuǎn)彎角度過大的問題，提出了一種基于起始位置與目標(biāo)位置構(gòu)建的L型路徑趨勢方法對A*算法規(guī)劃的初始路徑進(jìn)行局部優(yōu)化。仿真實(shí)驗(yàn)表明，L型路徑趨勢局部優(yōu)化方法能夠以微小的算法運(yùn)行時(shí)間為代價(jià)有效地減少A*算法規(guī)劃路徑中的轉(zhuǎn)折次數(shù)和累計(jì)轉(zhuǎn)彎角度，使物流機(jī)器人的路徑趨向于總體路徑方向，路徑更加平滑，有效提高倉儲的作業(yè)安全和效率。本文研究的是智能倉儲環(huán)境中物流機(jī)器人的全局路徑規(guī)劃問題，將來，可以在此基礎(chǔ)上考慮動態(tài)障礙物及避碰策略，更加有效地對物流機(jī)器人進(jìn)行協(xié)同調(diào)度和路徑規(guī)劃。