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