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