1、東南大學碩士學位論文移動機器人完全遍歷系統研究姓名:劉奎申請學位級別:碩士專業:機械電子工程指導教師:張赤斌20060306 3.2路徑規劃的分類路徑規劃的分類方式隨著標準的不同有很多分類方法。按移動目標主要有兩種路徑規劃,一種是傳統的點到點的路徑規劃,另一種就是完全遍歷路徑規劃。點到點的路徑規劃是一種從始點到終點的運動策略,它要求尋找一條從始點到終點的最優(如代價最小、路徑最短、時間最少并且合理的路徑,使移動機器人能夠在工作空間順利地通行而不碰到任何障礙物。完全遍歷路徑規劃是一種在二維工作空間中特殊的路徑規劃,指在滿足某種性能指標最優或準優的前提下,尋找一條在設定區域內從始點到終點且經過所有

2、可達點的連續路徑。圖3-1(a為傳統的點到點的路徑規劃,此路徑是一條從起點sN終點G的最短的避碰的路徑。(b為完全遍歷路徑規劃,此路徑是一條遍歷環境空間中所有可達點的路徑。 (a點到點路徑規劃(b完全遍歷路徑規劃圖31傳統路徑規劃和完全遍歷路徑規劃比較根據對環境信息掌握的程度和空間描述形式將機器人路徑規劃分成三類:基于環境先驗完全信息的全局路徑規劃、基于傳感器信息的局部路徑規劃和混合型方法。全局規劃方法依照己獲取的環境信息,給機器人規劃出一條運動路徑。全局路徑的精確度取決于獲取環境信息的準確程度。全局方法通常以尋找最優解,但需要預先知道環境準確的信息,并且計算量通常很大。局部規劃方法側重考慮機

3、器人當前局部環境信息,通過多種傳感器獲取位置或部分未知的環境信息,即障礙物的尺寸、形狀和位置等信息,使機器人具有良好的避碰能力。和全局規劃方法相比,更具實時性和實用性。缺陷是僅依靠局部信息,有時會產生局部極點,無法保證機器人能順利地到達目標點。混合型方法結合全局和局部方法的優點,將全局規劃的“粗”路徑作為局部規劃的子目標,特別在復雜環境中此方法經常被使用。總的來說,全局路徑規劃基于環境模型,環境的全部信息已知;局部路徑規劃基于傳感器的信息,環境信息全部未知或部分未知。局部路徑規劃和全局路徑規劃并沒有本質區別。前者只是把全局路徑規劃的環境考慮得更復雜一些,即環境是動態的。很多適用于全局路徑規劃的

4、方法經過改進都可以用于局部路徑規劃;而適用于局部路徑規劃的方法都可以適用于全局路徑規劃。3.3幾種典型路徑規劃移動機器人路徑規劃研究起始于20世紀70年代,目前對這一問題的研究仍十分活躍,許多學者做了大量的工作,提出了許多成熟的路徑規劃算法。根據空間描述形式的不同,從全局路徑規劃和局部路徑規劃來劃分國內外路徑規劃方法較為清晰。全局的路徑規劃有基于構型空間的幾何法和基于狀態空間的拓撲法,前者主要有單元分解法(柵格法、可視圖法、 在完全遍歷過程中,常常遇到“死基點”情況,首先,通過環境電子地圖找到最近的未遍歷區域。通過尋找具體方法是:首先,查找遍歷矩陣搜索未遍歷矩形區域;接著,計算當前區域到所有未

5、遍歷區域的距離(空間距離,找到晟近的未遍歷區域,作為下一目標區域:最后,利用反向梯度法找到最近未遍歷區域的路徑。如圖310所示,從基點1區域開始遍歷,依次遍歷了基點2、4、5、6、7、8、9基點所在矩形區域。遍歷完基點9所在的區域后,用搜索規則找下一目標基點時發現基點9為“死基點”;接著,就在未遍歷區域(基點12、13所在區域中尋找最近的未遍歷區域,經過計算,基點12距離基點9最近,即基點12就是下一目標基點。于是,就用反向梯度法求得基點9N基點12的最短路徑(基點9一基點8(10一基點7(11一基點12。 0bstaclt鬻56蕊謠8甲10塞9黧j456怒2345.,。,8l23./5678

6、_/,一3蕊邋89100】船麟34鶼憋黲9100bstacle圖39反向梯度法求最短路徑圖3-10完全遍歷中的反向梯度法全局路徑規劃完成所有基點的遍歷,而局部路徑規劃要完成某基點所在區域的局部遍歷。在全局路徑規劃層每搜索到一未遍歷基點,就要完成該矩形區域的局部遍歷。全局路徑規劃和局部路徑規劃交錯進行,最終實現環境完全遍歷。在局部路徑規劃中,移動機器人完成局部區域遍歷運動。這個過程分為三個部分:尋找局部區域遍歷起始點,局部區域遍歷和回到局部區域基點。(1局部遍歷模式在全局路徑規劃中,采用單元分解法的思想,在單元間建立交錯網路。在交錯網絡上實現對基點的遍歷。在局部層要完成對局部矩形區域的遍歷,由于

7、局部區域是連通的,很容易使用模板法實現遍歷。算法規定局部遍歷路徑規劃三種基本遍歷運動模式(如圖311:螺旋式,弓形式(橫和弓形式(豎。遍歷運動模式由環境的形狀決定,而環境的形狀通過環境學習得到。前種模式針對矩形區域中沒有障礙物的情況,后兩種模式適應于矩形區域中存在障礙物的情況。弓形式(橫和弓形式(豎其實是同一種遍歷模式,只是遍歷直線行走的方向不同,前者是橫著行走,后者是豎著行走。這三種基本的遍歷模式由5個基本模板組成,如圖312所示,算法中定義了5種基本模板:(a前進模板,(b右轉模板,(c左轉模板,(d后退右轉模板,(e后退左轉模板。 東南大學碩士學位論文 圖3-20完全遍歷路徑規劃經過大量

8、地圖的仿真表明,該遍歷算法的覆蓋率達到9096以上,有的甚至達到95%以上,而且重復率在lO%以下。對于不同的地圖覆蓋率和重復率是不同的,不過對大多數地圖而言,該算法是高效的、實用的,具有很強的適應性。由于算法只關注基點的信息,而基點是有限的,這樣就大大減少了計算量。而完全遍歷過程是機器人自主完成的,具有很高的智能。遍歷過程中很少有遺漏區域,在障礙物附近區域仍有重復的情況,這是無法避免的。但這比以往的遍歷算法有了大大的改善。對于特別復雜的環境該算法在局部區域的遍歷算法有待進一步改進,同時如何更合理的進行矩形化建模將是下一步要研究的課題。該完全遍歷算法特點是系統要處理的信息量很少,機器人實時性控制更強。特別是提出了基點這一重要概念,使得在未知環境中實現完全遍歷更有效、更方便。3.8本章小結路徑規劃是移動機器人導航中最重要的任務之一。本章從路徑規劃研究內容、分類方法入手,分別討論了幾種常見的路徑規劃方法,如人工勢場法,模糊邏輯法,遺傳算法,神經網絡法等。相對于點對點的路徑規劃方法,完全遍歷路徑規劃是一個全