基于響應(yīng)動態(tài)約束條件的倉儲AGV路徑規(guī)劃協(xié)同優(yōu)化模型

摘"要：為了解決倉儲AGV無碰撞路徑規(guī)劃問題，設(shè)計響應(yīng)動態(tài)約束條件的倉儲AGV路徑規(guī)劃協(xié)同優(yōu)化模型。建立路徑節(jié)點模型和車體坐標(biāo)系模型，獲得倉儲AGV所在位置；建立碰撞描述模型，將全局路徑規(guī)劃問題簡化為虛線框架的局部環(huán)境，建立時間窗，分別計算空車線段的時間窗、空車轉(zhuǎn)向段的時間窗，獲得不同工況下的運輸時間。將路徑最短作為動態(tài)約束條件，采用目標(biāo)規(guī)劃法對生成的多條路徑求解，處理沖突問題，實現(xiàn)倉儲AGV路徑規(guī)劃協(xié)同優(yōu)化。算例分析結(jié)果表明：基于無人倉庫二維頂視圖網(wǎng)格系統(tǒng)，在沒有障礙物的工況下，行走柵格較少；在有障礙物的工況下，以兩條路徑為例，未出現(xiàn)碰撞情況，路徑優(yōu)化效果明顯。

關(guān)鍵詞：響應(yīng)動態(tài)約束條件；倉儲；路徑規(guī)劃；協(xié)同優(yōu)化；目標(biāo)函數(shù)；碰撞

中圖分類號：TP18""文獻標(biāo)志碼：B""文章編號：1671-5276（2024）02-0170-05

Collaborative Optimization Model of Warehouse AGV Path Planning Based on Response Dynamic Constraints

YANG Zhengtao

（State Grid Tianjin Procurement Company，Tianjin 300304，China）

Abstract：A collaborative optimization model of storage AGV path planning responding to dynamic constraints is designed for planning a collision free path of storage AGV. Path node model and vehicle body coordinate system model are established to obtain the location of AGV in the warehouse. The collision description model is constructed to simplify the global path planning problem to the local environment of the dotted frame. Time window is built to calculate the time windows of empty car line segment and empty car steering segment respectively， obtaining the transportation time under different working conditions. Based on the shortest path as the dynamic constraint condition， the goal programming method is used to solve the generated multiple paths， deal with the conflicts， and realize the collaborative optimization of warehousing AGV path planning. The results of numerical examples show that， based on the 2D top view grid system of unmanned warehouse， there are fewer walking under the working condition with no obstacles， while under the working condition with obstacles， taking two paths as an example， no collision occurs， and the path optimization effect is obvious.

Keywords：response to dynamic constraints；warehousing；path planning；collaborative optimization；objective function；collision

0"引言

自動導(dǎo)引運輸車（automated guided vehicle， AGV）是智能倉庫中的一個關(guān)鍵設(shè)備，它在貨物的運輸、堆垛、分揀等過程中起著舉足輕重的作用。隨著自動駕駛設(shè)備智能化水平的不斷提高， AGV已被廣泛應(yīng)用于智能倉庫。

相關(guān)學(xué)者研究了AGV路徑規(guī)劃方法。徐晗等［1］研究了基于拓撲柵格建模的AGV路徑規(guī)劃算法的優(yōu)化方法，介紹了一種基于兩層環(huán)境模型的 AGV路線規(guī)劃模型并對其路徑規(guī)劃算法進行了改進，在該算法中加入了路徑平滑性分析過程，提出了仿真退火的群體選取方法，實現(xiàn)了AGV路徑規(guī)劃算法優(yōu)化；郭興海等［2］研究了一種融合多目標(biāo)與能耗控制的無人倉庫內(nèi)AGV路徑規(guī)劃方法，以最短路徑、最平滑度為約束條件，采用改進的微粒群算法求解曲率不連續(xù)的初始路徑，然后采用貝茲爾曲線和光滑動約束對原始軌跡進行擬合，得到速度變化小、能耗低的連續(xù)幾何軌跡，實現(xiàn)了路徑規(guī)劃。

以往研究成果雖然能夠?qū)崿F(xiàn)路徑規(guī)劃，但是規(guī)劃后的路徑還存在碰撞情況，并且在發(fā)生沖突時，路線規(guī)劃時間較長?；诖耍疚脑O(shè)計一個響應(yīng)動態(tài)約束條件的倉儲AGV路徑規(guī)劃協(xié)同優(yōu)化模型，以提高路徑規(guī)劃效果。

1"碰撞描述模型

在對路徑規(guī)劃之前，需要分析路徑中小車的碰撞問題。在多AGV環(huán)境中，事先建立了各路徑節(jié)點的坐標(biāo)，將工作路段的長度記作Q，根據(jù)節(jié)點坐標(biāo)和節(jié)點的限制，計算得到Q的帶權(quán)重臨接矩陣QW，其表示階方陣［3］，計算式如下：QW（i，j）=ei－ej，（ri，rj）∈E，（ri，rj）E（1）

式中：QW（i，j）表示i、 j兩個路徑之間的相對位置；ei、ej分別表示相對路徑的節(jié)點；（ri，rj）表示兩個節(jié)點之間的實際距離值；E表示連通參數(shù)。

車體坐標(biāo)系模型如圖1所示。

將AGV的位姿矩陣表示為

G=［X，Y，θ］t0（2）

式中：G表示兩個驅(qū)動輪連接線之間的中心點；［X，Y，θ］表示AGV位置角信息；t0表示初始時刻位置。

在整個路徑中，會不可避免地檢測到障礙物與小車碰撞情況［4］，為此在上述環(huán)境模型的基礎(chǔ)上建立碰撞描述模型。

在AGV路徑規(guī)劃中，各個路段的占用情況不同，有3種碰撞情況：相向碰撞、同向碰撞和節(jié)點碰撞。在不同碰撞情況的約束下，為了方便后續(xù)相對策略的應(yīng)用，需要按照占用情況分配時間窗［5］。設(shè)任務(wù)執(zhí)行時間為T，以時間為序列相關(guān)屬性系數(shù)，當(dāng)前位置坐標(biāo)計算公式為

Tni=［Tin，rj，k，Tout，rj，k］

Tnj=［Tin，nj，k，Tout，nj，k］（3）

式中：Tin，rj，k、Tout，rj，k分別表示第rj個節(jié)點中進入時間與離開時間的判斷參數(shù)；Tin，nj，k、Tout，nj，k分別表示第nj個節(jié)點中的進入時間與離開時間。

基于上述過程確定每一輛小車的位置［6］。為了確保小車在2D環(huán)境中不會出現(xiàn)碰撞，即小車的坐標(biāo)位置不會重疊，通過公式描述為

E=Yt［χi+k（t）］－∑uYt［χi（t）］（4）

式中：Yt［χi+k（t）］、∑uYt［χi（t）］分別表示相遇的兩個小車χi+k、 χi在t時刻所在的位置；u表示安全系數(shù)。

實際的小車軌跡規(guī)劃問題較為復(fù)雜，需要保證所有小車都不發(fā)生碰撞問題［7-8］，為此將小車所在窗體狀態(tài)與所在窗體目標(biāo)位置狀態(tài)誤差最小作為約束條件，碰撞描述公式為

I（t）=∑ni=1Y［χi（t）］－y［χi（T）］1/P（5）

式中P表示誤差計算參數(shù)。

經(jīng)過上述約束條件的建立，尋找到碰撞點，避免小車行走時出現(xiàn)碰撞情況。

2"時間窗模型建立

通過上節(jié)的碰撞描述模型避免碰撞情況，為進一步固定每輛小車的道路使用權(quán)，將時間窗口定義為一條路線的時間窗口。在時間窗模型建立前，設(shè)置如下假設(shè)條件：

1）在各道路上，小車可以雙向行駛，且同一方向上的小車數(shù)量不能超過道路的最大流量；

2）某一特定路線上AGV小車的車速是固定的；

3）AGV小車在相同的路線上，通過第一節(jié)碰撞檢測模型計算彼此間的安全距離和碰撞［9］；

4）每個通道可以容納至少一個AGV（包含裝載時的最大長度）。

在假設(shè)條件的基礎(chǔ)上，多AGV路徑規(guī)劃的時間窗模型如下：

A=M×cmsjk，cmejk（6）

式中：M表示負載運行的速度；cmsjk、cmejk分別表示時間為ms、me時的優(yōu)先級順序計算參數(shù)。

空車線段的時間窗計算公式如下：

L=cmejk－cmsjk×Kl0+Jj0K0（7）

式中：K0表示直線路段AGV空車運行的速度；Kl0、Jj0分別表示小車長度與路徑為j0上的直線路段長度。

空車轉(zhuǎn)向段的時間窗計算公式如下：

L=Jj0Kl0+H×lv02×K0（8）

式中：lv0表示路徑v0上的時間窗；K0表示交叉口編號；H表示交叉口的總數(shù)目。以此計算不發(fā)生其他工況下的行走時間。

3"路徑規(guī)劃協(xié)同優(yōu)化

基于時間窗模型，在滿足上述各個約束條件下，AGV運行的總時間最少，即選取的路徑是最短的［10］。在實際的運行中，需要考慮如下內(nèi)容：

1）考慮AGV小車從等候站返回路線的時間；

2）對AGV小車裝載和卸載的時間計算；

3）當(dāng)AGV小車在經(jīng)過十字路口時，其減速和通過之后的加速度需要計算［11］。

采用不同的調(diào)節(jié)策略能夠得到不同的路徑，但同時會出現(xiàn)不同的沖突工況［12］，不同沖突工況下構(gòu)建的目標(biāo)函數(shù)表示為

G=（Fi）+d/s×∑ni=1cdi（9）

式中：Fi表示在第i個路徑上調(diào)節(jié)沖突后的時間；d、s分別表示增加的時間量；c表示重新規(guī)劃后距離的增加量。

采用目標(biāo)規(guī)劃法進行多目標(biāo)決策問題求解［13］，將綜合指標(biāo)函數(shù)表示為

s′=∑ni=1ω2×ai

ω1×z+ω2×x（10）

式中：ω2、ω1分別表示在沖突調(diào)節(jié)后距離指標(biāo)；a、z、x分別表示沖突調(diào)節(jié)后的不同路徑長度值。

將最短路徑尋找方法與避障模型結(jié)合［14］，實現(xiàn)路徑優(yōu)化，避障路徑如圖2所示。

基于上述過程，采用目標(biāo)規(guī)劃法對多目標(biāo)問題求解，重新對路徑規(guī)劃，保證所走路徑花費時間最少，并且避免撞到障礙物。

4"算例分析

4.1"操作環(huán)境與參數(shù)

在CPU（Intel （R） Corei7-4710HQ CPU@2.50 HQ）， GB內(nèi)存，64位Windows10操作系統(tǒng)， Python3.5集成開發(fā)環(huán)境中，算例分析所用小車詳細參數(shù)如表1所示。

采用Python語言，在Pycharm平臺上開發(fā)了一套無人倉庫的二維頂視圖網(wǎng)格系統(tǒng)（20×20），其布局如圖3所示。

圖3中，白色表示可以通行的路徑，灰色表示貨架，紅色表示AGV，黑色表示禁止通行區(qū)，黑色圓點表示故障物。設(shè)置AGV在1s內(nèi)通過格柵，指示行駛速度與通過格柵的速度相對應(yīng)，即本次算例分析過程中，行駛速度是1m/s，則通過柵格的速度也為1m/s（本刊為黑白印刷，疑問之處可向作者咨詢）。

利用拓撲模型建立倉庫電子地圖，使具有配送作業(yè)的 AGV能夠在作業(yè)過程中進行雙向操作，并將其定義為

nm={c′，v′，b′，…，l′}×k1（11）

式中：c′、v′、b′、l′等分別表示待運輸?shù)呢浳铮籯1表示貨物的搬運狀態(tài)。

如果k1為-1時表示任務(wù)沒有安排小車，如果為0則表示任務(wù)即將被搬運，如果等于1則表示任務(wù)在搬運途中。

根據(jù)以上方法，對所提物品進行了分類，把工作排隊分為3個優(yōu)先級，再利用第2個時間窗口的計算方法，對各加點時間窗口進行鎖定。

4.2"結(jié)果分析

以部分柵格作為分析對象，運行序號1的AGV小車，使其運行到3附近，分別采用3種方法使其運動，對比結(jié)果如圖4所示。

分析圖4可知，所提出方法共走過12個柵格到達目標(biāo)位置，基于拓撲柵格方法共走過24個柵格，融合多目標(biāo)規(guī)劃方法共走過18個柵格。經(jīng)過對比可知，所提出方法所行走的路徑明顯少于另外兩種方法，各相差12個與6個柵格，優(yōu)勢較為明顯。

算例分析過程中，3種方法均能夠?qū)ふ业较鄳?yīng)的路徑，而在實際配送中，會存在障礙物，為此，以上述柵格中有障礙點的部分為例，在有障礙物的工況下對比各個方法的運行工況，對比結(jié)果如圖5所示。

圖5中，黑色圓點表示障礙物，分別由序號4小車向序號6小車運輸貨物，由7號小車向5號小車運輸貨物。

所提方法在序號4—序號6運輸路徑尋找上共走過9個柵格，沒有發(fā)生碰撞情況；在7號小車到5號小車運輸路徑上尋找，共走過6個柵格，這兩條路徑尋找沒有出現(xiàn)碰撞到障礙物的工況，均從障礙物周圍繞過。

基于拓撲柵格模型的方法，在序號4—序號6運輸路徑尋找上共走過23個柵格，尋找路徑較遠。原因是，在遇到障礙物的工況下，該方法選擇從其他路段繞過，走到目的地，在這個過程中沒有尋找到最短的路徑；在7號小車到5號小車運輸路徑尋找上，共走過12個柵格。

融合多目標(biāo)規(guī)劃方法在規(guī)劃后，在序號4—序號6運輸路徑上尋找共走過17個柵格；在7號小車到5號小車運輸路徑上尋找共走過12個柵格。在這兩條路徑尋找過程中，均發(fā)生碰撞情況，在發(fā)生碰撞后，選擇其他路徑進行運輸貨物。

通過上述對比結(jié)果可知，所提出方法在序號4—序號6號運輸上，尋找到的路徑較基于拓撲柵格方法少走14個柵格，較融合多目標(biāo)規(guī)劃方法少走8個柵格；在7號小車—5號小車路徑尋找上，較基于拓撲柵格方法、融合多目標(biāo)規(guī)劃方法少走6個柵格，證明所提出方法在有障礙物的工況下也能夠?qū)ふ业阶疃搪窂?，不發(fā)生碰撞情況。此次研究的優(yōu)化模型效果較好的原因是：預(yù)先建立了障礙物模型，在路徑規(guī)劃初始階段，充分考慮障礙物的影響并將尋找最短路徑作為目標(biāo)，有效提高了路徑尋找效果。

5"實例分析

基于全面性和相互獨立性的原則，應(yīng)用ET200S遠程通信模塊與PLC建立profinet通信連接小車，在720m2的范圍內(nèi)進行實例分析，即展示倉儲AGV路徑規(guī)劃協(xié)同優(yōu)化結(jié)果。以實心圓點和實心三角形代表兩輛小車標(biāo)志點，在同一條路線的時間窗口內(nèi)，設(shè)置同一個裝載任務(wù)，應(yīng)用本文方法進行路徑規(guī)劃，驗證其協(xié)同性，驗證結(jié)果如圖6所示。

如圖6所示，在兩輛小車同時執(zhí)行裝載任務(wù)時，本文方法可以同時繞開障礙物，避開同類小車且覆蓋面較廣，有利于保證倉儲AGV行駛過程的安全性。

6"結(jié)語

本文研究了倉儲AGV路徑規(guī)劃協(xié)同優(yōu)化方法，研究成果如下：

1）在分配時間窗的過程中，考慮到了相向碰撞、同向碰撞和節(jié)點碰撞的情況，降低了AGV路徑的阻塞程度，走過12個柵格即可到達目標(biāo)位置，從根本上減少路徑距離，提高效率；

2）設(shè)定優(yōu)化目標(biāo)并設(shè)定動態(tài)約束條件，整個運輸路徑上沒有發(fā)生碰撞情況，實現(xiàn)了路徑的最優(yōu)規(guī)劃；

3）在沒有障礙物與有障礙物工況下，小車均能夠?qū)ふ业阶疃搪窂?，并不發(fā)生碰撞，在很大程度上提高了倉儲的運作效率。

此次研究獲得了較好的應(yīng)用效果，但是還有不足之處，因為貨架調(diào)度具有動態(tài)性，在后續(xù)研究中還需要結(jié)合該特點做進一步分析。

參考文獻：

［1］ 徐晗，金隼，羅磊，等. 基于拓撲柵格建模的AGV路徑""規(guī)劃算法優(yōu)化［J］. 計算機工程與設(shè)計，2022，43（1）：101-109.

［2］ 郭興海，計明軍，劉雙福. 融合多目標(biāo)與能耗控制的無人倉庫內(nèi)AGV路徑規(guī)劃［J］. 計算機集成制造系統(tǒng)，2020，26（5）：1268-1276.

［3］ 李俊蘭，張中偉，吳立輝，等. 面向多運輸任務(wù)的節(jié)能單負載AGV路徑規(guī)劃研究［J］. 制造技術(shù)與機床，2022（3）：62-67.

［4］ 楊瑤，付克昌，蔣濤，等. 啟發(fā)式RRT算法的AGV路徑規(guī)劃［J］. 計算機工程與應(yīng)用，2020，56（12）：125-133.

［5］ 張飛，張彬，周烽，等. 面向自動倉儲的繩索牽引并聯(lián)機器人構(gòu)型選擇與參數(shù)優(yōu)化［J］. 機械工程學(xué)報，2020，56（1）：1-8.

［6］ 余娜娜，李鐵克，王柏琳，等. 自動化分揀倉庫中多AGV調(diào)度與路徑規(guī)劃算法［J］. 計算機集成制造系統(tǒng)，2020，26（1）：171-180.

［7］ 于軍琪，李若琳，趙安軍，等. 并行排序蟻群算法規(guī)劃倉庫AGV路徑研究［J］. 機械科學(xué)與技術(shù)，2021，40（4）：609-618.

［8］ 王曉軍，楊春霞，陳航慧，等. 考慮倒箱操作的AutoStore魔方型倉儲系統(tǒng)自動引導(dǎo)車雙層路徑規(guī)劃［J］. 科學(xué)技術(shù)與工程，2021，21（36）：15546-15554.

［9］ 姜興宇，王明皓，劉偉軍，等. 藥品倉庫堆垛機與AGV集成調(diào)度優(yōu)化［J］. 計算機集成制造系統(tǒng)，2022，28（1）：230-241.

［10］ 陳廣鋒，余立潮. 多幀時間窗輪換算法規(guī)劃倉儲多AGV小車路徑［J］. 計算機工程與應(yīng)用，2020，56（23）：270-278.

［11］ 王曉軍，王博，楊春霞，等. 緊致密集Auto Store系統(tǒng)AGV路徑規(guī)劃與避碰策略［J］. 計算機工程與應(yīng)用，2021，57（15）：259-270.

［12］ 袁洋，葉峰，賴乙宗，等. 結(jié)合負載均衡與A*算法的多AGV路徑規(guī)劃［J］. 計算機工程與應(yīng)用，2020，56（5）：251-256.

［13］ 馮浩然，吳瑞明，傅陽，等. 基于ROS與融合算法的AGV路徑規(guī)劃研究［J］. 機床與液壓，2022，50（9）：55-60.

［14］ 廉胤東，謝巍. 基于視覺引導(dǎo)多AGV系統(tǒng)的改進A*路徑規(guī)劃算法［J］. 控制與決策，2021，36（8）：1881-1890.

收稿日期：20221024