基于碰撞的三維場景尋徑算法研究.pdf

1、尋徑算法一直是人工智能的一個活躍方向。傳統(tǒng)的路徑搜索系統(tǒng)使用啟發(fā)式搜索算法對場景空間進(jìn)行搜索。現(xiàn)階段國內(nèi)外的相關(guān)研究集中在算法的優(yōu)化和搜索空間的簡化上。
　　 本文對傳統(tǒng)的尋徑算法進(jìn)行了探討，實(shí)現(xiàn)了一套三維場景下的路徑搜索系統(tǒng)。在分析和比較各種搜索算法的基礎(chǔ)上，特別是啟發(fā)式搜索，搜索空間的優(yōu)化以及二維環(huán)境下的基于碰撞的尋徑算法后，將二維場景下的基于碰撞的尋徑算法拓展與應(yīng)用到了三維場景中，給出了三維場景下基于碰撞的地圖尋徑新算法。

2、在行走過程中遇到障礙物時，將行走分成繞開物體與在物體表面上滑行兩種處理方式；同時在繞行方向上采用了一種新繞行算法；另外根據(jù)系統(tǒng)地圖的特點(diǎn)，將地表在拐點(diǎn)處分成一段一段，進(jìn)行分段尋徑。在分段過程中，給出了一種近似拐點(diǎn)算法。
　　 本文以上述理論為指導(dǎo)，進(jìn)行了系統(tǒng)的開發(fā)與實(shí)現(xiàn)。在實(shí)際的運(yùn)用中，實(shí)時性和擴(kuò)展性均比較好。現(xiàn)階段的尋徑系統(tǒng)仍然存在著不足。如在尋徑過程中遇到比較狹長的障礙物時，可能會發(fā)生幀速率的下降，這與頻繁的碰撞檢測相關(guān)。這