基于分層搜索的移動(dòng)機(jī)器人路徑優(yōu)化
李勁松112，宋立博2，葛志飛3，徐兆紅3，顏國正1
1、上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240；2上海交通大學(xué)工程訓(xùn)練中心，上海200240，3上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，上海200240)
摘 要：分析比較了經(jīng)典的全局路徑規(guī)劃算法，針對(duì)移動(dòng)機(jī)器人運(yùn)動(dòng)路徑規(guī)劃的優(yōu)化問題，將a、人工勢(shì)場(chǎng)、柵格等多種算法的優(yōu)勢(shì)加以綜合考慮，提出一種基于柵格的分層搜索概念：該方法采用柵格法進(jìn)行建模，以分層搜索為核一心思想，外層采用a算法將復(fù)雜的圖元模糊化以簡(jiǎn)化環(huán)境，內(nèi)層則采用人工勢(shì)場(chǎng)算法將具體的柵格還原以解模糊，具有一定的理論意義與應(yīng)用前號(hào)。其仿真實(shí)驗(yàn)表明，該方法能達(dá)到較好的路徑規(guī)劃效率和實(shí)時(shí)性。
關(guān)鍵詞：移動(dòng)機(jī)器人；路徑規(guī)劃；分層搜索；全局優(yōu)化
中圖分類號(hào)：t，242 文獻(xiàn)標(biāo)識(shí)碼：a
1引 言
移動(dòng)機(jī)器人不僅在軍事上有特殊的應(yīng)用價(jià)值，而且在工業(yè)生產(chǎn)、交通運(yùn)輸?shù)确矫娑加袕V泛的應(yīng)用前景。路徑規(guī)劃是移動(dòng)機(jī)器人自動(dòng)化技術(shù)的重要組成部分，是機(jī)器人智能化的重要標(biāo)志。按照機(jī)器人對(duì)環(huán)境信息的知曉的程度，可以將路徑規(guī)劃分為局部路徑規(guī)劃和全局路徑規(guī)劃兩種。
局部路徑規(guī)劃是在環(huán)境信息未知或者部分已知的情況下進(jìn)行的路徑規(guī)劃，適用于動(dòng)態(tài)環(huán)境，但計(jì)算量較大。局部路徑規(guī)劃的算法包括遺傳算法、神經(jīng)網(wǎng)絡(luò)、模糊邏輯算法等。全局路徑規(guī)劃是在環(huán)境信息完全已知的情況下進(jìn)行的路徑規(guī)劃，適用于靜態(tài)環(huán)境，但計(jì)算效率較高。全局路徑規(guī)劃的算法包括可視圖法、人工勢(shì)場(chǎng)法和柵格法等。
本文主要針對(duì)全局路徑規(guī)劃，首先對(duì)已有的一些經(jīng)典算法進(jìn)行總結(jié)和分析，然后提出基于柵格的分層搜索算法，最后是實(shí)驗(yàn)仿真以及結(jié)論。
2全局路徑規(guī)劃算法分析
下面對(duì)移動(dòng)機(jī)器人全局路徑規(guī)劃的常用算法做簡(jiǎn)要綜述與分析。
1)人工勢(shì)場(chǎng)法人工勢(shì)場(chǎng)法首先由khatibi7:提出，其基本思想類同于物理學(xué)中場(chǎng)的概念。把移動(dòng)機(jī)器人的運(yùn)動(dòng)環(huán)境抽象成人工力場(chǎng)，障礙物對(duì)機(jī)器人產(chǎn)生斥力場(chǎng)，目標(biāo)點(diǎn)對(duì)機(jī)器人產(chǎn)生引力場(chǎng)。勢(shì)場(chǎng)下降的方向就是機(jī)器人的運(yùn)動(dòng)方向。隨著這個(gè)下降方向，機(jī)器人將有可能搜索到目標(biāo)點(diǎn)。人工勢(shì)場(chǎng)法的優(yōu)點(diǎn)如下：搜索到的路徑遠(yuǎn)離障礙物，路徑比較光滑，計(jì)算量小，但是缺點(diǎn)是完備性比較差，即有時(shí)候搜索不到路徑，比如當(dāng)障礙物非�？拷繕�(biāo)點(diǎn)的時(shí)候，有可能出現(xiàn)斥力大于引力的情況，此時(shí)機(jī)器人就無法到達(dá)目標(biāo)點(diǎn)，又例如當(dāng)場(chǎng)中存在局部最小點(diǎn)時(shí)，機(jī)器人將無法脫離。
2)柵格法根據(jù)圖形建模過程的不同，柵格搜索算法分為確切柵格搜索和不確切柵格搜索。
確切柵格搜索將機(jī)器人所處的運(yùn)動(dòng)環(huán)境分割成固定大小的柵格，然后將柵格分為障礙物柵格和自由柵格，分別表示有無障礙物，最后用bfs-9（廣度優(yōu)先搜索）、（深度優(yōu)先搜索）或者啟發(fā)式搜索在柵格圖上搜索從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的****路徑。該算法中，所選取的柵格大小將直接影響算法信息的存儲(chǔ)量和計(jì)算量，同時(shí)也影響著算法搜索到路徑的完備性。不確切柵格搜索與確切柵格搜索的****不同在于其柵格大小是可變的，而確切柵格搜素柵格的大小是不可變的。不確切柵格搜索算法在環(huán)境建模完成之后，同確切柵格搜索算法一樣，也利用bfs，dfs或者啟發(fā)式搜索技術(shù)，搜索****路徑。
a 算法一啟發(fā)式搜索算法，與bfs，dfs有著自然而緊密的聯(lián)系，其思想的本質(zhì)在于啟發(fā)，從而有效地避免了bfs，dfs方法在應(yīng)用過程中的盲目性。
柵格搜索算法構(gòu)造簡(jiǎn)單，在處理障礙物的邊界信息時(shí)避免了復(fù)雜的計(jì)算，而且易于存儲(chǔ)有行到結(jié)構(gòu)構(gòu)成的柵格圖，這些優(yōu)點(diǎn)都為本文的研究提供了基礎(chǔ)。
3基于柵格的分層搜索算法
在研究中發(fā)現(xiàn)，當(dāng)障礙物分布比較稀疏，而且當(dāng)環(huán)境中分布著一些體積比較小的障礙物時(shí)，不確切柵格搜索算法有一個(gè)比較嚴(yán)重的缺點(diǎn)，即由于這些障礙物的存在，使得柵格必須得不斷的分解，以此來完成圖的構(gòu)建，這樣就大大增加了計(jì)算的復(fù)雜度以及存儲(chǔ)量�；诖耍髡哒J(rèn)為可以采用分層搜索的方法來解決這個(gè)問題。具體來說，是將搜索過程分為兩層進(jìn)行：第一層，將零星分布的障礙物先加以忽略，視其為自由 |
