[發明專利]多AGV無碰撞路徑規劃算法

有效

• 申請號: 201810534417.4
• 申請日: 2018-05-29
• 公開（公告）號: CN108762268B
• 公開（公告）日: 2022-08-05
• 發明（設計）人: 錢灝;馬飛
• 申請（專利權）人: 上海澳悅智能科技有限公司
• 主分類號: G05D1/02
• 分類號: G05D1/02;G01C21/34
• 代理公司: 上海尊肅專利代理事務所(普通合伙) 31454
• 代理人: 賴林東

本發明多AGV無碰撞路徑規劃算法，步驟如下：開始階段，包括：根據已知建模的交通地圖信息，進行系統設定；規劃多AGV運行路徑；運行階段，包括：構建時間序列多部圖:對目前已規劃任務的路徑，標記中相應路徑；取下一個任務；根據就近原則和空閑狀況確定執行任務小車；根據任務的起始位置和終止位置，利用Dijkstra算法和規劃最短路徑；根據規劃的最短路徑，標記中相應路徑；進行是否有未處理任務整理，是為返回下一個任務，否則結束。本發明采用時間軸圖和最短路徑算法在多AGV系統中為每臺AGV規劃運行路線，做到在優化的時間內規劃所有任務路線，且路線之間無沖突。

技術領域

本發明涉及AGV控制技術，特別涉及AGV導航控制技術領域，具體的，其展示基于時間序列多部圖和最短路徑算法的一種多AGV無碰撞路徑規劃算法。

背景技術

AGV是(Automated Guided Vehicle)的縮寫，意即自動導引運輸車，是指裝備有電磁或光學等自動導引裝置，它能夠沿規定的導引路徑行駛，具有安全保護以及各種移載功能的運輸車。

AGV廣泛應用于智能化物流系統中，即物料的流動通過AGV完成，AGV把原料在各個環節進行運送，完成各加工點之間半成品的傳送。AGV的運行需要有控制系統確定其運行路線。當系統中有多個AGV時，保證系統無沖突的情況下，實現評價指標最短，為每個AGV規劃出一條無碰撞、協調的路徑規劃是一個不易的任務。

因此，有必要提供基于時間序列多部圖和最短路徑算法的一種多AGV無碰撞路徑規劃算法來解決上述問題。

發明內容

本發明的目的是提供一種多AGV無碰撞路徑規劃算法。

技術方案如下：

一種基多AGV無碰撞路徑規劃算法，步驟如下：

開始階段，包括：

1)根據已知建模的交通地圖信息，進行系統設定：

2)規劃多AGV運行路徑：

運行階段，包括：

3)構建時間序列多部圖

3-1)基于系統中設定的AGV的運行速度，假設完成當前任務需要時間為T，確定時間序列多部圖所需部數

N_Partite＝T/10.

構造時間序列N_Partite部圖其中節點集V_i＝V，i＝1…N_Partite為在i時刻的交通圖；

3-2)根據時間序列N_Partite部圖構造相應的鄰接矩陣為(Num_Partite_Graph*p)×(Num_Partite_Graph*p)數組,其中p為頂點的個數；按每p個連續節點為一塊，將分成n×n的塊矩陣；并按一下流程設置

對i從1到n-1

對j從i+1到n

的(i,j)塊更新為W+(j-i-1)*10；

其中W為對應原交通圖的鄰接矩陣；

4)對目前已規劃任務的路徑，標記中相應路徑；

6)取下一個任務t_i；

6)根據就近原則和空閑狀況確定執行任務小車C_i；

7)根據任務t_i的起始位置O_i和終止位置D_i，利用Dijkstra算法和規劃最短路徑σ_i：