移動機器人完全遍歷系統(tǒng)研究_圖文

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

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

3、器人當前局部環(huán)境信息,通過多種傳感器獲取位置或部分未知的環(huán)境信息,即障礙物的尺寸、形狀和位置等信息,使機器人具有良好的避碰能力。和全局規(guī)劃方法相比,更具實時性和實用性。缺陷是僅依靠局部信息,有時會產生局部極點,無法保證機器人能順利地到達目標點?；旌闲头椒ńY合全局和局部方法的優(yōu)點,將全局規(guī)劃的“粗”路徑作為局部規(guī)劃的子目標,特別在復雜環(huán)境中此方法經常被使用?？偟膩碚f,全局路徑規(guī)劃基于環(huán)境模型,環(huán)境的全部信息已知;局部路徑規(guī)劃基于傳感器的信息,環(huán)境信息全部未知或部分未知。局部路徑規(guī)劃和全局路徑規(guī)劃并沒有本質區(qū)別。前者只是把全局路徑規(guī)劃的環(huán)境考慮得更復雜一些,即環(huán)境是動態(tài)的。很多適用于全局路徑規(guī)劃的

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

5、遍歷區(qū)域的距離(空間距離,找到晟近的未遍歷區(qū)域,作為下一目標區(qū)域:最后,利用反向梯度法找到最近未遍歷區(qū)域的路徑。如圖310所示,從基點1區(qū)域開始遍歷,依次遍歷了基點2、4、5、6、7、8、9基點所在矩形區(qū)域。遍歷完基點9所在的區(qū)域后,用搜索規(guī)則找下一目標基點時發(fā)現(xiàn)基點9為“死基點”;接著,就在未遍歷區(qū)域(基點12、13所在區(qū)域中尋找最近的未遍歷區(qū)域,經過計算,基點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完全遍歷中的反向梯度法全局路徑規(guī)劃完成所有基點的遍歷,而局部路徑規(guī)劃要完成某基點所在區(qū)域的局部遍歷。在全局路徑規(guī)劃層每搜索到一未遍歷基點,就要完成該矩形區(qū)域的局部遍歷。全局路徑規(guī)劃和局部路徑規(guī)劃交錯進行,最終實現(xiàn)環(huán)境完全遍歷。在局部路徑規(guī)劃中,移動機器人完成局部區(qū)域遍歷運動。這個過程分為三個部分:尋找局部區(qū)域遍歷起始點,局部區(qū)域遍歷和回到局部區(qū)域基點。(1局部遍歷模式在全局路徑規(guī)劃中,采用單元分解法的思想,在單元間建立交錯網路。在交錯網絡上實現(xiàn)對基點的遍歷。在局部層要完成對局部矩形區(qū)域的遍歷,由于

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

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