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