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

機(jī)器人是一種可編程和多功能的，用來搬運(yùn)材料、零件、工具的操作機(jī);或是為了執(zhí)行不同的任務(wù)而具有可改變和可編程動(dòng)作的專門系統(tǒng)。機(jī)器人作為人類的一種新型的生產(chǎn)工具在提高生產(chǎn)效率、降低勞動(dòng)強(qiáng)度、擴(kuò)展工作區(qū)域，從危險(xiǎn)、復(fù)雜、惡劣的情況下將人類的勞動(dòng)力解放出來的過程中顯示出了極大的優(yōu)越性。隨著機(jī)器人的研究的逐步深入，現(xiàn)代的機(jī)器人更是感知、決策、行動(dòng)和交互技術(shù)的高度有效結(jié)合的產(chǎn)物。根據(jù)應(yīng)用領(lǐng)域的不同，機(jī)器人可以分為移動(dòng)機(jī)器人、醫(yī)療機(jī)器人、空中機(jī)器、水下機(jī)器人、軍用機(jī)器人等各種智能機(jī)器人，它們在外形上己遠(yuǎn)遠(yuǎn)不再是最初仿人形機(jī)器人和工業(yè)機(jī)器人，而是根據(jù)不同的特殊應(yīng)用領(lǐng)域而制定的。移動(dòng)機(jī)器人自主導(dǎo)航包含的問題有：機(jī)器人定位，機(jī)器人路徑規(guī)劃以及機(jī)器人的運(yùn)動(dòng)控制。移動(dòng)機(jī)器人的路徑規(guī)劃在其中占據(jù)著主導(dǎo)的地位，也是各領(lǐng)域各學(xué)科研究的重點(diǎn)，是衡量機(jī)器人性能指標(biāo)的一大主要研究方向。移動(dòng)機(jī)器人路徑規(guī)劃具體是指在環(huán)境中存在障礙物的情況下，機(jī)器人按照一定的評價(jià)標(biāo)準(zhǔn)在一定時(shí)間內(nèi)獲得一條從運(yùn)動(dòng)起點(diǎn)到目標(biāo)終點(diǎn)的沒有碰撞的較優(yōu)路徑。機(jī)器人的路徑規(guī)劃問題從上世紀(jì)70年代就得到了諸多學(xué)者和專家的重點(diǎn)關(guān)注。路徑規(guī)劃規(guī)劃算法的運(yùn)算復(fù)雜度、穩(wěn)定性，間接影響著機(jī)器人的工作效率，結(jié)果的優(yōu)劣同樣影響著機(jī)器人動(dòng)作的準(zhǔn)確性和實(shí)時(shí)性。所以說，路徑規(guī)劃是實(shí)現(xiàn)機(jī)器人自主導(dǎo)航問題中最至關(guān)重要的一部分。一個(gè)好的路徑規(guī)劃應(yīng)該能在較短的時(shí)間內(nèi)找到一條較優(yōu)的路徑，該路徑不但可以避開環(huán)境中的障礙物而且還能處理環(huán)境中未知情況。早在20世紀(jì)就有科學(xué)家預(yù)測：20世紀(jì)的核心作戰(zhàn)武器是坦克，21世紀(jì)的核心作戰(zhàn)武器重心則會轉(zhuǎn)移向無人作戰(zhàn)系統(tǒng)發(fā)展。從上個(gè)世紀(jì)60年代末開始，以美國為首的發(fā)達(dá)國家就已經(jīng)對智能機(jī)器人展開了著重的研究工作，NilsNilsson和CharlesRosen等[2]人，于1966年至1972年間在斯坦福研究院(SRI)研制了名為Shakey的自主移動(dòng)機(jī)器人，用于在復(fù)雜環(huán)境下的自主推理、規(guī)劃和控制。在此期間著名的GeneralElectricQuadruped[3]的步行機(jī)器人也被研制成功，開辟了步行機(jī)器人的研究領(lǐng)域。進(jìn)入70年代，隨著計(jì)算機(jī)和傳感器領(lǐng)域的迅速發(fā)展，移動(dòng)機(jī)器人的研究進(jìn)入了一個(gè)新的高潮，日本早稻田大學(xué)研制出具有仿人功能的兩足步行機(jī)器人。為適應(yīng)原子能利用和海洋開發(fā)的需要，極限作業(yè)機(jī)器人和水下機(jī)器人也以較快的速度發(fā)展起來。美國國防高級研究計(jì)劃局(DARPA)專門立項(xiàng)，制定了地面無人作戰(zhàn)平臺的戰(zhàn)略計(jì)劃，揭開了室外移動(dòng)機(jī)器人研究的序幕。如DARPA的“戰(zhàn)略計(jì)算機(jī)”計(jì)劃中的自主地面車輛(ALV)計(jì)劃(1983-1990);能源部制定的為期10年的機(jī)器人和智能系統(tǒng)計(jì)劃RIPS(1986-1995)，以及后來的空間機(jī)器人計(jì)劃;歐洲尤里卡中的機(jī)器人計(jì)劃和日本通產(chǎn)省組織的極限環(huán)境下作業(yè)的機(jī)器人計(jì)劃等[4]。進(jìn)入20世紀(jì)以后以美國為代表在軍用和民用領(lǐng)域?qū)τ跈C(jī)器人的研究處于迅猛發(fā)展的階段，機(jī)器人被廣泛應(yīng)用于各個(gè)領(lǐng)域之中。在移動(dòng)機(jī)器人路徑規(guī)劃方面，W.E.Howden于1968年提出了柵格法來對路徑規(guī)劃進(jìn)行研究[2]。在進(jìn)行路徑規(guī)劃的時(shí)候?qū)⒌貓D劃分成為大小相同的若干個(gè)小的柵格，將存在障礙物的柵格均劃分出來，在處理不規(guī)則障礙物的時(shí)候就有良好的適應(yīng)性。在劃分柵格的時(shí)候，劃分的柵格越多，障礙物的表示會越精確，但同時(shí)占用的存儲空間也會相應(yīng)增加,算法的搜索范圍將按指數(shù)增加。柵格的粒度太大，規(guī)劃的路徑會很不精確。所以柵格粒度大小的確定,是柵格法在實(shí)際應(yīng)用中的主要問題。人工勢場法是Khatib于1986年首次提出的，由于其計(jì)算簡便，實(shí)時(shí)性強(qiáng)等優(yōu)點(diǎn)，許多學(xué)者都先后研究發(fā)展這一方法，并將其應(yīng)用于機(jī)器人的實(shí)時(shí)路徑規(guī)劃和運(yùn)動(dòng)控制中。人工勢場法路徑規(guī)劃技術(shù)的基本思想是把機(jī)器人在環(huán)境中的運(yùn)動(dòng)視為一種機(jī)器人在虛擬的人工受力場中的運(yùn)動(dòng)。障礙物對機(jī)器人產(chǎn)生斥力，目標(biāo)點(diǎn)對機(jī)器人產(chǎn)生引力，引力和斥力的合力作為機(jī)器人的控制力，從而使機(jī)器人避開障礙物而達(dá)到目標(biāo)位置[4]。人工勢場法,具有反應(yīng)速度快、計(jì)算量小和實(shí)時(shí)性等優(yōu)點(diǎn)，但同時(shí)這種方法也存在弊端，比如當(dāng)障礙物與目標(biāo)點(diǎn)處于機(jī)器人的同一連線上時(shí)容易產(chǎn)生局部極值點(diǎn),導(dǎo)致機(jī)器人停止移動(dòng),無法到達(dá)目標(biāo)區(qū)域，其另一個(gè)重要缺點(diǎn)就是它只根據(jù)障礙物和機(jī)器人的位置生成作用力,而無法考慮機(jī)器人的速度，在機(jī)器人快速移動(dòng)時(shí)可能會出現(xiàn)計(jì)算失敗的情況[5]。2.1.2本課題國內(nèi)研究進(jìn)展路徑規(guī)劃是移動(dòng)機(jī)器人自動(dòng)尋徑問題中需要解決的最為關(guān)鍵也最為重要的問題，本課題的設(shè)計(jì)任務(wù)就是研究如何利用蟻群算法以及人工勢場法為移動(dòng)機(jī)器人進(jìn)行路徑優(yōu)化，在起始點(diǎn)與目標(biāo)點(diǎn)直接找到一條路徑較短，用時(shí)最快的避障路線。主要研究內(nèi)容包括：了解目前常用移動(dòng)機(jī)器人路徑規(guī)劃算法的基本思想及其特點(diǎn)。

（2）弄清蟻群算法的基本原理及具體實(shí)現(xiàn)方法。

（3）對蟻群算法進(jìn)行必要的改進(jìn)。

（4）用C（或MATLAB）語言編制程序，進(jìn)行路徑規(guī)劃算法的仿真研究。3.2研究方法3.2.1蟻群算法概述現(xiàn)階段越來越多的學(xué)者專家對仿生智能算法進(jìn)行研究探討，如模擬生物界中的遺傳規(guī)律和自然選擇的遺傳算法、模擬螞蟻群體覓食行為的蟻群算法等。意大利學(xué)者M(jìn)arcoDorigo和他的同事受自然界中真實(shí)螞蟻群體行為的啟發(fā)，于1991年首次提出蟻群算法(AntColonyOptimizationACO)這個(gè)新型的啟發(fā)式路徑搜索算法概念。經(jīng)過長期研究發(fā)現(xiàn)每只螞蟻在外出尋找食物源、搬家等行為過程中都能夠在所經(jīng)過的路徑上釋放一種稱之為信息素的分泌物，蟻群之間通過這種信息素相互通信和路徑選擇，同時(shí)蟻群會自發(fā)的向信息素濃度高的方向移動(dòng)。隨著時(shí)間的推移，蟻群之間的集體行為表現(xiàn)出正反饋現(xiàn)象，當(dāng)某一條路徑上走過的螞蟻數(shù)量越多，積累的信息素濃度越大，隨后越多的螞蟻選擇該路徑，釋放的信息素濃度進(jìn)一步增強(qiáng)，從而能很快的找到最優(yōu)路徑。目前該算法被廣泛的應(yīng)用于求旅行商問題(TSP)、作業(yè)調(diào)度、二次分配、車輛路徑、多選擇背包及網(wǎng)絡(luò)路由等問題，取得了良好的實(shí)驗(yàn)效果。3.2.2蟻群算法基本原理現(xiàn)實(shí)生活中螞蟻們能通過相互協(xié)調(diào)、分工合作來完成一系列活動(dòng)如遷徙、筑巢尋找食物以及清掃等活動(dòng)。其中蟻群可以在可見提示的條件下找到從蟻穴到食物源的最短路徑，并且能隨著環(huán)境的變化而變化地搜索新的路徑，產(chǎn)生新的選擇。這是因?yàn)槲浵佋谄渥哌^的路上會分泌一種信息素，其他的螞蟻能夠感知這種物質(zhì)的存在和強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，使其傾向于朝著信息素強(qiáng)度高的方向移動(dòng)。蟻群算法就是從自然界中真實(shí)螞蟻覓食的群體行為中得到啟發(fā)而提出的。在蟻群算法中，為了實(shí)現(xiàn)對真實(shí)螞蟻的抽象，提出了人工蟻的概念。人工蟻和真實(shí)螞蟻有如下相同點(diǎn):(1)人工蟻和螞蟻一樣，是一群相互合作的個(gè)體，每個(gè)螞蟻都能建立一種解決方案，整個(gè)蟻群相互合作在全局范圍內(nèi)找出問題的較優(yōu)的解決方案。(2)人工蟻和真實(shí)螞蟻有著公共的任務(wù)，尋找最優(yōu)路徑。（3）人工蟻和真實(shí)螞蟻一樣也通過使用信息素進(jìn)行間接通訊。(4)人工蟻和真實(shí)螞蟻的覓食行為都是一種正反饋過程。(5)在蟻群算法中存在一種信息素的揮發(fā)機(jī)制，類似于真實(shí)世界中的情況，(6)不預(yù)測未來狀態(tài)概率的狀態(tài)轉(zhuǎn)移策略。人工蟻的策略是充分利用了局部信息，而沒有前瞻性的預(yù)測未來的狀態(tài)。

針對人工勢場法和蟻群算法各自的特點(diǎn)，部分學(xué)者利用勢場力改變蟻群算法狀態(tài)轉(zhuǎn)移規(guī)律，將蟻群算法與人工勢場力巧妙地結(jié)合在了一起。本課題將蟻群算法與人工勢場力結(jié)合起來，螞蟻在柵格環(huán)境區(qū)域內(nèi)移動(dòng)，不僅受到了信息素濃度和距離啟發(fā)信息的作用，同時(shí)還受到了人工勢場力的影響。人工勢場力的作用使移動(dòng)機(jī)器人在移動(dòng)過程中迅速的規(guī)避障礙物，向著目標(biāo)位置前行，它可以作為勢場蟻群算法的另一種啟發(fā)信息。一般在路徑規(guī)劃初期由于路徑信息素濃度較弱，蟻群的正反饋?zhàn)饔眯Ч幻黠@，因此需要側(cè)重于勢場信息作用，而隨著螞蟻迭代次數(shù)的增加，路徑上信息素濃度增多，正反饋?zhàn)饔迷鰪?qiáng)，此時(shí)需要降低勢場力作用，勢場力啟發(fā)信息影響系數(shù)的引入很好的平衡了蟻群算法和人工勢場算法在整個(gè)路徑規(guī)劃過程中的作用。勢場蟻群算法在路徑規(guī)劃時(shí)利用蟻群全局路徑搜索機(jī)制，綜合勢場力啟發(fā)信息和距離啟發(fā)信息的作用，能有效的避開己知環(huán)境中障礙物，尋找到一條從起始位置到目標(biāo)位置的最優(yōu)路徑。[12011，30（2）：5-8[2]2011，7（4）：348-351[3]2009，20（4）：70-74[4]2006，42（27）：26～28[5]2011，（23）：50[6]2010，s1：814-816[7]2010，（11）：24-25[8]..2011，24（5）：81-82[9]..2005[10]..2004，33（2）