貝塞爾曲線(xiàn)融合ACO的移動(dòng)機(jī)器人路徑規(guī)劃

徐 梁，高宏力，宋興國(guó)

（西南交通大學(xué)機(jī)械工程學(xué)院，四川 成都 610031）

1 引言

移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人研究領(lǐng)域的重要組成部分，是指在給定的有障礙物的運(yùn)動(dòng)空間中，根據(jù)一定的性能指標(biāo)（路徑最短、時(shí)間最少），尋找一條從初始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的無(wú)碰撞路徑。移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題是一種典型的NP-hard（非典型性多項(xiàng)式困難）問(wèn)題[1]，針對(duì)移動(dòng)機(jī)器人路徑規(guī)劃，傳統(tǒng)方法主要有柵格法[2]、模擬退火法、模糊邏輯法等，柵格法適用于結(jié)構(gòu)簡(jiǎn)單的環(huán)境中，當(dāng)空間結(jié)構(gòu)變復(fù)雜時(shí)，存在計(jì)算效率低，存儲(chǔ)空間大的問(wèn)題；模擬退火法計(jì)算量大、效率低等問(wèn)題。隨著環(huán)境復(fù)雜程度的增加，出現(xiàn)了免疫算法、遺傳算法[3]、人工魚(yú)群算法、A*算法、ACO等智能仿生算法，這類(lèi)算法在移動(dòng)機(jī)器人路徑規(guī)劃中取得了顯著的成果。

ACO最初是由M.Dorigo等人根據(jù)蟻群覓食行為中受到啟發(fā)提出的，用于解決旅行商問(wèn)題的一種仿生智能優(yōu)化算法，最近這些年在機(jī)器人路徑規(guī)劃方面取得了很好的效果。它具有較好的魯棒性、良好的分布式計(jì)算體制、易于與其他方法相互結(jié)合等優(yōu)點(diǎn)[4-5]。但是ACO規(guī)劃出來(lái)的路徑收斂速度慢、易陷入局部最優(yōu)等、折線(xiàn)多、轉(zhuǎn)角偏大，連接不夠平滑，為了提高算法的最優(yōu)性，必須對(duì)基本蟻群算法進(jìn)行改進(jìn)，同時(shí)為了機(jī)器人運(yùn)動(dòng)的柔順性，有必要對(duì)路徑進(jìn)行平滑處理。

在此，針對(duì)以上問(wèn)題，給出一種將貝塞爾曲線(xiàn)[6-7]與ACO融合的規(guī)劃算法。仿真實(shí)驗(yàn)結(jié)果表明，經(jīng)過(guò)貝塞爾曲線(xiàn)優(yōu)化后的路徑更適合機(jī)器人實(shí)際的運(yùn)動(dòng)規(guī)劃。

2 環(huán)境地圖的表示

環(huán)境地圖建模的過(guò)程就是實(shí)現(xiàn)現(xiàn)實(shí)空間到抽象空間的一個(gè)映射過(guò)程，環(huán)境中的障礙物映射成不可通過(guò)的區(qū)域。柵格法創(chuàng)建的環(huán)境地圖簡(jiǎn)單有效，數(shù)據(jù)方便處理。假定移動(dòng)機(jī)器人在二維平面RS上運(yùn)動(dòng)，平面上分布著隨機(jī)可數(shù)數(shù)量，形狀不確定的障礙物。柵格模型的建立采用序號(hào)法結(jié)合直角坐標(biāo)法的方式。柵格地圖中柵格信息直接與環(huán)境信息相對(duì)應(yīng)，其中白色柵格為可通過(guò)自由區(qū)域，黑色柵格為障礙區(qū)域。移動(dòng)機(jī)器人在每個(gè)柵格中下一個(gè)可移動(dòng)位置為八個(gè)相鄰柵格。

從實(shí)際環(huán)境地圖到柵格模型地圖轉(zhuǎn)換的過(guò)程中，對(duì)移動(dòng)機(jī)器人和障礙物環(huán)境做出以下約定：

（1）在描述障礙物時(shí)把障礙物外擴(kuò)1個(gè)機(jī)器人的最大直徑。

（2）障礙物占用不滿(mǎn)一個(gè)柵格時(shí)，擴(kuò)充該障礙物，占滿(mǎn)柵格。

劃分后的機(jī)器人工作空間，如圖1所示。

圖1 柵格地圖模型Fig.1 Grid Map Model

設(shè)柵格模型為M行N列，按從左到右，從上到下的順序，左上角第一個(gè)柵格坐標(biāo)為（1,1），序號(hào)為R的柵格坐標(biāo)為（xR，yR），則有：

式中：mod—取余運(yùn)算；int—取整運(yùn)算。

3 改進(jìn)蟻群算法

蟻群算法基本定義如下：

當(dāng)算法完成一次搜索循環(huán)后，對(duì)相應(yīng)路徑上的信息素進(jìn)行更新：

式中：ρ∈（0,1）—信息素?fù)]發(fā)系數(shù)；

（1-ρ）—信息素殘留系數(shù)；

駐τij（t）—節(jié)點(diǎn)i到節(jié)點(diǎn)j的信息素增量；

駐τkij（t）—第k只螞蟻在路徑上留下的信息素。

信息素更新有三種模型，蟻周（Ant-Cycle）模型、蟻量（Ant-Quantity）模型、蟻密（Ant-Density）模型。這里擬采用蟻周（Ant-Cycle）模型：

式中：Q—正整數(shù)；Lk—第k只螞蟻在一次循環(huán)中走的路徑總長(zhǎng)度。

為了避免算法陷入局部最優(yōu)解和提高算法的收斂性，對(duì)算法做出以下改進(jìn)：

3.1 信息素取值范圍

在算法完成一次迭代后，最優(yōu)路徑上的信息素做出如下改變：

通過(guò)將信息素限制在一個(gè)確定的范圍內(nèi)，可減少算法的過(guò)早收斂和保證每個(gè)路徑點(diǎn)上的信息素差異不會(huì)比較大。

3.2 揮發(fā)系數(shù)

在經(jīng)典蟻群算法中，揮發(fā)系數(shù)是一個(gè)恒定不變的值，信息素?fù)]發(fā)系數(shù)跟蟻群算法的全局搜索能力和算法的收斂速度有著緊密的聯(lián)系；因?yàn)棣训拇嬖?，從未被搜索到的路徑上的信息素?huì)逐漸減為0，當(dāng)ρ較大時(shí)，再一次選擇之前搜索到的路徑的可能性較大，算法的全局搜索能力和隨機(jī)搜索性能也會(huì)受到影響；雖然減小ρ可以通過(guò)提高算法的全局搜索能力和隨機(jī)搜索性能，但同時(shí)會(huì)使得算法的收斂速度降低。

通過(guò)以上分析結(jié)果，提出了一種自適應(yīng)改變信息素?fù)]發(fā)系數(shù)的蟻群算法改進(jìn)方略，意在通過(guò)自適應(yīng)調(diào)整信息素?fù)]發(fā)因子ρ來(lái)提高算法的全局性。在蟻群算法初期，算法的全局搜索能力需要提高，ρ需要比較大，隨著算法的執(zhí)行，為了提高算法的收斂速度，ρ的取值需要比較小。

式中：ρmin—ρ的最小值，可以避免ρ過(guò)小從而降低算法的收斂速度，a和b為系數(shù)。

4 路徑平滑處理

在柵格環(huán)境下蟻群算法規(guī)劃出來(lái)的路徑轉(zhuǎn)折次數(shù)多，折線(xiàn)多，路徑不夠平滑，機(jī)器人實(shí)際運(yùn)動(dòng)效率低。所以有必要對(duì)規(guī)劃后的路徑進(jìn)行平滑處理。

貝塞爾曲線(xiàn)是基于伯恩斯坦多項(xiàng)式發(fā)展而來(lái)的，由于控制簡(jiǎn)單卻有極強(qiáng)的圖形描述能力，位置點(diǎn)連接平滑，貝塞爾曲線(xiàn)在工業(yè)上得到了廣泛的應(yīng)用。

一條n次貝塞爾曲線(xiàn)表達(dá)式為：

式中：P（u）—貝塞爾曲線(xiàn)的運(yùn)動(dòng)控制點(diǎn)；u—獨(dú)立變量；P（i）—位置點(diǎn)；P（0）、P（1）—起點(diǎn)和終點(diǎn)。所有位置點(diǎn) P（i）構(gòu)成了一個(gè)特征多邊形；Bi，n（u）—n 次伯恩斯坦多項(xiàng)式，并且滿(mǎn)足：

當(dāng)n=1時(shí)，一階貝塞爾曲線(xiàn)為一條直線(xiàn)，位置點(diǎn)有兩個(gè)；當(dāng)n=2時(shí)，二階貝塞爾曲線(xiàn)為拋物線(xiàn)，位置點(diǎn)有三個(gè)；當(dāng)n≥3時(shí)，曲線(xiàn)為高階貝塞爾曲線(xiàn)，位置點(diǎn)有n+1個(gè)。

對(duì)貝塞爾曲線(xiàn)求導(dǎo)有：

貝塞爾曲線(xiàn)具有以下性質(zhì)：

（1）貝塞爾曲線(xiàn)的起點(diǎn)和終點(diǎn)也是特征多邊形的起點(diǎn)和終點(diǎn)。

（2）貝塞爾曲線(xiàn)的起點(diǎn)和終點(diǎn)的切線(xiàn)與特征多邊形的起始線(xiàn)和結(jié)尾線(xiàn)方向一致。

（3）貝塞爾曲線(xiàn)起始于 P（0）結(jié)束于 P（1）。

（4）貝塞爾曲線(xiàn)特征多邊形一旦確定，曲線(xiàn)的形狀也就唯一確定，不依賴(lài)選取的參考系。

通過(guò)以上兩個(gè)算法的分析，下面將融合貝塞爾曲線(xiàn)和改進(jìn)蟻群算法完成移動(dòng)機(jī)器人的路徑規(guī)劃。

5 基于平滑蟻群算法的路徑規(guī)劃

具體的機(jī)器人平滑路徑規(guī)劃算法基本步驟如下：

（1）柵格法建立環(huán)境地圖，確定初始化蟻群算法參數(shù)以及移動(dòng)機(jī)器人起始點(diǎn)S和目標(biāo)點(diǎn)T。

（2）螞蟻k從點(diǎn)S開(kāi)始運(yùn)動(dòng)，將S放置在禁忌表tabuk中，根據(jù)（2）式得到下個(gè)移動(dòng)位置，添加到相應(yīng)禁忌表中。

（3）判斷目標(biāo)點(diǎn)T是否到達(dá)，如果已到達(dá)，則令k=k+1，然后轉(zhuǎn)到（2），直到這次迭代過(guò)程所有的螞蟻都完成路徑搜索任務(wù)。

（4）根據(jù)禁忌表tabuk中相關(guān)信息，可以計(jì)算蟻群的路徑長(zhǎng)度，進(jìn)而比較得到最短路徑。調(diào)整最短路徑上各個(gè)節(jié)點(diǎn)全局信息素值。

（5）判斷算法是否滿(mǎn)足退出條件，如果滿(mǎn)足條件，輸出最短路徑，否則轉(zhuǎn)至（2）。

（6）對(duì)規(guī)劃的路徑進(jìn)行平滑處理。

對(duì)應(yīng)的流程圖，如圖3所示。

圖2 蟻群算法流程圖Fig.2 Flow Chart of Ant Colony Algorithm

6 仿真實(shí)驗(yàn)及其分析

本課題用Matlab 2014a對(duì)算法進(jìn)行仿真研究，硬件條件為CPU 2.6 GHz、內(nèi)存 8 GB。

在仿真環(huán)境中中各個(gè)參數(shù)設(shè)定如下，實(shí)驗(yàn)環(huán)境地圖柵格模型為15×15，蟻群算法螞蟻數(shù)目為40，最大迭代次數(shù)為50，揮發(fā)因子中系數(shù)a和b與分別為-0.8，25，改進(jìn)蟻群算法中重要參數(shù)α=1，β=7。當(dāng)機(jī)器人起始序號(hào)S為211，終點(diǎn)序號(hào)G為15時(shí)，仿真圖中坐標(biāo)系的x軸方向正向向右，y軸方向向上，黑色方塊為障礙物。基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃的仿真過(guò)程路徑圖，如圖4所示。

圖3 改進(jìn)蟻群算法最終尋優(yōu)路徑Fig.3 Final Path of Improved ACO

算法均采用運(yùn)行50次的平均值，對(duì)基本的蟻群算法和改進(jìn)后的蟻群算法做了仿真實(shí)驗(yàn)比較，兩種算法的尋優(yōu)路徑長(zhǎng)度和迭代次數(shù)，如表2所示。

表1 算法性能比較Tab.1 Algorithm Performance Comparison

由仿真對(duì)比結(jié)果可知，和基本蟻群算法相比，改進(jìn)優(yōu)化后的蟻群算法能避免搜索陷入局部最優(yōu)，收斂速度也更快。通過(guò)貝塞爾曲線(xiàn)平滑過(guò)后的路徑，如圖5所示。

圖4 路徑平滑F(xiàn)ig.4 Path Smoothing

通過(guò)平滑過(guò)后的路徑可知，優(yōu)化過(guò)后的路徑轉(zhuǎn)折次數(shù)大幅減少，更有利于機(jī)器人實(shí)際的運(yùn)動(dòng)，機(jī)器人運(yùn)動(dòng)更加平滑，對(duì)移動(dòng)機(jī)器人自身的沖擊也越小。

在隨機(jī)生成的（20×20）的地圖中運(yùn)行改進(jìn)蟻群算法規(guī)劃出的最優(yōu)路徑，如圖6所示。通過(guò)大量仿真實(shí)驗(yàn)結(jié)果證明了該改進(jìn)算法能夠有效的解決機(jī)器人的路徑規(guī)劃問(wèn)題。

圖5 尋優(yōu)路徑Fig.5 Optimization Path

6 結(jié)論

針對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題上，提出了一種基于改進(jìn)蟻群算法的方法，主要結(jié)論如下。（1）通過(guò)限制信息素的取值范圍，擴(kuò)大了搜索結(jié)果，從而避免了路徑陷入局部最優(yōu)。（2）同時(shí)還提出了一種自適應(yīng)調(diào)節(jié)信息素?fù)]發(fā)因子的蟻群算法改進(jìn)方針，通過(guò)自適應(yīng)的信息素?fù)]發(fā)因子來(lái)提高算法的全局性和算法的收斂速度，設(shè)置禁忌柵格，防止搜索時(shí)路徑死鎖。（3）針對(duì)蟻群算法在柵格環(huán)境中規(guī)劃出來(lái)的路徑為折線(xiàn)圖，提出了用貝塞爾曲線(xiàn)優(yōu)化路徑的方法，優(yōu)化后的路徑更有利于實(shí)際機(jī)器人運(yùn)動(dòng)情況。最后利用本研究提出的算法完成了路徑規(guī)劃任務(wù)，仿真實(shí)驗(yàn)驗(yàn)證了該方法具有可行性和有效性。