王江華，趙 燕

(1.華北科技學(xué)院 電子信息工程學(xué)院，河北 三河 065201； 2.燕京理工學(xué)院 信息科學(xué)與技術(shù)學(xué)院，河北 三河 065201)

改進(jìn)型蟻群算法在多關(guān)節(jié)機(jī)器人捕捉路徑規(guī)劃上的應(yīng)用

王江華1，趙 燕2

(1.華北科技學(xué)院 電子信息工程學(xué)院，河北 三河 065201； 2.燕京理工學(xué)院 信息科學(xué)與技術(shù)學(xué)院，河北 三河 065201)

針對(duì)狹窄空間中機(jī)械臂的路徑規(guī)劃問題，提出一種改進(jìn)型蟻群優(yōu)化算法應(yīng)用于機(jī)械臂的路徑規(guī)劃。通過對(duì)傳統(tǒng)蟻群算法從概率分布的計(jì)算、最優(yōu)路徑二次優(yōu)化、路徑淘汰機(jī)制等方面進(jìn)行改進(jìn)，并使用Matlab軟件進(jìn)行仿真。對(duì)比改進(jìn)前后算法的收斂效果，發(fā)現(xiàn)改進(jìn)型蟻群算法的自組織性大大增強(qiáng)了系統(tǒng)的魯棒性，能夠明顯提高機(jī)械臂在礦井等復(fù)雜環(huán)境下的適應(yīng)能力。

機(jī)械臂； 路徑規(guī)劃； 蟻群優(yōu)化算法； 自組織性

0 引 言

隨著工業(yè)3.0的普及和人工智能的發(fā)展，機(jī)器人已經(jīng)在結(jié)構(gòu)化的工廠環(huán)境中得以靈活應(yīng)用。在工業(yè)領(lǐng)域，機(jī)器人主要以機(jī)械臂的形式出現(xiàn)，并作為提升工作效率的利器被許多自動(dòng)化生產(chǎn)線所廣泛應(yīng)用，尤其像工礦企業(yè)，工作重復(fù)度較高且工作環(huán)境惡劣，完全可以使用機(jī)械臂替代傳統(tǒng)人工勞動(dòng)力。在對(duì)機(jī)械臂的優(yōu)化控制以及路徑規(guī)劃方面，近年來出現(xiàn)過很多算法，例如傳統(tǒng)的柵格法、人工勢(shì)場(chǎng)法，以及近幾年出現(xiàn)的一些仿生學(xué)算法，包括遺傳算法、蟻群算法等。本文提出一種改進(jìn)型蟻群算法，應(yīng)用于多關(guān)節(jié)機(jī)械臂的路徑規(guī)劃中，利用蟻群算法的自組織能力以及較強(qiáng)的魯棒性，提高機(jī)械臂在復(fù)雜環(huán)境下工作的適應(yīng)能力。

1 蟻群優(yōu)化算法

1.1蟻群優(yōu)化算法的基本原理

蟻群優(yōu)化算法(ACO)是一種基于種群的啟發(fā)式仿生進(jìn)化系統(tǒng)[1]。在螞蟻覓食過程中，依靠覓食的螞蟻在尋找食物過程中散發(fā)的信息素來引導(dǎo)其他螞蟻對(duì)路徑的選擇，選擇過程可用下式描述[2]：

(1)

通過信息素聚集與揮發(fā)的反饋?zhàn)饔脤?shí)現(xiàn)信息素的更新，以此來區(qū)分不同優(yōu)劣程度的路徑，最終使得螞蟻都能夠沿著一條最優(yōu)的路徑到達(dá)食物所在處，其更新過程可用下式描述：

(2)

(3)

1.2ACO在機(jī)械臂路徑規(guī)劃中存在的問題

經(jīng)過仿真實(shí)驗(yàn)，機(jī)械臂在傳統(tǒng)蟻群算法的引導(dǎo)下，并不能快速到達(dá)目標(biāo)點(diǎn)。經(jīng)過反復(fù)對(duì)比總結(jié)，原因在于機(jī)械臂的路徑規(guī)劃中最初只知道2個(gè)點(diǎn)的初、末位置，且其不確定性較大。同時(shí)，ACO是根據(jù)全局信息素來選擇道路，在初始狀態(tài)下各道路信息素濃度一致，在螞蟻遍歷過程中，逐漸淘汰信息素低的路徑，對(duì)新道路的試探性較低，這樣就會(huì)使得算法陷入局部最優(yōu)解的情況。故不能直接將ACO應(yīng)用到機(jī)械臂的路徑規(guī)劃中，需要對(duì)基本ACO做一些調(diào)整[4-5]。

2 ACO的改進(jìn)

ACO主要改進(jìn)的流程：①計(jì)算概率分布的改進(jìn)。結(jié)合道路選擇概率、轉(zhuǎn)移概率，根據(jù)不同狀態(tài)下蟻群系統(tǒng)的不同狀態(tài)進(jìn)行動(dòng)態(tài)融合兩種概率，以配置螞蟻的道路選擇概率[6]。②路徑優(yōu)化改進(jìn)。通過螞蟻淘汰制的應(yīng)用以及優(yōu)勢(shì)螞蟻?zhàn)疃搪窂降谋４?，加速蟻群系統(tǒng)的收斂速度達(dá)到加速算法的目的。

2.1計(jì)算概率分布的改進(jìn)

在機(jī)械臂的路徑規(guī)劃中，由于只知道起點(diǎn)與終點(diǎn)，不確定性因素較大，依靠原有的轉(zhuǎn)移概率，只能在路徑交叉點(diǎn)處，依靠信息啟發(fā)因子和期望啟發(fā)因子對(duì)路徑進(jìn)行選擇[7]。期望啟發(fā)因子ηij一般采用：

ηij=1/dij

其中：dij表示相鄰兩個(gè)城市之間的距離，是固定的量，僅能夠表示局部道路的情況。信息啟發(fā)因子雖有一定的全局效果，但是只有在正確的正反饋前提下才能夠發(fā)揮真正的作用。

(4)

式中：W(i)表示點(diǎn)i周圍可選擇點(diǎn)的集合，算法中人工螞蟻可以向前后左右、左上左下、右上右下8個(gè)方向活動(dòng)，因此W(i)中i≤8；distence(j,end)指點(diǎn)j到終點(diǎn)end的距離。由于相鄰格點(diǎn)距離差較小，故通過參數(shù)匹配，使用ω、μ、λ將其差距擴(kuò)大，設(shè)定ω=10=μ=2=λ=2。

Pnewij=(1-ρh)Pij+ρhPhij

(5)

隨著螞蟻路徑的逐漸收斂，地圖中的信息素差異性增大，故在一定時(shí)間后可逐步增加距離導(dǎo)向概率的融合比ρh，使得螞蟻能更加有目的的選擇路徑，從而加快蟻群的收斂速度，進(jìn)而加速算法的執(zhí)行速度。

2.2路徑優(yōu)化改進(jìn)

2.2.1最優(yōu)路徑二次優(yōu)化

為避免蟻群在尋找最優(yōu)路徑中陷入“死胡同”，在算法運(yùn)行之前，可將蟻群運(yùn)行環(huán)境進(jìn)行人為調(diào)整，將路障圖中的自然死路的路口進(jìn)行封閉。以此減小算法的失誤率。在算法執(zhí)行過程中不僅在地圖初始化過程中需要人工對(duì)地圖凸化處理，在每次迭代中產(chǎn)生的優(yōu)秀路線也需要進(jìn)行處理，化曲為直，并將優(yōu)秀路線引入到下一代的蟻群運(yùn)行中[10]。優(yōu)化路線化曲為直，首先判斷是否存在凹陷路線并查找路徑Path1數(shù)組，Path1數(shù)組用下式描述：

(6)

判斷該點(diǎn)附近的可到達(dá)點(diǎn)Iwt，是否在數(shù)組Path1中，若存在修正點(diǎn)Iwt，則舍去Path1數(shù)組中該點(diǎn)與當(dāng)前點(diǎn)的中間點(diǎn)，并將當(dāng)前點(diǎn)Path1和修正點(diǎn)Iwt保存于優(yōu)化路徑中，以達(dá)到修正路線的目的。最后將修正路線保存并移入下一次迭代指導(dǎo)算法的發(fā)展方向。

2.2.2路徑淘汰機(jī)制

在蟻群算法的路徑處理中，設(shè)置“路徑淘汰制”，當(dāng)有螞蟻在行走中已經(jīng)進(jìn)入“死胡同”，沒有道路可走時(shí)，自動(dòng)放棄該螞蟻的路徑，所經(jīng)過路徑不進(jìn)行信息素的更新。該種方法使得每次迭代只需對(duì)部分螞蟻路徑進(jìn)行信息素更新，降低計(jì)算量，同時(shí)也削弱了路徑質(zhì)量較差的螞蟻對(duì)蟻群系統(tǒng)的影響[11]。

2.3改進(jìn)的ACO

改進(jìn)的ACO實(shí)現(xiàn)過程如下[12-13]：

(1) 初始化蟻群參數(shù)。信息素τ，定義最大迭代次數(shù)Kmax，設(shè)定機(jī)械臂起始點(diǎn)S、終止點(diǎn)E，設(shè)置啟發(fā)因子α與期望啟發(fā)因子β以及信息素?fù)]發(fā)系數(shù)ρ與啟發(fā)函數(shù)η。

(2) 迭代循環(huán)K=K+1。

(3) 螞蟻編號(hào)m=m+1。

(4) 初始化地形圖矩陣，計(jì)算鄰接矩陣相關(guān)距離矩陣，并進(jìn)行凸化處理。

(5) 設(shè)置m只螞蟻從起點(diǎn)S出發(fā)，采用路徑淘汰原則進(jìn)行探索，并計(jì)算每只螞蟻的道路選擇概率。

(6) 結(jié)合道路選擇概率、轉(zhuǎn)移概率以及迭代分配比，計(jì)算螞蟻的路徑選擇概率。

(7) 是否到達(dá)目的地？是則執(zhí)行(8)，否則跳轉(zhuǎn)到(3)。

(8) 記錄螞蟻路線和長度，保留優(yōu)秀螞蟻，保存到下一次迭代。采用式(5)對(duì)路徑進(jìn)行優(yōu)化，同時(shí)執(zhí)行(3)。

(9) 根據(jù)式(1)、(4)，更新地圖中的信息素。

(10) 是否達(dá)到最大迭代次數(shù)Kmax，若達(dá)到則執(zhí)行(11)，否則跳轉(zhuǎn)到(2)。

(11) 循環(huán)結(jié)束，繪制最優(yōu)路徑圖、誤差曲線圖以及各代路徑圖。

3 仿真實(shí)驗(yàn)與分析

3.1仿真環(huán)境搭建

為了檢驗(yàn)改進(jìn)算法使機(jī)械臂在井下復(fù)雜狹窄環(huán)境中的適應(yīng)性，在Matlab中使用柵格法模擬井下狹窄空間內(nèi)的障礙分布情況，如圖1所示[14]。柵格障礙地圖中白色方塊為可通過路徑，黑色方塊為抽象障礙，將改進(jìn)型蟻群算法應(yīng)用于路徑規(guī)劃。設(shè)置地圖中的起點(diǎn)(即機(jī)械臂的位置)和終點(diǎn)(即所要捕捉的物體)，蟻群從起點(diǎn)出發(fā)，通過路徑規(guī)劃尋出一條到達(dá)終點(diǎn)的最優(yōu)路線。設(shè)定螞蟻個(gè)數(shù)m=15，期望啟發(fā)因子β=7，啟發(fā)式因子α=1，信息素蒸發(fā)系數(shù)ρ=0.3。

圖1 柵格障礙仿真地圖

3.2實(shí)驗(yàn)結(jié)果分析

由各代螞蟻路徑圖2可看出，蟻群對(duì)地圖中區(qū)域路徑都進(jìn)行過嘗試，所選擇的路徑具有一定的全局優(yōu)秀特征。在路徑圖中也可以看見有許多路徑并未到達(dá)終點(diǎn)便中途截止，可以看出，算法中淘汰制的有效應(yīng)用[15]。從收斂曲線圖3中可以看出，改進(jìn)型算法通過優(yōu)勢(shì)種群的傳遞以及距離導(dǎo)向概率的引入再加上動(dòng)態(tài)的概率選擇，使得整個(gè)算法在第40次迭代后基本收斂，即已經(jīng)搜尋到全局最優(yōu)路線。

圖2 各代螞蟻路徑圖

3.3ACO路徑規(guī)劃

在礦井的狹小環(huán)境下，機(jī)械臂可沿圖4所示路徑對(duì)目標(biāo)物體進(jìn)行抓取。原始算法與改進(jìn)算法所得最優(yōu)規(guī)劃路徑見圖4。

圖3 收斂曲線圖

(a) 改進(jìn)算法

經(jīng)過多次重復(fù)取點(diǎn)實(shí)驗(yàn)，所得原始算法與改進(jìn)算法的最優(yōu)路徑與執(zhí)行時(shí)間如表1所示。

表1 原始算法與改進(jìn)算法的最優(yōu)路徑與執(zhí)行時(shí)間表

4 結(jié) 語

傳統(tǒng)蟻群算法僅通過啟發(fā)因子α和期望啟發(fā)因子β控制螞蟻的道路選擇方向，在對(duì)機(jī)械臂路徑規(guī)劃應(yīng)用中極容易陷入局部最優(yōu)，并且由于算法的自組織性，使得系統(tǒng)需要一個(gè)較長時(shí)間的演化過程。本文針對(duì)ACO易陷入局部最優(yōu)解以及算法的執(zhí)行時(shí)間較長的缺陷，使用融合型道路選擇概率、最優(yōu)路徑二次優(yōu)化以及路徑淘汰機(jī)制對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)[16-17]。通過對(duì)傳統(tǒng)算法與改進(jìn)算法的仿真實(shí)驗(yàn)，可以看出改進(jìn)算法用時(shí)大幅度降低，最優(yōu)路徑中改進(jìn)后不存在路徑凹陷類型的路徑影響道路質(zhì)量，其次最優(yōu)路徑也得到了明顯的減少，基本接近理論值。實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)型蟻群算法在機(jī)械臂上的應(yīng)用能夠大幅度提高機(jī)械臂的運(yùn)動(dòng)能力。

[1] 張 成，凌有鑄，陳孟元.改進(jìn)蟻群算法求解移動(dòng)機(jī)器人路徑規(guī)劃[J].電子測(cè)量與儀器學(xué)報(bào)，2016(11)：1758-1764.

[2] 張曉玲，羅印升，張寶峰，等.基于蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].激光雜志，2016(11)：80-83.

[3] 楊雅寧，藺 勇.基于蟻群算法的一種無人機(jī)二維航跡規(guī)劃方法研究[J].電腦知識(shí)與技術(shù)，2016(28)：189-191.

[4] 宗澤宏.蟻群算法的應(yīng)用與改進(jìn)[J].電子技術(shù)與軟件工程，2017(1)：155.

[5] 尚夢(mèng)雨.無人機(jī)實(shí)時(shí)蟻群算法路徑規(guī)劃[J].自動(dòng)化應(yīng)用，2016(12)：61-63.

[6] 李 卿，吳玉渠.應(yīng)急救援路徑選擇的蟻群算法優(yōu)化[J].自動(dòng)化技術(shù)與應(yīng)用，2016(12)：1-5.

[7] 朱顥東，孫 振，吳 迪.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人三維路徑規(guī)劃[J].華中師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016(6)：812-817.

[8] 易正俊，李勇霞，易校石.自適應(yīng)蟻群算法求解最短路徑和TSP問題[J].計(jì)算機(jī)技術(shù)與發(fā)展，2016(12)：1-5.

[9] 唐勝景，陳天悅，李 震，等.基于感知模糊自適應(yīng)蟻群算法的非線性PID控制設(shè)計(jì)[J].計(jì)算機(jī)測(cè)量與控制，2016(11)：91-94，99.

[10] 趙曉俠，鞠成恩.基于改進(jìn)蟻群算法的農(nóng)業(yè)運(yùn)輸車輛路徑優(yōu)化研究[J].安徽農(nóng)業(yè)科學(xué)，2016(33)：237-238.

[11] 譚覃，劉樹東，張 艷.移動(dòng)機(jī)器人路徑規(guī)劃仿真研究[J].計(jì)算機(jī)仿真，2016(8)：354-358，424.

[12] 黃亞平，熊 婧.基于改進(jìn)蟻群算法作業(yè)車間調(diào)度問題仿真研究[J].計(jì)算機(jī)仿真，2009(8)：278-282.

[13] 朱顥東，孫 振，吳 迪，等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016(6)：849-855.

[14] 劉云龍，王瑞蘭，劉麗君，等.基于Matlab仿真的自動(dòng)控制原理實(shí)驗(yàn)教學(xué)改革[J].實(shí)驗(yàn)室研究與探索，2015(6)：103-106.

[15] 張汝波，李建軍，楊 玉.基于改進(jìn)蟻群算法的AUV航路避障任務(wù)規(guī)劃[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015(S1)：428-430.

[16] 穆 克，陳 濤，褚俊霞，等.網(wǎng)絡(luò)搜索中的“死胡同”現(xiàn)象及蟻群改進(jìn)算法[J].控制工程，2013(4)：762-765.

[17] 付 鵬，羅 杰.基于改進(jìn)蟻群算法的Q學(xué)習(xí)算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013(2)：123-126.

ApplicationofImprovedAntColonyAlgorithminPathPlanningofMulti-jointRobot

WANGJianghua1，ZHAOYan2

(1.Electronic Information Engineering College，North China Institute of Science and Technology，Sanhe 065201, Hebei，China； 2.College of Information Science and Technology，Yanching Institute of Technology，Sanhe 065201，Hebei, China)

In this paper, an improved ant colony algorithm is proposed to solve the path planning problem of manipulator in narrow space.The traditional ant colony algorithm is improved from the calculation of probability distribution, quadratic optimization of optimal path and path elimination mechanism, and the simulation results are compared by using Matlab software.The results show that the organization ability of the improved ant colony algorithm greatly enhances the robustness of the system, the algorithm can significantly improve the adaptability of robot arm in the mine and other complex environments.

mechanical arm； route plan； ant colony optimization(ACO) algorithm； self-organization

TP 301

A

1006-7167(2017)10-0041-04

2017-02-15

河北省高等學(xué)校科學(xué)技術(shù)研究項(xiàng)目(Z2015202)；廊坊市科技支撐計(jì)劃項(xiàng)目(2016011033)；華北科技學(xué)院科技基金項(xiàng)目(3142014072)

王江華(1981-)，男，河北邢臺(tái)人，碩士，講師，研究方向：智能控制、圖像處理以及電機(jī)控制等。Tel.：13785699600；E-mail：jianghua960@163.com

趙 燕(1982-)，女，河北石家莊人，碩士，講師，研究方向：實(shí)驗(yàn)室建設(shè)與管理、實(shí)驗(yàn)教學(xué)改革。Tel.：13784464373；E-mail：zhaoyan137@163.com