[發(fā)明專利]基于改進A*算法的分布式多AGV無碰撞路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202110022264.7
• 申請日: 2021-01-08
• 公開（公告）號: CN112833905B
• 公開（公告）日: 2022-09-27
• 發(fā)明（設計）人: 程翔;都圓圓
• 申請（專利權）人: 北京大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

本發(fā)明公布了一種基于改進A*算法的分布式AGV無碰撞路徑規(guī)劃方法，包括利用改進A*算法進行路徑規(guī)劃和利用柵格密度法進行碰撞處理，通過建立資源調度方法，使得多輛自動引導運輸車AGV以時間最短為目標，實現(xiàn)高效運行，解決沖突和死鎖，同時減少拐彎次數(shù)，協(xié)同完成分揀任務。

技術領域

本發(fā)明屬于多智能體路徑規(guī)劃技術領域，涉及物流系統(tǒng)中的多自動引導運輸車(automated guided vehicle，簡稱AGV)的分布式自動分揀任務路徑規(guī)劃技術，尤其涉及一種基于改進A*算法的分布式多AGV無碰撞路徑規(guī)劃方法。

背景技術

物流速度、物流服務、物流成本在網絡消費者購買階段具有重大影響,消費者在最終確定購買商品時，考慮最多的是物流因素。物流速度對消費者支付意愿有正影響，其中配送速度更受消費者的重視，電商物流服務企業(yè)對配送速度的關注是有意義的。隨著電子商務的不斷發(fā)展，物聯(lián)網、自動化等技術的盛行，物流由傳統(tǒng)低效逐步走向智能化、高效化。

具體表現(xiàn)為消費者在線下單后，倉庫自動倉儲檢索系統(tǒng)(AR/RS)會根據(jù)訂單挑選出消費者需要的商品，并通過傳送帶運輸?shù)桨b區(qū)域完成包裝，之后由自動導引運輸車(automated guided vehicle，簡稱AGV)來進行分揀操作。AGV上裝有自動導引機構可引導AGV小車沿著既定路徑運行，也能根據(jù)新的指令修正運行路線，以完成物料或貨物的移取功能。物流系統(tǒng)作業(yè)質量關乎倉儲系統(tǒng)的經濟效應,多輛AGV構成的集群式AGV系統(tǒng)(簡稱AGVs)具有節(jié)約勞動力、高效、安全、可用性好的絕對優(yōu)勢。AGVs對于減少工作人員負擔、提高倉庫效率，增強企業(yè)的競爭力等具有重要意義。

AGVs包含有多個AGV，存在AGV共享路徑網絡等，從而導致AGV之間的資源競爭，由此產生了資源調度的需要。AGV數(shù)量越多,資源調度的難度越大。目前，對AGV小車的控制方法共有兩種方式，集中式控制與分布式控制。現(xiàn)有技術大多采用集中式控制，其具有結構簡單，控制方便等優(yōu)點。但隨著系統(tǒng)規(guī)模的擴大，集中式控制中管理中心面臨的管理和計算壓力成為其瓶頸。分布式控制可以避免AGV數(shù)目增加情況下控制中心的計算壓力激增的問題，具有靈活性好，實時性好，易于擴展等優(yōu)點，系統(tǒng)具有更好的魯棒性。

發(fā)明內容

為了克服上述現(xiàn)有技術的不足，本發(fā)明提供一種基于改進A*算法的分布式多AGV無碰撞路徑規(guī)劃方法，目的在于建立物流系統(tǒng)中的資源調度策略和AGV運輸車路徑規(guī)劃方法，實現(xiàn)多AGV的無沖突高效運行，避免碰撞和死鎖等現(xiàn)象。

本發(fā)明方法主要包括路徑規(guī)劃和碰撞處理兩方面，通過建立相關的資源調度方法,使得多輛AGV小車以時間最短為目標,實現(xiàn)高效運行，合理解決沖突和死鎖問題，同時盡可能減少拐彎次數(shù)，協(xié)同完成分揀任務。

本發(fā)明為實現(xiàn)上述目的，采用以下技術方案：

一種基于改進A*算法的分布式AGV無碰撞路徑規(guī)劃方法。改進的A*算法主要解決多AGV路徑規(guī)劃問題，柵格密度法主要解決各類AGV間的沖突問題。包括如下步驟：

步驟一、采用柵格地圖法為倉庫場地建模，將AGV運行空間劃分為多個柵格類型區(qū)域，包括空閑區(qū)、裝載口、投遞口、臨時障礙區(qū)和AGV所在區(qū)。

步驟二、根據(jù)改進的A*路徑規(guī)劃算法為AGV規(guī)劃運行軌跡，得到AGV規(guī)劃初始運行軌跡。

初始運行軌跡即從AGV當前位置到任務裝載位置的路徑及從任務裝載位置到任務投遞位置的路徑；

以經典路徑規(guī)劃算法A*算法為基礎，修改搜索終止條件和啟發(fā)式函數(shù)，提高路徑搜索效率，減少轉向次數(shù)，避免沖突。包括如下操作過程：

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

2)定義用于存儲之后待處理的節(jié)點信息的OPEN列表、用于存儲已處理完畢的節(jié)點信息的CLOSE列表，兩個列表均初始化為空列表；