基于BFS算法的三維動態(tài)環(huán)境下機(jī)器人路徑規(guī)劃.pdf

1、移動機(jī)器人路徑規(guī)劃屬于機(jī)器人控制系統(tǒng)的重要應(yīng)用基礎(chǔ)問題，也是機(jī)器人研究領(lǐng)域一個關(guān)鍵的研究課題。機(jī)器人路徑規(guī)劃是指在有障礙物的空間中找到一條最短或者低代價的無碰撞路徑。動態(tài)環(huán)境即時變環(huán)境，指障礙物和目標(biāo)點的位置隨時間變化而變化。
　　 本文針對三維動態(tài)環(huán)境下，機(jī)器人路徑規(guī)劃的魯棒性問題，提出了一個基于寬度優(yōu)先搜索(BFS，Breadth-First Search)算法的路徑規(guī)劃。該算法通過對角線原則和前向鏈確定先行值，先行值是指從

2、起始點到目標(biāo)點的合適的時間步長。然后推算障礙物和目標(biāo)點到先行值時的位置，并計算空間中所有位置在所有時刻的位勢值。機(jī)器人從起點出發(fā)，沿著位勢值降低的方向朝目標(biāo)點行進(jìn)，安全到達(dá)目標(biāo)點。本文主要進(jìn)行了以下幾項工作：
　　 一、建立機(jī)器人三維工作環(huán)境模型。該環(huán)境模型是一種數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)反映的是機(jī)器人在某個位置隨機(jī)行進(jìn)一步與障礙物發(fā)生碰撞的可能性大小。
　　 二、給出機(jī)器人路徑規(guī)劃數(shù)學(xué)支持，本文提出的算法基于人工勢場法和調(diào)和函數(shù)

3、。并根據(jù)對角線原則和前向鏈確定先行值LA(Lookahead value)。對角線原則是指將四個起始點位于三維空間的底面，四個目標(biāo)點位于三維空間的頂面，在同樣環(huán)境大小和同樣障礙物密度下相距最遠(yuǎn)，則從起始點行進(jìn)到目標(biāo)點的時間步長相對最大。前向鏈的提出基于寬度優(yōu)先搜索(BFS)。BFS根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的結(jié)點。如果目標(biāo)結(jié)點存在于解答樹的有限層上，寬度優(yōu)先搜索算法一定能保證找到一條通向它的最佳路徑。