張文強(qiáng)，張 彥

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

0 引言

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

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

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

1 原始蟻群算法基本概述

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

1.1 三維搜索空間

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

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

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

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

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

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

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

1.3 信息素系數(shù)

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

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

τP=(1-ζ)τP

(1)

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

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

(2)

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

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

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

(3)

1.5 原始蟻群算法流程

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

圖3 原始蟻群算法流程圖

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

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

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

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

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

(4)

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

(5)

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

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

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

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

(6)

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

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

(7)

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

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

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

(8)

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

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

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

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

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

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

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

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

表1 仿真初始條件

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

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

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

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

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

4 結(jié)論

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

針對(duì)原始蟻群算法在復(fù)雜環(huán)境中收斂速度慢以及可能陷入局部最優(yōu)陷阱而導(dǎo)致收斂失敗的問題，改進(jìn)后的算法在啟發(fā)函數(shù)的設(shè)計(jì)中，引入了具有人工勢(shì)場(chǎng)思想的引力系數(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個(gè)案例分析 [M].2版.北京：北京航空航天大學(xué)出版社,2015.

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

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

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

[6] 畢慧敏, 董海鷹. 改進(jìn)遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 兵工自動(dòng)化, 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] 龍傳澤, 楊煜俊. 基于遺傳算法的柔性機(jī)器人制造單元調(diào)度問題研究[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2015(11):141-144.

[9] 林惠樂, 黃振峰, 毛漢領(lǐng). 基于遺傳神經(jīng)網(wǎng)絡(luò)的機(jī)器人焊接工藝參數(shù)優(yōu)化[J]. 組合機(jī)床與自動(dòng)化加工技術(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)蟻群算法的多機(jī)器人任務(wù)分配[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2013(2):34-37.