[發(fā)明專利]基于混合粒子群的移動(dòng)機(jī)器人全局路徑規(guī)劃算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710633541.1
• 申請(qǐng)日: 2017-07-28
• 公開(kāi)（公告）號(hào): CN107368075A
• 公開(kāi)（公告）日: 2017-11-21
• 發(fā)明（設(shè)計(jì)）人: 朱戰(zhàn)霞;唐必偉;劉紅慶;袁建平
• 申請(qǐng)（專利權(quán)）人: 西北工業(yè)大學(xué)
• 主分類號(hào): G05D1/02
• 分類號(hào): G05D1/02
• 代理公司: 西安通大專利代理有限責(zé)任公司61200
• 代理人: 強(qiáng)宏超

技術(shù)領(lǐng)域

本發(fā)明屬于機(jī)器人技術(shù)領(lǐng)域，涉及機(jī)器人全局路徑規(guī)劃算法，尤其涉及一種基于混合粒子群的移動(dòng)機(jī)器人全局路徑規(guī)劃算法。

背景技術(shù)

在過(guò)去幾十年中，移動(dòng)機(jī)器人已經(jīng)成功地用于工業(yè)和軍事領(lǐng)域去執(zhí)行一些關(guān)鍵且重要的無(wú)人任務(wù)，例如地面探測(cè)，監(jiān)視和搜救。在機(jī)器人執(zhí)行這些無(wú)人任務(wù)時(shí)，為機(jī)器人規(guī)劃出一條可行的安全路徑是機(jī)器人技術(shù)領(lǐng)域中一個(gè)重要的研究課題。機(jī)器人路徑規(guī)劃的目的是在一個(gè)相對(duì)復(fù)雜的工作環(huán)境中為機(jī)器人從起始位置到終點(diǎn)位置規(guī)劃出一條最優(yōu)或者次優(yōu)的避障路徑。由于其在不同領(lǐng)域的廣泛應(yīng)用，自20世紀(jì)60年代中期以來(lái)，路徑規(guī)劃問(wèn)題引起了廣大學(xué)者的研究興趣。

自路徑規(guī)劃這個(gè)問(wèn)題被提出開(kāi)始，已經(jīng)有許多路徑規(guī)劃方法。然而，在復(fù)雜環(huán)境下的路徑規(guī)劃問(wèn)題，是一個(gè)非確定性時(shí)間多項(xiàng)式困難(non-deterministic polynomial-time hard,NP-hard)問(wèn)題。該問(wèn)題的NP-hard特性給其求解帶來(lái)了巨大的挑戰(zhàn)。所以，為了有效地求解這類問(wèn)題，提出不同形式的高效能優(yōu)化算法是十分必要的。

由于進(jìn)化算法(Evolutionary Algorithms,EAS)基于種群的特性以及對(duì)復(fù)雜 NP-hard問(wèn)題良好的搜索能力，近年來(lái)，許多學(xué)者提出了不同的進(jìn)化算法例如遺傳算法(Genetic Algorithm,GA)，模擬退火法(Simulation Annealing Algorithm SAA) 和人工神經(jīng)網(wǎng)絡(luò)算法(Artificial Neural Network,ANN)等來(lái)求解路徑規(guī)劃問(wèn)題。

作為最強(qiáng)大的進(jìn)化算法之一，由于其簡(jiǎn)單性和快速收斂的特性，粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法已被廣泛應(yīng)用于解決路徑規(guī)劃問(wèn)題。然而，基本粒子群算法的性能有兩個(gè)典型的缺陷：第一個(gè)缺陷是不能很好地平衡粒子的全局和局部搜索能力，從而容易導(dǎo)致算法過(guò)早陷入局部最優(yōu)；此外，在一定迭代次數(shù)之后，當(dāng)粒子不能搜索到比歷史最優(yōu)位置更好的位置時(shí)，基本粒子群算法就會(huì)陷入迭代停滯。為了提高PSO的性能，需要對(duì)這兩個(gè)典型缺點(diǎn)進(jìn)行彌補(bǔ)或克服。

作為另外一個(gè)廣受歡迎的進(jìn)化算法，差分進(jìn)化(Differential Evolution,DE)算法由于其簡(jiǎn)單性，搜索可靠性以及易于實(shí)現(xiàn)等優(yōu)點(diǎn)，已經(jīng)被廣泛應(yīng)用于求解各種不同類型的優(yōu)化問(wèn)題。然而，對(duì)于不同的優(yōu)化問(wèn)題，DE算法的進(jìn)化策略和控制參數(shù)的設(shè)置不盡相同，這需要用戶根據(jù)自己的先驗(yàn)知識(shí)進(jìn)行設(shè)定。所以，DE算法的進(jìn)化策略和控制參數(shù)的設(shè)定是和具體問(wèn)題息息相關(guān)的，這給設(shè)計(jì)有效的DE 算法帶來(lái)了挑戰(zhàn)。

對(duì)移動(dòng)機(jī)器人進(jìn)行全局路徑規(guī)劃，采用基本粒子算法求解時(shí)，面臨以下兩個(gè)問(wèn)題：不能很好地平衡粒子的全局和局部搜索能力導(dǎo)致算法過(guò)早陷入局部最優(yōu)，不能達(dá)到全局最優(yōu)；在一定迭代次數(shù)之后就會(huì)陷入迭代停滯，從而影響粒子群算法在路徑規(guī)劃中的性能。

因?yàn)镻SO和DE都屬于處理群體演化計(jì)算的進(jìn)化算法，自然而然，可以考慮到將這兩種算法混合在一起，從而保證混合之后的算法可以借用兩個(gè)算法的優(yōu)點(diǎn)來(lái)提高算法的優(yōu)化性能。

參考文獻(xiàn)

[1][1]Zexuan Zhu,Fangxiao Wang,Shan He,and Yiwen Sun.Global Path Planning of Mobile Robots Using a Memetic Algorithm.International Journal of Systems Science,46(11):1982–1993,2015.

[2][2]Yong Zhang,Dun‐wei Gong,and Jian‐hua Zhang.Robot path planning in uncertain environment using multi‐objective particle swarm optimization.Neurocomputing,103:172–185,2013.

[3][3]N Geng,D W Gong,and Y Zhang.PSO‐Based Robot Path Planning for Multisurvivor Rescue in Limited Survival Time.Mathematical Problems in Engineering,2014(2014),2014.