基于限定Delaunay三角剖分的移動(dòng)機(jī)器人路徑規(guī)劃.pdf

1、本文對(duì)移動(dòng)機(jī)器人路徑規(guī)劃算法的研究狀況進(jìn)行了歸納總結(jié),指出了各算法的性能差異和優(yōu)缺點(diǎn)。全面闡述了路徑規(guī)劃中常用的啟發(fā)式搜索算法,重點(diǎn)介紹了A*、D*、D*Lite和LRTA*這四種基本的啟發(fā)式搜索算法。設(shè)計(jì)了啟發(fā)式搜索算法仿真平臺(tái),并在此平臺(tái)下對(duì)以上四種算法進(jìn)行了分析,評(píng)價(jià)其搜索思想,比較其優(yōu)缺點(diǎn)。 接著,本文闡述了基于限定Delaunay三角剖分的移動(dòng)機(jī)器人路徑規(guī)劃算法。該算法首先用限定Delaunay三角剖分把環(huán)境三角化,然

2、后將A*和D*Lite路徑搜索算法擴(kuò)展到了三角形環(huán)境中,分別用于靜態(tài)和動(dòng)態(tài)環(huán)境中搜索路徑。為了克服三角形形狀不規(guī)則所造成的非最優(yōu)路徑,充分考慮到了相鄰三角形的幾何位置關(guān)系和機(jī)器人當(dāng)前位置和目標(biāo)點(diǎn)的幾何位置關(guān)系,設(shè)計(jì)了搜索節(jié)點(diǎn)構(gòu)造規(guī)則,該方法能夠保證搜索到一條最優(yōu)或近似最優(yōu)的無(wú)碰撞路徑。本文還提出了一種動(dòng)態(tài)三角剖分方法,該方法能夠滿足動(dòng)態(tài)搜索算法的需要,保證大部分搜索節(jié)點(diǎn)可以重新利用,而且還可以快速重新剖分環(huán)境。與傳統(tǒng)的柵格法相比,本文所

3、述的算法屬于精確單元分解法,能夠完全表達(dá)外界環(huán)境,環(huán)境包含的搜索節(jié)點(diǎn)數(shù)要少,需要更少的存儲(chǔ)數(shù)據(jù)空間。而且本文所述算法找到的是一條從起點(diǎn)到目標(biāo)點(diǎn)的“通道”,便于應(yīng)用運(yùn)動(dòng)控制算法。理論分析證明了本算法的正確性和完整性,仿真實(shí)驗(yàn)表明了本算法的有效性和最優(yōu)性。 最后,本文將離散的三角形環(huán)境空間當(dāng)作離散系統(tǒng),機(jī)器人的速度的連續(xù)變化當(dāng)作連續(xù)系統(tǒng),構(gòu)造一個(gè)統(tǒng)一框架,即混雜系統(tǒng)。路徑規(guī)劃算法用于在三角化的環(huán)境中找到一個(gè)最優(yōu)的三角形序列,運(yùn)動(dòng)控制