精品久久一区,污黄啪啪网,16女下面流水不遮视频,色婷五月天

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

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

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

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

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

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

(2)把物流機器人看做是一個質點，暫不考慮其高度，且物流機器人可以在任意方向移動；

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 L型路徑趨勢的標識示意圖  下載原圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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