機器人路徑規劃(二)

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

首頁上一頁 1 2 下一頁尾頁 2/2/2

相關論文


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

Tags：機器人路徑規劃

【收藏】【返回頂部】

日韩一区国产在线观看_亚洲999一在线观看www_久久欧美在线电影_97人人做人人人难人人做_欧美黄色成人网_91超碰在线免费观看_欧美在线xxx_国产有码在线一区二区视频_精品国产一区二区三_久久久久久久久久久av

機器人路徑規劃(二)