基于時(shí)間窗的AGV動(dòng)態(tài)避碰路徑規(guī)劃方法

摘 要： 為了解決多AGV在動(dòng)態(tài)不穩(wěn)環(huán)境下的無(wú)碰撞路徑規(guī)劃和系統(tǒng)效率提升的問(wèn)題，提出了基于時(shí)間窗的AGV無(wú)碰撞路徑規(guī)劃方法。首先建立了多AGV的避碰模型，并結(jié)合時(shí)間窗模型，將多AGV的無(wú)碰撞路徑規(guī)劃分為預(yù)先規(guī)劃和實(shí)時(shí)規(guī)劃兩階段，預(yù)先規(guī)劃階段進(jìn)行多AGV無(wú)沖突時(shí)間窗的計(jì)算和最大化系統(tǒng)中AGV的流通量，實(shí)時(shí)規(guī)劃階段通過(guò)改變AGV在避碰模型上的占用優(yōu)先級(jí)和局部重規(guī)劃的方法進(jìn)行動(dòng)態(tài)避碰。最后以某智能倉(cāng)儲(chǔ)為應(yīng)用案例進(jìn)行仿真實(shí)驗(yàn)，證明了該算法能有效避免多AGV的碰撞，提高AGV的流通量，同時(shí)在動(dòng)態(tài)環(huán)境下具有較好的魯棒性和柔性。

關(guān)鍵詞： 自動(dòng)導(dǎo)引車； 時(shí)間窗； 路徑規(guī)劃； 動(dòng)態(tài)避碰

中圖分類號(hào)： TP11"" 文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1001-3695（2022）01-009-0054-05

doi：10.19734/j.issn.1001-3695.2021.05.0211

Path planning method for AGV dynamic collisionavoidance based on time window

Sun Maomao， Kuang Bing

（School of Mechanical amp; Electrical Engineering， Guilin University of Electronic Technology， Guilin Guangxi 541000， China）

Abstract： In order to solve the problem of collision free path planning and system efficiency improvement of multi AGV in dynamic unstable environment，this paper proposed a collision free path planning method based on time window for AGV.Firstly，this paper established a multi-AGV collision avoidance model，combined with the time window model，and divided the collision-free path planning of multiple AGV into two stages：pre-planning and real-time planning.In the pre-planning stage，this paper calculated the conflict-free time window of multiple AGV and maximized the circulation of AGV in the system.In the real-time planning stage，this paper used the method of changing the AGV’s occupancy priority on the collision avoidance model and local re-planning to dynamically avoid collisions.Finally，a simulation experiment with a smart warehouse as an application case proves that the algorithm can effectively avoid the collision of multiple AGV，increase the circulation of AGV，and has good robustness and flexibility in a dynamic environment.

Key words： AGV； time window； path planning； dynamic collision avoidance

0 引言

隨著物聯(lián)網(wǎng)和工業(yè)自動(dòng)化的快速發(fā)展，自動(dòng)導(dǎo)引車（automated guided vehicle）因其路線靈活、效率高等優(yōu)點(diǎn)被廣泛應(yīng)用于智能倉(cāng)儲(chǔ)、物流運(yùn)輸?shù)阮I(lǐng)域中，由多個(gè)協(xié)同作業(yè)的AGV組成的多AGV系統(tǒng)也越來(lái)越受到人們的關(guān)注，但同時(shí)也使得AGV路徑規(guī)劃以及實(shí)時(shí)避碰等研究變得更為復(fù)雜［1，2］。

針對(duì)多AGV無(wú)碰撞路徑規(guī)劃的問(wèn)題，國(guó)內(nèi)外學(xué)者做了大量研究。在多AGV路徑規(guī)劃中，雙向AGV模型相比于單向AGV模型可以顯著減少總行程、流動(dòng)時(shí)間、機(jī)隊(duì)規(guī)模和對(duì)路徑的空間要求，但卻是要求較復(fù)雜的控制算法［3］。近年來(lái)，由于時(shí)間窗方法可以精確計(jì)算出各個(gè)AGV在其任務(wù)路徑中的無(wú)碰撞行駛時(shí)間，所以被廣泛地應(yīng)用到多AGV無(wú)碰撞路徑規(guī)劃的研究中［4～7］。Kim等人［4］最早給出了無(wú)沖突最短時(shí)間程序（conflict free shortest time procedure，CFTP），在時(shí)間窗有向圖上搜索路徑節(jié)點(diǎn)的可到達(dá)空閑時(shí)間窗，實(shí)現(xiàn)了無(wú)沖突的預(yù)測(cè)規(guī)劃；Smolic-Rocak等人［5］提出了基于時(shí)間窗的動(dòng)態(tài)路由方法，通過(guò)在新任務(wù)路徑上重復(fù)進(jìn)行時(shí)間窗的插入、延伸和重疊檢測(cè)進(jìn)行避碰；張中偉等人［6］將等待時(shí)間、行駛距離、任務(wù)緊急程度作為量化動(dòng)態(tài)優(yōu)先級(jí)的考慮因素，提出了一種基于動(dòng)態(tài)優(yōu)先級(jí)策略的多AGV無(wú)沖突路徑規(guī)劃方法；梁承姬等人［7］以AGV最短路徑為目標(biāo)，通過(guò)在最短路徑或備選路徑上插入時(shí)間窗的方法進(jìn)行多AGV的無(wú)沖突路徑規(guī)劃。

以上方法均建立在AGV系統(tǒng)沒(méi)有受到突發(fā)事件和外界干擾的靜態(tài)環(huán)境中，對(duì)AGV進(jìn)行預(yù)測(cè)規(guī)劃，均沒(méi)有考慮AGV的實(shí)時(shí)避碰問(wèn)題，因此在實(shí)際應(yīng)用中不具有魯棒性。針對(duì)動(dòng)態(tài)不穩(wěn)環(huán)境下的多AGV無(wú)碰撞路徑規(guī)劃：劉國(guó)棟等人［8］提出了一種兩階段的動(dòng)態(tài)路徑規(guī)劃方法，離線階段生成所有站點(diǎn)的候選路徑庫(kù)，在線階段根據(jù)路徑庫(kù)的路徑表和已運(yùn)行AGV的信息生成無(wú)碰撞優(yōu)化路徑；很多學(xué)者在CFTP靜態(tài)規(guī)劃的基礎(chǔ)上進(jìn)行了實(shí)時(shí)避碰的研究［9～11］：Maza等人［9］提出增加實(shí)時(shí)規(guī)劃層的方法，通過(guò)嚴(yán)格維護(hù)CFTP方法給出的每個(gè)節(jié)點(diǎn)上AGV的通過(guò)順序進(jìn)行實(shí)時(shí)避碰；賀麗娜等人［10］通過(guò)實(shí)時(shí)改變AGV通過(guò)節(jié)點(diǎn)的優(yōu)先級(jí)，調(diào)整相應(yīng)節(jié)點(diǎn)的AGV通過(guò)順序進(jìn)行實(shí)時(shí)避碰；喬巖等人［11］通過(guò)將當(dāng)前AGV的通過(guò)次序置前，重新排列AGV的通過(guò)順序，進(jìn)行動(dòng)態(tài)不穩(wěn)環(huán)境下多自動(dòng)導(dǎo)引車的避碰。

綜上，多AGV無(wú)碰撞路徑規(guī)劃的現(xiàn)有研究通常存在以下問(wèn)題：僅考慮靜態(tài)理想情況下的無(wú)碰撞路徑規(guī)劃，或針對(duì)動(dòng)態(tài)不穩(wěn)環(huán)境提出的實(shí)時(shí)避碰方法魯棒性差；突發(fā)事件的類型考慮不全面；對(duì)AGV的運(yùn)行環(huán)境模型一般給出約束，比如忽略路徑節(jié)點(diǎn)的空間特性、單向?qū)б窂健⒙窂降膯蜛GV占用和特定區(qū)域劃分等，很大程度上降低了多AGV系統(tǒng)的優(yōu)勢(shì)性能和總體運(yùn)行效率。

1 問(wèn)題描述

多AGV發(fā)生碰撞的主要原因：AGV在其任務(wù)路徑上的占用時(shí)間與其他AGV存在沖突和AGV在實(shí)際運(yùn)行時(shí)受到突發(fā)事件的影響。將AGV可能發(fā)生的突發(fā)事件分為兩類［8］：a）暫時(shí)性突發(fā)事件，如AGV在障礙物前減速，或在車道或在節(jié)點(diǎn)上臨時(shí)停車充電等；b）永久性突發(fā)事件，主要由于AGV的故障長(zhǎng)期停車所致。針對(duì)這種由突發(fā)事件導(dǎo)致的動(dòng)態(tài)不穩(wěn)環(huán)境，多AGV 路徑規(guī)劃要求 AGV 控制系統(tǒng)對(duì)時(shí)間和空間資源進(jìn)行合理分配，協(xié)調(diào)所有 AGV 有序運(yùn)行，從而保證每輛車都能順利且最優(yōu)地完成運(yùn)輸任務(wù)［8］。

本文對(duì)雙向AGV模型作如下規(guī)定：

a）設(shè)AGV正常行駛速度為v m/s，不考慮加減速、轉(zhuǎn)彎以及貨物重量對(duì)AGV速度的影響；

b）每臺(tái)AGV同一時(shí)間只能承擔(dān)一個(gè)新任務(wù)，即當(dāng)前任務(wù)完成后才能接收下一任務(wù)；

c）根據(jù)AGV的行駛速度、剎車距離和避障傳感器的測(cè)量誤差等，將AGV的最小安全車距L表示為

L=Kc×（Ls+ts×v）（1）

其中：Ls、ts和Kc分別為AGV的制動(dòng)距離（m）、系統(tǒng)反應(yīng)時(shí)間（ms）和防撞緩沖系數(shù)（取20～50）。

AGV的任務(wù)Mi定義如下：

Mi=（AGVk，Si，Gi，Ek，ti，pi）（2）

其中：i為任務(wù)編號(hào)；k為執(zhí)行任務(wù)的AGV編號(hào)；Si和Gi為任務(wù)Mi的起始點(diǎn)和目標(biāo)點(diǎn)；Ek為任務(wù)Mi在起始點(diǎn)Si和目標(biāo)點(diǎn)Gi之間為AGVk規(guī)劃的最短路徑集合；ti為任務(wù)Mi的開(kāi)始時(shí)刻；pi為任務(wù)優(yōu)先級(jí)，用于指定各AGV執(zhí)行任務(wù)的先后順序（pi值越小，任務(wù)優(yōu)先級(jí)越高）。

AGV系統(tǒng)環(huán)境模型主要用于描述AGV運(yùn)行環(huán)境內(nèi)各個(gè)路徑節(jié)點(diǎn)之間的約束關(guān)系。本文中的環(huán)境模型是基于圖論表示，定義二元組G={N，E}［14］。其中：N是一個(gè)頂點(diǎn)集，N={n1，n2，…，ns}，元素ni（i=1，2，…，s）是圖G的一個(gè)頂點(diǎn)，表示環(huán)境模型中的一個(gè)路徑節(jié)點(diǎn)；E是連接圖G中各個(gè)頂點(diǎn)的邊集，E={e1，e2，…，es′}={（ni，nj），ni，nj∈N}。ek（k=1，2，…，s′）稱為路段，表示環(huán)境模型中兩個(gè)相關(guān)路徑節(jié)點(diǎn)ni和nj的約束關(guān)系。

建立多AGV的系統(tǒng)環(huán)境模型G，如下所示：

a）獲取多AGV環(huán)境模型內(nèi)所有路徑節(jié)點(diǎn)的坐標(biāo)，設(shè)編號(hào)為i的節(jié)點(diǎn)為Ni，坐標(biāo)為Pi。

b）將路段長(zhǎng)度作為圖G的權(quán)重，根據(jù)節(jié)點(diǎn)坐標(biāo)以及節(jié)點(diǎn)之間的約束關(guān)系，計(jì)算得到圖G的帶權(quán)重鄰接矩陣GA，GA是一個(gè)s階方陣，計(jì)算如下：

GA（i，j）=‖Pi-Pj‖2（Ni，Nj）∈E

∞（Ni，Nj）E（3）

其中：GA表示環(huán)境模型中兩路徑節(jié)點(diǎn)之間的相對(duì)位置及連通關(guān)系。當(dāng)兩節(jié)點(diǎn)Ni和Nj有路徑連通時(shí)，Ni和Nj為相關(guān)路徑節(jié)點(diǎn)，GA（i，j）為兩節(jié)點(diǎn)間實(shí)際距離值；當(dāng)兩節(jié)點(diǎn)Ni和Nj無(wú)路徑連通時(shí)，Ni和Nj為不相關(guān)路徑節(jié)點(diǎn)，GA（i，j）設(shè)為無(wú)窮大。

本文采用Dijkstra算法進(jìn)行路徑規(guī)劃，路徑規(guī)劃的結(jié)果是環(huán)境模型G中多個(gè)連續(xù)路段組成的路徑集合E。設(shè)AGVk任務(wù)路徑中的第j路段為rj∈Ek（j∈{1，2，…，s}，s為AGVk任務(wù)路徑Ek中路段的數(shù)量）。

4 結(jié)束語(yǔ)

動(dòng)態(tài)不穩(wěn)環(huán)境下的多AGV無(wú)碰撞路徑規(guī)劃一直是多AGV系統(tǒng)研究領(lǐng)域的重要內(nèi)容，本文旨在解決多AGV的無(wú)碰撞路徑規(guī)劃和最大化系統(tǒng)資源的利用率，以多AGV避碰模型為基礎(chǔ)，結(jié)合時(shí)間窗將多AGV的無(wú)碰撞規(guī)劃分為預(yù)先規(guī)劃和實(shí)時(shí)規(guī)劃兩階段。在預(yù)先規(guī)劃階段，進(jìn)行AGV避碰模型的無(wú)沖突時(shí)間窗計(jì)算和動(dòng)態(tài)調(diào)整系統(tǒng)中AGV的流通量，實(shí)現(xiàn)了系統(tǒng)中多AGV最大流量的無(wú)碰撞行駛。針對(duì)動(dòng)態(tài)不穩(wěn)環(huán)境下的突發(fā)事件，提出了在實(shí)時(shí)規(guī)劃階段通過(guò)改變AGV優(yōu)先級(jí)和重規(guī)劃的方法，實(shí)現(xiàn)了多個(gè)AGV在實(shí)際運(yùn)行中的動(dòng)態(tài)避碰。通過(guò)應(yīng)用案例證明了該算法在動(dòng)態(tài)不穩(wěn)環(huán)境下能夠?qū)崟r(shí)避免多AGV間的碰撞和提高系統(tǒng)中AGV的流通量，但在高密度AGV的運(yùn)行工況本文尚未涉及，需要進(jìn)一步深入研究。

參考文獻(xiàn)：

［1］于赫年，白樺，李超.倉(cāng)儲(chǔ)式多AGV系統(tǒng)的路徑規(guī)劃研究及仿真［J］.計(jì)算機(jī)工程與應(yīng)用，2020，56（2）：233-241. （Yu Henian，Bai Hua，Li Chao.Research and simulation on path planning of warehouse multi-AGV system［J］.Computer Engineering and Applications，2020，56（2）：233-241.）

［2］羅強(qiáng)，王海寶，崔小勁，等.動(dòng)態(tài)環(huán)境下改進(jìn)人工勢(shì)場(chǎng)法的倉(cāng)儲(chǔ)機(jī)器人自主導(dǎo)航系統(tǒng)研究［J］.計(jì)算機(jī)應(yīng)用研究，2020，37（3）：745-749，762. （Luo Qiang，Wang Haibao，Cui Xiaojin，et al.Research on autonomous navigation system of warehousing mobile robot based on improved artificial potential field method in dynamic environment［J］.Application Research of Computers，2020，37（3）：745-749，762.）

［3］Egbelu P J，Tanchoco J.Potentials for bi-directional guide-path for automated guided vehicle based systems［J］.International Journal of Production Research，1986，24（5）：1075-1097.

［4］Kim C W，Tanchocoj J.Operational control of a bidirectional automated guided vehicle system［J］.International Journal of Production Research，1993，31（9）：2123-2138.

［5］Smolic-Rocak N，Bogdan S，Kovacic Z，et al.Time windows based dynamic routing in multi-AGV systems［J］.IEEE Trans on Automation Science and Engineering，2009，7（1）：151-155.

［6］張中偉，張博暉，代爭(zhēng)爭(zhēng)，等.基于動(dòng)態(tài)優(yōu)先級(jí)策略的多 AGV 無(wú)沖突路徑規(guī)劃［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（7）：2108-2111. （Zhang Zhongwei，Zhang Bohui，Dai Zhengzheng，et al.Multi-AGV conflict-free path planning based on dynamic priority strategy［J］.Application Research of Computers，2021，38（7）：2108-2111.）

［7］梁承姬，沈珊珊，胡文輝.基于路段時(shí)間窗考慮備選路徑的AGV路徑規(guī)劃［J］.工程設(shè)計(jì)學(xué)報(bào)，2018（2）：200-208. （Liang Chengji，Shen Shanshan，Hu Weihui.AGV path planning considering alternative paths based on time window of road section［J］.Chinese Journal of Engineering Design，2018（2）：200-208.）

［8］劉國(guó)棟，曲道奎，張雷.多AGV調(diào)度系統(tǒng)中的兩階段動(dòng)態(tài)路徑規(guī)劃［J］.機(jī)器人，2005，27（3）：210-214. （Liu Guodong，Qu Daokui，Zhang Lei.Two-stage dynamic path planning for multi-AGV scheduling system［J］.Robot，2005，27（3）：210-214.）

［9］Maza S，Castagna P.A performance-based structural policy for conflict-free routing of bi-directional automated guided vehicles［J］.Computers in Industry，2005，56（7）：719-733.

［10］賀麗娜，樓佩煌，錢(qián)曉明，等.基于時(shí)間窗的自動(dòng)導(dǎo)引車無(wú)碰撞路徑規(guī)劃［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（12）：2630-2634. （He Lina，Lou Peihuang，Qian Xiaoming，et al.Conflict-free automated guided vehicles routing based on time window［J］.Computer Integrated Manufacturing Systems，2010，16（12）：2630-2634.）

［11］喬巖，錢(qián)曉明，樓佩煌.基于改進(jìn)時(shí)間窗的AGVs避碰路徑規(guī)劃［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（12）：2683-2688. （Qiao Yan，Qian Xiaoming，Lou Peihuang.Improved time window based on collision-free automated guided vehicle system routing［J］.Computer Integrated Manufacturing Systems，2012，18（12）：2683-2688.）

［12］Diestel R.Graph-theory［J］.Mathematical Gazette，2000，173（502）：67-128.