路徑規(guī)劃作為所有仿真實(shí)體物理行為的基礎(chǔ),是仿真系統(tǒng)中最基本也是應(yīng)用最為頻繁的部分,路徑規(guī)劃算法高效與否對仿真系統(tǒng)的性能有著最直接的影響。目前,路徑規(guī)劃的實(shí)時(shí)性問題已經(jīng)成為限制訓(xùn)練仿真發(fā)展的一個(gè)瓶頸,動(dòng)態(tài)環(huán)境下實(shí)時(shí)路徑規(guī)劃問題也成為當(dāng)前人工智能以及仿真領(lǐng)域研究的一個(gè)熱點(diǎn)和難點(diǎn)。同時(shí),計(jì)算機(jī)多核化的發(fā)展趨勢使得并行技術(shù)在提高計(jì)算效率方面具有很大潛力,通過并行化以提高算法效率也逐漸成為算法改進(jìn)的一個(gè)主要方面。本文旨在結(jié)合當(dāng)前仿真系統(tǒng)的實(shí)際需求,探索并行技術(shù)在路徑規(guī)劃中的應(yīng)用,最終在如何提高算法實(shí)時(shí)性方面進(jìn)行深入研究。文章主要針對訓(xùn)練仿真中復(fù)雜環(huán)境下實(shí)時(shí)路徑規(guī)劃問題,分別研究靜態(tài)大規(guī)模環(huán)境和動(dòng)態(tài)復(fù)雜環(huán)境下的并行路徑規(guī)劃問題。具體內(nèi)容為:針對靜態(tài)大范圍場景的特點(diǎn),文章研究通過快速收斂的粒子群（Particle Swarm Optimazation,PSO）算法進(jìn)行路徑規(guī)劃。結(jié)合PSO易于并行化的特點(diǎn),進(jìn)一步將并行技術(shù)與其結(jié)合,提出基于并行PSO的實(shí)時(shí)路徑規(guī)劃算法。并行算法通過將粒子平均分配在多個(gè)核上進(jìn)行計(jì)算,極大地提高了路徑規(guī)劃的效率。最后,分析并行化算法的優(yōu)缺點(diǎn),針對其不足提出分層并行的思想以... 

【文章來源】：國防科技大學(xué)湖南省 211工程院校 985工程院校

【文章頁數(shù)】：74 頁

【學(xué)位級別】：碩士

【部分圖文】：

坐標(biāo)轉(zhuǎn)換后的地圖空間步驟二：確定搜索空間

來的路徑隨著迭代次數(shù)的增加會(huì)越來越優(yōu)，但是對于路徑規(guī)劃問題，由于粒子的維數(shù)有限，一般不可能完全表達(dá)出地圖空間中所有可能的路徑，這就導(dǎo)致粒子的搜索空間不能完全覆蓋地圖空間，其找出來的路徑一般都是次優(yōu)解。如圖3.5所示，若S至G的最優(yōu)路徑在ln和ln+1段之間為折線 →CDE，而粒子的第n維和第n + 1 維只能表達(dá)圖中 →AB類的直線，所以其永遠(yuǎn)不可能搜索出最優(yōu)路徑。3.3.2 改進(jìn)方案路徑優(yōu)化第23頁

障礙物的話，即可直接將粒子第n維位置點(diǎn)刪去。圖3.6為優(yōu)化前后路徑對比，其中，虛線路徑為優(yōu)化前的路徑，實(shí)線路徑為優(yōu)化路徑。圖3.6路徑優(yōu)化對比圖分層并行并行PSO因?yàn)楦髁Ｗ娱g每個(gè)迭代周期只需在更新種群歷史最優(yōu)解時(shí)同步一次，所以可以獲得很好的加速比。但實(shí)驗(yàn)表明，當(dāng)處理器數(shù)目增多時(shí)，每個(gè)周期一次的同步使得加速比很難線性增加，甚至當(dāng)處理器數(shù)目增至一定程度時(shí)，加速比反而會(huì)有所下降。為取得良好的加速比，必須減少各粒子之間的同步頻率，我們將粒子每個(gè)迭代周期都進(jìn)行一次種群歷史最優(yōu)解的同步改為每隔一定周期進(jìn)行一次同步。這就類似于每個(gè)處理器上是一個(gè)獨(dú)立搜索的小種群，首先在小種群內(nèi)進(jìn)行搜索，一定周期后，所有小種群進(jìn)行同步，更新整個(gè)大種群的歷史最優(yōu)。這種分層并行的搜索方法可以極大地較少粒子間同步的次數(shù)


本文編號：3350792