智能倉(cāng)儲(chǔ)中基于A*算法的多AGV路徑規(guī)劃研究

(北京物資學(xué)院 北京 100000)

一、引言

AGV作為智能倉(cāng)儲(chǔ)揀選的主要工具已得到廣泛使用，它的使用帶來如節(jié)約勞動(dòng)成本、提高揀選準(zhǔn)確率等優(yōu)點(diǎn)。路徑規(guī)劃是AGV領(lǐng)域的熱點(diǎn)問題，是為AGV在包含障礙物的空間中規(guī)劃出一條從起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑。

近幾年多AGV路徑規(guī)劃問題近開始得到人們關(guān)注，如劉國(guó)棟[1]提出一種兩階段動(dòng)態(tài)路徑規(guī)劃策略，先應(yīng)用k最短路徑法生成離線路徑集，再綜合阻塞系數(shù)，進(jìn)行分階段路徑規(guī)劃。晁永生[2]等提出動(dòng)態(tài)修改路徑的兩階段協(xié)調(diào)方法，實(shí)現(xiàn)多機(jī)器人無碰撞運(yùn)動(dòng)。張丹露[3]提出基于交通規(guī)則、預(yù)約表和動(dòng)態(tài)加權(quán)地圖的方式完成多機(jī)器人路徑規(guī)劃。針對(duì)多AGV路徑規(guī)劃方法和策略雖多，但其在智能倉(cāng)儲(chǔ)領(lǐng)域的應(yīng)用中遠(yuǎn)沒有形成一套系統(tǒng)的理論和方法，還處于不斷發(fā)展和完善中，目前存在的問題是：

(1)實(shí)時(shí)性問題。由于環(huán)境的復(fù)雜性加之機(jī)器人受傳感器性能影響，無法進(jìn)行在線實(shí)時(shí)全局規(guī)劃，這是研究難點(diǎn)；

(2)機(jī)器人間避碰問題。多機(jī)器人系統(tǒng)中，每臺(tái)機(jī)器人要同時(shí)顧及與其它機(jī)器人間、障礙物間的碰撞,如何預(yù)測(cè)機(jī)器人行走動(dòng)向?qū)ふ覚C(jī)器人間無碰撞路徑是研究的熱點(diǎn)；

(3)避障協(xié)調(diào)規(guī)則問題。多機(jī)器人在確定沖突將要發(fā)生后，對(duì)于沖突點(diǎn)怎么合理解決是研究重點(diǎn)。

針對(duì)以上問題，在對(duì)智能倉(cāng)儲(chǔ)中多機(jī)器人路徑規(guī)劃過程中，本文主要對(duì)路徑的避碰問題和協(xié)調(diào)規(guī)則進(jìn)行研究。

二、算法設(shè)計(jì)

本文采用A*算法，主要原因如下：A*算法具有較小的時(shí)間復(fù)雜度、空間復(fù)雜度，能在短時(shí)間內(nèi)獲得最優(yōu)路徑；A*算法作為啟發(fā)式算法具有較強(qiáng)的適應(yīng)能力。

A*算法的核心思想體現(xiàn)在綜合考慮起始點(diǎn)到當(dāng)前點(diǎn)的真實(shí)代價(jià)和當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的估計(jì)代價(jià)，核心部分為評(píng)價(jià)函數(shù)，表達(dá)式為：f(n)=g(n)+h(n)

我們采用曼哈頓距離進(jìn)行距離的估算，這樣才能更接近移動(dòng)機(jī)器人行走的實(shí)際路程。由于倉(cāng)儲(chǔ)物流機(jī)器人進(jìn)行轉(zhuǎn)向的時(shí)間耗費(fèi)和能量耗費(fèi)不同，因此在h(n)中加入轉(zhuǎn)向代價(jià)，因此啟發(fā)式函數(shù)的表達(dá)式為：h’(n)=h(n)+ε

我們先通過A*算法對(duì)多個(gè)AGV規(guī)劃出各自的最優(yōu)臨時(shí)路線，這些路線可能導(dǎo)致多個(gè)AGV可能會(huì)同時(shí)經(jīng)過一個(gè)路口，在這種情況下，可以根據(jù)柵格地圖和時(shí)間窗來確定將會(huì)發(fā)生哪種沖突類型，然后采用避障協(xié)調(diào)策略解決沖突。

在本文中將采取兩種避障協(xié)調(diào)策略，等待策略和重新規(guī)劃路線策略。對(duì)于相向相遇沖突可以通過對(duì)低優(yōu)先級(jí)任務(wù)將沖突柵格對(duì)應(yīng)的代價(jià)值設(shè)置為∞，再重新規(guī)劃來解決；對(duì)于垂直相遇沖突通過預(yù)估低優(yōu)先級(jí)任務(wù)繞行耗費(fèi)時(shí)間和等待時(shí)間，并對(duì)二者進(jìn)行比較，選擇時(shí)間較短的方式。對(duì)于死鎖狀況，可以根據(jù)優(yōu)先級(jí)的高低按照前面方式逐一進(jìn)行規(guī)劃。AGV本身有自己的優(yōu)先級(jí)設(shè)定，負(fù)載的AGV優(yōu)先級(jí)高于空載AGV,負(fù)載狀態(tài)下前往貨架位置的AGV優(yōu)先級(jí)高于前往揀選臺(tái)的優(yōu)先級(jí)。

三、功能實(shí)現(xiàn)

本文針對(duì)電商倉(cāng)庫(kù)設(shè)計(jì)柵格地圖，目的在于確定機(jī)器人位置與目標(biāo)貨架最短的路徑上的點(diǎn)，得到AGV最短線路的計(jì)算。本文最終構(gòu)建28*30柵格地圖，每臺(tái)AGV在地圖中占據(jù)一個(gè)柵格大小。目標(biāo)貨架位置根據(jù)訂單貨物所在的貨架確定，通過柵格節(jié)點(diǎn)信息獲取貨物所在貨架信息，具體實(shí)現(xiàn)最短線路的步驟如下：

(1)確定地圖位置節(jié)點(diǎn)，包括起始點(diǎn)、取貨點(diǎn)、卸貨點(diǎn)；

(2)根據(jù)貨物訂單確定目標(biāo)貨架，利用求解算法得到最短路徑；

(3)利用時(shí)間窗對(duì)路徑進(jìn)行沖突檢查，如沖突發(fā)生采用避障策略解決沖突；

(4)對(duì)新路徑進(jìn)行時(shí)間窗檢查，如果發(fā)現(xiàn)沖突繼續(xù)激活避障策略，如果無沖突則找到最優(yōu)路徑，尋路結(jié)束。

四、實(shí)驗(yàn)結(jié)果

為方便直觀的用本文方法研究機(jī)器人路徑規(guī)劃問題，現(xiàn)對(duì)機(jī)器人一系列操作做以下假設(shè)：

(1)機(jī)器人直行路過一個(gè)柵格花費(fèi)1秒；轉(zhuǎn)彎花費(fèi)2秒，等待時(shí)間為3秒；

(2)AGV負(fù)載和未負(fù)載狀態(tài)下運(yùn)行速度相同且保持不變。

實(shí)驗(yàn)初步設(shè)置兩個(gè)任務(wù)實(shí)現(xiàn)避障。圖1中路線①為揀選臺(tái)到目標(biāo)貨架的初始路線，路線②為目標(biāo)貨架到揀選臺(tái)的初始路徑。經(jīng)過時(shí)間窗檢測(cè)后發(fā)現(xiàn)兩條路線在路徑重合點(diǎn)處發(fā)生沖突，根據(jù)本文提出的算法由于貨架到揀選臺(tái)的優(yōu)先級(jí)相對(duì)較低，所以對(duì)路徑②來說，將重疊時(shí)間窗內(nèi)沖突節(jié)點(diǎn)設(shè)置為在該時(shí)間段內(nèi)不可通過節(jié)點(diǎn)，比較等待代價(jià)和重新規(guī)劃路徑代價(jià)，最終路徑結(jié)果如圖2所示。經(jīng)過檢測(cè)后路徑①和路徑②沒有時(shí)間窗重疊，所以為最終最優(yōu)路徑。

圖1 初始路徑規(guī)劃 圖2 本文算法路徑規(guī)劃

五、結(jié)束語

本文通過A*算法對(duì)訂單任務(wù)進(jìn)行路徑規(guī)劃，并模擬訂單揀選過程完成最短路徑的獲取及機(jī)器人之間的避障。但是文中對(duì)可能產(chǎn)生的碰撞問題沒有完全考慮，并且文中采取的算法的實(shí)時(shí)性不足，這些都是以后要研究的重點(diǎn)。本文實(shí)現(xiàn)的僅僅是路徑方面的優(yōu)化避障，并未涉及機(jī)器人間信息交流方式。相信隨著智能倉(cāng)庫(kù)中AGV的數(shù)量越來越多工作量會(huì)越來越大，如何優(yōu)化工作流程，設(shè)計(jì)出合理路徑，進(jìn)而節(jié)約工作時(shí)間愈加變成一個(gè)重點(diǎn)問題。