基于改進(jìn)LPSO混合算法的多機(jī)器人編隊(duì)

仇國(guó)慶+牛婷+寇倩倩

摘 要：針對(duì)領(lǐng)航跟隨法和基于行為法在機(jī)器人編隊(duì)控制上的缺點(diǎn)，采用了混合編隊(duì)方法即動(dòng)態(tài)偏轉(zhuǎn)角度φ值的虛擬領(lǐng)航跟隨法結(jié)合基于行為法，能彌補(bǔ)傳統(tǒng)領(lǐng)航跟隨法的缺陷，可以保持隊(duì)形的穩(wěn)定，形成隊(duì)形反饋，在兩種編隊(duì)方法結(jié)合的基礎(chǔ)上，加入混合算法進(jìn)行在線優(yōu)化，該混合算法是在PSO算法的基礎(chǔ)上改進(jìn)慣性權(quán)重公式，加速收斂速率和解決易掉進(jìn)局部最優(yōu)的缺陷；同時(shí)引入能進(jìn)行長(zhǎng)短離搜索的萊維飛行，該混合算法能進(jìn)一步加快粒子跳出局部最優(yōu)，避免陷入早熟的情況，從而有效的優(yōu)化機(jī)器人編隊(duì)的路徑，可以使機(jī)器人的編隊(duì)時(shí)間縮短。實(shí)驗(yàn)仿真成果證實(shí)，所采用的方法的可行性和有用性。

關(guān)鍵詞：編隊(duì)控制；粒子群算法；慣性權(quán)重；萊維飛行

引言

近年來，多機(jī)器人編隊(duì)控制[1]是已經(jīng)成為多機(jī)器人協(xié)作的重要研究方向之一。編隊(duì)控制[2]是指機(jī)器人以一定的隊(duì)形避開環(huán)境的約束向目標(biāo)點(diǎn)運(yùn)動(dòng)的控制技術(shù)，很多學(xué)者根據(jù)任務(wù)需求，提出許多經(jīng)典方法，包含有領(lǐng)航跟隨（leader-follower）[3-4]基于行為法（behavior-based）[5]、人工勢(shì)場(chǎng)法[6]、虛擬結(jié)構(gòu)法（virtual-structure）等。文獻(xiàn)[7]在虛擬領(lǐng)航者的基礎(chǔ)上加入分散控制算法，但是仍然無法保證隊(duì)形的穩(wěn)定性，文獻(xiàn)[8]提出特定領(lǐng)航者的編隊(duì)方法，但是該算法要在一定的充分條件和收斂區(qū)間才能發(fā)揮作用，文獻(xiàn)[9]提出了改進(jìn)的人工勢(shì)場(chǎng)法的編隊(duì)控制，通過沿墻導(dǎo)航法來控制機(jī)器人的隊(duì)形變換，機(jī)器人無法到達(dá)最優(yōu)路徑，上述研究雖然都可以完成機(jī)器人的編隊(duì)控制，但是很少會(huì)在線對(duì)機(jī)器人的路徑做優(yōu)化。

針對(duì)上述問題，提出了一種用萊維飛行算法結(jié)合慣性權(quán)重對(duì)數(shù)遞減的粒子群算法來進(jìn)行多機(jī)器人編隊(duì)控制，該方法的思想是當(dāng)領(lǐng)航者的角度發(fā)生變化時(shí)，跟隨者能適應(yīng)其角度的變化，不會(huì)發(fā)生掉隊(duì)的現(xiàn)象，隊(duì)形保持穩(wěn)定，同時(shí)對(duì)粒子群算法的公式做改進(jìn)，以對(duì)數(shù)遞減函數(shù)做粒子群算法的慣性權(quán)重，可以使收斂速度有一定的提高，萊維飛行的引入，可以增加種群的搜索能力，避免早熟，得到最佳的機(jī)器人路徑。

1 混合編隊(duì)控制

1.1 基于動(dòng)態(tài)φ值的虛擬領(lǐng)航跟隨法

由于領(lǐng)航跟隨法比較簡(jiǎn)單、容易理解，所以就受到研究編隊(duì)控制人員的青睞，它的主要原理[10]是選取當(dāng)中某個(gè)機(jī)器人作為leader，另外剩余的機(jī)器人作為follower，設(shè)定領(lǐng)航者（leader）和跟隨者（follower） 運(yùn)動(dòng)位置關(guān)系，然后follower以固定的距離和方向跟隨leader，形成一定的隊(duì)形。但是這種方法太依賴于領(lǐng)航者，一旦領(lǐng)航者出現(xiàn)故障，那么機(jī)器人編隊(duì)的隊(duì)形就無法保持，且該方法無法形成反饋和只能求解局部最優(yōu)而不是全局最優(yōu)。動(dòng)態(tài)偏轉(zhuǎn)角度φ值的虛擬領(lǐng)航跟隨法能彌補(bǔ)其缺點(diǎn)，所示當(dāng)領(lǐng)航者遇到阻礙，偏轉(zhuǎn)角度太大，跟隨者可以自適應(yīng)的改變自己的角度，迅速到達(dá)隊(duì)形點(diǎn)。

1.2 基于行為法

基于行為法[11]是有幾個(gè)子行為組成，它有明確的隊(duì)形反饋。但是也存在著一些不足，沒有固定的數(shù)學(xué)模型，導(dǎo)致行為難以融合，即機(jī)器人躲避障礙物的時(shí)候和向目標(biāo)點(diǎn)移動(dòng)有可能很難同時(shí)進(jìn)行，所以隊(duì)形的穩(wěn)定性就無法控制。

1.3 混合編隊(duì)方法

針對(duì)前面所述的兩種方法的優(yōu)缺點(diǎn)，本文提出了動(dòng)態(tài)偏轉(zhuǎn)角度 φ值的虛擬領(lǐng)航跟隨法，同時(shí)結(jié)合基于行為法的機(jī)器人編隊(duì)控制，兩者之間相互互補(bǔ)，完成編隊(duì)任務(wù)。

當(dāng)領(lǐng)航機(jī)器人遇到障礙物時(shí)，會(huì)改變其原有的方向，如果偏轉(zhuǎn)角度過大，會(huì)使跟隨者產(chǎn)生掉隊(duì)或者回退的現(xiàn)象，采用動(dòng)態(tài)偏轉(zhuǎn)角度φ值的虛擬領(lǐng)航跟隨法，可以使跟隨者始終和領(lǐng)航者保持相同的偏轉(zhuǎn)角度φ，產(chǎn)生相同的弧形，穩(wěn)定隊(duì)形，同時(shí)在動(dòng)態(tài)偏轉(zhuǎn)角度φ值的虛擬領(lǐng)航跟隨法上加入基于行為法，可以防止機(jī)器人進(jìn)入死鎖狀態(tài)，通過基于行為法的隨機(jī)擾動(dòng)行為和通向目標(biāo)點(diǎn)的行為，使機(jī)器人脫離死鎖，形成完整的隊(duì)形。

2 改進(jìn)的LPSO（Levy Particle Swarm Optimization）算法

2.1 改進(jìn)的PSO（Particle Swarm Optimization）算法

式中β為對(duì)數(shù)調(diào)整因子，取1.2。K為當(dāng)前代次數(shù)，對(duì)數(shù)遞減的ωi的變化是先減少緩慢后加速減小，因此它可以使全局和局部的搜索能力有所改善，并加速收斂速度和提高收斂精度。

二是對(duì)改進(jìn)適應(yīng)度函數(shù)，它在算法中占有很高的地位，其性能可以反映粒子本身的好壞程度，本文所采用的就是在機(jī)器人原本路徑的基礎(chǔ)上加入穩(wěn)定度因子、光滑度因子，最后對(duì)所有的參數(shù)進(jìn)行加權(quán)平均，其公式：F=α×f1+β×f2+γ×f3，α、β、γ分別為的加權(quán)因子，可以通過調(diào)節(jié)α、β、γ來決定各自函數(shù)占的比重，且它們都是大于或者等于零，且小于1的實(shí)數(shù)。f1為機(jī)器人的路徑長(zhǎng)度，f2為穩(wěn)定函數(shù)，與粒子直線到目標(biāo)點(diǎn)遇到障礙物的個(gè)數(shù)有關(guān)，f2=M，M是一個(gè)較大的為起點(diǎn)到終點(diǎn)的直線路徑上的障礙物之和，f3路徑光滑度函數(shù)，f3=πr+πr，n1為機(jī)器人在原始方向上改變?yōu)?5度的次數(shù)之和，n2為在原始方向上改變?yōu)?0度的次數(shù)之和，r為機(jī)器人的半徑。f1在公式中占有的很高的地位，因此α的取值就比較高，f2其次，β就比α低一個(gè)數(shù)量級(jí)，f3幾乎可以不考慮，γ為接近或者等于0，仿真試驗(yàn)中α為0.9，β為0.09，γ為0.001。

2.2 萊維飛行

Levy飛行是服從Levy分布的隨機(jī)搜索路徑[13]，既能進(jìn)行短距離也能進(jìn)行長(zhǎng)距離的搜索，現(xiàn)很多優(yōu)化的領(lǐng)域都已在使用，主要原因是因?yàn)樗粌H能擴(kuò)大搜索的范圍，也可以增加種群的多樣性，因此采用萊維飛行能跳出局部最優(yōu)點(diǎn)[14]。

2.3 混合算法的機(jī)器人編隊(duì)控制

在機(jī)器人編隊(duì)控制中，引入萊維飛行的改進(jìn)的PSO混合算法，可以使機(jī)器人避免陷入局部極小點(diǎn)，并迅速找到最優(yōu)解，機(jī)器人能找到一條最優(yōu)路徑到達(dá)目標(biāo)點(diǎn)，混合算法優(yōu)化機(jī)器人編隊(duì)的步驟：

Step1：初始化種群，包括各參數(shù)N、x、v、Tmax；

Step2：計(jì)算適應(yīng)度函數(shù)F，找到每個(gè)粒子的局部最優(yōu)和整體最優(yōu)；

Step3：根據(jù)具有對(duì)數(shù)遞減的慣性權(quán)重粒子群公式更新粒子的位置和速度；

Step4：粒子更新迭代的次數(shù)是否大于10，如果大于10，則執(zhí)行Step5，否則執(zhí)行Step6；

Step5：進(jìn)行萊維飛行算法，重復(fù)Step2 和Step3；

Step6：判斷迭代的次數(shù)，如若大于Tmax，則程序結(jié)束，否則轉(zhuǎn)向Step2。

3 仿真成果和分析

為了檢驗(yàn)本文所采用算法的具體效果，在VC6.0的基礎(chǔ)上對(duì)其進(jìn)行仿真測(cè)試，在7×7的仿真測(cè)試環(huán)境下，并與傳統(tǒng)的MPLA編隊(duì)算法進(jìn)行比較分析。

MPLA算法[15]是在傳統(tǒng)的LFB編隊(duì)的基礎(chǔ)上，加入多智能體粒子群算法（MAPSO），MAPSO是將多個(gè)Agent智能體與PSO算法結(jié)合，引入鄰居的概念，加強(qiáng)粒子與其他粒子的相互通信，改變粒子本身的行為，使其多樣性增加，同時(shí)利用鄰居間的信息完成搜索到最優(yōu)值。以下是兩種算法的比較仿真圖，這兩種算法在多個(gè)復(fù)雜障礙物中的仿真結(jié)果如圖1和圖2。圖中矩形和圓形分別代表障礙物，黑色的點(diǎn)代表領(lǐng)航機(jī)器人。

在兩種算法中，設(shè)定機(jī)器人以三角形的隊(duì)形開始運(yùn)行，仿真過程中，機(jī)器人可以迅速到達(dá)三角形的隊(duì)形點(diǎn)，躲避障礙物完成編隊(duì)，但是兩種算法相比較，從仿真圖可以看出機(jī)器人在簡(jiǎn)單障礙物和復(fù)雜障礙物的情況下，機(jī)器人所走的路徑不同，在改進(jìn)的LPSO算法下，機(jī)器人的路徑得到優(yōu)化，因此本文所采用算法的編隊(duì)路徑效果優(yōu)于MPLA算法。

為了更好的表現(xiàn)所采用算法優(yōu)越性，表1記錄了簡(jiǎn)單障礙物和復(fù)雜障礙物下的兩種算法的性能指標(biāo)，即路徑長(zhǎng)度、仿真時(shí)間和轉(zhuǎn)角次數(shù)。

由表1可以看出，本文所采用算法的轉(zhuǎn)角次數(shù)少，機(jī)器人路徑的穩(wěn)定性和光滑性得到提高，同時(shí)隊(duì)形保持的效果更為明顯，在運(yùn)動(dòng)過程中，不會(huì)出現(xiàn)多次的拐角震蕩，保持穩(wěn)定的隊(duì)形向前移動(dòng)；仿真時(shí)間少于MPLA算法，可見其收斂速度快于MPLA，機(jī)器人能迅速到達(dá)目標(biāo)點(diǎn)，完成編隊(duì)的效率也有所提高；機(jī)器人所走的路徑步數(shù)也不同，且本文算法的路徑步數(shù)小于MPLA算法的步數(shù)，證實(shí)改進(jìn)的LPSO算法能使機(jī)器人選擇最佳路徑，使其到達(dá)目標(biāo)點(diǎn)所走的步數(shù)少，獲得的最優(yōu)路徑也比MPLA短。

4 結(jié)束語

把動(dòng)態(tài)偏轉(zhuǎn)角度φ值的虛擬領(lǐng)航跟隨法，與基于行為法相結(jié)合，形成隊(duì)形反饋，可以減少掉隊(duì)和保持隊(duì)形，在編隊(duì)控制中，本文采用對(duì)慣性權(quán)重和適應(yīng)度函數(shù)做改進(jìn)的PSO算法對(duì)路徑規(guī)劃，并在此基礎(chǔ)上引入萊維飛行，加快收斂速度，跳出局部極值，得到最優(yōu)路徑。實(shí)驗(yàn)仿真研究表明，本文算法能使機(jī)器人很快找到最優(yōu)路徑到達(dá)最終點(diǎn)，達(dá)成編隊(duì)要求。

參考文獻(xiàn)

[1]韓光勝，韓佳彤.多機(jī)器人編隊(duì)的研究與實(shí)現(xiàn)[D].北京：北京工業(yè)大學(xué)，2010.

[2]董勝龍，陳衛(wèi)東，席裕庚.多機(jī)器人編隊(duì)的分布式控制系統(tǒng)[J].機(jī)器人，2000，22（6）：433-438.

[3]Yu W W， Chen G R， CAO M. Distributed leader- follower flocking control for multi-agent dynamic a systems with time varying velocities[J].Systems and Control Letter，2010，59（9）：543-552.

[4]Ren D H， Lu G Z. Consideration on formation control[J].Control and Decision Making， 2005 2005，20（6）：601-606.

[5]FRESLUND J，MATARIC M J. A general algorithm for robot formations using local sensing and minimal communication robotics and automation[J].IEEE Transactions on Robotics and Automation，2002，18（5）：837-846.

[6]楊麗，曹志強(qiáng)，譚民.不確定環(huán)境下多機(jī)器人的動(dòng)態(tài)編隊(duì)控制[J].機(jī)器人，2010，32（2）：283-288.

[7]高芹，鄭新娟，鐘毅，等.基于PSO算法虛擬Leader的多機(jī)器人的編隊(duì)控制[J].武漢理工大學(xué)學(xué)報(bào)，2014，36（2）：136-140.

[8]杜柏陽，張良國(guó)，孫一杰，等.基于特定領(lǐng)航者的多機(jī)器人編隊(duì)控制方法[J].電光與控制，2015，22（9）：72-76.

[9]周自維，周冰，趙雪.基于改進(jìn)人工勢(shì)場(chǎng)的多機(jī)器人編隊(duì)控制[J].科技創(chuàng)新與應(yīng)用，2015，33.

[10]付帥. 動(dòng)態(tài)環(huán)境下的多機(jī)器人編隊(duì)控制方法的研究[J].計(jì)算機(jī)仿真，2014，31（12）：384-387.

[11]瞿勇，宋業(yè)新，張建軍.一類模糊多目標(biāo)雙矩陣對(duì)策的粒子群優(yōu)化算法[J].海軍工程大學(xué)學(xué)報(bào)，2009（3）：6-11.

[12]楊嬌，葉春明.應(yīng)用新型螢火蟲算法求解Job-shop調(diào)度問題[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（11）：213-215.

[13]Yang X S. Nature-inspired metaheuristic algorithm[M].2nded.Frome：Luniver Press，2010：16-29.

[14]王慶喜，郭曉波.基于萊維飛行的粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2015，33.

[15]唐賢倫，劉念慈，鄧露，等.基于MAPSO的混合式多機(jī)器人編隊(duì)控制[J].華中科技大學(xué)學(xué)報(bào)（自然科版），2015，43（7）：104-107.

作者簡(jiǎn)介：仇國(guó)慶（1963-），男，重慶人，副教授，碩士，主要從事現(xiàn)場(chǎng)總線控制、智能儀器儀表及控制裝置、運(yùn)動(dòng)控制系統(tǒng)。

寇倩倩（1991-），女，晉運(yùn)城人，碩士研究生，主要研究方向：交通流的數(shù)據(jù)挖掘。