基于柵格法多目標路徑規(guī)劃研究.pdf

1、路徑規(guī)劃問題是指存在障礙物的環(huán)境中，按照一定的評價標準，如：安全性、能耗、路經(jīng)長度等，求出一條從起始點至目標點的無碰撞路徑。路徑規(guī)劃問題的應用十分廣泛，主要在VLSI設計、機器人路徑規(guī)劃和地理信息系統(tǒng)等領域。其主要內(nèi)容同時也涉及到多個學科，如環(huán)境表達、規(guī)劃方法、路徑搜索等等。
　　本文主要的研究目標是在 A*算法的基礎上進行改進，設計出一個高效的尋找路徑的算法，將其運用至一個動態(tài)的虛擬環(huán)境，使得多個虛擬角色在并行運動中，達到無碰撞

2、，無沖突，且使得它們的路徑長度盡量小、線路折線和轉(zhuǎn)折角度盡量小。
　　A*是一種啟發(fā)式搜索算法，被廣泛應用于路徑搜索和圖的遍歷，它也有一些缺陷和不足。首先，它的好壞與啟發(fā)函數(shù)的選擇有關，啟發(fā)函數(shù)是基于經(jīng)驗的，受到的主觀影響很大；其次，在A*算法中會頻繁的訪問兩個狀態(tài)表，設計一個合適的數(shù)據(jù)結構提高訪問狀態(tài)表的效率也是很重要的；最后算法求出的路徑是一段段折線，轉(zhuǎn)折角度大，不夠真實。
　　針對A*算法存在的缺陷對A*算法提出了一些