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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、息啟發(fā)式因子，期望啟發(fā)式因子，信息素揮發(fā)系數(shù)。4進度安排本人簽名：年 月 日參 考 文 獻1張海英，范進楨. 移動機器人路徑規(guī)劃研究現(xiàn)狀及展望J. 微型機與應(yīng)用，2011，30（2）：5-82王保紅.移動機器人路徑規(guī)劃方法的研究與展望J.沈陽工程學(xué)院學(xué)報（自然科學(xué)版），2011，7（4）：348-3513孔峰，陶金，謝超平.移動機器人路徑規(guī)劃技術(shù)研究J.廣西工學(xué)院學(xué)報，2009，20（4）：70-744黃炳強，曹廣益基于人工勢場法的移動機器人路徑規(guī)劃研究J計算機工程與應(yīng)用，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.濰坊教育學(xué)院學(xué)報，2011，24（5）：81-829段海濱.蟻群算法原理及應(yīng)用M.北京：科學(xué)出版社，200510 張明路，丁承君，段萍.移動機器人的研究現(xiàn)狀與趨勢J.河北工業(yè)大學(xué)學(xué)報，2004，33（2）：110-11511張毅，羅元，鄭太雄.移動機器人技術(shù)及其應(yīng)用M.北京：電子工業(yè)出版社， 200712張捍東，鄭睿，岑豫皖.移動機器人路徑規(guī)