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

有效

• 申請(qǐng)?zhí)枺?/td>: 202110022264.7
• 申請(qǐng)日: 2021-01-08
• 公開（公告）號(hào): CN112833905B
• 公開（公告）日: 2022-09-27
• 發(fā)明（設(shè)計(jì)）人: 程翔;都圓圓
• 申請(qǐng)（專利權(quán)）人: 北京大學(xué)
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 北京萬(wàn)象新悅知識(shí)產(chǎn)權(quán)代理有限公司 11360
• 代理人: 黃鳳茹

1.一種基于改進(jìn)A*算法的分布式AGV無(wú)碰撞路徑規(guī)劃方法，包括利用改進(jìn)A*算法進(jìn)行路徑規(guī)劃和利用柵格密度法進(jìn)行碰撞處理，通過(guò)建立資源調(diào)度方法，使得多輛自動(dòng)引導(dǎo)運(yùn)輸車AGV以時(shí)間最短為目標(biāo)，實(shí)現(xiàn)高效運(yùn)行，解決沖突和死鎖，同時(shí)減少拐彎次數(shù)，協(xié)同完成分揀任務(wù)；包括如下步驟：

步驟一、采用柵格地圖法為AGV運(yùn)行空間場(chǎng)地建模，將AGV運(yùn)行空間劃分為多個(gè)柵格類型的區(qū)域，包括空閑區(qū)、裝載口、投遞口、臨時(shí)障礙區(qū)和AGV所在區(qū)；其中：

空閑區(qū)為自由可用的小車活動(dòng)區(qū)域；

裝載口為所有AGV可選起始位置；

投遞口為所有AGV可選目標(biāo)位置，從裝載口出發(fā)，到達(dá)目標(biāo)投遞口附近任意一個(gè)柵格啟用智能投遞裝置即完成一次車載貨物的投遞工作；非本AGV目標(biāo)投遞口在本AGV運(yùn)行過(guò)程中視為障礙物；

臨時(shí)障礙區(qū)為存在需要長(zhǎng)時(shí)間占據(jù)以完成任務(wù)的AGV的位置；

AGV所在區(qū)是當(dāng)前地圖上所有的AGV所處的位置；

步驟二、采用改進(jìn)的A*路徑規(guī)劃算法為AGV規(guī)劃初始運(yùn)行軌跡，得到AGV規(guī)劃初始運(yùn)行軌跡；所述初始運(yùn)行軌跡即從AGV當(dāng)前位置到任務(wù)裝載位置的路徑及從任務(wù)裝載位置到任務(wù)投遞位置的路徑；

通過(guò)修改A*路徑規(guī)劃算法的搜索終止條件和啟發(fā)式函數(shù)，提高路徑搜索效率，減少轉(zhuǎn)向次數(shù)，避免沖突；包括如下操作過(guò)程：

21)獲取柵格地圖信息、AGV起始位置信息和AGV目標(biāo)位置信息；

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

23)從AGV起始位置開始搜尋路徑，即將AGV起始位置加入OPEN列表；

24)判斷OPEN列表是否為空，即判斷是否還存在之后待處理的節(jié)點(diǎn)；如果存在之后待處理的節(jié)點(diǎn)則繼續(xù)進(jìn)行處理；否則結(jié)束操作，說(shuō)明不存在路徑；

25)判斷待處理節(jié)點(diǎn)中是否包含AGV目標(biāo)位置，即判斷AGV目標(biāo)位置是否在OPEN列表中；如果不存在則繼續(xù)進(jìn)行處理，如果存在則說(shuō)明尋路成功，結(jié)束操作；

26)選取待處理節(jié)點(diǎn)中節(jié)點(diǎn)代價(jià)最小的節(jié)點(diǎn)U，對(duì)其進(jìn)行進(jìn)一步搜索處理；

所述節(jié)點(diǎn)代價(jià)等于節(jié)點(diǎn)n距離AGV起始位置的代價(jià)、節(jié)點(diǎn)n距離AGV目標(biāo)位置的預(yù)計(jì)代價(jià)、轉(zhuǎn)向代價(jià)、柵格密度代價(jià)的加和；

節(jié)點(diǎn)代價(jià)的計(jì)算方法具體表示為：

f_n＝g_n+h_n+is_turn*t+density*d

其中，f_n代表節(jié)點(diǎn)綜合優(yōu)先級(jí)，g_n代表節(jié)點(diǎn)n距離AGV起始位置的代價(jià)，h_n代表節(jié)點(diǎn)n距離AGV目標(biāo)位置的預(yù)計(jì)代價(jià)；is_turn*t代表轉(zhuǎn)向代價(jià)，density*d代表柵格密度代價(jià)；t代表轉(zhuǎn)向參數(shù)；

27) 處理完畢后，將節(jié)點(diǎn)U放入CLOSE列表；

即得到AGV規(guī)劃初始運(yùn)行軌跡；

步驟三、各AGV按照規(guī)劃的結(jié)果運(yùn)行，根據(jù)等待及重新規(guī)劃的方法處理AGV在運(yùn)行過(guò)程中的沖突問(wèn)題；

運(yùn)行過(guò)程中如果發(fā)生沖突，則優(yōu)先采取原地等待策略；

運(yùn)行過(guò)程中如果檢測(cè)到死鎖則進(jìn)行重新規(guī)劃，找到之前由于死鎖始終無(wú)法到達(dá)的路徑規(guī)劃的下一位置的柵格，將其虛擬設(shè)置為臨時(shí)障礙，再進(jìn)行重新規(guī)劃；只規(guī)劃先檢測(cè)到死鎖的AGV小車；

通過(guò)上述步驟，即實(shí)現(xiàn)基于改進(jìn)A*算法的分布式AGV無(wú)碰撞路徑規(guī)劃。

2.如權(quán)利要求1所述基于改進(jìn)A*算法的分布式AGV無(wú)碰撞路徑規(guī)劃方法，其特征是，步驟一中，AGV每次移動(dòng)以一個(gè)柵格為單位；柵格的大小設(shè)置為與AGV的大小相同。

3.如權(quán)利要求1所述基于改進(jìn)A*算法的分布式AGV無(wú)碰撞路徑規(guī)劃方法，其特征是，節(jié)點(diǎn)代價(jià)的計(jì)算方法中，當(dāng)產(chǎn)生轉(zhuǎn)向時(shí)，則設(shè)置is_turn為1，加上對(duì)應(yīng)的轉(zhuǎn)向代價(jià)；否則不產(chǎn)生轉(zhuǎn)向時(shí)則設(shè)置is_turn為0，不產(chǎn)生轉(zhuǎn)向代價(jià)；t取值設(shè)置為[1,3]。

4.如權(quán)利要求1所述基于改進(jìn)A*算法的分布式AGV無(wú)碰撞路徑規(guī)劃方法，其特征是，節(jié)點(diǎn)代價(jià)的計(jì)算方法中，density具體為在預(yù)計(jì)抵達(dá)時(shí)刻附近時(shí)刻到達(dá)該柵格的AGV小車數(shù)量的加權(quán)平均和，表示如下：

其中，N_t表示在時(shí)刻t預(yù)計(jì)到達(dá)該柵格的小車數(shù)量。