張亞林，李曉松

(1.廣州應(yīng)用科技學(xué)院 計(jì)算機(jī)學(xué)院，廣東 廣州 511370；2.廣州大學(xué) 計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院，廣東 廣州 511370)

0 引 言

路徑規(guī)劃是機(jī)器人導(dǎo)航[1]的關(guān)鍵部分，其本質(zhì)是根據(jù)預(yù)設(shè)條件，在起點(diǎn)到終點(diǎn)間搜索一條安全避讓障礙物的最短路徑[2]。目前，機(jī)器人路徑規(guī)劃方法可分為兩種，一種是如人工勢(shì)場(chǎng)[3，4]、A*[5]、Voronoi圖[6]、可視圖等傳統(tǒng)方法。另一種是智能優(yōu)化算法。智能優(yōu)化算法擁有傳統(tǒng)方法無(wú)可比擬的啟發(fā)搜索機(jī)制，能夠模擬自然界種群的覓食和進(jìn)化行為。隨著路徑規(guī)劃場(chǎng)景規(guī)模、類型和障礙物復(fù)雜度增加，傳統(tǒng)方法已出現(xiàn)性能不足，智能算法在路徑規(guī)劃上逐漸體現(xiàn)優(yōu)勢(shì)。目前，蟻群算法[7]、遺傳算法[8]、粒子群算法[9]、蜂群算法[10]、蛙跳算法[11]等都已在路徑規(guī)劃有所應(yīng)用。但應(yīng)用智能算法解決路徑規(guī)劃問題，搜索精度高、收斂快的算法仍是學(xué)者們面臨的新問題。

阿基米德優(yōu)化算法AOA是受阿基米德原理啟發(fā)提出的一種元啟發(fā)隨機(jī)優(yōu)化算法[12]。由于算法較新，目前搜索到的文獻(xiàn)已應(yīng)用在參數(shù)尋優(yōu)[13]、風(fēng)電系統(tǒng)功率優(yōu)化[14]和機(jī)械設(shè)計(jì)[15]等領(lǐng)域。然而，AOA與同類智能算法一樣，在求解復(fù)雜多維問題時(shí)依然易出現(xiàn)搜索精度差、局部最優(yōu)及尋優(yōu)性能不穩(wěn)定的不足。研究人員也在該算法基礎(chǔ)上做了改進(jìn)工作[15]。然而，分析現(xiàn)有工作不難發(fā)現(xiàn)，AOA仍有不足：首先，種群初始化隨機(jī)，導(dǎo)致種群多樣性較差，迭代早期個(gè)體搜索盲目；其次，局部開發(fā)階段僅以最優(yōu)個(gè)體引領(lǐng)，全局搜索階段則以隨機(jī)個(gè)體指引，牽引方式盲目，容易導(dǎo)致算法陷入局部最優(yōu)；最后，平衡全局搜索與局部開發(fā)的密度降低因子沒有自調(diào)節(jié)功能，在不同迭代時(shí)期無(wú)法賦予個(gè)體差異化尋優(yōu)能力，易丟失適應(yīng)度較優(yōu)的個(gè)體。

為此，本文將設(shè)計(jì)一種改進(jìn)阿基米德優(yōu)化算法SIAOA，利用改進(jìn)阿基米德算法對(duì)路徑規(guī)劃進(jìn)行迭代求解，引入貝塞爾曲線平滑策略對(duì)生成路徑作平滑處理。在不同規(guī)模和復(fù)雜性的柵格地圖中對(duì)算法的有效性進(jìn)行驗(yàn)證。

1 阿基米德優(yōu)化算法AOA

AOA算法中，轉(zhuǎn)移因子TF用于控制個(gè)體碰撞與平衡態(tài)切換，即控制全局搜索和局部開發(fā)，定義為

(1)

式中：Tmax為最大迭代次數(shù)。

算法首先初始化個(gè)體密度den、體積vol及加速度acc。計(jì)算最優(yōu)個(gè)體xbest、最優(yōu)密度denbest、最優(yōu)體積volbest和最優(yōu)加速度accbest，并對(duì)密度、體積和加速度更新，具體為

(2)

式中：rand為(0，1)間隨機(jī)值，deni(t) 和deni(t+1) 指迭代t、t+1時(shí)個(gè)體i的密度，voli(t) 和voli(t+1) 指迭代t、t+1時(shí)個(gè)體i的體積，i=1，2，…，N，N為種群規(guī)模。

若TF≤0.5，AOA進(jìn)入全局搜索。個(gè)體加速度為

(3)

式中：denmr、volmr和accmr分別指隨機(jī)選擇碰撞個(gè)體mr的密度、體積和加速度。

若TF>0.5，AOA進(jìn)入局部開發(fā)。個(gè)體加速度更新為

(4)

將加速度進(jìn)行標(biāo)準(zhǔn)化處理為

(5)

式中：accmin、accmax為當(dāng)前種群中個(gè)體的最小加速度和最大加速度，u、l為常量。

全局搜索階段碰撞個(gè)體位置更新為

xi(t+1)=xi(t)+
c1·rand·acci-norm(t+1)·d·(xrand(t)-xi(t))

(6)

式中：c1為常量，xi(t+1)、xi(t) 指迭代t+1、t時(shí)個(gè)體i的位置，xrand(t) 為迭代t時(shí)隨機(jī)選擇個(gè)體位置，d為密度降低因子，更新為

(7)

局部開發(fā)階段個(gè)體位置更新為

xi(t+1)=xbest(t)+
F·c2·rand·acci-norm(t+1)·d·(T·xbest(t)-xi(t))

(8)

式中：xbest(t) 為迭代t時(shí)最優(yōu)個(gè)體，c2為常量，T=c3×TF，c3為常量。F為控制個(gè)體運(yùn)動(dòng)方向的標(biāo)識(shí)因子，定義為

(9)

式中：p=2×rand-c4，c4為常量。

2 分段慣性權(quán)重自適應(yīng)改進(jìn)AOA：SIAOA

2.1 混沌Circle種群初始化

AOA隨機(jī)生成初始種群，這會(huì)導(dǎo)致個(gè)體分布缺乏均勻性，算法易得到局部最優(yōu)。為此，改進(jìn)算法采用Circle混沌映射改進(jìn)初始種群生成方式?；煦缦到y(tǒng)具有隨機(jī)性和遍歷性，對(duì)種群的均勻分布更有利。目前，常用混沌映射有Logistic、Tent和Circle。圖1展示了3種混沌系統(tǒng)的序列值分布，一根柱狀圖的取值為0.05，即分別在[0，0.05]、[0.05，0.1]…進(jìn)行取值頻次統(tǒng)計(jì)?？梢钥闯?，Logistic在兩個(gè)邊界區(qū)域的取值概率明顯更高，呈切比雪夫型分布，這種不均勻分布對(duì)AOA的尋優(yōu)精度有不利影響。Tent的分布更加均勻，但容易陷入不動(dòng)點(diǎn)，且周期不穩(wěn)定，也存在均勻度較差的問題。Circle映射擁有與Tent一致的分布均勻性，且更加穩(wěn)定。

圖1 不同混沌映射混沌值取值頻次分布

改進(jìn)算法利用混沌Circle映射實(shí)現(xiàn)種群初始化，公式

yk+1=mod(yk+0.2-(0.5/2π)sin(2π×yk)，1)

(10)

式中：yk、yk+1為k、k+1次迭代的Circle混沌值。

生成Circle混沌值后，將混沌值與個(gè)體位置進(jìn)行逆映射，映射規(guī)則為xi，j=lbj+yi，j×(ubj-lbj)，xi，j為個(gè)體i在維度j的位置，yi，j為混沌值，[lbj，ubj] 為搜索邊界，j=1，2，…，d，d為位置維度。

在二維空間內(nèi)布置30個(gè)種群個(gè)體為例展示不同方法生成的個(gè)體分布情況。圖2是兩種方法生成的種群個(gè)體分布。隨機(jī)初始化容易發(fā)生位置重疊，Circle混沌初始化的均勻性更好，能夠更好地對(duì)解空間進(jìn)行遍歷。

圖2 兩種種群初始化分布

2.2 自適應(yīng)密度降低因子更新

根據(jù)式(7)，隨著算法迭代，密度降低因子d會(huì)從1呈線性遞減至0。結(jié)合AOA的全局搜索和局部開發(fā)式(6)、式(8)，d過小，會(huì)導(dǎo)致種群個(gè)體原有優(yōu)質(zhì)信息丟失，降低種群個(gè)體多樣性；d過大，又會(huì)影響個(gè)體向全局最優(yōu)的漸進(jìn)關(guān)系，降低收斂精度。為此，改進(jìn)算法設(shè)計(jì)自適應(yīng)密度降低因子更新，引入個(gè)體進(jìn)化成功率對(duì)因子d更新，使個(gè)體能夠依據(jù)進(jìn)化進(jìn)程對(duì)自身位置自適應(yīng)調(diào)整。

令Si(t+1) 為個(gè)體i在t+1次迭代的成功率，則

(11)

式中：pbi(t+1)、pbi(t) 指?jìng)€(gè)體i在t+1、t次迭代的歷史最優(yōu)解，f(pbi(t+1))、f(pbi(t)) 指?jìng)€(gè)體歷史最優(yōu)解適應(yīng)度。將種群進(jìn)化成功率SP定義為個(gè)體進(jìn)化成功數(shù)與種群規(guī)模之比，即

(12)

算法迭代早期，個(gè)體分布廣泛，成功進(jìn)化較多，表明全局最優(yōu)對(duì)種群進(jìn)化引領(lǐng)有效。迭代后期，種群逐漸聚集，進(jìn)化成功率隨之變低，此時(shí)應(yīng)保證更多優(yōu)質(zhì)個(gè)體信息促進(jìn)局部開采精度。結(jié)合種群進(jìn)化成功率SP，對(duì)個(gè)體進(jìn)化狀態(tài)自適應(yīng)更新，均衡算法全局尋優(yōu)，定義密度降低因子為

(13)

式中：γ、λ分別指種群進(jìn)化成功率系數(shù)和適應(yīng)度歸一化系數(shù)，0<γ、λ<1，且γ+λ=1，F(xiàn)i(t) 為適應(yīng)度歸一化值，定義為

(14)

式中：κ為衰減因子，ζ控制分母不為0，fi(t) 為迭代t時(shí)個(gè)體i的適應(yīng)度，fmin(t)、fmax(t) 為種群當(dāng)前最優(yōu)適應(yīng)度和最差適應(yīng)度。根據(jù)式(13)，d將根據(jù)個(gè)體適應(yīng)度動(dòng)態(tài)自適應(yīng)調(diào)整，若適應(yīng)度較優(yōu)，處于最優(yōu)解鄰域，接近全局最優(yōu)，d將維持原有性質(zhì)，提高收斂性；若適應(yīng)度較差，離全局最優(yōu)仍較遠(yuǎn)，d將接近最大值，激勵(lì)個(gè)體保持多樣性，實(shí)現(xiàn)廣泛搜索。

2.3 分段慣性權(quán)重位置更新

根據(jù)局部開發(fā)式(8)可知，種群更新將由最優(yōu)個(gè)體引導(dǎo)，若最優(yōu)個(gè)體為局部最優(yōu)解，種群將出現(xiàn)早熟收斂。為此，改進(jìn)算法引入分段慣性權(quán)重機(jī)制，在迭代前/中期，利用雙曲正切函數(shù)對(duì)權(quán)重值w(t) 更新，使算法中前期慣性權(quán)重呈非線性遞減；在算法迭代后期，利用正弦函數(shù)上下波動(dòng)對(duì)權(quán)重值w(t) 更新，利用跳躍式位置變異降低算法陷入局部最優(yōu)的概率。分段慣性權(quán)重計(jì)算公式為

(15)

式中：wstart、wend為慣性權(quán)重初值和終值，α、β2為調(diào)節(jié)因子，用于控制正切函數(shù)和正弦函數(shù)的曲線平滑性，β1、β3為常量。圖3為400次迭代w(t) 的變化曲線，相關(guān)參數(shù)均是多次實(shí)驗(yàn)的最優(yōu)檢驗(yàn)值?？梢?，迭代前期，w(t) 較大，這可保證算法在更廣泛空間內(nèi)進(jìn)行全局搜索，增加找到全局最優(yōu)解的概率；迭代中期，w(t) 逐漸減小，利于算法在最優(yōu)解鄰域進(jìn)行精細(xì)開發(fā)，提高搜索精度；而迭代后期，正弦函數(shù)不規(guī)則波動(dòng)使w(t) 變化出現(xiàn)不確定性，這可以增強(qiáng)局部區(qū)域內(nèi)開發(fā)的多元性，使算法具備跳離局部極值的能力。

圖3 分段慣性權(quán)重

結(jié)合分段慣性權(quán)重，改進(jìn)算法全局搜索為

xi(t+1)=w(t)·xi(t)+
c1·rand·acci-norm(t+1)·d·(xrand(t)-xi(t))

(16)

改進(jìn)算法局部開發(fā)為

xi(t+1)=w(t)·xbest(t)+
F·c2·rand·acci-norm(t+1)·d·(T·xbest(t)-xi(t))

(17)

2.4 SIAOA設(shè)計(jì)

步驟1 設(shè)置種群規(guī)模N、空間維度dim、個(gè)體密度den、體積vol、加速度acc、最大迭代次數(shù)Tmax、常量u、l、c1、c2、c3、c4、慣性權(quán)重初值wstart和終值wend、α、β1、β2、β3、θ；

步驟2 利用混沌Circle映射初始化種群，初始迭代t=0；

步驟3 計(jì)算個(gè)體適應(yīng)度，確定最優(yōu)的xbest、denbest、volbest和accbest；

步驟4 利用式(1)更新TF，利用式(2)更新den和vol，利用式(13)更新d，利用式(15)更新w(t)；

步驟5 若TF≤0.5，進(jìn)入全局搜索。利用式(3)更新個(gè)體加速度，根據(jù)式(5)對(duì)加速度acc作標(biāo)準(zhǔn)化處理，根據(jù)式(16)更新個(gè)體位置；

步驟6 若TF<0.5，進(jìn)入局部開發(fā)。根據(jù)式(17)更新個(gè)體位置；

步驟7 更新迭代次數(shù)t=t+1；

步驟8 判斷算法是否迭代Tmax次，若是，輸出全局最優(yōu)個(gè)體；否則，返回步驟3執(zhí)行。

3 結(jié)合SIAOA與貝塞爾曲線平滑的路徑規(guī)劃

3.1 路徑規(guī)劃建模

利用柵格地圖建立機(jī)器人路徑規(guī)劃模型。柵格地圖由二進(jìn)制0和1取值的柵格矩陣構(gòu)成。若柵格單元取值0，表示白色柵格，機(jī)器人可通過；若取值1，表示黑色柵格(障礙物)，機(jī)器人無(wú)法通過，需繞行。柵格地圖從下向上、從左向右依次編號(hào)1、2、…。如10×10柵格地圖，共有100個(gè)柵格單元，柵格序號(hào)與坐標(biāo)對(duì)應(yīng)，對(duì)應(yīng)關(guān)系可表示為式(18)，且坐標(biāo)值為柵格中心點(diǎn)坐標(biāo)

(18)

式中：(xi，yi) 為柵格i中心坐標(biāo)，Nx、Ny為地圖行列數(shù)，a為柵格單元邊長(zhǎng)，且柵格單元為相同正方形，mod為模運(yùn)算符，ceil()為向上取整。

柵格地圖實(shí)際應(yīng)用時(shí)，若柵格單元內(nèi)障礙物面積小于柵格單元，為避免機(jī)器人與障礙物碰撞，需對(duì)障礙物膨化處理，填充整個(gè)柵格。令機(jī)器人處于某柵格，如圖4(a)所示，周圍不存在任一障礙物柵格，可行進(jìn)路徑共8條，即圖4(a)的1～8，剔除前一步原路返回路徑，實(shí)際路徑共7條。若令柵格邊長(zhǎng)為1，在保證機(jī)器人不與障礙物碰撞前提下，機(jī)器人移動(dòng)一次的距離范圍為[1，21/2]。圖4(b)是有效避障可行進(jìn)路徑。圖4(c)和圖4(d)均為無(wú)效路徑，圖4(c)直接與障礙物發(fā)生碰撞，圖4(d)則是非行進(jìn)路徑。

圖4 路徑說明

3.2 路徑規(guī)劃評(píng)估

最優(yōu)路徑由適應(yīng)度函數(shù)評(píng)估，適應(yīng)度函數(shù)綜合考慮兩個(gè)指標(biāo)：一是路徑最短，二是確保路徑盡可能平滑，路徑拐點(diǎn)盡量少。

(1)最短路徑f1。令兩個(gè)臨近柵格單元的坐標(biāo)為Pi(xi，yi)、Pi+1(xi+1，yi+1)， 機(jī)器人從Pi移動(dòng)至Pi+1的距離為

(19)

則機(jī)器人路徑規(guī)劃總長(zhǎng)度為

(20)

其中，dim為經(jīng)過柵格總數(shù)。則最短路徑函數(shù)f1為

minf1=1/L

(21)

(2)路徑平滑度f(wàn)2。機(jī)器人行進(jìn)僅向臨近柵格單元移動(dòng)。如圖5所示，若機(jī)器人從柵格A移動(dòng)至O，接下來(lái)有OB、OC、OD、OE、OF、OG、OH共7個(gè)方向。由于對(duì)稱性，行進(jìn)路徑與原路徑AO之間夾角θ可能為45°、90°、135°和180°，分別對(duì)應(yīng)OB、OC、OD和OE。夾角θ越大(180°)，表明路徑越平滑，拐點(diǎn)越少。根據(jù)原路徑與下一條路徑夾角θ的不同，設(shè)置不同懲罰值β，具體為

圖5 路徑平滑度

(22)

則路徑平滑度函數(shù)f2為

(23)

結(jié)合路徑最短和路徑平滑度因素，適應(yīng)度函數(shù)定義為

fit=a×f1+b×f2

(24)

其中，a、b指路徑長(zhǎng)度和平滑度權(quán)重，a+b=1，0

路徑尋優(yōu)過程中，個(gè)體在搜索空間內(nèi)的位置代表一條候選路徑。算法通過啟發(fā)式搜索策略，從若干候選路徑集中搜索一條適應(yīng)度最優(yōu)的路徑，還需滿足兩項(xiàng)約束：①機(jī)器人移動(dòng)限定在固定大小柵格矩陣中，且移動(dòng)路徑和路徑間節(jié)點(diǎn)不能碰撞或穿越障礙物柵格；②移動(dòng)路徑不能迂回，即若機(jī)器人從柵格單元Pi(xi，yi) 移動(dòng)至Pi+1(xi+1，yi+1)， 則xi>xi+1和yi>yi+1或xi

3.3 個(gè)體編碼

利用SIAOA搜索機(jī)器人最優(yōu)路徑，即通過適應(yīng)度函數(shù)尋優(yōu)并以迭代方式更新個(gè)體代表的路徑規(guī)劃候選解。若個(gè)體編碼維度為dim，則代表路徑規(guī)劃中經(jīng)過dim個(gè)柵格，每個(gè)維度上元素為柵格序號(hào)(xj)，代表柵格j的位置，則個(gè)體i可表示為Xi={xi，S，…xi，j，…，xi，T}， 代表一條路徑規(guī)劃候選解，xi，S和xi，T代表機(jī)器人起點(diǎn)和終點(diǎn)。dim對(duì)應(yīng)路徑規(guī)劃優(yōu)化維度，個(gè)體位置的每一個(gè)維度元素對(duì)應(yīng)下一個(gè)移動(dòng)?xùn)鸥裎恢谩?/p>

3.4 貝塞爾曲線路徑平滑

結(jié)合柵格地圖的機(jī)器人移動(dòng)是以柵格中心點(diǎn)為導(dǎo)航點(diǎn)移動(dòng)，這種方式路徑轉(zhuǎn)折較多，機(jī)器人耗能較大。為了優(yōu)化路徑，引入貝塞爾曲線平滑對(duì)路徑拐點(diǎn)處理。

n階貝塞爾曲線函數(shù)式為

(25)

式中：u為獨(dú)立變量，P(u) 為貝塞爾曲線運(yùn)動(dòng)控制點(diǎn)，P(i) 為位置點(diǎn)，P(0)、P(1) 為曲線起點(diǎn)和終點(diǎn)。位置點(diǎn)P(i) 可構(gòu)成特征多邊形，Bi，n(u) 為n次伯恩斯坦多項(xiàng)式，滿足

(26)

若n=1，貝塞爾曲線為一階曲線，即直線，位置點(diǎn)僅有P(0) 和P(1) 兩個(gè)點(diǎn)；若n=2，貝塞爾曲線為二階曲線，即拋物線，位置點(diǎn)有P(0)、P(1)和P(2)； 若n≥3，曲線為高階貝塞爾曲線，位置點(diǎn)有n+1個(gè)。貝塞爾曲線導(dǎo)數(shù)形式為

(27)

圖6是貝塞爾曲線平滑路徑示意圖。

圖6 貝塞爾曲線平滑

3.5 路徑規(guī)劃算法

利用SIAOA求解機(jī)器人路徑規(guī)劃問題，即以適應(yīng)度函數(shù)(24)最小為目標(biāo)，迭代搜索行進(jìn)柵格單元。每個(gè)搜索空間內(nèi)的個(gè)體視為一條候選路徑規(guī)劃方案，個(gè)體位置維度對(duì)應(yīng)經(jīng)過柵格單元數(shù)，個(gè)體各維度的元素即為柵格單元坐標(biāo)值，整個(gè)種群代表路徑規(guī)劃候選解集。SIAOA將圍繞候選解集迭代尋優(yōu)，以目標(biāo)函數(shù)(24)最小作為評(píng)估個(gè)體位置質(zhì)量的適應(yīng)度函數(shù)，通過SIAOA對(duì)個(gè)體位置迭代更新，得到最終路徑規(guī)劃最優(yōu)解。算法具體步驟如下：

SIAOA求解機(jī)器人路徑規(guī)劃：

(1)設(shè)置SIAOA參數(shù)：種群規(guī)模N、搜索維度dim、最大迭代數(shù)Tmax和搜索范圍[lb，ub]；

(2)建立柵格地圖，設(shè)置機(jī)器人起點(diǎn)S和終點(diǎn)T，利用混沌映射規(guī)則生成N條初始可行路徑X1，X2，…，XN；

(3)對(duì)種群個(gè)體編碼，表示為一條路徑Xi={xi，1，xi，2，…，xi，dim}，i∈[1，N]，xi，j對(duì)應(yīng)一個(gè)柵格位置，dim為路徑節(jié)點(diǎn)數(shù)；

(4)按式(24)計(jì)算種群個(gè)體適應(yīng)度，并對(duì)個(gè)體降序排列；

(5)確定當(dāng)前種群最優(yōu)解，并標(biāo)記為下一輪的搜索目標(biāo)Xbest；

(6)whilet≤Tmaxthen

(7)執(zhí)行SIAOA的迭代搜索過程；

(8)End while

(9)返回最優(yōu)個(gè)體，解碼為路徑規(guī)劃解，并以貝塞爾曲線進(jìn)行路徑平滑處理。

以上算法步驟中，種群規(guī)模不能設(shè)置過大，一般設(shè)置30個(gè)種群個(gè)體即可，否則算法迭代時(shí)間會(huì)過長(zhǎng)。搜索維度則對(duì)應(yīng)于機(jī)器人行進(jìn)路徑中柵格中心的坐標(biāo)。對(duì)于路徑搜索問題，算法最大迭代次數(shù)可在實(shí)驗(yàn)運(yùn)行中動(dòng)態(tài)設(shè)置，一般小規(guī)模地圖中的路徑規(guī)劃，200次內(nèi)迭代可以找到最優(yōu)解。個(gè)體搜索范圍即對(duì)應(yīng)路徑坐標(biāo)的取值范圍。算法第(9)步中，最優(yōu)個(gè)體即代表機(jī)器人的最優(yōu)路徑，由機(jī)器人所經(jīng)過的柵格中心點(diǎn)坐標(biāo)構(gòu)成，連接中心點(diǎn)坐標(biāo)即可生成路徑規(guī)劃解。而貝塞爾曲線是對(duì)生成路徑中的轉(zhuǎn)彎點(diǎn)進(jìn)行平滑性處理，以減小機(jī)器人實(shí)際行進(jìn)路徑長(zhǎng)度。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)配置

在Matlab R2019a平臺(tái)構(gòu)建仿真實(shí)驗(yàn)，先以數(shù)組定義柵格地圖，并以元素為1的柵格定義障礙物柵格。然后，對(duì)SIAOA算法進(jìn)行初始化操作，迭代執(zhí)行SIAOA算法生成柵格地圖中路徑搜索最優(yōu)解。設(shè)置種群規(guī)模N=30，迭代次數(shù)Tmax=200，u=0.9，l=0.1，c1=2，c2=6，c3=1，c4=2，權(quán)重初值wstart=0.8，終值wend=0.4，α=0.75，β1=0.23，β2=0.18，β3=1.6，θ=0.5，適應(yīng)度函數(shù)權(quán)重因子a=b=0.5。引入標(biāo)準(zhǔn)AOA算法[12]、蟻群算法ACO[7]和協(xié)同改進(jìn)阿基米德優(yōu)化算法CIAOA[15]進(jìn)行對(duì)比分析。

構(gòu)造10×10和30×30柵格地圖進(jìn)行實(shí)驗(yàn)，10×10柵格地圖可模擬障礙物稀疏分布的小型室內(nèi)場(chǎng)景，30×30柵格地圖可模擬障礙物隨機(jī)且密集分布的大型室內(nèi)場(chǎng)景，柵格單元大小為1。為了避免偶然性，在相同參數(shù)配置下獨(dú)立運(yùn)行算法10次。將機(jī)器人起/終點(diǎn)設(shè)置在柵格地圖左上角和右下角柵格，即10×10中起/終點(diǎn)為柵格91和10，坐標(biāo)分別為(0.5，9.5)和(9.5，0.5)，30×30中起/終點(diǎn)為柵格871和30，坐標(biāo)分別為(0.5，29.5)和(29.5，0.5)。

4.2 實(shí)驗(yàn)分析

(1)10×10柵格地圖。圖7是10×10柵格地圖的路徑規(guī)劃結(jié)果。該地圖有22個(gè)障礙物，結(jié)構(gòu)相對(duì)簡(jiǎn)單，算法均能找到有效路徑。結(jié)合表1統(tǒng)計(jì)結(jié)果，SIAOA路徑規(guī)劃結(jié)果最優(yōu)。由于柵格規(guī)模較小，ACO、CIAOA雖然規(guī)劃路徑不一樣，但最優(yōu)路徑長(zhǎng)度相同，SIAOA在這兩種算法基礎(chǔ)上路徑長(zhǎng)度減小了4.0%。路徑拐點(diǎn)上，SIAOA拐點(diǎn)最少，僅有3個(gè)，且路徑長(zhǎng)度也最短。ACO和CIAOA在最優(yōu)解上均有5個(gè)拐點(diǎn)，而AOA雖然拐點(diǎn)數(shù)更少為4個(gè)，但其路徑最長(zhǎng)，不是最優(yōu)解。在路徑長(zhǎng)度和拐點(diǎn)數(shù)上標(biāo)準(zhǔn)差更小表明改進(jìn)算法的搜索穩(wěn)定性更好，其波動(dòng)幅度更小。此外，在迭代次數(shù)均值上，4種算法基本可在約30次迭代內(nèi)找到最優(yōu)解，而SIAOA可以在約22次迭代后即收斂在最優(yōu)解上，是算法中最少的。在尋優(yōu)運(yùn)行時(shí)間上，4種算法差別不是很明顯，主要是柵格規(guī)模較小，路徑搜索相對(duì)容易。圖8是算法迭代曲線圖。從最后的收斂精度看，SIAOA是所有算法中最優(yōu)的。

表1 10×10柵格地圖

圖7 10×10柵格地圖

圖8 10×10柵格地圖迭代曲線

(2)30×30柵格地圖。如圖9是30×30柵格地圖中算法的路徑規(guī)劃結(jié)果，表2是相關(guān)統(tǒng)計(jì)結(jié)果。在路徑長(zhǎng)度最優(yōu)值上，SIAOA為27.46，分別比CIAOA、ACO和AOA降低了15.79%、19.23%和27.38%。在路徑長(zhǎng)度均值上，分別降低了17.08%、25.85%和34.18%。此外，在該地圖中，SIAOA的拐點(diǎn)數(shù)量?jī)?yōu)勢(shì)更為明顯，平均要比對(duì)比算法少約一半路徑拐點(diǎn)。傳統(tǒng)算法搜索方式盲目性較大，個(gè)體搜索性能沒有得到有效優(yōu)化，導(dǎo)致路徑搜索時(shí)遠(yuǎn)離目標(biāo)方向行進(jìn)，甚至出現(xiàn)路徑回環(huán)交叉，規(guī)劃路徑肯定不是最優(yōu)。SIAOA在綜合考慮初始種群質(zhì)量、全局搜索與局部開發(fā)均衡和分段權(quán)重賦予的跳離局部最優(yōu)能力能夠有效提升算法搜索精度，得到拐點(diǎn)更少、與目標(biāo)位置方向更一致的柵格。從路徑長(zhǎng)度、拐點(diǎn)數(shù)量及迭代效率看，隨著柵格地圖規(guī)模增加，SIAOA的性能優(yōu)勢(shì)顯現(xiàn)更加明顯，說明在模型復(fù)雜性增加的環(huán)境下，算法保持著強(qiáng)健的搜索穩(wěn)定性。圖10也顯示SIAOA收斂更快。

圖9 30×30柵格地圖路徑規(guī)劃結(jié)果

圖10 30×30柵格地圖迭代曲線

(3)貝塞爾曲線路徑平滑。對(duì)SIAOA的最優(yōu)路徑做貝塞爾曲線平滑處理，結(jié)果如圖11所示。經(jīng)過平滑處理后，SIAOA路徑長(zhǎng)度分別減小3.61%和10.34%，說明引入貝塞爾曲線平滑能有效對(duì)路徑進(jìn)行二次優(yōu)化，平滑路徑長(zhǎng)度優(yōu)于原始折線路徑長(zhǎng)度，且在地圖規(guī)模增加后，曲線平滑對(duì)路徑長(zhǎng)度降低比例逐步提高，這是由于路徑規(guī)劃規(guī)模增加后，原算法路徑拐點(diǎn)會(huì)增加，而對(duì)更多拐點(diǎn)平滑處理勢(shì)必降低路徑長(zhǎng)度。相同平滑處理也可擴(kuò)展至對(duì)比算法生成的路徑上。

圖11 兩個(gè)柵格地圖的最優(yōu)路徑平滑前后對(duì)比

5 實(shí)證案例研究

為了驗(yàn)證SIAOA的實(shí)用性，以SpiderPi(樹莓派)六足機(jī)器人展開實(shí)證研究。在實(shí)驗(yàn)室建立一個(gè)3m×3m的正方形區(qū)域地圖。將SpiderPi樹莓派六足機(jī)器人放置于起始位置，在區(qū)域內(nèi)設(shè)置若干障礙物，并設(shè)置機(jī)器人的行進(jìn)終點(diǎn)位置。實(shí)際場(chǎng)地拍攝如圖12所示。將該實(shí)驗(yàn)場(chǎng)景處理為邊長(zhǎng)15 cm，大小為20×20的柵格地圖。設(shè)置機(jī)器人起點(diǎn)坐標(biāo)為(0.5，19.5)，目標(biāo)點(diǎn)坐標(biāo)為(19.5，0.5)，分別處于左上角柵格和右下角柵格。在六足機(jī)器人開發(fā)板中燒制程序?qū)崿F(xiàn)蟻群算法ACO、AOA和SIAOA算法，使機(jī)器人自動(dòng)搜索最優(yōu)移動(dòng)路徑。

圖12 實(shí)驗(yàn)場(chǎng)景

兩種算法的路徑規(guī)劃結(jié)果如圖13所示。可以看出，SIAOA在路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)方面都要優(yōu)于AOA和ACO，驗(yàn)證SIAOA在解決實(shí)際問題的機(jī)器人路徑規(guī)劃中具有實(shí)用性。

圖13 實(shí)證場(chǎng)景規(guī)劃結(jié)果

6 結(jié)束語(yǔ)

為了解決傳統(tǒng)算法求解機(jī)器人路徑規(guī)劃無(wú)法找到最短路徑、收斂慢且拐點(diǎn)多的不足，提出結(jié)合改進(jìn)阿基米德優(yōu)化算法與貝塞爾曲線平滑的機(jī)器人路徑規(guī)劃算法。首先引入混沌Circle映射、自適應(yīng)密度降低因子調(diào)節(jié)及分段慣性權(quán)重對(duì)傳統(tǒng)阿基米德優(yōu)化算法進(jìn)行改進(jìn)；再構(gòu)建移動(dòng)機(jī)器人路徑規(guī)劃模型，結(jié)合路徑長(zhǎng)度和路徑平滑性構(gòu)造適應(yīng)度函數(shù)，并利用改進(jìn)算法和貝塞爾曲線平滑對(duì)路徑規(guī)劃迭代求解。結(jié)果表明，改進(jìn)算法能夠更快地生成更短更平滑的機(jī)器人路徑，算法在搜索路徑性能上是具備優(yōu)勢(shì)的。