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