開題報告 路徑規(guī)劃

1、四 川 農(nóng) 業(yè) 大 學學士學位論文開題報告論文題目 移動機器人路徑規(guī)劃的智能算法研究 學 號： 姓 名： 杜 春 龍 指導教師： 陳 松 柏 學科專業(yè)： 農(nóng)業(yè)電氣化與自動化 所在學院： 信息與工程技術學院 2011 年 4 月 10 日填 四川農(nóng)業(yè)大學本科生畢業(yè)論文（設計）開題報告畢業(yè)論文（設計）題目移動機器人路徑規(guī)劃的智能算法研究選題類型應用型課題來源自選題目學 院信息與工程技術學院專 業(yè)農(nóng)業(yè)電氣化與自動化指導教師陳松柏職 稱高級實驗師姓 名杜春龍年 級2008-1學 號一、本課題的研究意義，現(xiàn)狀、水平和發(fā)展趨勢1.1 項目的現(xiàn)狀與背景1.1國內外現(xiàn)狀1.1.1 國外機器人發(fā)展狀況隨著社會的

2、進步和科學技術的日新月異，人們越來越希望能夠創(chuàng)造出一種幫助自身完成各種功能的機器包括一些存在巨大安全隱患的作業(yè)。早在20世紀60年代，世界各國就開始了機器人的研究。從第一臺機器人誕生至今，機器人技術取得了非凡的發(fā)展，現(xiàn)已發(fā)展成為一門集機械、電子、計算機、控制、傳感器、信號處理等多學科門類為一體的綜合性尖端科學。1.1.2 國內機器人的發(fā)展狀況在智能機器人方面，我國也做了不少研究。同國外的研究相比，我國在智能機器人方面的研究起步較晚，但發(fā)展較為迅速。國家“863智能機器人專家組將智能機器人的研究作為今后發(fā)展的重點。在最近的十年里，我國已經(jīng)陸續(xù)研制出一些機器人。這些機器人都較為成功的利用了多傳感器

3、信息融合技術和路徑規(guī)劃。這些機器人都具備一定的自主能力。同時，在核工業(yè)機器人、排險機器人水下機器人、室外移動機器人、爬壁機器人等方面，我國也取得了一定的研究成果。1.2機器人的發(fā)展趨勢機器人作為科技進步的產(chǎn)物，有如下優(yōu)點： 可以代替人們進行高危作業(yè)。 可以代替人們進行簡單、枯燥的工作。 可以不斷重復相同的工作而不知疲倦。正是因為它有這些優(yōu)點，故而它在國民生產(chǎn)、醫(yī)療保健，特別是工業(yè)方面有廣泛的應用。目前機器人的發(fā)展趨勢有如下幾個方向： 工業(yè)機器人的性能不斷提高而價格卻在不斷降低； 工業(yè)機器人的控制系統(tǒng)逐步向基于PC機的開發(fā)型控制發(fā)展，其成本低，具有標準網(wǎng)絡功能，同時系統(tǒng)可靠性、易操作性、可維修性

4、得到了大幅度的提高。 機器人不斷向人機交互控制方向發(fā)展。 機器人不斷向實用化方向發(fā)展。1.3 研究的意義雖然我國已經(jīng)在機器人方面已經(jīng)有了不少成果，但是相對于國外來說，還是有一定的差距。在機器人的路徑規(guī)劃方面，還有許多問題亟需解決。在已有的路徑規(guī)劃方案中，仍有一些地方需要改進，主要有以下幾個方面： 算法的求解精度較差，算法的時空開銷都較大。 算法的靈活性有待進一步提高。 算法的穩(wěn)定性不是很理想。部分算法存在局部最優(yōu)的問題。 算法的收斂性不能滿足實時性的要求。在充分考慮了以上問題的情況下，本課題采用遺傳算法實現(xiàn)機器人的路徑規(guī)劃。設計的遺傳算法除能解決以上問題外還具有如下優(yōu)點： 克服了人工勢場法中的

5、局部極小值問題，對于各種問題的尋優(yōu)具有很好的適應性，魯棒性較強。 通過設計合理的適應度函數(shù)體現(xiàn)不同的標準。具有很好的靈活性。 通過引入一定的選擇機制，加快其收斂速度。同時由于其在宏觀上具有一定的方向性，所以它較以往的隨機搜索算法搜索效率較高。二、研究方案2.1設計的主要內容 本課題主要研究內容是利用智能算法實現(xiàn)移動機器的路徑規(guī)劃。根據(jù)環(huán)境信息是否已知，又可以分為環(huán)境已知的全局路徑規(guī)劃和環(huán)境未知的局部路徑規(guī)劃。其中全局路徑規(guī)劃無法解決動態(tài)避障和復雜多變的環(huán)境問題。而局部路徑規(guī)劃，由于沒有完整的環(huán)境信息，無法達到全局的最優(yōu)，只能達到某種程度上的次優(yōu)。本課題在充分結合兩者的優(yōu)點的情況下，實現(xiàn)機器人的

6、路徑規(guī)劃。2.2預期達到的目標2.2.1 機器人能夠判斷出所遇到的障礙物的位置并能自動進行避障處理。2.2.2 機器人能夠自動尋找出一條從出發(fā)點到目標的路徑。2.2.3 尋找出的路徑應盡可能平滑。2.2.4 尋找出的路徑應盡可能短。2.3研究中存在的難點2.3.1 環(huán)境的建模2.3.2 算法的設計及仿真。2.3.3 軟件與硬件的結合。2.4 路徑規(guī)劃總體設計 課題采用兩重遺傳算法實現(xiàn)路徑規(guī)劃。第一重遺傳算法主要實現(xiàn)存在靜態(tài)障礙物時的路徑規(guī)劃；第二重循環(huán)主要實現(xiàn)存在動態(tài)障礙物時的路徑規(guī)劃，主要結構如圖1所示。 圖1 路徑規(guī)劃總體設計2.4遺傳算法原理及特點2.4.1 遺傳算法的原理遺傳算法是根據(jù)

7、達爾文的進化論，模擬自然選擇的一種智能算法，“適者生存”是它的核心機制。遺傳算法是從代表問題可能潛在解集的一個種群開始的。在隨機產(chǎn)生初代種群之后，按照適者生存、優(yōu)勝劣汰的原理，逐代進化產(chǎn)生出越來越好的近似種群。在每一代中，根據(jù)問題域中個體適應度大小來挑選個體，再將挑選出來的個體，用自然遺傳學的遺傳算子進行組合交叉和變異，產(chǎn)生出代表解的解集的種群。通過這些步驟，后生代種群比前代對于環(huán)境具有更好的適應性。末代種群中的最優(yōu)個體經(jīng)過解碼可以作為問題近似最優(yōu)解。遺傳算法的主要流程圖如圖2所示： 圖2 遺傳算法的流程圖2.4.2 遺傳算法的特點 作為一種智能算法，遺傳算法具有如下特點：遺傳算法在尋優(yōu)過程中

8、，只把適應度函數(shù)的值作為尋優(yōu)判據(jù)。遺傳算法是由一個問題集合（種群）開始的，而不是從一個個體開始的。故而遺傳算法的搜索面很積大，適合全局尋優(yōu)。遺傳算法根據(jù)概率性的變換規(guī)則進行個體的優(yōu)勝劣汰和并推動種群的進化。遺傳算法具有隱含的并行性。遺傳算法具有自組織、自適應以及內在的學習性，同時遺傳算法具有很強的容錯能力。遺傳算法的基本思想簡單。對于復雜的和非線性的問題具有良好的適應性。2.4.3 遺傳算法在路徑規(guī)劃中的應用思路本課題采用遺傳算法實現(xiàn)機器人的路徑規(guī)劃。在進行路徑規(guī)劃前，可對環(huán)境做如下假設，以方便以后的路徑規(guī)劃研究。 將機器人所要運動的環(huán)境設想為一個二維空間。同時將機器人視為一個質點。 對于環(huán)境

9、中的靜態(tài)的障礙物，可以作為已知信息對待；對于環(huán)境中的運動著的障礙物，可以根據(jù)檢測得知其位置。 將障礙物的邊緣進行適當?shù)倪吘壔幚?，同時根據(jù)機器人的尺寸進行適當放大。由于在本設計中是將遺傳算法用在尋找路徑上。所以，種群就表示為機器人在工作空間的多條路徑，個體就是具體的某一條路徑，路徑上的具體某一點就是基因。在本設計中，主要是為了根據(jù)遺傳算法找出一條從初始點到目標點的最優(yōu)路徑。在設計的過程中要保證這條路徑具有很好的可行性，即不再障礙物空間中；同時，這條路徑應盡可能的平滑；再者，這條路徑應該力求最短。因此，在使種群適應度函數(shù)滿足這些條件下，使種群朝著越來越優(yōu)的方向發(fā)展，最終找出滿足這些條件的路徑。2

10、.4.4 環(huán)境建模好的環(huán)境建模，不但可以使問題簡化，同時使數(shù)學方法運用于問題的解決中。目前的路徑規(guī)劃方法有: 柵格法、四叉樹法和多邊形法。其中柵格法存在表示效率不高、時空開銷和求解精度存在矛盾等特點。四叉樹法在計算鄰接關系時，時間代價較大等缺點。同時，多邊形法占用空間資源少等優(yōu)點，故而在本設計中采用多邊形法進行環(huán)境建模。運用多邊形法進行環(huán)境建模，主要是用多邊形去逼近障礙物。如圖3所示,，黑色多邊形表示障礙物。在多邊形法中，把機器人看成是一個質點，同時，將障礙物各頂點與目標點已經(jīng)機器人質點兩兩相連，要求這些線段都不能穿越障礙物。該方法只需存儲障礙物的各頂點的信息，股信息量較少。三、設計方案3.1

11、 遺傳算法的設計3.11 個體編碼在遺傳算法實現(xiàn)路徑規(guī)劃中，基因為每條路徑上的路徑點，而這一個一個的路徑點在二維空間中可以用坐標表示。所以在遺傳算法中可以用浮點編碼較為合適，且每個編碼包含橫坐標和縱坐標兩個部分。用浮點編碼的精度較高，更符合路徑規(guī)劃的要求。3.1.2 初始化種群 在初始化種群時，種群太小會，將不能包含整個區(qū)域的信息，種群太大，又會時使算法的收斂速度不理想。所以在隨機產(chǎn)生初始化種群時，引入選擇機制，使初始化種群隨機的包含搜索空間的每個區(qū)域。3.1.3 適應度函數(shù) 在用遺傳算法實現(xiàn)路徑規(guī)劃中，適應度函數(shù)主要表現(xiàn)為路徑的長度、平滑度以及接近障礙物的程度。其中路徑根據(jù)路徑是否經(jīng)過障礙物

12、，又可分為可行路徑和不可行路徑，可行路徑的適應度函數(shù)的條件表現(xiàn)為路徑的長度、障礙物的程度、路徑的平滑度等參數(shù)。為了使可行路徑由于不可行路徑，所以不可行路徑在可行路徑適應度函數(shù)的基礎上加上路徑與障礙物的交叉點數(shù)。在滿足適應度函數(shù)的情況下，使種群沿著最優(yōu)的方向進化，最終得到符合條件的路徑。3.1.4 遺傳操作算子 遺傳算子主要包含選擇、交叉、變異。它們是模仿自然選擇以及遺傳變異的載體。是遺傳算法的核心。3.1.5 控制參數(shù)遺傳算法的參數(shù)由種群的規(guī)模、交叉的概率、變異的概率、最大進化的代數(shù)等構成，這參數(shù)的選擇直接影響遺傳算法的性能。因此，在初始化種群階段以及群體進化階段，都要合理的進行選擇和控制這些

13、參數(shù)，以便遺傳算法能以較快的收斂性和較高的搜索效率找出一條滿足要求的路徑。 3.2 方案分析3.2.1方案可行性分析3.2.1.1 項目實現(xiàn)的理論知識保障本設計涉及的知識有：人工智能技術、傳感器技術，機器人技術，控制技術、電子技術等。由實現(xiàn)所涉及知識來看，本設計都緊緊與我們的學科知識相連，但是又不僅僅限于我們學科以內。在往后的學習中，我將進行有針對的學習。3.1.2 項目的技術保障本設計主要實現(xiàn)用智能算法實現(xiàn)機器人的路徑規(guī)劃。本設計涉及到多傳感器融合技術、計算機技術、自主避障技術。就目前而言，利用超聲波定位這項技術已經(jīng)較為成熟，遺傳算法在路徑規(guī)劃方面也有部分學者進行了研究，也都取得了一定的成果

14、，因此這些方面是有經(jīng)驗可以借鑒的。同時現(xiàn)有的傳感器技術也已非常的成熟，這就為設計的實現(xiàn)提供了有力的保障。3.2項目方案與現(xiàn)有解決方案比較分析目前路徑規(guī)劃中常用的方法有人工勢場法、柵格法、模板模型法、人工智能法。3.2.1人工智能法人工勢場法主要是通過將機器人所處環(huán)境設計為一種勢場。在人工勢場法中，把不希望機器人進入的區(qū)域或者是障礙物設計成斥力極，把清潔區(qū)域或者系統(tǒng)建議的區(qū)域設計成引力極。在極的周圍產(chǎn)生相應的勢，在任何一點的勢等于該點產(chǎn)生的勢之和。對于局部最優(yōu)點的問題，此算法容易產(chǎn)生死鎖現(xiàn)象，因而運用此方法可能會使機器人在到達目的地之前就停留在局部最優(yōu)點，不過由于它算法簡單，在實時避障和平滑的軌

15、跡控制方面，仍然有廣泛的應用。3.2.2柵格法柵格法主要是將機器人的路徑用一系列方形區(qū)域表示，同時把機器人視為一個點，將運動過程中所遇到的障礙物的邊界做相應的擴展和模糊化處理。通過使用柵格法，把機器人的工作空間劃分為一個個大小相同的柵格，用柵格數(shù)組表示當前所處環(huán)境。此方法的缺點主要表現(xiàn)在效率不高、存在時空開銷和精度之間的矛盾，環(huán)境信息的存儲量的大小與柵格的大小密切相關。所以，柵格的設計直接影響控制算法的優(yōu)劣。3.2.3模板模型法模板模型法是一種常用的模型，主要是依靠一種二維的清潔環(huán)境地圖和一種基于完全遍歷的路徑規(guī)劃模板來實現(xiàn)路徑的完全遍歷。此方法不適用于變化著的環(huán)境。3.2.4人工智能法所謂人

16、工智能，就是研究如何使計算機模擬人的思維去做相關工作，目前在運用于機器人的路徑選擇方面的算法主要有模糊邏輯、人工神經(jīng)網(wǎng)絡、遺傳算法。模糊控制算法在線規(guī)劃中，模糊控制方法是通常采用的一種規(guī)劃方法。包括建模和全局規(guī)劃。該方法最大的優(yōu)點就是能夠模擬人的駕駛經(jīng)驗，該算法計算量不大，能夠做到路徑實時規(guī)劃，同時可以克服人工勢場法中的局部極點問題，效果較佳。模糊控制的路徑規(guī)劃方法特別適用于局部避碰規(guī)劃，具有設計簡單、直觀、速度快、效果好等特點。神經(jīng)網(wǎng)絡路徑規(guī)劃 在路徑規(guī)劃方面，神經(jīng)網(wǎng)絡算法也有很多應用。它是一種能夠通過自學習進行自主導航的路徑規(guī)劃算法。完全遍歷路徑規(guī)劃能夠通過離線學習。遺傳算法遺傳算法是基于

17、自然選擇和自然遺傳機制的搜索算法。它是一種有效的解決最優(yōu)化問題的方法，是進化算法的一種。對于復雜的優(yōu)化問題，遺傳算法無需建模和進行復雜的運算，只要用遺傳算法的三種算子就能找到優(yōu)化解，因此在多個領域中，遺傳算法得到了廣泛的應用。在機器人領域，遺傳算法也有部分應用。 從以上幾種算法的分析可以看出，遺傳算法是一種借鑒生物界自然選擇和適者生存遺傳機制的高度并行、隨機、自適應搜索算法，它主要用于處理最優(yōu)化問題和機器學習。所以遺傳算法在機器人的路徑規(guī)劃方面具有顯著的優(yōu)勢。四、論文進度安排序號時間研究內容14.257.15了解各系統(tǒng)工作原理，查找相關資料27.168.1確定總體設計方案38.19.30完成第一重路徑規(guī)劃模塊的程序的編寫410.110.15完成第二重障路徑規(guī)劃模塊的程序的編寫511.1612.1進行系統(tǒng)仿真和調試612.2答辯日完成論文寫作五、參考文獻1 李雯雯. 基于多種傳感器的自動導航小車避障的研究 D. 2008.：1,22 蔡自興中國的智能機器人研究 J莆田學院學報，2002，9(3)：3639 3 吳林智能機器人主題型號工作的回顧 J機器人技術與應用，2001694 龍飛. 動態(tài)未知環(huán)境中的機器人路徑規(guī)劃方法研究 D. 2005.5 鐘競輝. 基于模糊邏輯遺傳算法的機器人動態(tài)路徑規(guī)劃