[發明專利]基于跳點尋路與協同避障的多AGV路徑規劃方法

有效

• 申請號: 202110253326.5
• 申請日: 2021-03-05
• 公開（公告）號: CN113074728B
• 公開（公告）日: 2022-07-22
• 發明（設計）人: 程翔;都圓圓
• 申請（專利權）人: 北京大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

1.一種基于跳點尋路與協同避障的多AGV路徑規劃方法，通過對場地地圖采用跳點尋路算法和協同避障方法進行設計規劃，得到多AGV的分布式路徑，使得各個AGV無沖突地執行分派的分揀任務，有效提升分布式多AGV的工作效率；包括如下步驟：

步驟一、對AGV運行空間場地建模，將AGV運行空間劃分為緊密排列的多個柵格類型的柵格區域；將每個柵格區域作為一個路徑節點；

步驟二、根據跳點尋路算法為AGV規劃初始運行軌跡；

初始運行軌跡是從AGV當前位置到任務裝載位置的路徑，以及從任務裝載位置到任務投遞位置的路徑；通過如下過程進行路徑搜索，為AGV規劃得到初始運行軌跡：

21)獲取柵格地圖信息、AGV起點和目標位置信息；

22)定義用于存儲待處理路徑節點信息的OPEN列表、用于存儲處理完成的路徑節點信息的CLOSE列表；OPEN列表和CLOSE列表均初始化為空列表；

23)從起點開始搜索路徑，即將AGV起點加入OPEN列表；

24)判斷OPEN列表是否為空；當OPEN列表不為空即存在待處理的路徑節點，繼續進行處理；否則說明不存在路徑，結束操作；

25)以距離作為節點代價，選取待處理路徑節點中代價最小的路徑節點U；

26)判斷節點U是否為終點，如果不是則繼續處理；如果是則說明尋路成功，結束步驟二的路徑搜索操作，輸出路徑即為初始運行軌跡；

27)對U進行拓展，即對U的鄰居節點進行進一步處理；

令當前節點為x，當前節點的父節點為p，當節點n滿足len(p,…,n\x)≥len(p,x,n)，則節點n為節點x的鄰居節點；如果節點n同時滿足len(p,…,n\x)len(p,x,n)，則節點n為節點x的特殊鄰居節點；終點為特殊鄰居節點；

對U的每個鄰居節點進行拓展處理的方法具體包括如下步驟：

271)判斷當前鄰居節點nb是否可檢測到跳點，如果檢測到跳點，則對跳點進行進一步的處理，即進入步驟272)；

272)如果節點nb之前已經完成處理即在CLOSE列表中，則不需要進行處理；

如果節點nb是一個新的節點，則對nb計算其節點代價，之后選擇從節點U到達節點nb的路徑，將節點nb加入待處理節點，即加入OPEN列表；

如果節點nb正在等待被處理即在OPEN列表中，則更新到達節點nb的方式為更新為從nb節點原先父節點到達nb和從節點U到達nb中代價更小的一項；

28)處理完畢后，將節點U放入CLOSE列表；

29)繼續處理后續節點，即返回步驟24)；

步驟二結束即得到各AGV規劃的初始運行軌跡；

步驟三、根據反應式協同避障方法處理AGV之間在運行過程中可能遇到的各類沖突；當多AGV發生資源沖突問題時，無需主控中心的參與，多AGV處理沖突包括如下步驟：

31)判斷下一位置是否可行：可行則前進一步，對下一步繼續判斷處理，即進入步驟31)，如果不可行則需要對當前的路徑進行修正，即進入步驟32)；

32)修正路徑：根據當前沖突情況對基礎路徑進行修改，針對不同的沖突，可采用的修正方法包括：第一類修正路徑方案是修正部分路徑；第二類修正路徑方案是原地等待一個運行時刻；第三類修正路徑方案是重新規劃從當前節點至目標節點的路徑；

具體的方法包括：

321)判斷前方是否被長期阻塞，如果前方被長期阻塞，則將前方位置視為障礙，進入第三類修正路徑方案，重新規劃路徑；

322)判斷前方是否被已經到達終點的空閑AGV阻塞，是則空閑AGV主動避讓到附近的空閑位置，沖突處理結束，小車正常前進；

323)判斷是否有直接沖突AGV，是則進入第一類修正路徑方案，否則進入第二類修正路徑方案，原地等待；

其中，第一類修正路徑的具體方法如下：

a)判斷理想情況下的協同避讓方案是否可行，可行則依據理想情況下的策略解決沖突，不可行則嘗試最優避讓方案，即則進入步驟b)；

b)確定避讓AGV和通行AGV：下下步驟位置空閑的AGV能夠獲得通行資格、是通行AGV，與之沖突的AGV為避讓AGV；若雙方都獲得通行資格，則任意指定一組避讓通行AGV，另外的一組作為備用方案；

c)判斷避讓AGV是否存在可用的最優避讓區域，最優避讓區域指避讓AGV周圍除通行AGV下下步驟目標位置外的柵格區域；是則進入最優避讓，即進入步驟d)，否則判斷是否有必要進行次優避讓，即進入步驟e)；

d)避讓AGV駛入避讓區域進行避讓，通行AGV優先行駛；之后避讓AGV回歸原路徑行駛；

e)判斷當前是否為二次沖突，如果當前為二次沖突，則進一步判斷是否存在備用方案，即進入步驟h)；否則進行次優避讓，即進入步驟f)；

f)避讓AGV先駛入通行AGV下下步驟目標位置，通行AGV追隨避讓AGV駛入通行AGV之前占用位置；

g)判斷當前的二次沖突情形，針對二次沖突的情況嘗試對應的理想情況，即進入步驟a)；

h)判斷是否存在備用方案，是則嘗試備用方案，即進入步驟a)；否則不存在合適的協同方案，沖突雙方需要原地等待；

通過上述步驟，實現基于跳點尋路與協同避障的多AGV路徑規劃。