劉傳領(lǐng), 韓承雪

一種基于優(yōu)化融合算法的機(jī)器人路徑規(guī)劃技術(shù)

劉傳領(lǐng)1, 韓承雪2

(1.商丘師范學(xué)院 計算機(jī)與信息技術(shù)學(xué)院,河南 商丘 476000； 2. 商丘職業(yè)技術(shù)學(xué)院,河南 商丘 476100)

局部最優(yōu)問題是當(dāng)前移動機(jī)器人路徑規(guī)劃算法中存在的一個關(guān)鍵問題. 為了解決該問題，文章提出了一種基于PSO和QGA的移動機(jī)器人路徑規(guī)劃算法. 該算法利用粒子群具有記憶能力、能參考局部最佳位置方向和全局最佳位置方向進(jìn)行擇優(yōu)搜索的特點，對路徑進(jìn)行局部優(yōu)化；然后利用量子遺傳算法的收斂速度快和全局尋優(yōu)能力強(qiáng)的特點，對最優(yōu)或次優(yōu)個體進(jìn)行選擇, 為最優(yōu)或次優(yōu)個體進(jìn)入下一代提供了保障，提高了算法的性能. 仿真結(jié)果表明，該算法的穩(wěn)定性及尋優(yōu)能力均被明顯改善，且有更好的收斂性以及更強(qiáng)的連續(xù)空間搜索能力，適合于求解復(fù)雜優(yōu)化問題.

粒子群優(yōu)化；路徑規(guī)劃；移動機(jī)器人；量子遺傳算法

移動機(jī)器人路徑規(guī)劃是機(jī)器人領(lǐng)域的一項重要課題，機(jī)器人根據(jù)自身傳感器對環(huán)境的感知，從起始點到目標(biāo)點之間找到一條安全無碰的路徑,高效完成作業(yè)任務(wù). 依據(jù)對環(huán)境知識的了解,可分為已知環(huán)境、部分已知環(huán)境和未知環(huán)境下的路徑規(guī)劃[1]78，[2]279，[3]476. 智能移動機(jī)器人路徑規(guī)劃的研究起始于20世紀(jì)70年代，許多學(xué)者對其進(jìn)行了深入地研究，取得了大量的研究成果，且已進(jìn)入了政府和商業(yè)的實際應(yīng)用領(lǐng)域[4]110，[5]1646，[6]903，[7]1356，[8]134. 2008年徐玉如等提出了一種基于遺傳算法和粒子群優(yōu)化算法的全局路徑規(guī)劃思想[5]1647，用于水下機(jī)器人導(dǎo)航. Casillas等人[6]907提出了一種基于模糊系統(tǒng)不確性的多目標(biāo)遺傳數(shù)據(jù)挖掘算法，該方法采用模糊規(guī)則和多目標(biāo)遺傳的融合算法應(yīng)用于客戶的行為消費模型，有效處理了客戶消費行為中的許多不確定性數(shù)據(jù). Kumar和Rao結(jié)合蟻群算法和遺傳算法及基于數(shù)據(jù)挖掘的技巧，提出了一種新的混合遺傳算法并應(yīng)用于工作調(diào)度等問題，也取得了較好的效果[9]589，[10]39-43. 但這些算法在應(yīng)用中也存在不足，例如，出現(xiàn)局部最小問題、運行時間長、找不到最優(yōu)解等.

基于以上分析，本文提出了一種基于PSO和QGA的移動機(jī)器人路徑規(guī)劃技術(shù). 該算法在量子遺傳算法中融合粒子群優(yōu)化算法的優(yōu)點實現(xiàn)一種混合路徑規(guī)劃技術(shù)，通過粒子群優(yōu)化方法來實現(xiàn)量子比特狀態(tài)的更新,實現(xiàn)了對空間廣泛細(xì)致的搜索. 通過仿真實驗證明該算法具有更快的收斂速度和很好的實用性.

1 PSO及其改進(jìn)

這里c1、c2被稱為學(xué)習(xí)因子，根據(jù)實際情況取值，rand1()、rand2()是均勻隨機(jī)函數(shù).vij(t-1)反映了個體的運動“習(xí)慣” ，即個體具有保持自己原先運動狀態(tài)的趨勢；c1rand1()(Pij-xij(t-1))反映了個體對自己原先運動狀態(tài)的記憶或回憶，說明個體具有向自己最佳位置逼近的趨勢；c2rand2()(Plj-xij(t-1))反映了個體之間協(xié)同合作，代表個體具有向群體或鄰域最佳位置逼近的趨勢[11]69-73. 為了迅速找到最優(yōu)解，本文對粒子群優(yōu)化算法做如下改進(jìn)：

1)動態(tài)探測機(jī)制的引入，使粒子個體獲得能夠感知環(huán)境變化的能力；

2)環(huán)境響應(yīng)機(jī)制的引入，在探測到環(huán)境變化后，采用相應(yīng)的響應(yīng)措施來適應(yīng)環(huán)境的變化.

具體的設(shè)計方案為：

1)利用探測粒子探測環(huán)境是否發(fā)生變化，若沒有變化，則不改變算法；

2)若環(huán)境發(fā)生改變，把改變的環(huán)境空間劃分為N1個均勻的子空間；在每個子空間內(nèi)隨機(jī)設(shè)置N2個敏感粒子；

3)計算每次迭代時敏感粒子適應(yīng)值fi，并計算相鄰2次迭代適應(yīng)值的差值Δfi；

Δfi=f(i+1)-f(i) (1in)

4)對所有差值的絕對值求和F.

×

當(dāng)F=0，環(huán)境不發(fā)生變化；F>0，環(huán)境發(fā)生變化，則設(shè)置響應(yīng)閾值Fthreshold，當(dāng)F>Fthreshold時，對粒子的位置和速度進(jìn)行修改.

vi(t)=(vi1,vi2,…,

2 QGA及PSO和QGA的融合方法

2.1 量子比特編碼

一個量子比特的狀態(tài)可以取0或1，其狀態(tài)表示為

|φ〉=α|0〉+β|

其中α、β為代表相應(yīng)狀態(tài)出現(xiàn)概率的兩個復(fù)數(shù)，且

對一個具有s位量子態(tài)的數(shù)據(jù)q，構(gòu)造對應(yīng)數(shù)據(jù)結(jié)構(gòu)p，p為長度為s的二進(jìn)制串，p稱為觀測態(tài)[12].q和p分別為：

2.2 量子染色體變異操作

量子染色體變異是通過量子態(tài)的變換來實現(xiàn)的，即通過量子門的旋轉(zhuǎn)角變換來實現(xiàn)量子染色體的變異操作, 加快收斂速度. 量子旋轉(zhuǎn)門的調(diào)整操作如下:

θi=s(αi,βi)Δ

θi=s(αi,βi)和Δθi分別代表量子門旋轉(zhuǎn)的方向和角度,根據(jù)經(jīng)驗Δθi的取值一般在0.1π～0.005π之間.

2.3PSO和QGA的融合流程

PSO-QGA算法流程描述如下：

Step1 算法初始化，t=t+1；

Step3 染色體變異：根據(jù)變異概率，對染色體的量子比特的幾率幅(α,β)位置對調(diào)；

Step5 根據(jù)2.1節(jié)的粒子群優(yōu)化算法進(jìn)行局部優(yōu)化和確定全局優(yōu)化解；

Step6 判斷是否滿足終止條件，若滿足則退出；否則t=t+1，轉(zhuǎn)到step3，進(jìn)入循環(huán)迭代.

3 仿真結(jié)果與分析

采用Matlab仿真軟件，對上述算法進(jìn)行了仿真測試. 為了便于測試，仿真試驗放在10×10和20×20單位區(qū)域的環(huán)境中進(jìn)行，機(jī)器人起點(Start)設(shè)在(0，0)點，目標(biāo)點(End)設(shè)在(9，9)點. 算法參數(shù)為：群體規(guī)模為n=30，個體長度m=40，迭代次數(shù)t=60，學(xué)習(xí)因子c1=1.5，c2=2.0，vmax=10.

實驗1 如圖1所示，S點為機(jī)器人的出發(fā)點，E為機(jī)器人的終點，實驗在10×10單位區(qū)域環(huán)境中進(jìn)行. 實驗分別給出了PSO算法、QGA算法和本文算法規(guī)劃的路徑，結(jié)果顯示，PSO算法規(guī)劃的路徑是一條無效路徑，QGA算法規(guī)劃的路徑是一條非優(yōu)化路徑，本文算法規(guī)劃的路徑是一條優(yōu)化路徑 . 如圖2所示給出了本文算法在20×20單位區(qū)域環(huán)境中的實驗，規(guī)劃出了一條優(yōu)化路徑.

實驗2 因為路徑規(guī)劃是在滿足安全的條件下尋找一條耗時最少、距離最短的優(yōu)化路徑，因此，如圖3所示中路徑的適應(yīng)值越小，則路徑越優(yōu)化. 圖3給出種群平均適應(yīng)值及最優(yōu)個體的進(jìn)化圖，結(jié)果顯示，對于個體最優(yōu)來說，算法運行到18次時就基本達(dá)到最優(yōu)，而對于種群的平均優(yōu)化來說，算法運行到43次時才能到達(dá)基本最優(yōu). 因此，在進(jìn)化過程中應(yīng)該根據(jù)實際情況選擇最優(yōu)解進(jìn)入下一代.

圖1 三種算法性能的比較

圖2 本文算法規(guī)劃的優(yōu)化路徑

圖3 本文算法進(jìn)化圖

實驗3 在相同實驗條件下，對遺傳算法(GeneticAlgorithm，GA)、QGA算法和本文算法從可行解平均長度、獲得可行解比例、平均消耗時間進(jìn)行了性能比較. 實驗結(jié)果表明本文算法的優(yōu)化能力比較強(qiáng). 見表1.

表1 三種算法的測試數(shù)據(jù)

4 結(jié)論

粒子群優(yōu)化算法和量子遺傳算法都是應(yīng)用比較廣泛的優(yōu)化算法，應(yīng)用于移動機(jī)器人路徑規(guī)劃取得了良好的效果. 本文算法融合了兩種算法的優(yōu)點，通過粒子群優(yōu)化來實現(xiàn)量子比特狀態(tài)的更新，從而更加方便、簡潔. 此算法應(yīng)用于機(jī)器人路徑規(guī)劃技術(shù)上，表現(xiàn)出了比較穩(wěn)定的性能、較快的尋優(yōu)速度. 仿真實驗結(jié)果表明，本文所提算法在穩(wěn)定性能、尋優(yōu)能力和收斂性方面均優(yōu)于PSO算法、GA算法和QGA算法.

[1] 劉傳領(lǐng)，楊靜宇. 復(fù)雜環(huán)境下解決勢場法局部極小問題的路徑規(guī)劃方法[J].哈爾濱理工大學(xué)學(xué)報, 2014，31(11).

[2]XU,C.MING,A.NAGAOKA,T.SHIMOJO,M..Motioncontrolofagolfswingrobot[J].InJournalofRoboticandSystem,February2009,Vol.56.

[3] 李 磊, 葉 濤, 譚 民, 等. 移動機(jī)器人技術(shù)研究現(xiàn)狀與未來[J]. 機(jī)器人,2002, 24(5).

[4] 徐玉如, 姚耀中. 考慮海流影響的水下機(jī)器人全局路徑規(guī)劃研究[J]. 中國造船, 2008, 49(4).

[5]CasillasJ，etal.Mininguncertaindatawithmultiobjectivegeneticfuzzysystemstobeappliedinconsumerbehaviormodeling[J].ExpertSystemswithApplication, 2009, 36(2).

[6]KumarS，RaoCSP.Applicationofantcolony,geneticalgorithmanddatamining-basedtechniquesforscheduling[J].RoboticsandComputer-IntegratedManufacturing, 2009, 25(6).

[7]HanKuk-Hyun,KimJong-Hwan.Geneticquantumalgorithmanditsapplicationtocombinatorialoptimizationproblem[C].Proceedingsofthe2000CongressonEvolutionaryComputation, 2000.

[8] 朱慶保, 張玉蘭. 基于柵格法的機(jī)器人路徑規(guī)劃蟻群算法[J]. 機(jī)器人，2005，27(2).

[9] 朱慶保. 復(fù)雜環(huán)境下的機(jī)器人路徑規(guī)劃螞蟻算法[J]. 自動化學(xué)報, 2006, 32(6).

[10]EberhartR,KennedyJ.Anewoptimizerusingparticlewarmtheory[A].ProccedingsoftheSixthInternationalSymposiumonMicroMachineandHumanScience[C].Nagoya:IEEEPress, 1995.

[11]ShiY,EberhartRC.Amodifiedparticleswarmoptimizer[C].ProceedingsofInternationalConferenceonEvolutionComputationAnchorage, 1998.

[12]knightP.Quantuminformationprocessingwithoutentanglement[J].Science, 2000(287).

[責(zé)任編輯 冰 竹]

A Mobile Robot Path Planning Technology Based on Optimization Fusion Algorithm

LIU Chuanling1, HAN Chengxue2

(1.DepartmentofComputerandInformationTechnology,ShangqiuNormalUniversity,Shangqiu476000,China;2.ShangqiuVocationalandTechnicalCollege,Shangqiu476100,China)

Local optimum is a key problem in current research related mobile robot path planning methods. In order to solve the problem, a novel mobile robot path planning algorithm is proposed in this paper, which uses memory ability, the ability of the best position & direction investigation of the individual and the global of particle swarm optimization (PSO) to plan path locally for mobile robot, and uses fast convergence & searching the best solution capability of quantum genetic algorithm (QGA) to select the optimal or sub-optimal path in order to protect the optimal or sub-optimal path into the next generation. It increases greatly the efficiency of the algorithm. Results of the simulation demonstrate the ability of finding the best solution and the stability of this method are greatly improved, it has better convergent property and ability of searching more extensive space and is fit for finding the solution in complex optimization problems.

particle swarm optimization (PSO); path planning; mobile robot; quantum genetic algorithm (QGA)

2015-01-28

劉傳領(lǐng)(1969- )，男，河南商丘人，商丘師范學(xué)院副教授，博士，主要從事為模式識別、計算機(jī)智能控制研究。

1671-8127(2015)02-0012-04

TP202.7

A