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

有效

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

1.一種基多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)對目前已規劃任務的路徑，標記中相應路徑；

5)取下一個任務t_i；

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

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

7-1)初始化，S中只包含源節點S，U包含除去V之外的其他所有節點；每個節點的鄰接關系和權值已知，且權值非負；

7-2)從U中選取與S₀有鄰接關系且權值最小的頂點S_k，把S_k加入到S中(S₀到S_k的最短路徑長度即為權值大小，最短路徑即是S₀-S_k；

7-3)以S_k為新的中間節點，考察U中與S_k鄰接的節點；若從源點S₀到U中節點的距離(經過S_k)比原來的距離(不經過S_k)的短，則修改U中已經考察過頂點的路徑，修改后的路徑值為經過S_k的路徑；同時把新的具有最短路徑的節點加入S；

7-4)重復執行步驟7-2)和7-3).直到所有頂點都包含在S中或者已經找到最短路徑；

8)根據規劃的最短路徑σ_i，標記中相應路徑；

9)進行是否有未處理任務整理，是為返回步驟5)，否則結束。

2.根據權利要求1所述的一種基多AGV無碰撞路徑規劃算法，其特征在于：步驟1)包括：

1-1)交通地圖中規劃出的每條弧表示可雙向行駛的單行道，即該路徑只能允許一臺AGV通過，但AGV可以在此路徑上雙向行駛；

1-2)小車運行時速度恒定，本系統中假設所有小車運行速度為lm/s；

1-3)每一條路徑在同一時間只能被一個小車占據，即不允許兩輛小車同時出現在同一段路徑上；

1-4)為保證AGV不會發生碰撞，每個AGV都有自己的安全區域，設安全區域的半徑為r(r根據車體大小和速度確定)，在此區域范圍內，別的AGV不能進入；

1-5)每個任務被在下發時指定一個優先級，具有同樣優先級的任務，較早下達的任務有更高的優先權；

1-6)每一條路徑中的轉彎大部分都是直角，轉彎時間設定為常數；兩條路徑在同一直線上則不需要轉彎；

1-7)取貨卸貨操作需要用的時間定義為常數，充電采用快充方式，AGV只有在電池電量低于一定的值的時候才進行充電，充電時間也近似為一個常數；

1-8)任務只包括一個起點一個終點，如果一個任務是從取貨點A運送貨物到B點，且該任務需要目前在C點的小車R執行，則該任務可分成兩個任務，分別是讓R從C點到A點，和讓R從A點到B點。

3.根據權利要求2所述的一種基多AGV無碰撞路徑規劃算法，其特征在于：步驟2)包括：

2-1)設圖G＝(V，E)表示整個交通地圖，其中：

V＝{v₁，v₂，…，v_p}表示地圖中所有節點的集合，

E＝{e₁，e₂，...，ex)表示所有連接節點的弧的集合，

2-2)w_ij表示節點(i，j)之間弧的權值；

W為表示圖G的鄰接矩陣；其中W中(i,j)位置上的值為連接i，j節點的邊的權值；

2-3)R＝{c₁，c₂，…，c_n)為系統中可執行任務小車集合；

2-4)M＝{t₁，t₂，…，t_m}為當前需要執行的任務集合；

2-5)P_i為任務t_i的優先級；

2-6)O_i為任務t_i的起始位置；

2-7)D_i為任務t_i的終止位置；

2-8)σ_i＝(e_j，e_k，…，e_q)為任務t_i的執行路徑，該路徑為一系列弧段的集合，從起始位置O_i到終止位置D_i的路徑可以表示為有序弧段集合，其中e_j，e_k，…，e_q∈E，是環境地圖邊集合中的路段；

2-9)m_i＝(O_i，D_i，σ_i，P_i，r_i)描述任務t_i。