基于改進(jìn)A*算法的多機(jī)器人動(dòng)態(tài)路徑規(guī)劃①

董朝瑞 郭 欣 李 寧 邵謝寧

(河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院 天津 300130)

0 引 言

近年來，隨著電商行業(yè)的迅猛發(fā)展，物流配送作為電商行業(yè)的核心要素之一越來越受到人們的關(guān)注。由于電子商務(wù)的物流配送工作具有品種多、批次多的特點(diǎn)，傳統(tǒng)工作模式下工人大多數(shù)的時(shí)間都浪費(fèi)在了取貨上[1]。因此人們對(duì)智能倉儲(chǔ)系統(tǒng)的需求越來越迫切，隨著以亞馬遜Kiva Systems為代表的智能倉儲(chǔ)系統(tǒng)興起，高效的多移動(dòng)機(jī)器人智能倉儲(chǔ)系統(tǒng)成為研究熱點(diǎn)之一[2]。將多移動(dòng)機(jī)器人應(yīng)用在智能倉儲(chǔ)系統(tǒng)中代替人來進(jìn)行搬運(yùn)工作可以有效降低倉儲(chǔ)系統(tǒng)運(yùn)維成本，提高運(yùn)作效率。在多移動(dòng)機(jī)器人智能倉儲(chǔ)系統(tǒng)的研究中，多機(jī)器人路徑規(guī)劃和碰撞預(yù)防是實(shí)現(xiàn)多移動(dòng)機(jī)器人智能倉儲(chǔ)系統(tǒng)的關(guān)鍵。

對(duì)于多機(jī)器人路徑規(guī)劃，傳統(tǒng)的方法是將Dijkstra算法和時(shí)間窗原理結(jié)合起來進(jìn)行多機(jī)器人路徑規(guī)劃[3-5]。但是，隨著節(jié)點(diǎn)數(shù)量的不斷增加，Dijkstra算法的效率將顯著降低，因此Dijkstra算法僅適用于小型系統(tǒng)。目前在智能倉庫的環(huán)境下研究多機(jī)器人系統(tǒng)主要采用以A*算法[6，7]、蟻群算法[8，9]、D*算法[10]為基礎(chǔ)的路徑規(guī)劃。其中蟻群算法和D*算法可以避開環(huán)境中未知障礙，屬于動(dòng)態(tài)路徑規(guī)劃算法，但是這2種算法無法得到全局最優(yōu)的路徑。A*算法作為一種啟發(fā)式搜索算法，具有簡(jiǎn)單高效的特點(diǎn)，能夠得到全局最優(yōu)路徑，是目前最流行的機(jī)器人路徑規(guī)劃算法。由于智能倉儲(chǔ)系統(tǒng)中多機(jī)器人同時(shí)工作的特點(diǎn)，機(jī)器人工作環(huán)境變化迅速，應(yīng)用傳統(tǒng)的A*算法進(jìn)行路徑規(guī)劃可能會(huì)導(dǎo)致交通堵塞問題，甚至產(chǎn)生死鎖現(xiàn)象，導(dǎo)致系統(tǒng)崩潰。……