應用快速擴展隨機樹和人工魚群演算法及危險度於路徑規劃

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：58

、訪客IP：3.133.139.142

姓名

沈昱廷(Yu-Ting Shen) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

應用快速擴展隨機樹和人工魚群演算法及危險度於路徑規劃
(Application of the RRT&AFS algorithms with danger degree in path planning)

相關論文

★ 影像處理運用於家庭防盜保全之研究	★ 適用區域範圍之指紋辨識系統設計與實現
★ 頭部姿勢辨識應用於游標與機器人之控制	★ 智慧型機器人定位與控制之研究
★ 基於人工蜂群演算法之物件追蹤研究	★ 即時人臉偵測、姿態辨識與追蹤系統實現於複雜環境
★ 基於環型對稱賈柏濾波器及SVM之人臉識別系統	★ 改良凝聚式階層演算法及改良色彩空間影像技術於無線監控自走車之路徑追蹤
★ 模糊類神經網路於六足機器人沿牆控制與步態動作及姿態平衡之應用	★ 四軸飛行器之偵測應用及其無線充電系統之探討
★ 結合白區塊視網膜皮層理論與改良暗通道先驗之單張影像除霧	★ 基於深度神經網路的手勢辨識研究
★ 人體姿勢矯正項鍊配載影像辨識自動校準及手機接收警告系統	★ 模糊控制與灰色預測應用於隧道型機械手臂之分析
★ 模糊滑動模態控制器之設計及應用於非線性系統	★ 階層式模糊控制及其在倒三角體系統之應用

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

對於自走車來說，要如何從一個佈滿各種障礙物的環境中，找到一條合適的路徑，並確保自己能成功的從起始點到達目標點，且行經的路程要是最短的，是個值得研究的方向。
本篇文章提出一種結合人工魚群演算法(AFSA)和快速擴展隨機樹(RRT)的新型演算法。和過去傳統的人工魚群演算法用於規畫路徑不同的地方在於，它是藉由類似樹枝生長的方式來去增加延伸點，在數個增加的點相互比較後，選擇最佳的延伸點去當做下一條魚的移動位置。
這個方法改善了人工魚群演算法後期收斂時間慢、不易收斂於全體最佳解的缺點，加上基本的快速擴展隨機樹演算法每次在規畫路徑上並不是那麼穩定，所以本文就利用模擬快速擴展隨機樹演算法的方式去加入到人工魚群演算法，再配合危險度地圖觀念去有效閃避障礙物。
經過測試，我們可以由數據上顯示這個新式演算法比單一個人工魚群演算法或是快速擴展隨機樹演算法應用在路徑規劃上都好且更穩定，且路徑長度也能是最短的。

摘要(英)

In terms of self-propelled vehicles, how to find a suitable route from the environment filled with varied obstacles and how to ensure the target point from the starting point with the minimum passing away can be successfully reached is a direction worthy of research
In this thesis, the new algorithm in a combination of Artificial Fish Swarm Algorithm (AFSA) and Rapidly-Exploring Random Tree (RRT) is proposed. Compared with the traditional AFSA, the difference of the new algorithm in path planning is it is by similar branch growing up to increase extension points, and after the increase points are compared with each other, the best extension point is chosen as the point of the next moving fish.
The new algorithm improves the shortcomings of the later-period AFSA in slow convergence time and being hard to be converged in the optimal solution. In addition, the basic RRT algorithm is not so stable on each path planning, so in this paper, the simulation of the RRT algorithm is used to be included in AFSA, with the concept of danger degree map to effectively dodge obstacles.
After testing, it is shown that the data of the new algorithm on path planning are better than those of either AFSA or RRT and the path is the shortest.

關鍵字(中)

★ 人工魚群演算法
★ 自走車
★ 危險度地圖
★ 快速擴展隨機樹
★ 路徑規劃

關鍵字(英)

★ AFSA
★ Danger Degree Map
★ Rapidly-exploring Random Tree (RRT)
★ Path Planning
★ Self-propelled Vehicle

論文目次

目錄 IV
圖目錄 VII
表目錄 IX
第一章緒論 1
1.1 簡介 1
1.2 研究背景 2
1.3 文獻探討 3
1.4 主要貢獻 4
1.5 論文架構 5
第二章問題定義與敘述 6
2.1 定義路徑規劃的和其作用 6
2.2 全局路徑規劃&區域路徑規劃 7
2.3 路徑規劃方法 7
2.3.1 Dijkstra’s演算法 7
2.3.2 A*搜尋演算法 9
2.4 全局規劃路徑方法 11
2.5 局部路徑規劃方法 14
2.6 一般論文的自走車環境設定 16
2.7 本篇論文所使用的環境設定 19
第三章採用方法與分析 21
3.1 快速擴展隨機樹演算法(RRT) 21
3.1.1 傳統的快速擴展隨機樹 21
3.1.2 雙向擴展快速擴展隨機樹 24
3.2 人工魚群演算法(AFSA) 25
3.3 基本概念與其優缺點 26
3.4 人工魚群設置參數和行為描述 27
3.5 人工魚群各種參數對收斂性能的影響 31
第四章混合演算法改良路徑規劃 33
4.1 修正方法I 33
4.1.1 設計想法 33
4.1.2 適應函數與懲罰值的設計想法 36
4.2 修正方法II 40
4.2.1 如何選擇下個延伸點 40
4.2.2 修正方法II算法流程 41
4.3 AFSA結合RRT 45
4.3.1 延伸點選擇方式的改良 45
4.3.2 人工魚群加上快速搜索隨機樹成長演算法步驟 49
第五章實驗結果與討論 54
5.1 相關參數設定 54
5.2 AFSA+RRT混合型演算法細項討論 55
5.2.1 延伸點設定的多寡 55
5.2.2 產生延伸點之間疊代次數變化 56
5.3 在簡單地圖中與其他演算法比較 58
5.3.1 AFSA+RRT混和型演算法在簡單地圖中與其它 59
改良型PSO比較 59
5.3.2 AFSA+RRT混和型演算法在複雜地圖中與其它 63
改良型PSO比較 63
5.4 安全區和危險度機制的加入 67
5.5 動態環境測試 69
第六章總結與未來方向 71
6.1 結論 71
6.2 建議 72
參考文獻 73

參考文獻

[1] Q. Wu and B. Zeng, “Real-time globally optimized path planning in a dynamic environment,” IEEE International Conference on Intelligent Computation Technology and Automation, Vol.3, pp. 261-264, 2009.
[2] X. Ye, Y. Lei and H. Hon, “Design of intelligent mobile vehicle system and its global optimal path planning,” IEEE International Conference on Industrial Technology, pp. 1-5,21-24, 2008.
[3] A. T. Klesh, P. T. Kabamba and A.R. Girard, “Optimal Path planning for uncertain exploration,” American Control Conference, pp. 2421-2426, 2009.
[4] S. L. Valle, J. Kuffner. “Rapidly-exploring random trees: Progress and Prospects,” In Proceedings of Algorithmic and Computational Robotics: New Directions, pp. 293-308, 2001.
[5] J. Kennedy and R. Eberhart, "Particle Swarm Optimization," In Proceedings of IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.
[6] Q. Mal and X. Lei, “Application of Artificial Fish School Algorithm in UCAV Path Planning”, IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), pp.555-559, 2010.
[7] S. Tao, X. F. Xie , Y. Q. Sun and S. Y. Li, “Airplane Route Planning for Plan-Missile Cooperation Using Improved Fish-Search Algorithm”, 2009 International Joint Conference on Artificial Intelligence, pp. 853-856, 2009.
[8] K. Sugihara and J. Smith, “Genetic Algorithms for Adaptive Motion Planning of an Autonomous Mobile Robot,” In Proceedings of IEEE international Symposium on Computational Intelligence in Robotics and Automation, pp. 138-143, 1997.
[9] I. Ashiru, C. Czarnecki, and T. Routen, “Characteristics of a Genetic Based Approach to Path Planning for Mobile Robots,” J. Network and Computer Applications, Vol. 19, pp. 149-169, 1996.
[10] A. Coloni, M. Dorigo, V. Maniezzo, et a1. Distributed optimization by ant colonies. In Proceedimgs of the 1st European Confercnce on Artificial Life, pp. 134-142, 1991.
[11] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik 1, pp. 269-271, 1959.
[12] P. E. Hart, N. J. Nilsson, B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2), pp. 100-107, 1968.
[13] P. E. Hart, N. J. Nilsson, B. Raphael, “Correction to A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” SIGART Newsletter 37, pp. 28-29, 1972.
[14] R. Dechter, P. Judea, “Generalized best-first search strategies and the optimality of A*,” Journal of the ACM 32 (3), pp. 505-536, 1985.
[15] http://theory.stanford.edu/~amitp/GameProgramming
[16] D. Fox, W. Burgard, and S. Thrun, “Markov localization for mobile
robots in dynamic environments,” Journal of Artificial Intelligence Research, Vol. 11, pp. 391-427, 1999.
[17] F. Dellaert, D. Fox, W. Burgard and S. Thrun, “Monte Carlo localization for mobile robots,” IEEE International Conference on Robotics and Automation, Vol. 2, pp. 1322-1328, 1999.
[18] S. Thrun, D. Fox, W. Burgard and F. Dallaert, “Robust Monte Carlo Localization for Mobile Robots,” Artificial Intelligence, Vol. 128, pp. 99-141, 2001.
[19] M. B. Metea. “Planning and intelligence autonomous land vehicles using hierarchical terrain representation,” In Proceedings of IEEE International Conference on Robotics and Automation, pp. 1947-1952, 1987.
[20] E. Hernandez, M. Carreras, J. Anitich, P. Ridao, and A. Ortiz, “A topologically guided path planner for an AUV using homotopy classes,” 2011 IEEE International Conference on Robotics and Automation, pp.2337-2343, 2011.
[21] J. C. Latombe, Robot Motion Planning. Norwood, MA, Kluwer Academic Publishers, 1991.
[22] J. A. Janet, R. C. Luo, M. G. Kay, “The essential visibility graph: an approach to global motion planning for autonomous mobile robots,” IEEE International Conference on Robotics and Automation, Vol. 2, pp. 21-27, 1995.
[23] W. Adiprawita, A.S. Ahmad, J. Sembiring and B.R. Trilaksono, “New resampling algorithm for particle filter localization for mobile robot with 3 ultrasonic sonar sensor,” International Conference on Electrical Engineering and Informatics, pp.1-6, 2011.
[24] W. Hong, C. Zhou and Y. Tian, “Robust Monte Carlo Localization for humanoid soccer robot”, IEEE/ASME International Conference on Advanced Intelligent Mechatronics, pp.934-939, 2009.
[25] O. Takahashi, R. J. Schilling. “Motion Planning in a plane using gene-realized voronoi diagrams,” IEEE Trans Robotics and Automation, pp.143-150, 1989.
[26] Khatib, “Real-time obstacle for manipulators and mobile robot,” International Journal of Robotic Research, pp. 90-98, 1986.
[27] M. A. Goodrich, Potential Fields Tutorial, 2002. Available at：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.3259&rep=rep1&type=pdf
[28] N. H. C. Yung and Y. Cang, “An Intelligent Mobile Vehicle Navigator Based on Fuzzy Logic and Reinforcement Learning,” IEEE Trans on Sys Man and Cybern. Part B: Cyberneics, pp, 314-320, 1999.
[29] R. Fierro, F. L. Lewis. “Control of nonholonomic mobile robot using neural networks,” IEEE Transactions on Neural Networks, pp.589-600, 1998.
[30] W Li, G. Y. Wang. “Application of improved PSO in mobile robotic path planning,” IEEE Intelligent Computing and Integrated Systems, pp. 45-48, 2010.
[31] S. M. Lavalle, J. J. Kuffner. “Randomized kinodynamic planning,” In Proceedings of 1999 IEEE International Conference on Robotics and Automation, Vol.1, pp.473,479, 1999.
[32] 嚴蔚敏,吳偉民,數據結構.北京:清華大學出版社,2008.
[33] Q. Wang, W. Wang, Y. Li. “A multi-RRT based hierarchical path planning method,” International Conference of IEEE Communication Technology, pp.971-975, 2012.
[34] Y. Xue, G. Tian and B. Huang, “Optimal Robot Path Besed on Danger Degree Map,” IEEE International Conference on Automation and Logistics, pp.1040,1045, 5-7, 2009.
[35] 陳依璟，「自走車之路徑規劃與位置追蹤」，國立中央大學，碩士論文，民國101年。
[36] 姜俊甫，「在室內環境中使用ALC-PSO演算法與危險度指標改良RRT路徑規劃」，國立中央大學，碩士論文，民國102年。
[37] 梁嘉晉，「混和粒子群與人工魚群演算法於奈米研磨製程參數最佳化之研究」，國立雲林科技大學，碩士論文，民國102年。

指導教授

鍾鴻源(Hung-Yuan Chung)

審核日期

2015-8-17

推文