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

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

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

中圖分類(lèi)號(hào)：TP18""文獻(xiàn)標(biāo)志碼：B""文章編號(hào)：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òng)導(dǎo)引運(yùn)輸車(chē)（automated guided vehicle， AGV）是智能倉(cāng)庫(kù)中的一個(gè)關(guān)鍵設(shè)備，它在貨物的運(yùn)輸、堆垛、分揀等過(guò)程中起著舉足輕重的作用。隨著自動(dòng)駕駛設(shè)備智能化水平的不斷提高， AGV已被廣泛應(yīng)用于智能倉(cāng)庫(kù)。

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

以往研究成果雖然能夠?qū)崿F(xiàn)路徑規(guī)劃，但是規(guī)劃后的路徑還存在碰撞情況，并且在發(fā)生沖突時(shí)，路線規(guī)劃時(shí)間較長(zhǎng)。基于此，本文設(shè)計(jì)一個(gè)響應(yīng)動(dòng)態(tài)約束條件的倉(cāng)儲(chǔ)AGV路徑規(guī)劃協(xié)同優(yōu)化模型，以提高路徑規(guī)劃效果。

1"碰撞描述模型

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

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

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

將AGV的位姿矩陣表示為

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

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

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

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

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

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

式中：Tin，rj，k、Tout，rj，k分別表示第rj個(gè)節(jié)點(diǎn)中進(jìn)入時(shí)間與離開(kāi)時(shí)間的判斷參數(shù)；Tin，nj，k、Tout，nj，k分別表示第nj個(gè)節(jié)點(diǎn)中的進(jìn)入時(shí)間與離開(kāi)時(shí)間。

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

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

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

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

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

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

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

2"時(shí)間窗模型建立

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

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

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

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

4）每個(gè)通道可以容納至少一個(gè)AGV（包含裝載時(shí)的最大長(zhǎng)度）。

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

A=M×cmsjk，cmejk（6）

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

空車(chē)線段的時(shí)間窗計(jì)算公式如下：

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

式中：K0表示直線路段AGV空車(chē)運(yùn)行的速度；Kl0、Jj0分別表示小車(chē)長(zhǎng)度與路徑為j0上的直線路段長(zhǎng)度。

空車(chē)轉(zhuǎn)向段的時(shí)間窗計(jì)算公式如下：

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

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

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

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

1）考慮AGV小車(chē)從等候站返回路線的時(shí)間；

2）對(duì)AGV小車(chē)裝載和卸載的時(shí)間計(jì)算；

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

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

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

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

采用目標(biāo)規(guī)劃法進(jìn)行多目標(biāo)決策問(wèn)題求解［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é)后的不同路徑長(zhǎng)度值。

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

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

4"算例分析

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

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

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

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

利用拓?fù)淠Ｐ徒}(cāng)庫(kù)電子地圖，使具有配送作業(yè)的 AGV能夠在作業(yè)過(guò)程中進(jìn)行雙向操作，并將其定義為

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

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

如果k1為-1時(shí)表示任務(wù)沒(méi)有安排小車(chē)，如果為0則表示任務(wù)即將被搬運(yùn)，如果等于1則表示任務(wù)在搬運(yùn)途中。

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

4.2"結(jié)果分析

以部分柵格作為分析對(duì)象，運(yùn)行序號(hào)1的AGV小車(chē)，使其運(yùn)行到3附近，分別采用3種方法使其運(yùn)動(dòng)，對(duì)比結(jié)果如圖4所示。

分析圖4可知，所提出方法共走過(guò)12個(gè)柵格到達(dá)目標(biāo)位置，基于拓?fù)鋿鸥穹椒ü沧哌^(guò)24個(gè)柵格，融合多目標(biāo)規(guī)劃方法共走過(guò)18個(gè)柵格。經(jīng)過(guò)對(duì)比可知，所提出方法所行走的路徑明顯少于另外兩種方法，各相差12個(gè)與6個(gè)柵格，優(yōu)勢(shì)較為明顯。

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

圖5中，黑色圓點(diǎn)表示障礙物，分別由序號(hào)4小車(chē)向序號(hào)6小車(chē)運(yùn)輸貨物，由7號(hào)小車(chē)向5號(hào)小車(chē)運(yùn)輸貨物。

所提方法在序號(hào)4—序號(hào)6運(yùn)輸路徑尋找上共走過(guò)9個(gè)柵格，沒(méi)有發(fā)生碰撞情況；在7號(hào)小車(chē)到5號(hào)小車(chē)運(yùn)輸路徑上尋找，共走過(guò)6個(gè)柵格，這兩條路徑尋找沒(méi)有出現(xiàn)碰撞到障礙物的工況，均從障礙物周?chē)@過(guò)。

基于拓?fù)鋿鸥衲Ｐ偷姆椒?，在序?hào)4—序號(hào)6運(yùn)輸路徑尋找上共走過(guò)23個(gè)柵格，尋找路徑較遠(yuǎn)。原因是，在遇到障礙物的工況下，該方法選擇從其他路段繞過(guò)，走到目的地，在這個(gè)過(guò)程中沒(méi)有尋找到最短的路徑；在7號(hào)小車(chē)到5號(hào)小車(chē)運(yùn)輸路徑尋找上，共走過(guò)12個(gè)柵格。

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

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

5"實(shí)例分析

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

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

6"結(jié)語(yǔ)

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

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

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

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

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

參考文獻(xiàn)：

［1］ 徐晗，金隼，羅磊，等. 基于拓?fù)鋿鸥窠５腁GV路徑""規(guī)劃算法優(yōu)化［J］. 計(jì)算機(jī)工程與設(shè)計(jì)，2022，43（1）：101-109.

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

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

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

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

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

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

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

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

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

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

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

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

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

收稿日期：20221024