CGF并行路徑規(guī)劃方法研究.pdf

1、路徑規(guī)劃作為所有仿真實(shí)體物理行為的基礎(chǔ)，是仿真系統(tǒng)中最基本也是應(yīng)用最為頻繁的部分，路徑規(guī)劃算法高效與否對(duì)仿真系統(tǒng)的性能有著最直接的影響。目前，路徑規(guī)劃的實(shí)時(shí)性問(wèn)題已經(jīng)成為限制訓(xùn)練仿真發(fā)展的一個(gè)瓶頸，動(dòng)態(tài)環(huán)境下實(shí)時(shí)路徑規(guī)劃問(wèn)題也成為當(dāng)前人工智能以及仿真領(lǐng)域研究的一個(gè)熱點(diǎn)和難點(diǎn)。
　　同時(shí)，計(jì)算機(jī)多核化的發(fā)展趨勢(shì)使得并行技術(shù)在提高計(jì)算效率方面具有很大潛力，通過(guò)并行化以提高算法效率也逐漸成為算法改進(jìn)的一個(gè)主要方面。本文旨在結(jié)合當(dāng)前仿真系

2、統(tǒng)的實(shí)際需求，探索并行技術(shù)在路徑規(guī)劃中的應(yīng)用，最終在如何提高算法實(shí)時(shí)性方面進(jìn)行深入研究。
　　文章主要針對(duì)訓(xùn)練仿真中復(fù)雜環(huán)境下實(shí)時(shí)路徑規(guī)劃問(wèn)題，分別研究靜態(tài)大規(guī)模環(huán)境和動(dòng)態(tài)復(fù)雜環(huán)境下的并行路徑規(guī)劃問(wèn)題。具體內(nèi)容為：
　　針對(duì)靜態(tài)大范圍場(chǎng)景的特點(diǎn)，文章研究通過(guò)快速收斂的粒子群(Particle Swarm Optimazation, PSO)算法進(jìn)行路徑規(guī)劃。結(jié)合PSO易于并行化的特點(diǎn)，進(jìn)一步將并行技術(shù)與其結(jié)合，提出基于并行P

3、SO的實(shí)時(shí)路徑規(guī)劃算法。并行算法通過(guò)將粒子平均分配在多個(gè)核上進(jìn)行計(jì)算，極大地提高了路徑規(guī)劃的效率。最后，分析并行化算法的優(yōu)缺點(diǎn)，針對(duì)其不足提出分層并行的思想以提高算法可擴(kuò)展性。
　　對(duì)于動(dòng)態(tài)復(fù)雜場(chǎng)景，首先，文章研究對(duì)動(dòng)態(tài)環(huán)境具有較強(qiáng)適應(yīng)能力的四叉樹(shù)空間表示方法；然后，介紹一種基于四叉樹(shù)空間表示的路徑規(guī)劃算法——Quad*，對(duì)算法特點(diǎn)進(jìn)行分析；最后，提出雙邊并行Quad*(Parallel Bidirectional Quad*,