基于時間窗的AGV動態避碰路徑規劃方法

摘 要： 為了解決多AGV在動態不穩環境下的無碰撞路徑規劃和系統效率提升的問題，提出了基于時間窗的AGV無碰撞路徑規劃方法。首先建立了多AGV的避碰模型，并結合時間窗模型，將多AGV的無碰撞路徑規劃分為預先規劃和實時規劃兩階段，預先規劃階段進行多AGV無沖突時間窗的計算和最大化系統中AGV的流通量，實時規劃階段通過改變AGV在避碰模型上的占用優先級和局部重規劃的方法進行動態避碰。最后以某智能倉儲為應用案例進行仿真實驗，證明了該算法能有效避免多AGV的碰撞，提高AGV的流通量，同時在動態環境下具有較好的魯棒性和柔性。

關鍵詞： 自動導引車； 時間窗； 路徑規劃； 動態避碰

中圖分類號： TP11"" 文獻標志碼： A

文章編號： 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 引言

隨著物聯網和工業自動化的快速發展，自動導引車（automated guided vehicle）因其路線靈活、效率高等優點被廣泛應用于智能倉儲、物流運輸等領域中，由多個協同作業的AGV組成的多AGV系統也越來越受到人們的關注，但同時也使得AGV路徑規劃以及實時避碰等研究變得更為復雜［1，2］。

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

以上方法均建立在AGV系統沒有受到突發事件和外界干擾的靜態環境中，對AGV進行預測規劃，均沒有考慮AGV的實時避碰問題，因此在實際應用中不具有魯棒性。針對動態不穩環境下的多AGV無碰撞路徑規劃：劉國棟等人［8］提出了一種兩階段的動態路徑規劃方法，離線階段生成所有站點的候選路徑庫，在線階段根據路徑庫的路徑表和已運行AGV的信息生成無碰撞優化路徑；很多學者在CFTP靜態規劃的基礎上進行了實時避碰的研究［9～11］：Maza等人［9］提出增加實時規劃層的方法，通過嚴格維護CFTP方法給出的每個節點上AGV的通過順序進行實時避碰；賀麗娜等人［10］通過實時改變AGV通過節點的優先級，調整相應節點的AGV通過順序進行實時避碰；喬巖等人［11］通過將當前AGV的通過次序置前，重新排列AGV的通過順序，進行動態不穩環境下多自動導引車的避碰。

綜上，多AGV無碰撞路徑規劃的現有研究通常存在以下問題：僅考慮靜態理想情況下的無碰撞路徑規劃，或針對動態不穩環境提出的實時避碰方法魯棒性差；突發事件的類型考慮不全面；對AGV的運行環境模型一般給出約束，比如忽略路徑節點的空間特性、單向導引路徑、路徑的單AGV占用和特定區域劃分等，很大程度上降低了多AGV系統的優勢性能和總體運行效率。

1 問題描述

多AGV發生碰撞的主要原因：AGV在其任務路徑上的占用時間與其他AGV存在沖突和AGV在實際運行時受到突發事件的影響。將AGV可能發生的突發事件分為兩類［8］：a）暫時性突發事件，如AGV在障礙物前減速，或在車道或在節點上臨時停車充電等；b）永久性突發事件，主要由于AGV的故障長期停車所致。針對這種由突發事件導致的動態不穩環境，多AGV 路徑規劃要求 AGV 控制系統對時間和空間資源進行合理分配，協調所有 AGV 有序運行，從而保證每輛車都能順利且最優地完成運輸任務［8］。

本文對雙向AGV模型作如下規定：

a）設AGV正常行駛速度為v m/s，不考慮加減速、轉彎以及貨物重量對AGV速度的影響；

b）每臺AGV同一時間只能承擔一個新任務，即當前任務完成后才能接收下一任務；

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

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

其中：Ls、ts和Kc分別為AGV的制動距離（m）、系統反應時間（ms）和防撞緩沖系數（取20～50）。

AGV的任務Mi定義如下：

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

其中：i為任務編號；k為執行任務的AGV編號；Si和Gi為任務Mi的起始點和目標點；Ek為任務Mi在起始點Si和目標點Gi之間為AGVk規劃的最短路徑集合；ti為任務Mi的開始時刻；pi為任務優先級，用于指定各AGV執行任務的先后順序（pi值越小，任務優先級越高）。

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

建立多AGV的系統環境模型G，如下所示：

a）獲取多AGV環境模型內所有路徑節點的坐標，設編號為i的節點為Ni，坐標為Pi。

b）將路段長度作為圖G的權重，根據節點坐標以及節點之間的約束關系，計算得到圖G的帶權重鄰接矩陣GA，GA是一個s階方陣，計算如下：

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

∞（Ni，Nj）E（3）

其中：GA表示環境模型中兩路徑節點之間的相對位置及連通關系。當兩節點Ni和Nj有路徑連通時，Ni和Nj為相關路徑節點，GA（i，j）為兩節點間實際距離值；當兩節點Ni和Nj無路徑連通時，Ni和Nj為不相關路徑節點，GA（i，j）設為無窮大。

本文采用Dijkstra算法進行路徑規劃，路徑規劃的結果是環境模型G中多個連續路段組成的路徑集合E。設AGVk任務路徑中的第j路段為rj∈Ek（j∈{1，2，…，s}，s為AGVk任務路徑Ek中路段的數量）。

4 結束語

動態不穩環境下的多AGV無碰撞路徑規劃一直是多AGV系統研究領域的重要內容，本文旨在解決多AGV的無碰撞路徑規劃和最大化系統資源的利用率，以多AGV避碰模型為基礎，結合時間窗將多AGV的無碰撞規劃分為預先規劃和實時規劃兩階段。在預先規劃階段，進行AGV避碰模型的無沖突時間窗計算和動態調整系統中AGV的流通量，實現了系統中多AGV最大流量的無碰撞行駛。針對動態不穩環境下的突發事件，提出了在實時規劃階段通過改變AGV優先級和重規劃的方法，實現了多個AGV在實際運行中的動態避碰。通過應用案例證明了該算法在動態不穩環境下能夠實時避免多AGV間的碰撞和提高系統中AGV的流通量，但在高密度AGV的運行工況本文尚未涉及，需要進一步深入研究。

參考文獻：

［1］于赫年，白樺，李超.倉儲式多AGV系統的路徑規劃研究及仿真［J］.計算機工程與應用，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］羅強，王海寶，崔小勁，等.動態環境下改進人工勢場法的倉儲機器人自主導航系統研究［J］.計算機應用研究，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］張中偉，張博暉，代爭爭，等.基于動態優先級策略的多 AGV 無沖突路徑規劃［J］.計算機應用研究，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］梁承姬，沈珊珊，胡文輝.基于路段時間窗考慮備選路徑的AGV路徑規劃［J］.工程設計學報，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］劉國棟，曲道奎，張雷.多AGV調度系統中的兩階段動態路徑規劃［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］賀麗娜，樓佩煌，錢曉明，等.基于時間窗的自動導引車無碰撞路徑規劃［J］.計算機集成制造系統，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］喬巖，錢曉明，樓佩煌.基于改進時間窗的AGVs避碰路徑規劃［J］.計算機集成制造系統，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.