[發(fā)明專(zhuān)利]一種基于交流策略蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010893573.7
• 申請(qǐng)日: 2020-08-31
• 公開(kāi)（公告）號(hào): CN112000105B
• 公開(kāi)（公告）日: 2021-07-06
• 發(fā)明（設(shè)計(jì)）人: 侯文彬;熊志華;王長(zhǎng)生
• 申請(qǐng)（專(zhuān)利權(quán)）人: 大連理工大學(xué);大連理工大學(xué)寧波研究院
• 主分類(lèi)號(hào): G05D1/02
• 分類(lèi)號(hào): G05D1/02
• 代理公司: 大連理工大學(xué)專(zhuān)利中心 21200
• 代理人: 李曉亮

1.一種基于交流策略蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法，其特征在于，該方法包括以下步驟：

S1，設(shè)置地圖任務(wù)

根據(jù)機(jī)器人的工作環(huán)境建立地圖坐標(biāo)系，以橫向?yàn)閤軸，豎向?yàn)閥軸，并把地圖劃分為均勻的網(wǎng)格節(jié)點(diǎn)，依次按x軸正向和y軸負(fù)向進(jìn)行編號(hào)并獲取對(duì)應(yīng)的坐標(biāo)值；對(duì)可行點(diǎn)和障礙物進(jìn)行二進(jìn)制處理，可行點(diǎn)的值為0，障礙物的值為1；然后根據(jù)任務(wù)在地圖上設(shè)置起始點(diǎn)S和目標(biāo)點(diǎn)E；

S2，初始化基本參數(shù)

初始化交流策略閾值n₀、單批螞蟻數(shù)量m、迭代總次數(shù)K、信息素強(qiáng)度系數(shù)Q、信息素激發(fā)因子α、啟發(fā)式信息激發(fā)因子β、信息素的揮發(fā)速率ρ；

S3，初始化信息值

信息素濃度的初始值τ_ij(0)設(shè)為1；啟發(fā)式信息的初始值η_ij(0)的設(shè)定公式如下：

其中，i表示當(dāng)前節(jié)點(diǎn)，j表示下一步要選擇的節(jié)點(diǎn)；d_jE是節(jié)點(diǎn)j到目標(biāo)點(diǎn)E之間的歐幾里得距離；pi是圓周率；θ_jiE是連線(i,j)與(j,E)之間的夾角；d_SE是起始點(diǎn)S到目標(biāo)點(diǎn)E之間的歐幾里得距離；C_q為螞蟻下一步允許選擇的節(jié)點(diǎn)集合；

S4，更新信息值

(1)信息素濃度值更新

當(dāng)k＝1即第一輪迭代時(shí)，τ_ij(1)＝τ_ij(0)；當(dāng)k＝2,3,...,K時(shí)，按照S9和S11處理；

(2)啟發(fā)式信息值更新

第k輪迭代時(shí)，其中k＝1,2,...,K，通過(guò)引入可調(diào)節(jié)衰減系數(shù)A_T來(lái)提高啟發(fā)式信息功能，啟發(fā)式信息值η_ij(k)如下公式所示：

η_ij(k)＝(η_ij(0))*A_T (2)

其中，δ為保留系數(shù)，決定啟發(fā)式信息最終保留的比例；μ為變化因子，控制A_T的變化速率；

S5，開(kāi)始一輪迭代

每輪迭代里包含m次單只螞蟻探索，螞蟻之間互不干涉；

S6，單只螞蟻探索

(1)選擇前進(jìn)路徑

單只螞蟻從起點(diǎn)S出發(fā)，每一步都先計(jì)算相鄰8個(gè)節(jié)點(diǎn)的信息量I_ij(k)，然后進(jìn)行排序獲得最大信息值I_ijmax(k)，再利用可調(diào)節(jié)乘子系數(shù)A_M對(duì)最大信息值I_ijmax(k)進(jìn)行放大后獲得相鄰8個(gè)節(jié)點(diǎn)新的信息量I_ijmax(k)′，再計(jì)算相鄰8個(gè)節(jié)點(diǎn)的選擇概率P_ij，最后通過(guò)輪盤(pán)賭法選擇下一步；具體公式如下：

其中，λ為刺激系數(shù)，決定A_M的最大放大倍數(shù)；σ為變化因子，控制A_M的變化速率；

(2)更新禁忌表

單只螞蟻?zhàn)哌^(guò)的路徑都放入其私有的禁忌表中，避免重復(fù)行走；

(3)判斷是否死鎖

若螞蟻未到達(dá)目標(biāo)點(diǎn)E且無(wú)路可走時(shí)，判定為死鎖，即該螞蟻無(wú)效，記錄其最后兩步路徑；否則，繼續(xù)選擇前進(jìn)路線；

(4)判斷是否結(jié)束探索

若螞蟻到達(dá)目標(biāo)點(diǎn)E，則該螞蟻有效，記錄其走過(guò)的完整路徑和路徑長(zhǎng)度，并結(jié)束探索；否則，繼續(xù)選擇前進(jìn)路線；

S7，判斷是否結(jié)束一輪迭代

若同一輪迭代執(zhí)行的單只螞蟻探索次數(shù)達(dá)到m次時(shí)，結(jié)束該輪迭代，然后對(duì)該輪有效的螞蟻路徑根據(jù)長(zhǎng)度從短至長(zhǎng)進(jìn)行排序，記錄最短路徑和長(zhǎng)度，對(duì)于無(wú)效即死鎖的螞蟻，統(tǒng)計(jì)最后兩步路徑相同的死鎖螞蟻數(shù)量；否則，繼續(xù)執(zhí)行S6；

S8，懲罰死鎖信息素

通過(guò)統(tǒng)計(jì)同一輪迭代中同一死鎖路徑的螞蟻數(shù)量Lost_ij，采用懲罰函數(shù)A_P對(duì)死鎖路徑進(jìn)行信息素懲罰獲得新的信息素濃度值τ_ij(k)′，具體公式如下：

τ_ij(k)′＝A_P*τ_ij(k) (7)

式(8)中，υ是數(shù)量因子，在[2,4]之間取整數(shù)；ceil是指向上舍入為最接近的整數(shù)；

S9，更新全局信息素

計(jì)算每只螞蟻的信息素濃度變化值根據(jù)到達(dá)終點(diǎn)的有效螞蟻路徑進(jìn)行全局信息素濃度更新，獲得下一輪迭代的信息素濃度過(guò)渡值τ_ij(k+1)′，具體公式如下：

其中，w表示同一輪迭代里有效的單只螞蟻的序號(hào)；L_w(k)是螞蟻w走過(guò)路徑的總長(zhǎng)度；

S10，選擇螞蟻交流策略

當(dāng)?shù)喆蝛≤n₀時(shí)，執(zhí)行螞蟻全交流策略；具體為：首先，進(jìn)行第k輪迭代的同代交流；然后依次與前面所有輪次進(jìn)行異代交流，直到與第1輪迭代完成交流獲得新的螞蟻交流路徑；

當(dāng)?shù)喆蝛n₀時(shí)，執(zhí)行螞蟻平衡交流策略；具體為：首先，進(jìn)行第k輪迭代的同代交流；然后依次與前面所有輪次進(jìn)行異代交流，直到與第k-n₀+1輪迭代完成交流獲得新的螞蟻交流路徑；

S11，信息素雙重獎(jiǎng)勵(lì)

首先計(jì)算S7中的最短有效螞蟻路徑的信息素獎(jiǎng)勵(lì)值和S10中的螞蟻交流路徑的信息素獎(jiǎng)勵(lì)值然后對(duì)信息素進(jìn)行雙重獎(jiǎng)勵(lì)，獲得下一輪迭代的信息素濃度值τ_ij(k+1)；具體公式如下：

其中，L_b(k)是S7中的最短有效螞蟻路徑的長(zhǎng)度；L_c(k)是S10中的螞蟻交流路徑的長(zhǎng)度；

S12，判斷是否滿(mǎn)足結(jié)束條件

若達(dá)到收斂條件或迭代輪次達(dá)到上限K時(shí)，返回最后一輪迭代的螞蟻交流路徑作為最佳路徑Path_best，其長(zhǎng)度作為最短長(zhǎng)度L_min；否則，返回S4繼續(xù)執(zhí)行。