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

王江華，趙 燕

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

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

王江華1，趙 燕2

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

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

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

0 引 言

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

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

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

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

(1)

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

(2)

(3)

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

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

2 ACO的改進

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

2.1計算概率分布的改進

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

ηij=1/dij

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

(4)

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

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

(5)

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

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

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

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

(6)

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

2.2.2路徑淘汰機制

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

2.3改進的ACO

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗與分析

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

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

圖1 柵格障礙仿真地圖

3.2實驗結(jié)果分析

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

圖2 各代螞蟻路徑圖

3.3ACO路徑規(guī)劃

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

圖3 收斂曲線圖

(a) 改進算法

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

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

4 結(jié) 語

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

[1] 張 成，凌有鑄，陳孟元.改進蟻群算法求解移動機器人路徑規(guī)劃[J].電子測量與儀器學報，2016(11)：1758-1764.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[17] 付 鵬，羅 杰.基于改進蟻群算法的Q學習算法研究[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

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

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

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