[發(fā)明專利]一種基于蟻群算法的室內(nèi)AGV路徑規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202111149575.6
• 申請(qǐng)日: 2021-09-29
• 公開(kāi)（公告）號(hào): CN113848919A
• 公開(kāi)（公告）日: 2021-12-28
• 發(fā)明（設(shè)計(jì)）人: 肖金壯;余雪樂(lè);周振;孫可可
• 申請(qǐng)（專利權(quán)）人: 河北大學(xué)
• 主分類(lèi)號(hào): G05D1/02
• 分類(lèi)號(hào): G05D1/02
• 代理公司: 石家莊國(guó)域?qū)＠虡?biāo)事務(wù)所有限公司 13112
• 代理人: 胡素梅

本發(fā)明提供了一種基于蟻群算法的室內(nèi)AGV路徑規(guī)劃方法。本發(fā)明通過(guò)引用距離函數(shù)和方向函數(shù)作為啟發(fā)因子改進(jìn)啟發(fā)函數(shù)，增加算法的啟發(fā)性，引導(dǎo)螞蟻向著較優(yōu)的方向和位置節(jié)點(diǎn)搜索，有效減少在AGV移動(dòng)過(guò)程中可能出現(xiàn)的尖銳轉(zhuǎn)彎，提升路徑質(zhì)量。而且，本發(fā)明還通過(guò)改進(jìn)狀態(tài)轉(zhuǎn)移概率和自適應(yīng)參數(shù)調(diào)整策略，在不斷迭代的過(guò)程中，算法的控制參數(shù)不斷調(diào)整和變化。再有，本發(fā)明基于差異化?分級(jí)信息素更新改進(jìn)信息素更新方法。將改進(jìn)后的蟻群算法應(yīng)用到AGV室內(nèi)路徑規(guī)劃中，可以使AGV快速地搜索得到實(shí)際環(huán)境中一條起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的無(wú)碰撞的較優(yōu)路徑，從而提升運(yùn)輸效率，減少人工運(yùn)輸成本。

技術(shù)領(lǐng)域

本發(fā)明涉及機(jī)器人技術(shù)應(yīng)用領(lǐng)域，具體地說(shuō)是一種基于蟻群算法的室內(nèi)AGV路徑規(guī)劃方法。

背景技術(shù)

路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航發(fā)展的關(guān)鍵技術(shù)之一，在很多領(lǐng)域都有著非常重要的應(yīng)用，比如自動(dòng)駕駛、AGV物流倉(cāng)儲(chǔ)、地面移動(dòng)機(jī)器人導(dǎo)航等等。其中，AGV的路徑規(guī)劃技術(shù)實(shí)際上是指基于某個(gè)或者多個(gè)參數(shù)(如最小能耗、最短路徑、最短運(yùn)行時(shí)間等)指標(biāo)，在AGV自由移動(dòng)空間內(nèi)找到一條從起始節(jié)點(diǎn)到目標(biāo)地點(diǎn)的安全路徑。其本質(zhì)是在各種約束條件下獲得最優(yōu)或可行解的問(wèn)題。路徑規(guī)劃結(jié)果的優(yōu)劣會(huì)直觀地影響AGV任務(wù)的實(shí)時(shí)性和結(jié)果的質(zhì)量。

路徑規(guī)劃最早始于20世紀(jì)60年代，路徑規(guī)劃的基礎(chǔ)是環(huán)境模型的建立，它直接影響算法的選擇。環(huán)境建模主要包括網(wǎng)格(柵格)模型、幾何模型、拓?fù)淠Ｐ汀Ｆ渲袞鸥衲Ｐ捅粡V泛利用。但是對(duì)于大規(guī)模環(huán)境來(lái)說(shuō)，過(guò)多的柵格會(huì)造成內(nèi)存變多，計(jì)算量大。路徑規(guī)劃算法的早期研究主要是針對(duì)全局靜態(tài)的規(guī)劃，比如可視圖法、A*算法。但是隨著人工智能的不斷發(fā)展，基于仿生學(xué)的智能算法的優(yōu)越性逐漸體現(xiàn)出來(lái)，比如蟻群算法、粒子群算法、麻雀算法。對(duì)于復(fù)雜和大規(guī)模的地圖，早期的路徑規(guī)劃算法往往不能得到較好的求解效果。隨著人工智能的發(fā)展，越來(lái)越多的人集中于智能仿生算法在路徑規(guī)劃上的研究。

蟻群算法具有易與其他規(guī)劃算法結(jié)合、魯棒性強(qiáng)、正反饋、具有啟發(fā)式性等特點(diǎn)。蟻群算法是一種尋找優(yōu)化路徑的概率算法，它是模仿螞蟻尋找食物的過(guò)程，螞蟻在尋找食物的過(guò)程中會(huì)釋放一種可稱之為信息素的物質(zhì)，路徑較短的螞蟻會(huì)釋放更多的信息素，隨著時(shí)間的推進(jìn)，較短的路徑會(huì)積累越來(lái)越多的信息素，那么選擇該路徑的螞蟻也越來(lái)越多，最終在正反饋的機(jī)制下尋找出最優(yōu)路徑。它從產(chǎn)生之日起就成為一個(gè)熱門(mén)話題，研究者廣泛運(yùn)用改進(jìn)的蟻群優(yōu)化算法解決各種復(fù)雜的組合優(yōu)化問(wèn)題，作為群智能算法的一種，最早是被用于解決TSP問(wèn)題的，同樣的，也被成功證明能夠解決路徑規(guī)劃問(wèn)題。但是作為一種概率優(yōu)化的智能算法，和其他的智能算法一樣，其具有一些明顯的缺點(diǎn)，比如：收斂速度慢、容易出現(xiàn)死鎖現(xiàn)象和搜索效率低，尤其在大規(guī)模復(fù)雜地圖中算法搜索效率較差等問(wèn)題。

發(fā)明內(nèi)容

本發(fā)明的目的就是提供一種基于蟻群算法的室內(nèi)AGV路徑規(guī)劃方法，以解決傳統(tǒng)蟻群算法致使全局搜索效率低、收斂速度慢、規(guī)劃的路徑轉(zhuǎn)彎過(guò)多且不夠平滑等的缺點(diǎn)。

本發(fā)明是這樣實(shí)現(xiàn)的：一種基于蟻群算法的室內(nèi)AGV路徑規(guī)劃方法，包括如下步驟：

a、構(gòu)建柵格地圖，為AGV設(shè)定好起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)。

b、初始化蟻群算法各項(xiàng)參數(shù)；蟻群算法各項(xiàng)參數(shù)包括：螞蟻數(shù)量m，最大迭代次數(shù)NC，信息素重要程度因子α，信息素初始濃度τ_ij(0)，啟發(fā)函數(shù)重要因子最大值β_max和最小值β_min，信息素?fù)]發(fā)因子ρ，自適應(yīng)狀態(tài)轉(zhuǎn)移概率選擇參數(shù)q₀，信息素強(qiáng)度Q，精英螞蟻(包括一級(jí)螞蟻和二級(jí)螞蟻)個(gè)數(shù)ε。

c、將螞蟻放在起始節(jié)點(diǎn)上。

d、計(jì)算改進(jìn)的啟發(fā)函數(shù)，并按照改進(jìn)的自適應(yīng)偽隨機(jī)概率選擇下一節(jié)點(diǎn)，改進(jìn)的自適應(yīng)偽隨機(jī)概率轉(zhuǎn)移規(guī)則如下面公式所示：

其中，q為0-1之間的隨機(jī)值，q₀是自適應(yīng)狀態(tài)轉(zhuǎn)移概率選擇參數(shù)，為傳統(tǒng)蟻群算法的輪盤(pán)賭隨機(jī)選擇模型，的計(jì)算公式如下所示：