基于改進(jìn)粒子群算法的移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃

蒲興成，李俊杰，吳慧超，張毅

(1.重慶郵電大學(xué) 數(shù)理學(xué)院，重慶 400065；2.重慶郵電大學(xué) 智能系統(tǒng)及機(jī)器人研究所，重慶 400065；3.重慶郵電大學(xué) 先進(jìn)制造學(xué)院，重慶 400065)

基于改進(jìn)粒子群算法的移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃

蒲興成1，李俊杰2，吳慧超2，張毅3

(1.重慶郵電大學(xué) 數(shù)理學(xué)院，重慶 400065；2.重慶郵電大學(xué) 智能系統(tǒng)及機(jī)器人研究所，重慶 400065；3.重慶郵電大學(xué) 先進(jìn)制造學(xué)院，重慶 400065)

針對移動機(jī)器人遍歷多個(gè)目標(biāo)點(diǎn)的路徑規(guī)劃問題，提出了一種基于改進(jìn)粒子群算法和蟻群算法相結(jié)合的路徑規(guī)劃新方法。該方法將目標(biāo)點(diǎn)的選擇轉(zhuǎn)化為旅行商問題，并利用蟻群算法進(jìn)行優(yōu)化，定義了每兩個(gè)目標(biāo)點(diǎn)之間的路徑規(guī)劃目標(biāo)函數(shù)，利用粒子群算法對其進(jìn)行優(yōu)化。針對粒子群算法存在的早熟現(xiàn)象，將反向?qū)W習(xí)策略引入粒子群算法，并對粒子群算法的慣性權(quán)重和學(xué)習(xí)因子進(jìn)行改進(jìn)。性能測試結(jié)果表明，改進(jìn)的粒子群算法能有效避免粒子早熟現(xiàn)象，提高粒子群算法的尋優(yōu)能力及穩(wěn)定性。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了新方法能有效地實(shí)現(xiàn)機(jī)器人的多目標(biāo)點(diǎn)無碰撞路徑規(guī)劃。真實(shí)環(huán)境下的實(shí)驗(yàn)結(jié)果證明了新方法在機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃的實(shí)際應(yīng)用中也具有有效性。

移動機(jī)器人；多目標(biāo)點(diǎn)路徑規(guī)劃；蟻群算法；改進(jìn)粒子群算法；反向?qū)W習(xí)策略；慣性權(quán)重；學(xué)習(xí)因子

中文引用格式：蒲興成，李俊杰，吳慧超，等.基于改進(jìn)粒子群算法的移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(3): 301-309.

英文引用格式：PU Xingcheng， LI Junjie， WU Huichao, et al. Mobile robot multi-goal path planning using improved particle swarm optimization[J]. CAAI transactions on intelligent systems, 2017, 12(3): 301-309.

路徑規(guī)劃是研究移動機(jī)器人的一個(gè)重要內(nèi)容，按其規(guī)劃范圍，分為全局路徑規(guī)劃和局部路徑規(guī)劃。目前，針對這兩種路徑規(guī)劃方式許多學(xué)者進(jìn)行了深入研究，并提出了相應(yīng)的解決方法。全局路徑規(guī)劃方法有柵格法、可視圖法和神經(jīng)網(wǎng)絡(luò)法等；局部路徑規(guī)劃方法包括人工勢場法、A*算法、人工蜂群算法等[1]。雖然這些算法得到廣泛應(yīng)用，但也存在一些缺點(diǎn)：柵格力度越小，柵格法對障礙物的描述越精確，但環(huán)境信息的存儲會占據(jù)大量的存儲空間，算法的搜索范圍也將成指數(shù)增加[2]；人工勢場法由于斥力的作用，機(jī)器人很難準(zhǔn)確到達(dá)目標(biāo)點(diǎn)。A*算法對開放列表的維護(hù)是最耗時(shí)的，尤其是在地圖過大的情況下。

移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃是指在復(fù)雜的環(huán)境下找到一條從起始點(diǎn)開始經(jīng)過所有目標(biāo)點(diǎn)的無碰撞的最優(yōu)路徑。在實(shí)際應(yīng)用中，移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃多應(yīng)用于電廠巡檢、醫(yī)院查房等。移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃的基本原則包括3個(gè)方面：1)當(dāng)前點(diǎn)或起始點(diǎn)以及目標(biāo)點(diǎn)提前已知；2)任意時(shí)刻機(jī)器人都可以決定移動路線；3)機(jī)器人必須經(jīng)過的所有目標(biāo)點(diǎn)來完成路徑規(guī)劃。根據(jù)移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃的特點(diǎn)，移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃問題可以轉(zhuǎn)化為旅行商(traveling saleman problem, TSP)問題。目前有很多算法用于解決TSP問題[3]，但多目標(biāo)點(diǎn)路徑規(guī)劃與TSP問題相比更復(fù)雜。因此本文提出了一種基于粒子群算法和蟻群算法相結(jié)合的混合算法用于解決移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃問題。

蟻群算法(ant colony optimization, ACO)是一種啟發(fā)式進(jìn)化算法，由螞蟻覓食行為演化而來。在解決TSP問題上，蟻群算法表現(xiàn)出了較強(qiáng)的優(yōu)越性。粒子群算法(particle swarm optimization, PSO)是一種群體智能算法，由鳥群覓食行為演化而來[4]。與一般的群體智能算法相比，PSO具有記憶特性，可以通過自我學(xué)習(xí)和向他人學(xué)習(xí)方式獲得更多的信息。由于參數(shù)少，計(jì)算方便等優(yōu)點(diǎn)，PSO廣泛應(yīng)用在優(yōu)化問題上，并取得了很好的效果。隨著移動機(jī)器人技術(shù)的發(fā)展，國內(nèi)外學(xué)者對粒子群算法在移動機(jī)器人路徑規(guī)劃上做了大量的研究，如多機(jī)器人路徑規(guī)劃[5-6]，自由浮動機(jī)器人軌跡規(guī)劃[7]以及其他應(yīng)用領(lǐng)域[8-9]。PSO在路徑規(guī)劃上應(yīng)用廣泛，ACO善于解決TSP問題，因此采用兩者結(jié)合的方式非常適合移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃問題。

在一個(gè)包含障礙物的空間內(nèi)，利用PSO算法對起始點(diǎn)到目標(biāo)點(diǎn)及每個(gè)目標(biāo)點(diǎn)與目標(biāo)點(diǎn)之間進(jìn)行路徑規(guī)劃。起始點(diǎn)、目標(biāo)點(diǎn)以及障礙物位置已知，但是哪一條路線會被選擇是未知的。為了確定哪一條路徑會被選擇，ACO被用于遍歷起始點(diǎn)和所有目標(biāo)點(diǎn)，以便得到一條經(jīng)過所有點(diǎn)的最短路徑。為了避免PSO出現(xiàn)早熟現(xiàn)象，提高算法的效率，提出了具有快速收斂性的粒子群算法。實(shí)驗(yàn)結(jié)果驗(yàn)證了混合算法的有效性以及改進(jìn)的粒子群算法的優(yōu)越性。

1 問題描述

1.1 多目標(biāo)點(diǎn)路徑規(guī)劃

假設(shè)在移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃中含有n個(gè)目標(biāo)點(diǎn)，則移動機(jī)器人會產(chǎn)生n(n-1)/2條路徑。為了滿足移動機(jī)器人行走路徑最短的要求，機(jī)器人需要從n(n-1)/2條路線中選擇出一條經(jīng)過所有點(diǎn)的最短路徑。圖1描述了在起始點(diǎn)和目標(biāo)點(diǎn)位置已知的情況下，移動機(jī)器人的運(yùn)動軌跡。從圖1(a)中可知移動機(jī)器人的移動路線有很多條，且必須經(jīng)過所有目標(biāo)點(diǎn)才能完成路徑規(guī)劃；圖1(b)表示移動機(jī)器人運(yùn)動的理想路線。

(a)所有路徑

(b)理想路徑圖1 多點(diǎn)之間的路徑軌跡Fig.1 The path trajectory of multi-goal

為了解決上述問題，我們將目標(biāo)點(diǎn)的選擇規(guī)劃為TSP問題的一個(gè)分支。目前，求解TSP問題最有效的方法主要有郭濤算法、模擬退火算法、遺傳算法、蟻群算法等[3]。由于這些算法都有優(yōu)缺點(diǎn)，因此有些學(xué)者嘗試結(jié)合兩種或多種算法解決彼此算法上的缺點(diǎn)[10]。蟻群算法作為一種自組織正反饋算法，與其他算法相比，具有很強(qiáng)的魯棒性。而且從本質(zhì)上講，蟻群算法的并行特性，強(qiáng)化了算法的可靠性。因此在解決多目標(biāo)點(diǎn)選擇的問題上，我們將采用蟻群算法搜索能夠遍歷所有目標(biāo)點(diǎn)的方法。

1.2 粒子的適應(yīng)度函數(shù)

粒子的適應(yīng)度函數(shù)是檢驗(yàn)粒子群算法收斂性的重要函數(shù)。在路徑規(guī)劃中，移動距離最短是機(jī)器人首要考慮的目標(biāo)，其次是安全性。因此，將移動機(jī)器人運(yùn)動距離作為粒子的首要適應(yīng)度函數(shù)。移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃如圖2所示。由圖2可知，移動機(jī)器人從起始位置開始避開障礙物，經(jīng)過一系列目標(biāo)點(diǎn)到達(dá)目標(biāo)點(diǎn)n。

圖2 移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃示意圖Fig.2 The diagram of mobile robot multi-goal path planning

為了便于理解移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃，可將圖2中的多目標(biāo)點(diǎn)路徑規(guī)劃分解為多個(gè)目標(biāo)點(diǎn)中的兩兩目標(biāo)點(diǎn)之間路徑規(guī)劃。機(jī)器人在保證兩點(diǎn)之間路徑規(guī)劃最短的基礎(chǔ)上才能保證多目標(biāo)路徑規(guī)劃最短。分解后如圖3所示，機(jī)器人在當(dāng)前點(diǎn)需要選擇下一個(gè)所經(jīng)過點(diǎn)，然后到達(dá)目標(biāo)點(diǎn)，在此期間要避開障礙物。

圖3 當(dāng)前點(diǎn)到目標(biāo)點(diǎn)避障描述 Fig.3 The obstacle avoidance description of current point to goal

綜上所述，為了保證路徑規(guī)劃的最短性，下一個(gè)移動點(diǎn)的選取是保證移動機(jī)器人運(yùn)動軌跡最短的前提。因此，設(shè)立移動機(jī)器人路徑規(guī)劃目標(biāo)函數(shù)F1，F(xiàn)1決定了移動機(jī)器人行走路徑長度。本文中，F(xiàn)1定義為

式中，g是目標(biāo)點(diǎn)的個(gè)數(shù)，S是粒子個(gè)數(shù)。

移動機(jī)器人在向目標(biāo)點(diǎn)移動過程中，除了要保證其最短性，安全性也是必須要考慮的。為此，將障礙物對目標(biāo)點(diǎn)的斥力場函數(shù)作為安全性的懲罰函數(shù)。斥力場函數(shù)定義如下：

式中：F2是障礙物對機(jī)器人的斥力；kr是斥力場系數(shù)；d(xR,xO)為機(jī)器人到障礙物的距離；d(xR,xG)是機(jī)器人到目標(biāo)點(diǎn)的距離；dm是障礙物的影響范圍。

移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃問題可以抽象為當(dāng)前位置到目標(biāo)點(diǎn)的最短距離的優(yōu)化問題，而障礙物對機(jī)器人的斥力作用是保證最短路徑安全性的前提。因此，針對路徑規(guī)劃的目標(biāo)函數(shù)可以定義為

F=λF1+μF2

式中λ和μ分別是最短路路徑和約束條件的權(quán)重。

2 基本知識

2.1 標(biāo)準(zhǔn)粒子群算法

2.2 反向?qū)W習(xí)策略

Tizhoosh[11]在2005年基于相反數(shù)或?qū)αⅫc(diǎn)的概念提出了反向?qū)W習(xí)策略。在隨后的發(fā)展中，該方法被應(yīng)用于解決一些優(yōu)化問題中[12-13]。反向坐標(biāo)定義如下。

式中x∈[a,b]，且為實(shí)數(shù)。把上述定義應(yīng)用到高維空間可表示成定義2。

將定義2應(yīng)用到優(yōu)化過程中，則反向機(jī)制的優(yōu)化過程如定義3。

3 反向?qū)W習(xí)粒子群算法

基于反向?qū)W習(xí)策略的思想，本文提出一種改進(jìn)的粒子群算法(opposition-based learning improved PSO, OBLIPSO)。本文采用反向?qū)W習(xí)策略時(shí)，將反向?qū)W習(xí)策略應(yīng)用到單個(gè)粒子中，而不是粒子群體中，以便減小粒子迭代過程中的計(jì)算量。性能測試結(jié)果證明，改進(jìn)的粒子群算法能抑制粒子早熟現(xiàn)象，提高收斂效率。下面介紹改進(jìn)算法的主要機(jī)制和流程。

3.1 初始化種群

粒子在問題空間中找到最優(yōu)解的時(shí)間與粒子初始化時(shí)在空間中的分布存在正比關(guān)系，距離最佳位置近的粒子找到最優(yōu)解的時(shí)間比距離最佳位置遠(yuǎn)的粒子要快。但是，粒子在問題空間中是隨機(jī)分布的，每一個(gè)粒子相對于最優(yōu)解的位置都是未知的。

基于以上分析，在改進(jìn)的粒子群算法初始化時(shí)引入反向?qū)W習(xí)策略有助于粒子尋找最優(yōu)解。在初始化時(shí)，首先，計(jì)算粒子的適應(yīng)度值以及其反向粒子適應(yīng)度值，并對兩者進(jìn)行比較，選擇適應(yīng)度值較好的粒子；其次，從種群中選擇S個(gè)適應(yīng)度值最好的粒子作為初始種群。

3.2 迭代進(jìn)化過程

在標(biāo)準(zhǔn)PSO算法中，粒子在問題空間中選擇另一個(gè)粒子作為學(xué)習(xí)對象，根據(jù)式(1)、(2)進(jìn)行移動。但在粒子進(jìn)化的過程中，粒子會發(fā)生早熟現(xiàn)象，導(dǎo)致算法無法得到最優(yōu)解。由式(1)可知，粒子的速度受到慣性權(quán)重和學(xué)習(xí)因子的影響：慣性權(quán)重影響著粒子的全局搜索和局部搜索能力，學(xué)習(xí)因子影響粒子獲取信息的能力。為了找到問題最優(yōu)解，粒子在進(jìn)化的過程中，其全局搜索能力和局部搜索能力也應(yīng)該隨之發(fā)生變化，即從全局搜索漸變?yōu)榫植克阉鳎ＷC粒子可以尋找到問題的最優(yōu)解。同樣，粒子也應(yīng)該逐漸增強(qiáng)社交能力，由“自我”學(xué)習(xí)逐漸向“他人”學(xué)習(xí)過渡，以便獲取更多有用的信息。

根據(jù)以上分析，粒子在尋優(yōu)過程中，慣性權(quán)重應(yīng)該保持動態(tài)變化。ω取值較大時(shí)，粒子的全局搜索能力較強(qiáng)；ω取值較小時(shí)，粒子的局部搜索能力較強(qiáng)。由于粒子在尋優(yōu)的過程中，會逐漸靠近最優(yōu)點(diǎn)，粒子的慣性權(quán)重應(yīng)該隨著尋優(yōu)過程自適應(yīng)變化。因此粒子的慣性權(quán)重更新公式為

式中:ωmax和ωmin分別是粒子慣性權(quán)重的最大值和最小值;disti是第i個(gè)粒子到全局最優(yōu)粒子的歐幾里德距離;max_dist是粒子到全局最優(yōu)粒子的最大距離。disti和max_dist表達(dá)式分別為[15]

學(xué)習(xí)因子c1和c2控制粒子本身記憶與同伴記憶之間的相對影響：c1的值較小時(shí)，表現(xiàn)為自我認(rèn)知能力不足；c2的值較小時(shí)，表現(xiàn)為社交能力不足。為了保證在迭代過程中，粒子的自我認(rèn)知和社交能力能夠因時(shí)而異，因此，粒子的學(xué)習(xí)因子更新公式[16]如下：

式中：c1max和c2max以及c1min和c2min分別是學(xué)習(xí)因子c1和c2的最大值和最小值;t是當(dāng)前的迭代次數(shù)；Tmax是最大迭代次數(shù)。

3.3 算法實(shí)現(xiàn)流程

1)首先初始化種群P(S)，包括粒子的位置xi和速度vi，i=1,2,…,S，S是種群的大小，初始化慣性權(quán)重ω以及學(xué)習(xí)因子c1和c2等參數(shù)。

2)在速度和位置規(guī)定的范圍內(nèi)根據(jù)式(1)、(2)更新第i個(gè)粒子的速度vi和位置xi。

3)計(jì)算第i個(gè)粒子的適應(yīng)度值fi。

4)ai=min(xi)。

5)bi=max(xi)。

9)從最優(yōu)適應(yīng)度值中選出S個(gè)適應(yīng)度值最好的粒子組成初始化種群。

10)接下來同粒子群算法基本流程。

11)算法滿足結(jié)束條件，結(jié)束算法過程。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 OBLIPSO性能測試

為了驗(yàn)證改進(jìn)粒子群算法的性能是否得到改進(jìn)，筆者將反向?qū)W習(xí)的粒子群算法與其他改進(jìn)算法[15，17-18]在4個(gè)適應(yīng)度函數(shù)上進(jìn)行對比。這4個(gè)適應(yīng)度函數(shù)分別為Sphere函數(shù)、Rastrigin函數(shù)、Grewank函數(shù)、Schaffer函數(shù)，測試函數(shù)參數(shù)設(shè)置如表1所示。

表1 測試函數(shù)參數(shù)設(shè)置

在表2中，OBLIPSO算法在四測試函數(shù)上的平均值均小于其他3種算法的值，尤其是在Sphere函數(shù)和Rastrigin函數(shù)中。從表2中數(shù)據(jù)可知，OBLIPSO算法具有更好的收斂性，得到的解更優(yōu)。表3中的數(shù)據(jù)反映出改進(jìn)算法的穩(wěn)定性。OBLIPSO算法與IAPSO算法、IPSO算法和WPSO算法對比，在穩(wěn)定性上表現(xiàn)得更好。

表2 平均最優(yōu)值結(jié)果對比

表3 標(biāo)準(zhǔn)方差結(jié)果對比

由表2和表3數(shù)據(jù)可得：反向?qū)W習(xí)策略提高了種群的多樣性，增加了粒子尋優(yōu)成功概率，節(jié)省了粒子尋優(yōu)時(shí)間；線性變化的慣性權(quán)重保障了粒子從全局搜索到局部搜索的線性轉(zhuǎn)換，抑制了粒子早熟現(xiàn)象；學(xué)習(xí)因子的變化保證了粒子能夠充分完成自我學(xué)習(xí)和社交行為，提高了粒子的收斂速度。

4.2 路徑規(guī)劃仿真實(shí)驗(yàn)

為了驗(yàn)證新方法的實(shí)用性及有效性，筆者將該方法在仿真環(huán)境下進(jìn)行實(shí)驗(yàn)。仿真實(shí)驗(yàn)環(huán)境設(shè)置在18×16的二維矩形空間內(nèi)，并設(shè)置成簡單環(huán)境和復(fù)雜環(huán)境。在環(huán)境中有不規(guī)則的障礙物，起始點(diǎn)位置使用方形表示，目標(biāo)點(diǎn)處用五角形表示。

1) 第1次實(shí)驗(yàn)中，OBLIPSO算法的參數(shù)設(shè)置為：ωmax=0.9，ωmin=0.4，S=10，c1max=2.75，c2max=2.25,c1min=1.25,c2min=0.5，vmax=1.9，vmin=0，斥力場中的安全距離dm=2，kr=2.7，λ=0.25，μ=0.25，最大迭代次數(shù)為100。圖4(a)給出了在簡單環(huán)境下的OBLIPSO作用的移動機(jī)器人多目標(biāo)點(diǎn)移動軌跡。圖4(b)是IAPSO作用的運(yùn)動軌跡。圖4(c)是IPSO作用的運(yùn)動軌跡。

(a)OBLIPSO路徑軌跡

(b) IAPSO路徑軌跡

(c)IPSO路徑軌跡圖4 簡單環(huán)境下的優(yōu)化過程Fig.4 The motion process in the first environment

由圖4框中路徑軌跡可知：在目標(biāo)點(diǎn)3到目標(biāo)點(diǎn)4和目標(biāo)點(diǎn)6到目標(biāo)點(diǎn)7之間，OBLIPSO和IAPSO的避障性能上優(yōu)于IPSO，在經(jīng)過目標(biāo)點(diǎn)4和目標(biāo)點(diǎn)5時(shí)，OBLIPSO的路徑較為平滑。而且OBLIPSO在迭代72次左右時(shí)成功完成路徑規(guī)劃。

2)在第2次實(shí)驗(yàn)中，實(shí)驗(yàn)環(huán)境相對第1次實(shí)驗(yàn)而言，增加了障礙物以及目標(biāo)點(diǎn)的個(gè)數(shù)。實(shí)驗(yàn)參數(shù)設(shè)置如下：vmax=20，最大迭代次數(shù)為300，其余參數(shù)與第1次實(shí)驗(yàn)中參數(shù)相同。由于環(huán)境復(fù)雜度的增加，相對第1次實(shí)驗(yàn)而言，粒子收斂速度變慢。圖5(a)是在復(fù)雜環(huán)境下的OBLIPSO獲得的移動機(jī)器人多目標(biāo)點(diǎn)運(yùn)動軌跡。圖5(b)是IAPSO獲得的運(yùn)動軌跡。圖5(c)是IPSO作用的運(yùn)動軌跡。

(a)OBLIPSO路徑軌跡

(b)IAPSO路徑軌跡

(c) IPSO路徑軌跡圖5 復(fù)雜環(huán)境下迭代過程Fig.5 The iteration process in complicated environment

對比圖5中3條軌跡可知，隨著障礙物和目標(biāo)點(diǎn)增加，3種算法都滿足了路徑的可達(dá)性。根據(jù)圖5框中的路徑軌跡可知，在經(jīng)過目標(biāo)點(diǎn)6和目標(biāo)點(diǎn)9時(shí)，OBLIPSO算法規(guī)劃的路徑相比于IAPSO和IPSO算法規(guī)劃的路徑更為平滑。OBLIPSO算法規(guī)劃的路徑在目標(biāo)點(diǎn)5與目標(biāo)點(diǎn)10之間相比于IAPSO和IPSO算法規(guī)劃的路徑安全性更好，OBLIPSO移動距離較短(見表4)，而且其規(guī)劃的路徑安全性最好。

3)路徑規(guī)劃性能對比

重復(fù)10次上述兩種任務(wù)的實(shí)驗(yàn)，取其平均值。移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃的時(shí)間消耗和移動距離性能對比如表4所示。

表4 路徑性能對比

從表4數(shù)據(jù)中可以得出，隨著任務(wù)復(fù)雜度的增加，OBLIPSO、IAPSO和IPSO在時(shí)間消耗上也在增加，任務(wù)越復(fù)雜，用時(shí)越多。但在進(jìn)行相同任務(wù)時(shí)，OBLIPSO用時(shí)比IAPSO和IPSO少；在移動距離方面，簡單任務(wù)時(shí)，OBLIPSO的移動距離比其他兩種對比算法短，在復(fù)雜任務(wù)時(shí)，雖然OBLIPSO的移動距離長于IAPSO，但其比IPSO算法短；在路徑安全性方面，OBLIPSO算法要優(yōu)于其他兩種對比算法。由于在設(shè)計(jì)路徑規(guī)劃目標(biāo)函數(shù)時(shí)不僅考慮了路徑最短性問題，也考慮到了其安全性的問題，因此綜合兩種環(huán)境下實(shí)驗(yàn)結(jié)果可以得出OBLIPSO算法綜合性能強(qiáng)于IAPSO算法和IPSO算法。

圖6給出的是簡單環(huán)境下OBLIPSO算法、IAPSO算法和IPSO算法在目標(biāo)函數(shù)上的收斂曲線對比。從圖6中曲線可以得出，在迭代72次左右時(shí)，OBLIPSO算法可在多目標(biāo)點(diǎn)路徑規(guī)劃中尋到最優(yōu)路徑，而IAPSO算法和IPSO算法在迭代100次時(shí)仍未獲得OBLIPSO算法的收斂值。

圖6 OBLIPSO與IAPSO和IPSO目標(biāo)函數(shù)收斂曲線比較Fig.6 The convergence comparison of OBLIPSO with IAPSO and IPSO

綜上所述，在相同任務(wù)下，OBLIPSO算法的綜合性能優(yōu)于IAPSO算法和IPSO算法。隨著任務(wù)復(fù)雜度的變化，OBLIPSO算法能夠有效且較好地完成移動距離和時(shí)間消耗以及安全性上表現(xiàn)得更好，表明了OBLIPSO算法能夠有效且較好地完成移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃上有效性。

4.3 實(shí)際環(huán)境下路徑規(guī)劃

為了驗(yàn)證OBLIPSO算法在實(shí)際應(yīng)用中的有效性，筆者將在實(shí)際環(huán)境下對OBLIPSO算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)環(huán)境設(shè)置為重慶郵電大學(xué)自動化學(xué)院辦公樓一樓。實(shí)驗(yàn)平臺為先鋒3機(jī)器人，軟件背景為ROS(robot operation system)[19-21]。實(shí)驗(yàn)中設(shè)置了3個(gè)目標(biāo)點(diǎn)，機(jī)器人從目標(biāo)點(diǎn)1出發(fā)經(jīng)過兩個(gè)目標(biāo)點(diǎn)，最后返回目標(biāo)點(diǎn)1。

圖7中顯示的是機(jī)器人在無障礙環(huán)境中完成的多目標(biāo)點(diǎn)路徑規(guī)劃。圖7(a)為OBLIPSO算法規(guī)劃的路徑，圖7(b)為IAPSO算法規(guī)劃的路徑。由圖7可知：機(jī)器人從目標(biāo)點(diǎn)2到目標(biāo)點(diǎn)3的過程中，OBLIPSO算法能夠保證機(jī)器人與墻體保持安全距離且路徑平滑；IAPSO算法雖然保證了機(jī)器人與墻的安全距離，但由于機(jī)器人遠(yuǎn)離墻體移動造成了路徑的交叉，如圖7中方框所示。

(a)OBLIPSO路徑軌跡

(b)IAPSO路徑軌跡圖7 機(jī)器人在無障礙環(huán)境下的移動過程Fig.7 The motion process of robot in barrier-free environment

為了進(jìn)一步驗(yàn)證OBLIPSO算法的有效性，環(huán)境中設(shè)置了障礙物，并改變了目標(biāo)點(diǎn)3的位置，如圖8所示。圖8表示機(jī)器人在含有障礙物的環(huán)境下實(shí)現(xiàn)的多目標(biāo)點(diǎn)路徑規(guī)劃。圖8(a)為OBLIPSO算法規(guī)劃的路徑，圖8(b)為IAPSO算法規(guī)劃的路徑。由圖8可知：在含有障礙物的環(huán)境中，機(jī)器人在兩種算法下都能夠避開障礙物完成路徑規(guī)劃，但是機(jī)器人從目標(biāo)點(diǎn)2到目標(biāo)點(diǎn)3的過程中，OBLIPSO算法能夠保證機(jī)器人與障礙物保持安全距離并且路徑平滑；IAPSO算法在移動過程中，雖然機(jī)器人與障礙物保持了安全的距離，但由于其路徑的交叉導(dǎo)致移動軌跡較長，如圖8中方框所示。

表5為兩次實(shí)驗(yàn)重復(fù)10次取得的時(shí)間和路徑長度的平均值。由表5可知：在障礙環(huán)境下，OBLIPSO算法可以實(shí)現(xiàn)機(jī)器人多目標(biāo)點(diǎn)的路徑規(guī)劃，并且消耗的時(shí)間較少。

(a)OBLIPSO路徑軌跡

(b)IAPSO路徑軌跡圖8 機(jī)器人在障礙環(huán)境下的移動過程Fig.8 The motion process of robot in the obstacle environment

指標(biāo)無障礙有障礙(OBLIPSO/IAPSO)(OBLIPSO/IAPSO)時(shí)間/s114/114186/216距離/m20.1/20.119.5/20

5 結(jié)束語

本文提出了一種結(jié)合ACO算法和OBLIPSO算法的移動機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃新方法，并通過實(shí)驗(yàn)驗(yàn)證了新方法的可行性。ACO算法在TSP問題上表現(xiàn)出較好的優(yōu)越性，因此ACO算法適用于移動機(jī)器人的目標(biāo)點(diǎn)選擇問題。OBLIPSO算法不僅繼承了PSO算法計(jì)算簡單的特點(diǎn)，而且在初始化時(shí)引入反向?qū)W習(xí)策略，保證了粒子的多樣性。在迭代過程中，OBLIPSO算法抑制了粒子的早熟，提高了收斂速度。采用4個(gè)適應(yīng)度函數(shù)對OBLIPSO算法進(jìn)行性能評估，取得了良好的測試結(jié)果。仿真實(shí)驗(yàn)與真實(shí)環(huán)境下實(shí)驗(yàn)結(jié)果表明提出的新方法是一種有效的多目標(biāo)點(diǎn)路徑規(guī)劃方法。將本文提出的新方法應(yīng)用到動態(tài)環(huán)境下的移動機(jī)器人的多目標(biāo)點(diǎn)路徑規(guī)劃是下一步的研究內(nèi)容。

[1]楊興, 張亞, 楊巍,等. 室內(nèi)移動機(jī)器人路徑規(guī)劃研究[J]. 科學(xué)技術(shù)與工程, 2016, 16(15):234-238. YANG Xing, ZHANG Ya, YANG Wei, et al.Research on path planning of indoor mobile robot [J]. Science technology and engineering, 2016, 16 (15): 234-238.

[2]Ammar A, Bennaceur H, Chari I, et al. Relaxed Dijkstra and A*with linear complexity for robot path planning problems in large-scale grid environments[J]. Soft computing, 2016, 20(10):4149-4171.

[3]杜鵬楨, 唐振民, 孫研. 一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問題求解[J]. 控制與決策, 2014(10):1729-1736. DU Pengzhen, TANG Zhenmin, SUN Yan. An object-oriented multi-role ant colony optimization algorithm for solving TSP problem[J].Control and decision, 2014 (10): 1729-1736.

[4]AGRAWAL R K, BAWANE N G. Multiobjective PSO based adaption of neural network topology for pixel classification in satellite imagery[J]. Applied soft computing, 2015, 28(C):217-225.

[5]DAS P K, BEHERA H S, PANIGRAHI B K. Intelligent-based multi-robot path planning inspired by improved classical Q-learning and improved particle swarm optimization with perturbed velocity[J]. Engineering science and technology, an international journal, 2015, 19(1): 651-669.

[6]YANG Mao, LI Chunzhe. Path planning and tracking for multi-robot system based on improved PSO algorithm[C]//Proceedings of 2011 International Conference on Mechatronic Science, Electric Engineering and Computer(MEC). Jilin: IEEE, 2011: 1667-1670.

[7]WANG Mingming, LUO Jianjun, WALTER U. Trajectory planning of free-floating space robot using particle swarm optimization(PSO)[J]. Acta astronautica, 2015, 112: 77-88.

[8]張萬緒, 張向蘭, 李瑩. 基于改進(jìn)粒子群算法的智能機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(2): 510-513. ZHANG Wanxu, ZHANG Xianglan, LI Ying. Path planning for intelligent robots based on improved particle swarm optimization algorithm[J]. Journal of computer applications, 2014, 34(2): 510-513.

[9]王娟, 吳憲祥, 郭寶龍. 基于改進(jìn)粒子群優(yōu)化算法的移動機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(15): 240-244. WANG Juan, WU Xianxiang, GUO Baolong. Robot path planning using improved particle swarm optimization[J]. Computer engineering and applications, 2012, 48(15): 240-244.

[10]張勇, 陳玲, 徐小龍, 等. 基于PSO-GA混合算法時(shí)間優(yōu)化的旅行商問題研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(12): 3613-3617. ZHANG Yong, CHEN Ling, XU Xiaolong, et al. Research on time optimal TSP based on hybrid PSO-GA[J]. Application research of computers, 2015, 32(12): 3613-3617.

[11]TIZHOOSH H R. Opposition-based learning: a new scheme for machine intelligence[C]//Proceedings of 2005 and International Conference on Intelligent Agents, Web Technologies and Internet Commerce, International Conference on Computational Intelligence for Modelling, Control and Automation. Vienna: IEEE, 2005: 695-701.

[13]汪慎文, 丁立新, 謝大同, 等. 應(yīng)用反向?qū)W習(xí)策略的群搜索優(yōu)化算法[J]. 計(jì)算機(jī)科學(xué), 2012, 39(9): 183-187. WANG Shenwen, DING Lixin, XIE Datong, et al. Group search optimizer applying opposition-based learning[J]. Computer science, 2012, 39(9): 183-187.

[14]AL-QUNAIEER F S, TIZHOOSH H R, RAHNAMAYAN S. Opposition based computing-a survey[C]//Proceedings of the 2010 International Joint Conference on Neural Networks (IJCNN). Barcelona: IEEE, 2010.

[15]SURESH K, GHOSH S, KUNDU D, et al. Inertia-adaptive particle swarm optimizer for improved global search[C]//Proceedings of Eighth International Conference on Intelligent Systems Design and Applications. Kaohsiung: IEEE, 2008: 253-258.

[16]姜建國, 葉華, 劉慧敏, 等. 融合快速信息交流和局部搜索的粒子群算法[J]. 哈爾濱工程大學(xué)學(xué)報(bào), 2015, 36(5): 687-691. JIANG Jianguo, YE Hua, LIU Huimin, et al. Particle swarm optimization method with combination of rapid information communication and local search[J]. Journal of Harbin engineering university, 2015, 36(5): 687-691.

[17]GAO Bingkun, REN Xiuju, XU Mingzi. An improved particle swarm algorithm and its application[J]. Procedia engineering, 2011, 15: 2444-2448.

[18]許少華, 李新幸. 一種自適應(yīng)改變慣性權(quán)重的粒子群算法[J]. 科學(xué)技術(shù)與工程, 2012, 12(9): 2205-2208. XU Shaohua, LI Xinxing. An adaptive changed inertia weight particle swarm algorithm[J]. Science technology and engineering, 2012, 12(9): 2205-2208.

[19]張建偉, 張立偉, 胡穎, 等. 開源機(jī)器人操作系統(tǒng): ROS[M]. 北京: 科學(xué)出版社, 2012.

[20]COUSINS S, GERKEY B, CONLEY K, et al. Sharing Software with ROS[J]. IEEE robotics & automation magazine, 2010, 17(2): 12-14.

[21]ZAMAN S, SLANY W, STEINBAUER G. ROS-based mapping, localization and autonomous navigation using a Pioneer 3-DX robot and their relevant issues[C]//Proceedings of 2011 Saudi International Electronics, Communications and Photonics Conference (SIECPC). Riyadh: IEEE, 2011: 1-5.

Mobile robot multi-goal path planning using improvedparticle swarm optimization

PU Xingcheng1， LI Junjie2， WU Huichao2， ZHANG Yi3

(1.School of Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, China; 2.Research Center of Intelligent System and Robot， Chongqing University of Posts and Telecommunications, Chongqing 400065, China; 3.Advanced Manufacturing Engineering School， Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

To solve the problem of multi-goal path planning for mobile robots that pass multiple goals, a new path planning method, based on improved particle swarm optimization (PSO) and ant colony optimization (ACO), is proposed. In this new method, the first step is to use an improved PSO, which has high convergence, to optimize the path between two goals among a sequence of goals. The second step is to use the ACO to obtain the shortest path for all target points. The performance experimental result demonstrates that the improved PSO algorithm can effectively avoid premature convergence and enhances search ability and stability. Simulation results show that the improved PSO algorithm can make a mobile robot realize collision-free multi-goal path planning effectively . Experiments in a real environment demonstrate that this algorithm has practical application for multi-goal path planning.

mobile robot; multi-goal path planning; ACO; improved PSO; opposition-based learning; inertia weight; learning factors

10.11992/tis.201606046

http://kns.cnki.net/kcms/detail/23.1538.TP.20170404.1218.004.html

2016-06-30. 網(wǎng)絡(luò)出版日期：2017-04-04.

國家自然科學(xué)基金(51604056)，重慶市科學(xué)技術(shù)委員會項(xiàng)目(cstc2015jcyBx0066)；重慶市教委項(xiàng)目(KJ1400432).

李俊杰. E-mail：lijunjie166@126.com.

TP242.6

A

1673-4785(2017)03-0301-09

蒲興成，男，1973年生，副教授，博士，主要研究方向?yàn)榉蔷€性系統(tǒng)、隨機(jī)系統(tǒng)和現(xiàn)代智能算法。主持重慶郵電大學(xué)校級科研項(xiàng)目3項(xiàng),參與國際合作項(xiàng)目1項(xiàng),參與省部級項(xiàng)目6項(xiàng)。發(fā)表學(xué)術(shù)論文30余篇,出版著作1部。

李俊杰，男，1990年生，碩士研究生，主要研究方向?yàn)橐苿訖C(jī)器人自主導(dǎo)航。

吳慧超，女，1990年生，碩士研究生，主要研究方向?yàn)橹悄芊?wù)機(jī)器人。