基于蟻群算法與人工勢場法的機器人路徑規(guī)劃_研究生選題報告

1、北 京 科 技 大 學研究生畢業(yè)設計(論文)選題報告題目： 基于蟻群算法與人工勢場法 的機器人路徑規(guī)劃 學院： 自動化學院 專業(yè)： 控制工程 姓名： 田澤文 學號： G 指導教師簽字：_ 年 月 日目 錄1課題研究的目的與意義22文獻綜述32.1國內外研究現狀32.1.1本課題國內研究進展32.1.2本課題國內研究進展43研究內容、預期目標及研究方法53.1研究內容53.2研究方法53.3預期目標73.4技術難度74進度安排8參 考 文 獻91課題研究的目的與意義機器人是一種可編程和多功能的，用來搬運材料、零件、工具的操作機;或是為了執(zhí)行不同的任務而具有可改變和可編程動作的專門系統。機器人作為

2、人類的一種新型的生產工具在提高生產效率、降低勞動強度、擴展工作區(qū)域，從危險、復雜、惡劣的情況下將人類的勞動力解放出來的過程中顯示出了極大的優(yōu)越性。隨著機器人的研究的逐步深入，現代的機器人更是感知、決策、行動和交互技術的高度有效結合的產物。根據應用領域的不同，機器人可以分為移動機器人、醫(yī)療機器人、空中機器、水下機器人、軍用機器人等各種智能機器人，它們在外形上己遠遠不再是最初仿人形機器人和工業(yè)機器人，而是根據不同的特殊應用領域而制定的。移動機器人自主導航包含的問題有：機器人定位，機器人路徑規(guī)劃以及機器人的運動控制。移動機器人的路徑規(guī)劃在其中占據著主導的地位，也是各領域各學科研究的重點，是衡量機器人

3、性能指標的一大主要研究方向。移動機器人路徑規(guī)劃具體是指在環(huán)境中存在障礙物的情況下，機器人按照一定的評價標準在一定時間內獲得一條從運動起點到目標終點的沒有碰撞的較優(yōu)路徑。機器人的路徑規(guī)劃問題從上世紀70年代就得到了諸多學者和專家的重點關注。路徑規(guī)劃規(guī)劃算法的運算復雜度、穩(wěn)定性，間接影響著機器人的工作效率，結果的優(yōu)劣同樣影響著機器人動作的準確性和實時性。所以說，路徑規(guī)劃是實現機器人自主導航問題中最至關重要的一部分。一個好的路徑規(guī)劃應該能在較短的時間內找到一條較優(yōu)的路徑，該路徑不但可以避開環(huán)境中的障礙物而且還能處理環(huán)境中未知情況。2文獻綜述2.1國內外研究現狀2.1.1本課題國內研究進展早在20世紀

4、就有科學家預測：20世紀的核心作戰(zhàn)武器是坦克，21世紀的核心作戰(zhàn)武器重心則會轉移向無人作戰(zhàn)系統發(fā)展。從上個世紀60年代末開始，以美國為首的發(fā)達國家就已經對智能機器人展開了著重的研究工作，Nils Nilsson和Charles Rosen等2人，于1966年至1972年間在斯坦福研究院(SRI )研制了名為Shakey的自主移動機器人，用于在復雜環(huán)境下的自主推理、規(guī)劃和控制。在此期間著名的General Electric Quadruped3的步行機器人也被研制成功，開辟了步行機器人的研究領域。進入70年代，隨著計算機和傳感器領域的迅速發(fā)展，移動機器人的研究進入了一個新的高潮，日本早稻田大學研

5、制出具有仿人功能的兩足步行機器人。為適應原子能利用和海洋開發(fā)的需要，極限作業(yè)機器人和水下機器人也以較快的速度發(fā)展起來。美國國防高級研究計劃局(DARPA )專門立項，制定了地面無人作戰(zhàn)平臺的戰(zhàn)略計劃，揭開了室外移動機器人研究的序幕。如DARPA的“戰(zhàn)略計算機”計劃中的自主地面車輛(ALV)計劃( 1983-1990 );能源部制定的為期10年的機器人和智能系統計劃RIPS(1986-1995)，以及后來的空間機器人計劃;歐洲尤里卡中的機器人計劃和日本通產省組織的極限環(huán)境下作業(yè)的機器人計劃等4。進入20世紀以后以美國為代表在軍用和民用領域對于機器人的研究處于迅猛發(fā)展的階段，機器人被廣泛應用于各個

6、領域之中。在移動機器人路徑規(guī)劃方面，W. E. Howden于1968 年提出了柵格法來對路徑規(guī)劃進行研究2。在進行路徑規(guī)劃的時候將地圖劃分成為大小相同的若干個小的柵格，將存在障礙物的柵格均劃分出來，在處理不規(guī)則障礙物的時候就有良好的適應性。在劃分柵格的時候，劃分的柵格越多，障礙物的表示會越精確，但同時占用的存儲空間也會相應增加,算法的搜索范圍將按指數增加。柵格的粒度太大，規(guī)劃的路徑會很不精確。所以柵格粒度大小的確定,是柵格法在實際應用中的主要問題。人工勢場法是Khatib于1986年首次提出的，由于其計算簡便，實時性強等優(yōu)點，許多學者都先后研究發(fā)展這一方法，并將其應用于機器人的實時路徑規(guī)劃和

7、運動控制中。人工勢場法路徑規(guī)劃技術的基本思想是把機器人在環(huán)境中的運動視為一種機器人在虛擬的人工受力場中的運動。障礙物對機器人產生斥力，目標點對機器人產生引力，引力和斥力的合力作為機器人的控制力，從而使機器人避開障礙物而達到目標位置4。人工勢場法,具有反應速度快、計算量小和實時性等優(yōu)點，但同時這種方法也存在弊端，比如當障礙物與目標點處于機器人的同一連線上時容易產生局部極值點, 導致機器人停止移動, 無法到達目標區(qū)域，其另一個重要缺點就是它只根據障礙物和機器人的位置生成作用力, 而無法考慮機器人的速度，在機器人快速移動時可能會出現計算失敗的情況5。2.1.2本課題國內研究進展 國內對移動機器人的研

8、究起步較晚，但隨著機器人的不斷發(fā)展我國也在移動機器人研究領域開展了大量的工作。隨著我國經濟水平的快速發(fā)展，對于機器人的研究也越來越重視，諸多國內學者對于機器人展開了大量深入的研究工作。最早國內關于這方面研究于20世紀80年代末。但即便如此由于我國在機器人領域的研究起步相對較晚，經濟條件相對不足，其發(fā)展水平與發(fā)達國家比較仍然有一定的差距。3研究內容、預期目標及研究方法3.1研究內容路徑規(guī)劃是移動機器人自動尋徑問題中需要解決的最為關鍵也最為重要的問題，本課題的設計任務就是研究如何利用蟻群算法以及人工勢場法為移動機器人進行路徑優(yōu)化，在起始點與目標點直接找到一條路徑較短，用時最快的避障路線。主要研究內

9、容包括：（1） 了解目前常用移動機器人路徑規(guī)劃算法的基本思想及其特點。（2）弄清蟻群算法的基本原理及具體實現方法。（3）對蟻群算法進行必要的改進。（4）用C（或MATLAB）語言編制程序，進行路徑規(guī)劃算法的仿真研究。3.2研究方法3.2.1 蟻群算法概述現階段越來越多的學者專家對仿生智能算法進行研究探討，如模擬生物界中的遺傳規(guī)律和自然選擇的遺傳算法、模擬螞蟻群體覓食行為的蟻群算法等。意大利學者Marco Dorigo和他的同事受自然界中真實螞蟻群體行為的啟發(fā)，于1991年首次提出蟻群算法(Ant Colony Optimization ACO)這個新型的啟發(fā)式路徑搜索算法概念。經過長期研究發(fā)現

10、每只螞蟻在外出尋找食物源、搬家等行為過程中都能夠在所經過的路徑上釋放一種稱之為信息素的分泌物，蟻群之間通過這種信息素相互通信和路徑選擇，同時蟻群會自發(fā)的向信息素濃度高的方向移動。隨著時間的推移，蟻群之間的集體行為表現出正反饋現象，當某一條路徑上走過的螞蟻數量越多，積累的信息素濃度越大，隨后越多的螞蟻選擇該路徑，釋放的信息素濃度進一步增強，從而能很快的找到最優(yōu)路徑。目前該算法被廣泛的應用于求旅行商問題(TSP )、作業(yè)調度、二次分配、車輛路徑、多選擇背包及網絡路由等問題，取得了良好的實驗效果。3.2.2 蟻群算法基本原理現實生活中螞蟻們能通過相互協調、分工合作來完成一系列活動如遷徙、筑巢尋找食物

11、以及清掃等活動。其中蟻群可以在可見提示的條件下找到從蟻穴到食物源的最短路徑，并且能隨著環(huán)境的變化而變化地搜索新的路徑，產生新的選擇。這是因為螞蟻在其走過的路上會分泌一種信息素，其他的螞蟻能夠感知這種物質的存在和強度，并以此指導自己的運動方向，使其傾向于朝著信息素強度高的方向移動。蟻群算法就是從自然界中真實螞蟻覓食的群體行為中得到啟發(fā)而提出的。在蟻群算法中，為了實現對真實螞蟻的抽象，提出了人工蟻的概念。人工蟻和真實螞蟻有如下相同點:(1)人工蟻和螞蟻一樣，是一群相互合作的個體，每個螞蟻都能建立一種解決方案，整個蟻群相互合作在全局范圍內找出問題的較優(yōu)的解決方案。(2)人工蟻和真實螞蟻有著公共的任務

12、，尋找最優(yōu)路徑。（3）人工蟻和真實螞蟻一樣也通過使用信息素進行間接通訊。(4)人工蟻和真實螞蟻的覓食行為都是一種正反饋過程。(5)在蟻群算法中存在一種信息素的揮發(fā)機制，類似于真實世界中的情況，(6)不預測未來狀態(tài)概率的狀態(tài)轉移策略。人工蟻的策略是充分利用了局部信息，而沒有前瞻性的預測未來的狀態(tài)。3.3預期目標針對人工勢場法和蟻群算法各自的特點，部分學者利用勢場力改變蟻群算法狀態(tài)轉移規(guī)律，將蟻群算法與人工勢場力巧妙地結合在了一起。本課題將蟻群算法與人工勢場力結合起來，螞蟻在柵格環(huán)境區(qū)域內移動，不僅受到了信息素濃度和距離啟發(fā)信息的作用，同時還受到了人工勢場力的影響。人工勢場力的作用使移動機器人在移

13、動過程中迅速的規(guī)避障礙物，向著目標位置前行，它可以作為勢場蟻群算法的另一種啟發(fā)信息。一般在路徑規(guī)劃初期由于路徑信息素濃度較弱，蟻群的正反饋作用效果不明顯，因此需要側重于勢場信息作用，而隨著螞蟻迭代次數的增加，路徑上信息素濃度增多，正反饋作用增強，此時需要降低勢場力作用，勢場力啟發(fā)信息影響系數的引入很好的平衡了蟻群算法和人工勢場算法在整個路徑規(guī)劃過程中的作用。勢場蟻群算法在路徑規(guī)劃時利用蟻群全局路徑搜索機制，綜合勢場力啟發(fā)信息和距離啟發(fā)信息的作用，能有效的避開己知環(huán)境中障礙物，尋找到一條從起始位置到目標位置的最優(yōu)路徑。3.4技術難度(1)機器人規(guī)劃空間地圖的建立。(2)蟻群算法中參數的選擇，如信

14、息啟發(fā)式因子，期望啟發(fā)式因子，信息素揮發(fā)系數。4進度安排本人簽名：年 月 日參 考 文 獻1張海英，范進楨. 移動機器人路徑規(guī)劃研究現狀及展望J. 微型機與應用，2011，30（2）：5-82王保紅.移動機器人路徑規(guī)劃方法的研究與展望J.沈陽工程學院學報（自然科學版），2011，7（4）：348-3513孔峰，陶金，謝超平.移動機器人路徑規(guī)劃技術研究J.廣西工學院學報，2009，20（4）：70-744黃炳強，曹廣益基于人工勢場法的移動機器人路徑規(guī)劃研究J計算機工程與應用，2006，42（27）：26285胡琥.智能機器人路徑規(guī)劃方法研究J. 黑龍江科技信息，2011，（23）：506黎紅.自

15、主移動機器人路徑規(guī)劃中的主要方法J.中國電力教育，2010，s1：814-8167 徐會成，單建華. 基于改進粒子群算法的移動機器人全局路徑規(guī)劃J. 機械工程師，2010，（11）：24-258付寧，張東霞，國海濤.蟻群算法在機器人路徑規(guī)劃中研究及發(fā)展趨勢J.濰坊教育學院學報，2011，24（5）：81-829段海濱.蟻群算法原理及應用M.北京：科學出版社，200510 張明路，丁承君，段萍.移動機器人的研究現狀與趨勢J.河北工業(yè)大學學報，2004，33（2）：110-11511張毅，羅元，鄭太雄.移動機器人技術及其應用M.北京：電子工業(yè)出版社， 200712張捍東，鄭睿，岑豫皖.移動機器人路徑規(guī)