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

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

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

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