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

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

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

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