群智能優化算法在機器人路徑規劃中的應用的畢業設計(文件)

　

【正文】 率。任何一種智能機器人，他在完成工作的過程中，總是需要基于某一規則，譬如，所要話費的時間要少，或是所要經過的路徑長度要最短，或是其消耗的資源要少，再或是要求資源的利用率要高等等。當環境完全己知時，智能機器人能夠進行離線的路徑規劃，意思就是通過己經知道了解的地圖環境信息，使用合適的算法，得出一條可行的的路徑，該路徑既要到達目標點又要滿足規劃的要求，之后通過管理機器人運行的控制模塊來驅動智能機器人沿這條可行路徑路徑運動到達目標位置?！C器人路徑規劃的思想起源最近幾年, 隨著移動機器人技術快速發展, 其應用領域也在不斷擴展發展。在工業生產中常用智能機器人來完成上下料和運輸等任務，而且路徑規劃經常被廣泛應用于醫療、農業、工業、食品業、交通業等不同的領域。2）對于傳感器感知的環境模型中的不確定性因素和路徑運行中出現的誤差，該規劃系統能夠對其進行及時的處理。2）智能機器人怎樣基于外部及內部的傳感器的信息來獲取其當前位于地圖環境中的哪一個位置。2）傳感技術。因此，以障礙物的狀態和環境模型來進行分析，可以考慮以下4種情況：1）已知環境下的靜態障礙物的大小、形狀和位置對規劃系統的影響，并且其障礙物一定是靜止不動的。總之，之所以要研究機器人路徑規劃這個問題，就是因為在我們的生活中，我們為了提高工作效率，為了讓機器人從起始點到達目標點，即要過障礙物，又要讓其經過的路徑最短，這樣既節省了時間，又節約了資源，而且對于工業上的各個方面都有很大的幫助，這就是為什么我們要研究這個課題的原因。笛卡爾的直角坐標空間經常稱為局部方法，人工勢場法經常被人們稱為全局方法。定義2兩個柵格之間連線的長度指任意兩個柵格之間的距離，稱為dist（gi (xi,yi ), gj(xj, yj)），其中gi，gj∈A，i,j∈C。={2,22}。定義7 gigj(i,j∈C,gi,gj∈FS) 稱為柵格gi gj的中心線。則編碼方法為{(xij)|1≤j≤m,且當j∈SS, xij=1,否則xij=0}。使用這種方式進行編碼，保證了每一時刻所有的粒子都是同維的，因而粒子群的位置和速度向量均是定長的。設選擇的下一個節點gj(j∈C) 與gi的中心連線從兩個障礙柵格之間經過，即出現了圖5中所列的情況之一，將把節點gj記為NS。3)改變gi的當前值做為本次所要選取的柵格gw，所以此次加入禁忌集合tabuk的柵格為gw。得到其對應的位置向量XK可采用機器人位置編碼方法得到。這樣既可以節約時間，而且可以提高機器人的運行效率，同時對我們的實際生活也會有所啟發，促使我們做出更深入的研究。我相信大家都知道在我們日常生活中，我們所面對的事物都是形象的東西，是我們能夠感受到和體會到的東西，但是當我們研究一項課題的時候，我們不可能將其直接應用到實際生活中的，我們要先給它建模，模擬其活動，所以在研究機器人路徑規劃時，我們就必須先對其進行環境建模，模擬出其運行的路徑以及路徑中的障礙物。環境建模的方法紛繁復雜，在應用于移動機器人路徑規劃方面，絕大多數是將實際的環境信息轉換為了圖的問題，進而抽象為對環境空間的骨架圖進行描述[4]。而它之所以應用廣泛也是有原因的：它在求解最短路徑問題上比別的方法要簡單易懂很多。出于安全性考慮，設計的Voronoi圖具有獨特的幾何特性。柵格法用大小相等的矩形柵格均勻劃分環境空間，并對環境中的自由空間與障礙物進行特別區分。優點主要表現在：即使環境空間發生局部變化，也不用重新設計規劃圖，因而表現出了靈活性。圖6因此由上述dijkstra算法的啟示，我就考慮使用柵格法進行環境建模，而且在柵格模型中使用Dijkstra 算法進行路徑規劃, 可以一次規劃出從初始節點到其他所有節點的最短路徑, 但是同時存在計算量大、規劃時間長、擴展節點個數多等缺點。 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0。 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0。 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0。 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0。 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0。其中矩陣中的0表示該網格不是障礙，1表示該網格為障礙環境建模圖： 圖7網格賦值矩陣為：G2=[0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0。 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0。 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0。 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0。 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0。]。 %終止節點向量W=[1 2 12 6 3 4 4 15 7 2 7 7 15 3 10]。P=biograph(G,[],39。)。,39。,[1 ])。set(edges,39。LineWidth39。4　粒子群優化算法在機器人路徑規劃中的具體應用　問題描述與建模為了達到本論文的路徑規劃算法,在機器人運動環境建模時，我們作出了以下假設[20]：1) 智能機器人的運動環境空間為二維的；2) 在智能機器人的運行環境中存在著有限的已知靜態障礙物,我們能夠用多邊形表示障礙物。記AS為智能機器人在二維空間上的不規則或規則多邊形的有限移動空間，其空間內存在著有限個障礙物bbb......、bn，而且這n個障礙物是靜態的。G矩陣中的每一個二進制值0或1就代表環境中一個位置。令柵格序號集合為C= {1, 2, 3, ,M}，g(1, 1)的序號為1, g(1, 2)序號為2, g(2, 1)序號為Nx+1...。為了使得這個模型方便而且合理, 假定：在機器人從起始點到達目標位置的整個運行過程中, 所有在此環境模型中的障礙物的大小、幾何形狀均是靜止的和不變的?！∷惴鞒虉D開始建立基于柵格的機器人運行環境，設置初始起點Gbegin和目標點Gend以及各參數和路徑表path根據初始化種群產生的方法初始化粒子的位置Xi和速度Vi由式(10)計算每一個粒子的適應值根據式(7)更新沒一個粒子i的歷史最優解Pbesti由式(8)更新種群的全局最優解Gbest由式（1）更新每一個粒子的速度，根據式(9)調整根新后的速度由式(2)更新每一個粒子的位置，將iter的值加1若iteritermax N Y將得到的最佳路徑添加到path路徑表中若到達Gend或到達柵格g(xg,yg)，且不會出現圖5的狀況 Y N結束 　粒子群算法與機器人路徑規劃的結合實現　優化算法的適應度函數的確定方式假設第i個微粒的位置分量的集合為Xi=(Xi1,Xi2,Xi3,……,XiD)，而且定義其對應的路徑為{gi1, gi2, gi2,....., gin}，那么以下計算式就可以得到第i個粒子的適應度函數值：Fi=j=1n1dist(gij,gij+1) (10)式中，gij(1≤j≤n) 均為路徑點，dist(gij,gij+1)由式() 計算得出。該論文中的微粒位置的更新以式(2)為標準，以下為本文采用的粒子位置更新策略:由PSO算法本身的特點，本篇論文中對微粒位置的更新事實上是對粒子位置向量中的某一個分量的更新，定義第i個微粒的位置向量為Xi=(Xi1,Xi2,Xi3,……,XiD)，那么定義更新后的位置分量為Xi39。,……,XiD39。但是上述位置分量的變化也許有可能使的更新后的位置分量Xi39。,……,XiD39。,Xi239。如果即達到安全避障又沒有超過視野域范圍，就可以允許將Xi添加到Xi39。,Xi239。如由5圖所示，其中位置向量為X=1000001100001000011000011，那么機器人可能經過的的路徑為1→7→8→13→19→18→24→25或者1→7→8→13→18→19→24→25。,Xi239。本篇文章所使用的檢查策略為提取出來位置向量Xi=(Xi1,Xi2,Xi3,……,XiD) 中值為1的柵格序號，并將提取出來的這些序號構成集合CGS={u|u∈C,Xiu=1}，對其進行全排列P|CGS||CGS|，并且對P|CGS||CGS|中的每一個序列u1, u2, u3,......, u|CGS|進行避障檢查和邊界檢查。在此我選擇的是基于自然選擇的粒子群優化算法。優化后粒子群算法實現收斂效果圖：圖10 改進粒子群算法適應度曲線　仿真效果圖圖11 收斂曲線圖12 最優化路徑仿真圖5　結論通過以上過程的論述，我起初用基本粒子群算法對問題進行優化，但是基本粒子群算法雖然能夠進行優化，但是其優化效率低，而且運算精度也打不到要求，何況針對移動機器人路徑規劃這一復雜的問題，其運算復雜，而且要求的結果要比較精確，所以最終我就采用了混合粒子群算法，其與基本粒子群算法沒有很明顯的區別，只是在迭代運算的過程中加入了一些遺傳算法中交叉算子的思想，再加入該思想之后，通過matlab的編碼實現對機器人路徑的規劃，其效果可以通過上述仿真圖看出。6　致謝歷經了幾個月的忙碌學習，這一次艱難卻有意義的畢業設計將要馬上結束，作為一個本科生的畢業設計，由于經驗的匱乏，所以不可避免存在許多考慮不周全的地方，因此，假設沒有導師的循循善誘的知道和督促，以及一起研究的同學們的幫助和支持，能夠這么順利的完成這個畢業設計簡直是非常難的。我的設計較為復雜煩瑣，而且本身學習底子不是很好，但是江老師仍然細心地糾程序和文章中的錯誤。clc。%c2=2。 %學習因子2w=。 %搜索空間維數（未知數個數）N=40。 %隨機初始化速度 endend%先計算各個粒子的適應度，并初始化Pi和Pgfigure(3)for i=1:N P(i)=fitness2(x(i,:))。 endend%進入主要循環，按照公式依次迭代，直到滿足精度要求for t=1:MaxDT for i=1:N v(i,:)=w*v(i,:)+c1*rand*(y(i,:)x(i,:))+c2*rand*(Pgx(i,:))。 end if P(i)fitness2(Pg) Pg=y(i,:)。 %雜交池中粒子的位置 PoolVX=v(1: numPool,:)。 childx1(i,:)=pb*PoolX(seed1,:)+(1pb)*PoolX(seed2,:)。 %子代速度替換父代速度 end Pbest(t)=fitness2(Pg)。title(TempStr)。ylabel(39。*************************************************************39。)。迭代次數39。c1= %g ,c2=%g39。endx(1:numPool,:)=childx1。 seed2=floor(rand()*(numPool1))+1。if r1Pc %雜交概率 numPool=round(Sp*N)。 if fitness2(x(i,:))P(i) P(i)=fitness2(x(i,:))。endPg=x(N,:)。 %設置精度(在已知最小值時候用)%初始化種群的個體(可以在這里限定位置和速度的范圍)for i=1:N for j=1:D x(i,j)=randn。MaxDT=10000。Sp=。%給定初始化條件c1=2。最后，值此論文完成之際，謹向我的導師江祥奎老師致以衷心的感謝和崇高的敬意。 所以，此時此刻我首先要感謝我的導師江祥奎老師給予我莫大的支持和幫助。通過粒子群優化算法與路徑規劃方法的結合最終完成了機器人最優路徑的選取。通過父代位置進行算術交叉得到子代位置：child(x)=P*parent1(x)+(1P)* parent2(x) ()其中P是0到1之間的隨機數?！×Ｗ尤簝灮惴ǖ母倪M混合粒子群算法：該論文中采用的粒子群優化算法是混合粒子群優化算法，混合粒子群算法是指借鑒其他一些智能優化算法的思想而形成的粒子群算法。,……,XiD39。因此，怎樣對更新后的位置向量Xi39。,……,XiD39。可以假設微粒更新后的位置向量為Xi39。,……,XiD39。因此，在我們改變某一微粒的位置Xi=(Xi1,Xi2,Xi3,……,XiD) 的某一維分量的值的時候，我們都要對系統進行越界檢查和避障檢查，看更新后的位置向量Xi39。,Xi239。從Xi到Xi39。,Xi239?！×Ｗ游恢煤退俣雀虏呗粤Ｗ铀俣雀氯匀徊捎脴藴柿Ｗ尤核惴ㄖ械乃俣雀鹿?，即式(1)。依據改進的粒子群算法的原理以及與智能機器人的路徑規劃方法的結合，粒子群優化算法在機器人路徑規劃的算法步驟為：1)首先應該建立基于柵格法的環境模型，取Gbegin(xbegin,ybegin)為初始起始點和取Gend(xend,