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

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

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