機(jī)器人路徑規(guī)劃(二)

本論文在其他論文欄目，由論文格式網(wǎng)整理,轉(zhuǎn)載請(qǐng)注明來(lái)源www.donglienglish.cn,更多論文,請(qǐng)點(diǎn)論文格式范文查看
http://www.91paofun.net/Article/HardTech/ControlTech/200412/248.html
黃玉芳　趙京. 具有容錯(cuò)性能的冗余度機(jī)器人軌跡規(guī)劃
http://www.wenloo.com/WenLooPage174353-7.htm
董玉成陳義華 .基于螞蟻算法的移動(dòng)機(jī)器人路徑規(guī)劃
http://www.madio.net/Soft/Class8/Class73/Class139/200411/2189.html
李團(tuán)結(jié) , 張學(xué)鋒 , 陳永琴.一種全向滾動(dòng)球形機(jī)器人的運(yùn)動(dòng)分析與軌跡規(guī)劃
http://vip.ilib.cn/A-xadzkjdx200701007.html
佚名. 我國(guó)的仿人形機(jī)器人研究
http://brilliantwangym.bokee.com/2514668.html
B、選擇“雅虎”http://www.yahoo.com.cn/查找相關(guān)網(wǎng)頁(yè)：
查找到相關(guān)網(wǎng)頁(yè)數(shù)約：777,480篇。檢索與本課題相關(guān)的文獻(xiàn)為:
1. 王科俊，徐晶,王磊，張燕. 基于可拓遺傳算法的機(jī)器人路徑規(guī)劃
http://web.gdut.edu.cn/~extenics/lw15.htm
2. 佚名.基于遺傳算法的足球機(jī)器人路徑規(guī)劃
http://blog.csdn.net/aqua4/archive/2006/04/07/654217.aspx
3. 王挺.基于極坐標(biāo)、柵格法和模糊方法的路徑規(guī)劃
http://hi.baidu.com/rayen/blog/item/f0f4baeca2337b2662d09f29.html
秦元慶, 孫德寶, 李寧, 馬強(qiáng).基于粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃
http://www.sia.ac.cn/qikan/front/viewone.php?id=851&Language=0&ClassId=0
佚名. 基于模糊邏輯的移動(dòng)機(jī)器人無(wú)碰撞路徑規(guī)劃(dzx23)
http://www.studa.net/dianzijixie/050608/172439.html
C、選擇“網(wǎng)易”http://www.163.com/查找相關(guān)網(wǎng)頁(yè)：
查找到相關(guān)網(wǎng)頁(yè)數(shù)約：8900篇。檢索與本課題相關(guān)的文獻(xiàn)為:
. 黃祎, 孫德寶, 秦元慶.基于粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃
http://www.4bao.net/A-bgzdh200604023.html
2. 朱慶保.復(fù)雜環(huán)境下的機(jī)器人路徑規(guī)劃螞蟻算法
http://ckrd.cnki.net/grid20/detail.aspx?dbname=cjfd2006&filename=moto200604014
佚名.基于模糊邏輯的移動(dòng)機(jī)器人無(wú)碰撞路徑規(guī)劃(dzx23)
http://www.lwhoo.com/mac/11728503698117.html
霍迎輝，張連明.一種移動(dòng)機(jī)器人的路徑規(guī)劃算法
http://91tech.net/Article/SoftTech/TheoryTech/200501/312.html
張曉麗.基于微分進(jìn)化算法的機(jī)器人路徑規(guī)劃方法
http://www.cczzdd.com/viewthread.php?tid=67617
朱慶保, 張玉蘭.基于柵格法的機(jī)器人路徑規(guī)劃蟻群算法
http://www.4bao.net/A-jqr200502008.html
徐晶.基于可拓遺傳算法的機(jī)器人路徑規(guī)劃
http://youth.hrbeu.edu.cn/exhibition/Show.asp?id=394
四、評(píng)估檢索結(jié)果：
通過(guò)這門(mén)課程的學(xué)習(xí)，讓我學(xué)會(huì)了如何通過(guò)檢索的方式查出我所需要的東西，只要按著步驟做就能得出想要結(jié)果。我在完成這次作業(yè)的過(guò)程中遇到了很多的問(wèn)題，主要有以下幾點(diǎn)：
1.在手工檢索時(shí)找相關(guān)的資料挺難找到的，也許是所找的范圍挺小，還是沒(méi)有找對(duì)地方用了很久的時(shí)間。在査外文相關(guān)的內(nèi)容時(shí)，困難更是很大，不但在寫(xiě)相關(guān)內(nèi)容是太難書(shū)寫(xiě)，而且更主要的是所需相關(guān)內(nèi)容找不上，英語(yǔ)底子太薄弱，在這里明顯就明顯得感覺(jué)到好無(wú)能為力啊。
2.深有體會(huì)地感覺(jué)到這門(mén)課在檢索的格式上要求很嚴(yán)格，必須按著規(guī)定來(lái)做，使操作起來(lái)覺(jué)得挺麻煩的，這就是所謂沒(méi)有規(guī)矩不成方圓的道理吧。
3.利用中文數(shù)據(jù)庫(kù)檢索相關(guān)內(nèi)容時(shí)，由于平時(shí)沒(méi)有接觸過(guò)，對(duì)其的操作挺生疏的，但是只要掌握了方法要找所需內(nèi)容是很快捷方便的，利用它能夠找到平時(shí)想找都很難找上的好用的資料，這點(diǎn)是我們這在大學(xué)里所能感受到的很有利的資源，聽(tīng)老師給我們解說(shuō)，只有通過(guò)學(xué)校的網(wǎng)絡(luò)才能進(jìn)到這些數(shù)據(jù)庫(kù)網(wǎng)站，在外面是根本進(jìn)不去的，除非是你交費(fèi)的。可見(jiàn)，這個(gè)資源的寶貴之處了，對(duì)于我們學(xué)生來(lái)說(shuō)，最值得一提的是它們對(duì)我們來(lái)說(shuō)是免費(fèi)的！好處多多吧！要倍加利用好這個(gè)資源！
4.在完成這個(gè)綜合檢索時(shí)，遇到了挺多的困難，通過(guò)問(wèn)同學(xué)他們不厭其煩的給我解說(shuō)，是我學(xué)到了很多，我很感謝他們，使那些原來(lái)看起來(lái)根本就無(wú)從下手的東西變得簡(jiǎn)單起來(lái)。
5.學(xué)了這門(mén)課程，由以前幾乎不太會(huì)搜索資料到現(xiàn)在感覺(jué)挺輕松的就能找到所需的資料，心里上都覺(jué)得有種成就感了，能有今天的進(jìn)步最主要的就事帶我們課的周春宏老師，沒(méi)有他的特別細(xì)心和和有耐心的教我們，我想是不會(huì)有今天滿足感了。感謝您——周老師！！
五、課程論文：
機(jī)器人路徑規(guī)劃中的雙向Dijkstra二叉樹(shù)算法
(Bi-directional Dijkstra with Binary Tree Sorted Algorithmin Robot Path Plan)
作者：周躦，王騰飛，戴光明
(中國(guó)地質(zhì)大學(xué)計(jì)算機(jī)學(xué)院，武漢430074)
摘要：在分析現(xiàn)有路徑規(guī)劃和碰撞檢測(cè)方法的基礎(chǔ)上，提出了一種新的機(jī)器人路徑規(guī)劃方法：雙向Dijkstra二叉樹(shù)算法。在機(jī)器人路徑規(guī)劃中應(yīng)用傳統(tǒng)的Dijkstra算法時(shí)間復(fù)雜度是O(n2)，應(yīng)用該文提出的算法進(jìn)行路徑規(guī)劃的時(shí)間復(fù)雜度為O(nlog2n)。通過(guò)一些數(shù)據(jù)的檢測(cè)，驗(yàn)證了在機(jī)器人路徑規(guī)劃中，尤其是在測(cè)試數(shù)據(jù)較多的情況下，該算法可以有效提高效率。
關(guān)鍵詞：機(jī)器人路徑規(guī)劃；最短路徑；雙向Dijkstra；二叉樹(shù)
中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A
ZHOU Zuan,WANG Tengfei,DAI Guangming
(School of Computer,China University of Geosciences,Wuhan 430074)
【Abstract】On the basis of analysis of current path plan methods and collision examining methods,a new robot path plan method is put forward:
bi-directional Dijkstra with binary tree sorted algorithm.It is well known that Dijkstra algorithm solves the path plan problem in time O(n2).As an
improvement on Dijkstra algorithm,because it begins from start point and end point at one time when it executes the algorithm,and sorts the set of
the points which have not been marked by binary tree,the algorithm solves path planning problem in time O(nlog n).And the enhancement on the
efficiency in robot path plan with the algorithm has been proved by testing some data,especially in the situation where the number of testing data is
very large.
【Key words】Robot path plan;Shortcut;Bi-directional Dijkstra;Binary tree
在機(jī)器人路徑規(guī)劃中，常常需要考慮給定兩點(diǎn)S、T和若干障礙物，要求找出機(jī)器人從S到T并避開(kāi)所有障礙物的最短路徑，也就是所謂的ESPO問(wèn)題。對(duì)于二維的ESPO問(wèn)題，可以將兩點(diǎn)和各障礙物之間關(guān)系轉(zhuǎn)換成帶權(quán)圖，從而將二維ESPO問(wèn)題轉(zhuǎn)化成帶權(quán)圖的最短路徑問(wèn)題。最短路徑算法有很多，包括圖論基本方法、啟發(fā)式搜索方法、動(dòng)態(tài)規(guī)劃方法、神經(jīng)網(wǎng)絡(luò)方法等。傳統(tǒng)的最短路徑算法主要有Floyd算法和迪杰斯特拉(Dijkstra)算法等。其中Floyd算法用于計(jì)算網(wǎng)絡(luò)中每一對(duì)頂點(diǎn)之間的最短路徑；Dijkstra算法用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其它節(jié)點(diǎn)的最短代價(jià)路徑。Dijkstra算法由于適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓阅芊€(wěn)定，因此在計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)渎窂竭x擇得到廣泛的應(yīng)用。但是它們的時(shí)間復(fù)雜度與圖的頂點(diǎn)數(shù)的平方成正比，在頂點(diǎn)較多的情況下就難以滿足實(shí)際運(yùn)算的需要。比如在我們的研究過(guò)程中，當(dāng)機(jī)器人要避開(kāi)的障礙物較多時(shí)，將障礙物的信息轉(zhuǎn)化為無(wú)項(xiàng)帶權(quán)圖的時(shí)候頂點(diǎn)數(shù)目較多，運(yùn)行所需的時(shí)間就較多。本文提出的雙向Dijkstra二叉樹(shù)算法就是為解決上述問(wèn)題對(duì)Dijkstra算法的一種改進(jìn)，經(jīng)實(shí)驗(yàn)證明，在頂點(diǎn)數(shù)較多的圖上是一種很理想的最短路徑算法。
1.經(jīng)典Dijkstra算法簡(jiǎn)介
Dijkstra算法用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其它節(jié)點(diǎn)的最短代價(jià)路徑，它是按路徑長(zhǎng)度遞增的次序來(lái)產(chǎn)生最短路徑的算法。
1.1 Dijkstra算法的網(wǎng)絡(luò)表示方法
交通網(wǎng)絡(luò)圖中的路段和節(jié)點(diǎn)，可以抽象為邊和頂點(diǎn)，這樣整個(gè)交通網(wǎng)絡(luò)就抽象為一張圖。對(duì)于一張N個(gè)節(jié)點(diǎn)的圖，用一個(gè)二維C[N][N]數(shù)組存儲(chǔ)網(wǎng)絡(luò)中的數(shù)據(jù)，若節(jié)點(diǎn)I與節(jié)點(diǎn)J之間有邊，則C[I][J]中存儲(chǔ)節(jié)點(diǎn)I到節(jié)點(diǎn)J的邊的權(quán)值。
1.2 Dijkstra算法的實(shí)現(xiàn)標(biāo)號(hào)方法
這是大多數(shù)最短路徑算法的核心過(guò)程，Dijkstra算法就是采用這種方法進(jìn)行最短路徑搜索。下面是Dijkstra算法的實(shí)現(xiàn)流程。其中數(shù)組D[i]記錄當(dāng)前節(jié)點(diǎn)I到源點(diǎn)S的最短路徑。初始化D[i]=MaxInt，D[s]=0；mark[i]是個(gè)布爾數(shù)組，若已經(jīng)求得從S到I的最短路徑，則將mark[i]=true，對(duì)于所有的I，初始化mark[i]=flase；C[i][j]表示圖中從節(jié)點(diǎn)I到節(jié)點(diǎn)J的路徑長(zhǎng)度，如果從I到J沒(méi)有通路，則C[i][j]=MaxInt。(1)While mark[t]=flase do begin(2)選取節(jié)點(diǎn)u，滿足u=min{D[x]|其中mark[x]=false}，(3)for每個(gè)從u出發(fā)的節(jié)點(diǎn)v do(4)D[v]<-min{D[v]，D[u]+c[u][v]};(5)mark[u]<-true;(6)end while
2.雙向Dijkstra二叉樹(shù)算法
2.1使用二叉樹(shù)對(duì)當(dāng)前最優(yōu)節(jié)點(diǎn)選擇的改進(jìn)
從上述經(jīng)典Dijkstra算法流程可知，該算法的效率取決于算法的(2)～(4)步，為了提高效率，可以使用優(yōu)先隊(duì)列來(lái)存儲(chǔ)滿足mark[x]=false的所有節(jié)點(diǎn)。通常，可以用二叉樹(shù)來(lái)表示這個(gè)優(yōu)先隊(duì)列。同時(shí)，規(guī)定二叉樹(shù)每個(gè)結(jié)點(diǎn)的優(yōu)先級(jí)高于其自己子節(jié)點(diǎn)的優(yōu)先級(jí)，具體到這個(gè)問(wèn)題來(lái)說(shuō)，就是D[i]值小于子節(jié)點(diǎn)值。使用數(shù)組T[n]來(lái)存儲(chǔ)二叉樹(shù)，n為數(shù)組元素個(gè)數(shù)，節(jié)點(diǎn)T[i]的左右子樹(shù)分別為T(mén)[2i]和T[2i+1]，則節(jié)點(diǎn)T[1]為D[i]中最小的元素對(duì)于二叉樹(shù)定義如下操作：
Push(x)：往優(yōu)先隊(duì)列后面插入一個(gè)新節(jié)點(diǎn)，并不停地與比其優(yōu)先級(jí)低的父節(jié)點(diǎn)換位，稱為向上調(diào)整，使得二叉樹(shù)仍然滿足“父節(jié)點(diǎn)優(yōu)先級(jí)低于子節(jié)點(diǎn)優(yōu)先級(jí)”的性質(zhì)。
Pop()：刪除優(yōu)先隊(duì)列的根結(jié)點(diǎn)，此節(jié)點(diǎn)即為當(dāng)前最優(yōu)節(jié)點(diǎn)。將最后一個(gè)葉子節(jié)點(diǎn)作為新的根節(jié)點(diǎn)，然后不停地與比其優(yōu)先級(jí)高的子節(jié)點(diǎn)交換，稱為向下調(diào)整。
Update(i)：先將節(jié)點(diǎn)i不停地向上調(diào)整，然后不停地向下調(diào)整。這是為了實(shí)現(xiàn)算法第4步優(yōu)先隊(duì)列中節(jié)點(diǎn)優(yōu)先級(jí)改變時(shí)，對(duì)節(jié)點(diǎn)的調(diào)整，使其仍然滿足性質(zhì)。由于每次都將新節(jié)點(diǎn)都加在數(shù)組T末尾，因此二叉樹(shù)高度始終為log2n。調(diào)整時(shí)最壞是將一個(gè)節(jié)點(diǎn)從最低層升到最高
層，所以最壞情況下需進(jìn)行l(wèi)og2n次操作，因此上述操作時(shí)間復(fù)雜度為O(log2n)。所以使用優(yōu)化隊(duì)列的Dijkstra算法復(fù)雜度為O(nlog2n)，比經(jīng)典算法有了較大的改進(jìn)。
2.2雙向Dijkstra二叉樹(shù)算法
(1)算法思路
通常在基本Dijkstra算法中，要找到到終點(diǎn)的最短路徑，必須先找到所有比終點(diǎn)最短路徑短的所有最短路徑，在頂點(diǎn)分布均勻的情況下，所要找到的最短路徑條數(shù)和兩頂點(diǎn)之間的距離的平方成正比。如果從兩個(gè)端點(diǎn)同時(shí)開(kāi)始搜索，到相遇時(shí)(即從兩個(gè)端點(diǎn)都找到了到達(dá)同一頂點(diǎn)的最短路徑)所要找到的最短路徑條數(shù)只有基本Dijkstra算法的一半，然后再
從結(jié)果中找出最短路徑，從而在圖的頂點(diǎn)較多時(shí)能大幅度縮短搜索時(shí)間。若起點(diǎn)為S，終點(diǎn)為T(mén)，搜索時(shí)在節(jié)點(diǎn)K相遇，則SK＋KT為從S到T的一條路徑，然后與已保存的最短路徑比較，看是否要更優(yōu)，是則保存為最短路徑。若搜索時(shí)當(dāng)前路徑長(zhǎng)度長(zhǎng)于最短路徑，舍棄該節(jié)點(diǎn)，不進(jìn)行拓展。
(2)算法實(shí)現(xiàn)
1)圖的表示
定義一個(gè)數(shù)據(jù)類型：typedef struct ttype{int id;//與其相連的節(jié)點(diǎn)號(hào)double cost;//邊的權(quán)值struct ttype*next;//下一個(gè)相鄰的節(jié)點(diǎn)信息}vtype; Vtype map[maxnode];//map[i]表示第I個(gè)節(jié)點(diǎn)的信息
2)算法過(guò)程
配合上述的二叉樹(shù)算法，本文的雙向Dijkstra二叉樹(shù)算法如下。使用一個(gè)Flag[n]表，表示節(jié)點(diǎn)n是否已經(jīng)被訪問(wèn)過(guò)。Flag[i]初始為0。1表示被正向訪問(wèn)過(guò)，-1表示被反向訪問(wèn)過(guò)。建兩個(gè)堆f、b，分別代表從正、反向計(jì)算時(shí)的優(yōu)先隊(duì)列。堆初始時(shí)各只有一個(gè)元素，分別為計(jì)算的出發(fā)點(diǎn)s和t。While(f、b不都為空)do beginIf(f不為空)then beginOut<-f.pop();If(out花費(fèi)大于最短路徑長(zhǎng)度)then不處理節(jié)點(diǎn)outElse if(out逆向計(jì)算時(shí)已經(jīng)被訪問(wèn)過(guò))then比較并更新最短路徑Else begin標(biāo)記Flag，out被正向計(jì)算訪問(wèn)過(guò)For每個(gè)從out出發(fā)可到達(dá)的節(jié)點(diǎn)do更新優(yōu)先隊(duì)列的值End begin End if End beginIf(b不為空)then begin Out<-b.pop();If(out花費(fèi)大于最短路徑長(zhǎng)度)then不處理節(jié)點(diǎn)out Else if(out反向計(jì)算時(shí)已經(jīng)被訪問(wèn)過(guò))then比較并更新最短路徑 Else begin標(biāo)記Flag[out]被逆向計(jì)算訪問(wèn)過(guò)For每個(gè)從out出發(fā)可到達(dá)的節(jié)點(diǎn)do更新優(yōu)先隊(duì)列的值End begin End if End begin End while 輸出最短路徑
(3)時(shí)間復(fù)雜度分析
本算法從兩個(gè)方面降低經(jīng)典算法的時(shí)間復(fù)雜度：(1)兩端開(kāi)始的搜索，每一端要訪問(wèn)的節(jié)點(diǎn)平均不會(huì)超過(guò)n/2；(2)在標(biāo)記完一個(gè)節(jié)點(diǎn)并更新為標(biāo)記節(jié)點(diǎn)到起點(diǎn)或終點(diǎn)的路徑長(zhǎng)度后，要從未標(biāo)記節(jié)點(diǎn)中選取到起點(diǎn)或終點(diǎn)路徑長(zhǎng)度最短的頂點(diǎn)。本算法采取優(yōu)先隊(duì)列的方法，與經(jīng)典算法相比，只需要O(log2n)時(shí)間。綜上所述，本文算法的時(shí)間復(fù)雜度為2O (n logn)，所以，總的時(shí)間花費(fèi)要比O(n2)少很多。
3.算法檢驗(yàn)
根據(jù)以上介紹的方法，筆者在VC中實(shí)現(xiàn)了雙向Dijkstra二叉樹(shù)算法，數(shù)據(jù)是隨機(jī)生成的。
4.結(jié)論
本文提出的雙向Dijkstra二叉樹(shù)算法原理簡(jiǎn)單，實(shí)現(xiàn)方便，雖然這種方法增加了其它開(kāi)銷，但在頂點(diǎn)較多的圖上，效果很明顯，是一種優(yōu)秀的最短路徑求解方法。
5 .總結(jié)
在基于分布構(gòu)件的軟件中，為了使得軟件模型能夠使用工具自動(dòng)地轉(zhuǎn)換為性能模型，必須提供一種將性能相關(guān)信息標(biāo)注在軟件模型中的方法。現(xiàn)有的標(biāo)注方法不適用于分布化、構(gòu)件化應(yīng)用的特征，本文提出了擴(kuò)展CCPE Profile以及基于CCPE Profile的軟件模型標(biāo)注方法，以滿足分布構(gòu)件化軟件模型轉(zhuǎn)換成性能模型的需要。本方法使性能預(yù)測(cè)過(guò)程與軟件開(kāi)發(fā)過(guò)程集成起來(lái)，以減小性能預(yù)測(cè)周期和代價(jià)。
參考文獻(xiàn):
[1] 周培德.計(jì)算幾何－－算法分析與設(shè)計(jì)[M].北京:清華大學(xué)出版社,2005-04.
[2] 司連法,王文靜.快速Dijkstra最短路徑優(yōu)化算法的實(shí)現(xiàn)[J].測(cè)繪通報(bào),2005,(8):15.
[3] 康志諭,王明生.城市交通網(wǎng)中最短路徑算法及其實(shí)現(xiàn)[J].國(guó)防交通工程與技術(shù),2005,(1):57.
[4] 王曉東,陳國(guó)龍,林柏鋼.網(wǎng)絡(luò)最短路問(wèn)題的改進(jìn)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2002,23(9).
[5] 李寧寧,劉玉樹(shù).改進(jìn)的Dijkstra算法在GIS路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)與現(xiàn)代化,2004,(9):12.
[6] 孟正大,王小忠.機(jī)器人無(wú)碰撞路徑規(guī)劃方法研究及實(shí)現(xiàn)[J].華中科技大學(xué)學(xué)報(bào),2004,32(增刊).

首頁(yè) 上一頁(yè) 1 2 下一頁(yè) 尾頁(yè) 2/2/2

相關(guān)論文


上一篇：DDS的幅度量化雜散分析	下一篇：一種基于窗函數(shù)法設(shè)計(jì)FIR數(shù)字濾波..

Tags：機(jī)器人路徑規(guī)劃

【收藏】【返回頂部】