【文章內(nèi)容簡介】 內(nèi)容，它是依據(jù)某一性能指標(biāo)尋求一條從起始位置到達(dá)目標(biāo)位置的最優(yōu)或近似最優(yōu)的無碰撞的路徑[10]。因而，在智能機(jī)器人路徑規(guī)劃系統(tǒng)中，有以下幾點主要要求，它們分別是：1）在周圍環(huán)境的建模中尋找一條路徑，確保機(jī)器人沿這條路徑運行時，不會與外界產(chǎn)生碰撞。2）對于傳感器感知的環(huán)境模型中的不確定性因素和路徑運行中出現(xiàn)的誤差，該規(guī)劃系統(tǒng)能夠?qū)ζ溥M(jìn)行及時的處理。3）通過使機(jī)器人避開外界物體而使其對機(jī)器人的傳感器感知范圍的影響降到最小。4）該規(guī)劃系統(tǒng)可以依據(jù)人們的需求獲得最優(yōu)路徑。基于以上幾點要求，智能機(jī)器人路徑規(guī)劃中就會關(guān)聯(lián)到 4個問題：1）智能機(jī)器人怎樣才能從周圍的環(huán)境中獲取障礙物的信息和與其相關(guān)的其他信息。2）智能機(jī)器人怎樣基于外部及內(nèi)部的傳感器的信息來獲取其當(dāng)前位于地圖環(huán)境中的哪一個位置。3）智能機(jī)器人機(jī)怎樣確定它的下一步行動策略，依據(jù)當(dāng)前地圖中的信息和其處于當(dāng)前地圖的位置。4）智能機(jī)器人怎樣發(fā)出有效的驅(qū)動信號，促使智能機(jī)器人在預(yù)定的軌跡上移動。所以為了解決上述所提出的問題，要對對應(yīng)的 4個技術(shù)展開研究：1）自動定位技術(shù)。2）傳感技術(shù)。3）規(guī)劃和決策。4）運動控制。僅從機(jī)器人本身來考慮對于研究機(jī)器人的路徑規(guī)劃是不夠的，我們還需要研究環(huán)境的狀況。因此，以障礙物的狀態(tài)和環(huán)境模型來進(jìn)行分析，可以考慮以下4種情況：1）已知環(huán)境下的靜態(tài)障礙物的大小、形狀和位置對規(guī)劃系統(tǒng)的影響，并且其障礙物一定是靜止不動的。2）已知環(huán)境下的動態(tài)障礙物的大小、形狀和位置對規(guī)劃系統(tǒng)的影響，但是它與靜態(tài)不同，它的位置是動態(tài)可變的。3）對規(guī)劃系統(tǒng)來說，環(huán)境的狀況是部分未知的或者是未知的，其障礙物的形狀和大小是在那樣的，只要是靜態(tài)障礙物，它在環(huán)境中都是靜止不動的。4）對路徑規(guī)劃系統(tǒng)來說，環(huán)境事先是部分未知的或未知的，障礙物的形狀或是大小怎樣，只要是動態(tài)障礙物，其在環(huán)境中一定是可變的?？傊砸芯繖C(jī)器人路徑規(guī)劃這個問題，就是因為在我們的生活中，我們?yōu)榱颂岣吖ぷ餍?，為了讓機(jī)器人從起始點到達(dá)目標(biāo)點，即要過障礙物，又要讓其經(jīng)過的路徑最短，這樣既節(jié)省了時間，又節(jié)約了資源，而且對于工業(yè)上的各個方面都有很大的幫助，這就是為什么我們要研究這個課題的原因?！∫苿訖C(jī)器人路徑規(guī)劃的原理　基本原理機(jī)器人學(xué)中很重要的一個方面就是路徑規(guī)劃問題，有很多的國內(nèi)和國外的參考文獻(xiàn)將上述問題稱為Path Planning。移動式機(jī)器人和關(guān)節(jié)式機(jī)械手是機(jī)器人研究的兩個不同的方向。因此從空間這個方面來看，基本可以分為：1)依據(jù)C空間，即構(gòu)形空間(configuration space)的拓?fù)浞ê蛶缀畏ǎ?)人工勢場法，該法依據(jù)笛卡爾的直角坐標(biāo)空間。笛卡爾的直角坐標(biāo)空間經(jīng)常稱為局部方法，人工勢場法經(jīng)常被人們稱為全局方法。與從空間方面不同，以機(jī)器人獲取周圍環(huán)境信息的多少，大致可以分為：1)機(jī)器人對周圍的環(huán)境信息基本不熟悉，就連周圍障礙物的幾何性質(zhì)和位置都不了解；2)機(jī)器人對周圍的環(huán)境信息基本不熟悉或者是只知道一部分，只能借用傳感器在線地探測機(jī)器人的移動環(huán)境的信息，以此方法來獲得障礙物的幾何性質(zhì)和位置等信息，所以，上述的規(guī)劃方法可以隨時對周圍環(huán)境信息的采集以及機(jī)器人所處環(huán)境模型的動態(tài)信息進(jìn)行更正和更新；3)機(jī)器人周圍的環(huán)境信息中存在某種障礙物，其能夠以某種可知或可預(yù)知的方法來不斷移動，這就是所謂的動態(tài)障礙物。　相關(guān)定義為了敘述方便, 給出如下定義和約束條件：定義1 ?g∈A，g不∈S則將g稱為可用的柵格，可行柵格集就是由所有可用的的柵格組成的，可以將其以FS作為標(biāo)記；?g∈A, g∈S此時可將g稱為障礙物（即障礙柵格），所以，障礙柵格集就是指由所有的障礙柵格所組成的，記為NFS。 即A = FS∪NFS。定義2兩個柵格之間連線的長度指任意兩個柵格之間的距離，稱為dist（gi (xi,yi ), gj(xj, yj)），其中g(shù)i，gj∈A，i,j∈C。：dist（gi (xi, yi), gj(xj, yj)）= （xixj）2+（yiyj）2 (3)定義3 ARi={g|g∈A,d(g,gi)≤L，i∈C}稱為柵格gi處的鄰域，其中L={1，2}。定義4 BRi={g|g∈A,d(g,gi)≤L39。，i∈C}，那么，可知柵格gi處的視野域即為BRi，其中L39。={2,22}。定義5 很多個柵格所構(gòu)成的集合{gi1, gi2, gi2,....., gin}，其中將SS記為{ij|1≤j≤n,ij∈C}，gk∈FS(k∈SS)，并且滿足dist(gij,gij+1)=1或者dist(gij,gij+1)= 2，則此集合表示一條路徑，而且gk為此可行路徑上的一個路徑點。定義6 tabuit為第i個粒子在t時刻已走柵格位置的集合，稱為禁忌集合，防止粒子重復(fù)走某一個柵格。其中tabui0表示初始時刻第i個粒子已走柵格位置的集合，即tabui0為空集。定義7 gigj(i,j∈C,gi,gj∈FS) 稱為柵格gi gj的中心線?！C(jī)器人位置編碼方法在PSO算法中，第i 個微粒的位置Xi=(Xi1,Xi2,Xi3,……,XiD)。在本文中，假定柵格gi處的視野域為BRi，其中的柵格數(shù)為m。此視野域中存在某一條路徑{gi1, gi2, gi2,....., gin}，其中n≤m，gk∈FS(k∈SS)。則編碼方法為{(xij)|1≤j≤m,且當(dāng)j∈SS, xij=1,否則xij=0}。如圖4所示，(其中陰影部分表示障礙柵格)，假設(shè)某一條局部路徑為{1, 7, 8, 13, 18, 19, 24, 25}, 則此條路徑對應(yīng)的粒子編碼為X=1000001100001000011000011。這樣，每一位置向量都表示了一條或者多條路徑。因此，粒子的維數(shù)由某時刻柵格gi處視野域BRi中柵格總數(shù)m決定，因此整個路徑規(guī)劃過程中粒子群的維數(shù)是可變的。使用這種方式進(jìn)行編碼，保證了每一時刻所有的粒子都是同維的，因而粒子群的位置和速度向量均是定長的。12345678910111213141516171819202122232425圖4 粒子群編碼方法示例　初始種群的產(chǎn)生對于智能機(jī)器人的初始路徑(初始位置)的產(chǎn)生是這樣定義的：每次通過當(dāng)前位置確定下一個柵格的位置，等到找到所有到達(dá)目標(biāo)點的柵格后，然后將這些柵格連起來產(chǎn)生一條初始路徑[ 11]。因此，怎樣搜索到下一個柵格稱為初始種群產(chǎn)生的關(guān)鍵一步。從柵格gi(gi∈FS,i∈C)出發(fā)，設(shè)ARi為它的鄰域，視野域為BRi，此時能夠選擇的下一個節(jié)點gj(j∈C) 必須要滿足條件gj∈ARi且gj∈FS, 此時除去如圖5所示的那種情況(其中障礙柵格有黑色部分表示)，意思就是移動機(jī)器人不可能從兩個障礙物柵格之間經(jīng)過。設(shè)選擇的下一個節(jié)點gj(j∈C) 與gi的中心連線從兩個障礙柵格之間經(jīng)過，即出現(xiàn)了圖5中所列的情況之一，將把節(jié)點gj記為NS。則式(4)可以計算下一個節(jié)點的柵格集合可選項。而本篇論文采用賭輪盤法來決定即將走的下一個路徑點，式(9)計算概率，得到：NGS={gj|j∈C, gj∈ARi, gj∈FS, gj≠NS} (4)Prob=1/|NGS| (5) 圖5 路徑排除情況　路徑規(guī)劃的規(guī)劃流程以第k個微粒為例，其產(chǎn)生初始位置的算法的完整步驟為以下6步:1)gi(gi∈FS,i∈C)作為當(dāng)前出發(fā)的初始柵格，由上述所做的定義可知當(dāng)前的tabuk0為空集。2)下一個路徑點的選擇范圍可由式(4)所決定,基于式(5)的公式計算概率的方式并且采用賭輪盤法在當(dāng)前位置gi的視野域BRi范圍內(nèi)，即將路過的節(jié)點由柵格gw承擔(dān)，即gw必須滿足w∈C，gw∈NGS且gw不∈tabuk。3)改變gi的當(dāng)前值做為本次所要選取的柵格gw，所以此次加入禁忌集合tabuk的柵格為gw。4)而越界可以依據(jù)上述已經(jīng)定義的視野域來進(jìn)行檢查。假設(shè)(xi,yi)為柵格gi對應(yīng)的橫縱坐標(biāo)，若滿足xi=1或者xi=5或者yi=1或者yi=5，則gi柵格被稱為邊界柵格，轉(zhuǎn)(5)否則轉(zhuǎn)(2)。5)通過上述方法將會產(chǎn)生移動機(jī)器人的原始節(jié)點集{gi1, gi2, gi2,....., gin}，其中n≤m。得到其對應(yīng)的位置向量XK可采用機(jī)器人位置編碼方法得到。6)對種群中所有粒子的初始位置均由上述算法產(chǎn)生，最后得到了種群初始位置?！÷窂揭?guī)劃所要達(dá)到的目的通過使用柵格法使用二進(jìn)制編碼方法對機(jī)器人的路徑進(jìn)行規(guī)劃，該方法所要實現(xiàn)的目的也是很有實際意義的，通過環(huán)境建模得到機(jī)器人運行路徑的模型，最后根據(jù)位置編碼的方法，得到機(jī)器人路徑的路線。對機(jī)器人進(jìn)行路徑規(guī)劃的目的就是使機(jī)器人最終繞過障礙物到達(dá)目標(biāo)點，并且從起始點到達(dá)目標(biāo)點的路徑長度最短。這樣既可以節(jié)約時間，而且可以提高機(jī)器人的運行效率，同時對我們的實際生活也會有所啟發(fā)，促使我們做出更深入的研究。　路徑規(guī)劃的問題描述和建模智能機(jī)器人路徑規(guī)劃實際上是將機(jī)器人智能化的一項比較重要的科學(xué)技術(shù)，采用該項技術(shù)可以使移動機(jī)器人的工作效率大大提高。路徑規(guī)劃是指依據(jù)規(guī)定的性能指標(biāo)來尋找一條從起始位置到達(dá)目標(biāo)位置的無碰撞路徑，而且這條路徑或者最優(yōu)或者近似最優(yōu)，所以要實現(xiàn)智能機(jī)器人的路徑規(guī)劃，就必須首先完成以下兩個步驟：1） 建立移動機(jī)器人的環(huán)境模型；2） 確立路徑搜索的方法?！〗⒁苿訖C(jī)器人移動的環(huán)境模型建立環(huán)境模型就要將實際生活中的問題進(jìn)行抽象化處理后再建立相關(guān)的環(huán)境模型。我相信大家都知道在我們?nèi)粘Ｉ钪校覀兯鎸Φ氖挛锒际切蜗蟮臇|西，是我們能夠感受到和體會到的東西，但是當(dāng)我們研究一項課題的時候，我們不可能將其直接應(yīng)用到實際生活中的，我們要先給它建模，模擬其活動，所以在研究機(jī)器人路徑規(guī)劃時，我們就必須先對其進(jìn)行環(huán)境建模，模擬出其運行的路徑以及路徑中的障礙物。所謂環(huán)境建模就是合理而有效地表示移動機(jī)器人的工作空間(環(huán)境信息)。環(huán)境建模是移動機(jī)器人實現(xiàn)導(dǎo)航定位的基礎(chǔ)與前提。一個適當(dāng)?shù)沫h(huán)境模型有助于對環(huán)境的理解，有利于降低路徑規(guī)劃決策搜索空間的計算量，從而減小不必要的消耗。環(huán)境建模的方法紛繁復(fù)雜，在應(yīng)用于移動機(jī)器人路徑規(guī)劃方面，絕大多數(shù)是將實際的環(huán)境信息轉(zhuǎn)換為了圖的問題，進(jìn)而抽象為對環(huán)境空間的骨架圖進(jìn)行描述[4]。對于簡單的低維空間[12]環(huán)境模型的描述方法，可簡要總結(jié)為通過可視圖法，Voronoi圖法，柵格法[13]、自由空間法[14]等進(jìn)行描述。以下對著集中環(huán)境建模方法進(jìn)行介紹和比較：l 可視圖法有它的應(yīng)用條件：規(guī)劃中的機(jī)器人必須可以等效地看成一個活動點，而且還要保證可以完成對起始點、目標(biāo)點以及障礙物中的每一個頂點進(jìn)行連接的操作，同時要保證這些連線均不與障礙物相交，這就構(gòu)成一張無向圖，即為可視圖。顧名思義，可視圖法是基于障礙物頂點連線的，所以適用于多邊形多頂點的障礙物，不適用于無頂點的圓形障礙物。而它之所以應(yīng)用廣泛也是有原因的：它在求解最短路徑問題上比別的方法要簡單易懂很多。缺點也是顯而易見的，如果環(huán)境空間發(fā)生了變化，比如障礙物個數(shù)改變了，這樣就比較麻煩了，就不得不再從新構(gòu)造一張圖，也由此看出了它缺乏靈活性和實時性，而且位置誤差對機(jī)器人無碰撞安全行走的影響很大。l Voronoi圖法是對可視圖法的改進(jìn)，此方法有效地減少了搜索時間。它是俄國數(shù)學(xué)家Voronoi最早提出的，也因此而命名。出于安全性考慮，設(shè)計的Voronoi圖具有獨特的幾何特性。分兩種情況討論，如果障礙物可以看成質(zhì)點，那么機(jī)器人沿著障礙物的Voronoi邊行走而碰到障礙物的幾率是最小的；如果障礙物不能看成質(zhì)點，這時可采用擴(kuò)展的Voronoi圖理論進(jìn)行環(huán)境建模。相對于可視圖法，Voronoi圖法實時性較好，生成的路徑也比較平滑，但是它不能獲得最短路徑。l 在上世紀(jì)60年代柵格法應(yīng)運而生，并迅速在之后的移動機(jī)器人系統(tǒng)中得到實踐。柵格法用大小相等的矩形柵格均勻劃分環(huán)境空間，并對環(huán)境中的自由空間與障礙物進(jìn)行特別區(qū)分。它的優(yōu)點在于，處理障礙物的邊界時，避免了復(fù)雜的數(shù)學(xué)計算。作為一種有效的環(huán)境表示方法，柵格法越來越得到人們的重視，并表現(xiàn)出很好的發(fā)展前景。l 自由空間法首先把環(huán)境空間中的障礙物抽象為二維平面內(nèi)的各種凸多邊形，然后在這個空間內(nèi)構(gòu)造連通圖，即完成了自由空間法的環(huán)境建模。優(yōu)點主要表現(xiàn)在：即使環(huán)境空間發(fā)生局部變化，也不用重新設(shè)計規(guī)劃圖，因而表現(xiàn)出了靈活性。不足之處是：障礙物的密集度很大程度上會影響到程序的復(fù)雜性，而且它只能做到粗略地估計路程情況。Dijkstra[11]搜索算法對我的啟發(fā)：該算法運用起來非常簡單，如下圖，圖中有9個節(jié)點，分別代表機(jī)器人從起點到達(dá)終點所必須經(jīng)過的節(jié)點，該圖中任意兩個節(jié)點之間都標(biāo)有權(quán)值。假設(shè)機(jī)器人要從Node1到達(dá)Node9如果不使用任何優(yōu)化算法，那么該機(jī)器人有8條路徑可走，但是這8條路徑的長短都不一樣，有比較長的，有比較短的，而此時我們使用dijkstra搜索算法，就可以對每一條路徑的權(quán)值之和進(jìn)行比較，最終選擇權(quán)值之和最小的一條路徑，作為機(jī)器人從起點到達(dá)終點的最優(yōu)路徑，下圖中的紅色線條標(biāo)示的路徑就是我們要尋找的最優(yōu)路徑。圖6因此由上述dijkstra算法的啟示，我就考慮使用柵格法進(jìn)行環(huán)境建模，而且在柵格模型中使用Dijkstra 算法進(jìn)行路徑規(guī)劃, 可以一次規(guī)劃出從初始節(jié)點到其他所有節(jié)點的最短路徑, 但是同時存在計算量大、規(guī)劃時間長、擴(kuò)展節(jié)點個數(shù)多等缺點。在柵格模型中我們可以隨意規(guī)劃障礙物的位置，是路徑規(guī)劃常采用的方法。而本篇論文我采用的是柵格法，原因是其操作容易而且能夠達(dá)到所要的效果。使用柵格法所產(chǎn)生的環(huán)境建摸圖如下圖所示：網(wǎng)格賦值矩陣為：G1=[0 0 0 0 0 0 0 0 0 0 0 0 0 0 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。 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0。 0