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

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

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

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