基于改進(jìn)蟻群算法的機器人三維空間路徑規(guī)劃*

張文強，張 彥

(合肥工業(yè)大學(xué) 機械工程學(xué)院，合肥 230009)

0 引言

無碰撞路徑規(guī)劃也稱為避障路徑規(guī)劃，是軌跡規(guī)劃問題的一個重要組成部分，也是研究軌跡規(guī)劃問題的前提[1]。機器人的無碰撞路徑規(guī)劃是指：在一個存在已知或未知障礙物的環(huán)境中，機器人通過相應(yīng)算法能夠獲得一條從出發(fā)點到目標(biāo)點的路徑，該路徑能夠避開所有障礙物并滿足一定的限制條件[2]。

三維路徑規(guī)劃是指在已知三維地圖中，規(guī)劃出一條從出發(fā)點到目標(biāo)點并避開所有障礙物的最優(yōu)路徑?，F(xiàn)有的路徑規(guī)劃算法例如人工勢場法、模擬退火法等[3-5]多用于二維平面規(guī)劃空間，該類問題處理起來較為簡單。而進(jìn)行一般的三維路徑規(guī)劃時，往往要面對數(shù)據(jù)存儲量大、運算過程長、進(jìn)行全局規(guī)劃復(fù)雜等問題?，F(xiàn)有的三維路徑規(guī)劃算法主要有A*算法、遺傳算法、粒子群算法等[6-9]，但其中A*算法的計算量會隨著搜索維數(shù)的增加而急劇加大，遺傳算法和粒子群算法只能進(jìn)行準(zhǔn)三維空間的路徑規(guī)劃。針對本文所研究的問題，采用蟻群算法[10-12]較為適用，但原始的蟻群算法仍然存在著對待復(fù)雜環(huán)境靈活性不足、容易在障礙物表面反復(fù)震蕩而影響收斂速度等缺點。

本文提出了一種結(jié)合人工勢場思想的改進(jìn)蟻群算法，結(jié)合了人工勢場法和蟻群算法的優(yōu)勢，可以規(guī)避或在一定程度上降低兩種算法的不足，使其可以更好的應(yīng)用于三維空間中的無碰撞路徑規(guī)劃問題。

1 原始蟻群算法基本概述

本文提出的結(jié)合人工勢場思想的改進(jìn)蟻群算法是以蟻群算法為主體的一種改進(jìn)算法，因此本節(jié)先對原始蟻群算法的概念進(jìn)行簡單介紹，以方便在下文中對改進(jìn)方法及仿真結(jié)果進(jìn)行說明和對比。

1.1 三維搜索空間

圖1 規(guī)劃空間示意圖

三維路徑規(guī)劃算法首先需要從真實三維空間中抽象出三維空間模型，其方法如下：首先將地圖左下角頂點作為三維坐標(biāo)的原點A，以此為基準(zhǔn)建立三維坐標(biāo)系，x軸為縱向增加方向，y軸為橫向增加方向，z軸為高度增加方向。沿x方向取長度AB，沿y軸方向取長度AD，沿z軸方向取長度AA′，這樣就構(gòu)成了一個三維空間ABCD—A′B′C′D′,該區(qū)域即為三維路徑規(guī)劃空間，如圖1所示。

三維路徑空間建立之后，采用等分空間法從三維規(guī)劃空間中抽取路徑規(guī)劃所需的網(wǎng)格點。

首先沿著邊AB將規(guī)劃空間ABCD—A′B′C′D′分為n等分，得到n+1個分層面，接著對n+1個分層面沿邊AB進(jìn)行m等分，沿邊AA′進(jìn)行l(wèi)等分，并求解出里面的交點。這樣規(guī)劃空間就離散化為一個三維點集合，蟻群算法即在這些三維路徑點上進(jìn)行規(guī)劃。

1.2 分層前進(jìn)原則與可達(dá)域

圖2 空間分層及可視域示意圖

在實際應(yīng)用中，蟻群算法能夠很好地解決二維路徑規(guī)劃問題，這是因為在二維空間中對節(jié)點的選擇較為簡單。而在三維空間中，由于選擇范圍的擴大，往往會造成所選路徑局限在幾個啟發(fā)值較高的節(jié)點往復(fù)震蕩，如不能較快地跳出這個陷阱會造成收斂速度的降低甚至算法的失效。為應(yīng)對這個問題，在算法中采取了一種分層前進(jìn)的原則，其思想是：選定從起點到終點的方向為前進(jìn)方向，以該方向上以單位距離劃分層次，以當(dāng)前節(jié)點所在平面為基準(zhǔn)，建立可達(dá)域，所選節(jié)點全部出自下一平面的可達(dá)區(qū)域內(nèi)。圖2為其示意圖。

1.3 信息素系數(shù)

信息素概念是蟻群算法的核心概念，蟻群算法通過信息素的濃度對節(jié)點進(jìn)行尋優(yōu)。將搜索空間離散為一系列三維離散點，這些離散點就是算法所需要搜索的點，這里將信息素的值賦予在每個離散點中，這樣每一點的信息素值就是一個關(guān)于坐標(biāo)的函數(shù)，將其命名為信息素系數(shù)I(P)。該函數(shù)值由待選節(jié)點上的信息素濃度決定，信息素濃度越高證明之前經(jīng)過的螞蟻數(shù)越多。在算法具體運行過程中信息素是隨時更新的，這里包括局部更新和全局更新。

局部更新是指當(dāng)螞蟻經(jīng)過某一節(jié)點時，令該點信息素獲得較大的衰減，從而保證后續(xù)的螞蟻可以尋訪其他節(jié)點，避免陷于局部最優(yōu)，從而達(dá)到全局搜索的目的。其公式為：

τP=(1-ζ)τP

(1)

τP是點(i,j,k)上的信息素值，ζ為信息素衰減系數(shù)。

全局更新是指在放出的一批螞蟻完成了一條路徑的搜索后，根據(jù)評價函數(shù)找出最短路徑并增加該路徑上的節(jié)點的信息素值。其表達(dá)式為：

(2)

其中，ρ為全局信息素更新系數(shù)；K為信息素增長系數(shù)；min(l)為該批次螞蟻所尋得最短路徑。

1.4 最佳個體適應(yīng)度

最佳個體適應(yīng)度是體現(xiàn)結(jié)果優(yōu)化程度的指標(biāo)。在該算法中以路徑的總長度為優(yōu)化準(zhǔn)則，每完成一次搜索，都會用評價函數(shù)計算路徑的總長度并記錄下來。這里將記錄的最短路徑數(shù)據(jù)稱為最佳個體適應(yīng)度。評價函數(shù)的計算公式為：

(3)

1.5 原始蟻群算法流程

根據(jù)蟻群算法的思想，實現(xiàn)其功能的流程如圖3所示。

圖3 原始蟻群算法流程圖

2 算法改進(jìn)方案

當(dāng)螞蟻從當(dāng)前點向下一點移動時，需要對下一點進(jìn)行選擇，在原始算法中選擇節(jié)點的依據(jù)是由信息素系數(shù)單方面決定的，在實際應(yīng)用中該系數(shù)波動較大，會造成收斂速度慢、易于落入局部最優(yōu)等問題。為改進(jìn)上述不足，在改進(jìn)算法中引入結(jié)合人工勢場法思想的啟發(fā)函數(shù)，該啟發(fā)函數(shù)將與信息素系數(shù)共同作用來對節(jié)點進(jìn)行選擇。

2.1 啟發(fā)函數(shù)

針對節(jié)點選擇的啟發(fā)函數(shù)的表達(dá)式為：

H(P)=D(P)z1·G(P)z2·S(P)z3

(4)

式中，D(P)為當(dāng)前點與待選點間的距離，其計算公式如下：

(5)

a為當(dāng)前點，b為待選節(jié)點。由式可知兩點間距離越小則函數(shù)值越大，通過該式可令螞蟻優(yōu)先選擇較近的點。

G(P)和S(P)分別引力系數(shù)和避障系數(shù)。z1,z2,z3為權(quán)重系數(shù)，分別代表各因素的重要程度。

2.2 引力系數(shù)及避障系數(shù)

在人工勢場理論中，目標(biāo)點對機器人末端執(zhí)行器有一個虛擬的引力勢，本文在改進(jìn)蟻群算法中將其功能轉(zhuǎn)化為另一種形式，即G(P)，并稱G(P)為引力系數(shù)，其表達(dá)式為：

(6)

其中，P代表節(jié)點空間坐標(biāo)，b為待選節(jié)點，d為最終目標(biāo)點。其含義是在待選節(jié)點中，距離終點最近的點可得到更高的引力系數(shù)，從而影響該點的啟發(fā)值，獲得更高的選擇概率。

同理，將人工勢場理論中的斥力勢概念轉(zhuǎn)化為避障系數(shù)，用于判斷下一點是否可達(dá)，其表達(dá)式如下：

(7)

式中,d0為避障極限距離，dm為斥力作用距離，d為待選節(jié)點與障礙物距離，h為避障系數(shù)最大值。當(dāng)d小于d0時，S(P)取值為0，使該節(jié)點無法被選取。當(dāng)d位于d0與dm之間時，可根據(jù)公式計算該節(jié)點的避障系數(shù)。當(dāng)d大于dm時，節(jié)點不受斥力勢影響，避障系數(shù)取最大值h。

2.3 節(jié)點選擇概率函數(shù)

在蟻群算法中引入人工勢場方法，得到的改進(jìn)節(jié)點選擇概率函數(shù)形式為：

(8)

式中，C代表規(guī)劃空間的可行區(qū)域，α、β分別代表啟發(fā)函數(shù)與信息素系數(shù)的權(quán)重。

2.4 改進(jìn)蟻群算法流程

實現(xiàn)改進(jìn)后的蟻群算法功能的流程如圖4所示。

圖4 改進(jìn)蟻群算法流程圖

3 算法仿真及結(jié)果分析

在機器人的工作空間中抽取三維空間ABCD—A′B′C′D′作為路徑規(guī)劃空間，對空間進(jìn)行離散化，置入虛擬障礙并對障礙物進(jìn)行包裹處理，最終得到的規(guī)劃空間如圖5所示。對算法的仿真分析都將在該空間中進(jìn)行。

圖5 三維規(guī)劃空間

為驗證在算法中引入引力系數(shù)和避障系數(shù)所起的作用，下面分別利用原始蟻群算法和改進(jìn)后的蟻群算法以相同的初始條件進(jìn)行仿真，并對結(jié)果做對比分析。算法仿真的初始條件如表1所示。

表1 仿真初始條件

經(jīng)過程序運算，得到仿真路徑規(guī)劃結(jié)果，三維空間路徑如圖6所示，圖7為最佳個體適應(yīng)度變化趨勢圖，圖中虛線為原始算法，實線為改進(jìn)算法。

圖6 三維空間路徑規(guī)劃結(jié)果

圖7 最佳個體適應(yīng)度變化

通過觀察三維空間路徑的搜索結(jié)果可知，原始算法和改進(jìn)算法搜索到的路徑均滿足避障要求，但可以明顯看到原始算法得到的路徑較為曲折，而改進(jìn)算法得到的路徑要光滑許多。這是因為在啟發(fā)函數(shù)中引入引力系數(shù)令路徑節(jié)點的選擇更具有目的性，使每次的選擇都更加接近目標(biāo)點，而斥力系數(shù)的引入令路徑更有效地避開障礙物防止路徑在障礙物附近震蕩。通過對比最佳個體適應(yīng)度變化趨勢可以看到改進(jìn)算法在迭代初期就已獲得適應(yīng)度在30以下的路徑，并隨迭代次數(shù)增加獲得了更優(yōu)的路徑；而原始算法的適應(yīng)度從35

左右開始，經(jīng)過迭代雖有所下降，但在迭代200次之后仍高于改進(jìn)算法，這說明通過對原始算法的改進(jìn)，可令算法達(dá)到更快的收斂速度。

4 結(jié)論

為了提高進(jìn)行路徑規(guī)劃時的收斂效率和增加面對復(fù)雜規(guī)劃空間的靈活性，本文對機器人的無碰撞路徑規(guī)劃問題進(jìn)行了探討，并提出了一種結(jié)合人工勢場思想的改進(jìn)蟻群算法。

針對原始蟻群算法在復(fù)雜環(huán)境中收斂速度慢以及可能陷入局部最優(yōu)陷阱而導(dǎo)致收斂失敗的問題，改進(jìn)后的算法在啟發(fā)函數(shù)的設(shè)計中，引入了具有人工勢場思想的引力系數(shù)和避障系數(shù)，以提高算法的搜索效率和收斂速度，使其更加適合于復(fù)雜規(guī)劃空間。通過仿真及其結(jié)果分析表明，該改進(jìn)算法比原始蟻群算法能更快地搜索到更優(yōu)的解。該算法的提出可以為三維空間中的無碰撞路徑規(guī)劃提供一種快速而有效地解決問題的新方法。

[參考文獻(xiàn)]

[1] FANG H C, ONG S K, NEE A Y C. Interactive robot trajectory planning and simulation using Augmented Reality[J]. Robotics and Computer-Integrated Manufacturing, 2012, 28(2):227-237.

[2] 史峰, 王輝, 郁磊, 等. MATLAB智能算法30個案例分析 [M].2版.北京：北京航空航天大學(xué)出版社,2015.

[3] 王肖青, 王奇志. 傳統(tǒng)人工勢場的改進(jìn)[J]. 計算機技術(shù)與發(fā)展, 2006, 16(4):96-98.

[4] 丁家如, 杜昌平, 趙耀,等. 基于改進(jìn)人工勢場法的無人機路徑規(guī)劃算法[J]. 計算機應(yīng)用, 2016, 36(1):287-290.

[5] 徐飛. 基于改進(jìn)人工勢場法的機器人避障及路徑規(guī)劃研究[J]. 計算機科學(xué), 2016, 43(12):293-296.

[6] 畢慧敏, 董海鷹. 改進(jìn)遺傳算法在機器人路徑規(guī)劃中的應(yīng)用[J]. 兵工自動化, 2006, 25(4):53-54.

[7] LI Q, ZHANG W, YIN Y, et al. An Improved Genetic Algorithm of Optimum Path Planning for Mobile Robots[C]// Intelligent Systems Design and Applications, 2006. ISDA ′06. Sixth International Conference on IEEE, 2006:637-642.

[8] 龍傳澤, 楊煜俊. 基于遺傳算法的柔性機器人制造單元調(diào)度問題研究[J]. 組合機床與自動化加工技術(shù), 2015(11):141-144.

[9] 林惠樂, 黃振峰, 毛漢領(lǐng). 基于遺傳神經(jīng)網(wǎng)絡(luò)的機器人焊接工藝參數(shù)優(yōu)化[J]. 組合機床與自動化加工技術(shù), 2015(10):124-127.

[10] SONG H, WANG D. Path Planning for Mobile Robot Based on Modified Ant Colony Optimization[J]. Machine Tool & Hydraulics, 2012.

[11] 李擎, 張超, 陳鵬,等. 一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J]. 控制與決策, 2013,28(6):873-878.

[12] 曹宗華, 吳斌, 黃玉清,等. 基于改進(jìn)蟻群算法的多機器人任務(wù)分配[J]. 組合機床與自動化加工技術(shù), 2013(2):34-37.