在室內環境中使用ALC-PSO演算法與危險度指標改良RRT路徑規劃

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：37

、訪客IP：52.14.118.57

姓名

姜俊甫(Jyun-Fu Jiang) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

在室內環境中使用ALC-PSO演算法與危險度指標改良RRT路徑規劃
(Using ALC-PSO Algorithm to Improve RRT Path Planning in Indoor Environments with Danger Degree)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在移動式機器人中，要如何在有障礙物的環境中，規劃出一條合適的無障礙物的路徑，讓移動機器人能從起始點移動到達目標點且確保路徑是最短的，是一個很重要議題。
本文提出一種最佳路徑規劃方法於移動機器人，利用改良式粒子群演算法也就是老齡化領導者與挑戰者粒子群演算法(ALC-PSO)來模擬快速搜尋隨機樹(RRT)，與過去傳統粒子群演算法用於路徑規劃方法有所不同，在本文是藉由樹枝生長的方式來增加延伸點，在我們比較之後，選擇最好的延伸點加到粒子之中，而這是基於使用ALC-PSO演算法的基礎下產生的創新路徑規劃演算法。
這個方法克服了粒子群演算法容易陷入區域最佳點應用於機器人路徑規劃方面上的缺點，而且因為基本的RRT演算法在每次規劃路徑上是不穩定的，所以本文利用模擬RRT演算法的方式來改良ALC-PSO演算法應用在路徑規劃上，且加入了危險度地圖的概念來避開障礙物，經過模擬結果，我們可以證明這個改良創新演算法可以使結果穩定在室內環境中而且比RRT演算法更好，同時也確保規劃路徑會是最短的。

摘要(英)

Path planning is an important issue in mobile robotics. In an environment with obstacles, path planning is to find a suitable collision-free path for a mobile robot to move from a start location to a target location along the shortest path.
This paper proposes an optimal path planning algorithm for mobile robots based on Particle Swam Optimization with an Aging Leader and Challengers (ALC-PSO) to imitate Rapidly-exploring Random Tree (RRT), traditional Particle Swam Optimization (PSO) for path planning is different, In this paper, we propose a branches-grow method based on the ALC-PSO algorithm, and add extend point to particles after we compare.
This method overcomes the drawback for particle swam optimization is easy to fall into local optimization in robotic path planning. Because the basic Rapidly-exploring Random Tree (RRT) path planning is unstable for every time, so this paper improved algorithm of ALC-PSO to imitate RRT in path planning, and add Danger Degree Map to avoid obstacles. From the results of simulations, we show that this algorithm can improve the stability of RRT path planning in static environment, and ensures that the path is almost optimal.

關鍵字(中)

★ 老齡化領導者與挑戰者粒子群演算法
★ 危險度指標
★ 快速搜尋隨機樹
★ 路徑規劃
★ 移動機器人

關鍵字(英)

★ ALC-PSO
★ Danger Degree
★ Rapidly-exploring Random Tree
★ Path Planning
★ Mobile Robots

論文目次

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 vii
表目錄 x
第一章　　緒論 1
1-1　研究背景 1
1-2　研究目的與動機 2
1-3　文獻探討 4
1-3-1　Dijkstra 演算法與A*演算法及RRT演算法之比較 4
1-3-2　粒子群演算法的研究進展 5
1-4　成果與主要貢獻 6
1-5　論文架構 7
第二章　　研究問題定義與描述 8
2-1　路徑規劃的定義和作用 8
2-2　路徑規劃的分類 10
2-2-1　全局路徑規劃方法 10
2-2-2　局部路徑規劃方法 14
2-3　機器人的環境設定 17
2-3-1　一般論文使用柵欄法的環境設定 17
2-3-2　本篇論文所使用的環境設定 21
第三章　本論文採用之方法與分析 23
3-1　快速隨機搜尋樹演算法(RRT) 24
3-1-1　傳統的快速隨機搜尋樹 24
3-1-2　雙向擴展快速隨機搜尋樹 27
3-2　粒子群演算法(PSO) 28
3-2-1　粒子群演算法的起源及機制原理 28
3-2-2　粒子群演算法的數學描述 29
3-2-3　粒子群演算法的流程 30
3-2-4　粒子群演算法的參數分析 32
3-3　改良式粒子演算法介紹 33
3-3-1　PSO with an aging leader and challengers(ALC-PSO) 34
3-3-2　生命週期機制 35
3-3-3　產生挑戰者機制 37
3-3-4　產生新的領導人的機制 38
3-3-5　詳細的ALC-PSO演算法步驟 39
第四章　　改良路徑規劃之方法 42
4-1　改良方法一 43
4-1-1　改良方法一的設計理念 43
4-1-2　適應函數設計與懲罰函數設計 47
4-2　改良方法二 51
4-2-1　延伸點的選擇方式 51
4-2-2　改良方法二的演算法流程 52
4-3　粒子成長暨ALC-PSO改良演算法 57
4-3-1　改良延伸點選擇方式 57
4-3-2　粒子成長暨ALC-PSO演算法流程 62
第五章　　實驗結果與討論 67
5-1　各個演算法相關參數設定 67
5-2　粒子成長暨ALC-PSO演算法的細節設定 68
5-2-1　群體大小是否隨著疊代次數改變而減少規劃時間 68
5-2-2　延伸點設定的多寡 70
5-2-3　在產生延伸點之間的疊代次數變化 71
5-3　與其他改良粒子群演算法比較(一般地圖) 74
5-3-1　本文使用之改良粒子演算法與其他改良粒子群演算法之比較 74
5-3-2　本文演算法與其他路徑規劃演算法之比較 75
5-4　加入危險度機制與安全區比較(一般地圖) 78
5-5　與其他改良演算法比較(複雜地圖) 81
5-6　模擬在動態環境中 85
第六章　　結論與建議 87
6-1　結論 87
6-2　建議 88
參考文獻 89
文章發表 94

參考文獻

[1] S. J. Russell, P. Norvig, Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. pp. 97–104, 2003.
[2] 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, No.261-264, 2009.
[3] X. Ye, Y. L. and H. Hon, “Design of intelligent mobile vehicle system and its global optimal path planning,” IEEE International Conference on Industrial Technology, No.1-5, 2008.
[4] A. T. Klesh, P. T. Kabamba and A.R. Girard, “Optimal Path planning for uncertain exploration,” American Control Conference, No.2421-2426, 2009.
[5] S. L. Valle, J. Kuffner. “Rapidly-exploring random trees: Progress and Prospects,” Proceedings of Algorithmic and Computational Robotics: New Directions, pp. 293-308, 2001.
[6] 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.
[7] 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.
[8] A. Coloni, M. Dorigo, V. Maniezzo, et a1. Distributed optimization by ant colonies. Proceedimgs of the 1st European Confercnce on Artificial Life, pp. 134-142, 1991.
[9] J. Kennedy and R. Eberhart, "Particle Swarm Optimization," Proceedings of IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.
[10] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik 1, pp. 269–271, 1959.
[11] 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.
[12] 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.
[13] R. Dechter, P. Judea, “Generalized best-first search strategies and the optimality of A*,” Journal of the ACM 32 (3), pp. 505–536, 1985.
[14] http://theory.stanford.edu/~amitp/GameProgramming.
[15] Heppner F, Grenander U. “A Stochastic Nonlinear Model for Coordinated Bird Filcks” Krasner S, ed. The Ubiquity of Chaos Washington, USA: American Association for the Advancement of Science, pp. 233-238, 1990.
[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, May 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, May 2001.
[19] J. C. Latombe, Robot Motion Planning. Norwood, MA, Kluwer Academic Publishers, 1991.
[20] J. J. A. “The essential visibility graph: an approach to global motion planning for autonomous mobile robots,” IEEE International Conference on Robotics and Automation, Nagoya, 1995.
[21] R. A. Brooks. “Solving the Find-path problem by good representation of free space,” IEEE Trans on Sys Man and Cybern, pp. 190-197, 1983.
[22] R. Chatila. “Path Planning and Environment Learning in a Mobile Robot System,” Proceedings of the European Conference on A I. 1982.
[23] E. Hernandez, M. Carreras, J. Anitich, P. Ridao, and A. Ortiz, “A topologically guided path planner for an AUV using homotopy classes,” in Proc.IEEE Int. Conf. Robot. Autom, Piscataway, NJ, USA, pp. 2337–2343, 2011.
[24] M. B. Metea. “Planning and intelligence autonomous land vehicles using hierarchical terrain representation,” Proceedings of IEEE International Conference on Robotics and Automation, pp. 1947-1952, 1987.
[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] 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, July 2011.
[27] 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, July 2009.
[28] Khatib, “Real-time obstacle for manipulators and mobile robot,” International Journal of Robotic Research, pp. 90-98, 1986.
[29] 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.
[30] Nelson H C, Yung Cang Ye. “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.
[31] R. Fierro, F. L. Lewis. “Control of nonholonomic mobile robot using neural networks,” IEEE Transactions on Neural Networks, pp. 589-600, 1998.
[32] W. Li, G. Y. Wang. “Application of improved PSO in mobile robotic path planning,” IEEE Intelligent Computing and Integrated Systems, pp. 45-48, 2010.
[33] S. M. Lavalle, J. J. Kuffner. Randomized kinodynamic planning. Detroit, Michigan, pp. 473-479, USA,1999.
[34] 嚴蔚敏,吳偉民,數據結構.北京:清華大學出版社,2008。
[35] Q. Wang, W. Wang, Y. Li. “A multi-RRT based hierarchical path planning method,” International Conference of IEEE Communication Technology, pp. 971-975, 2012.
[36] http://blog.xuite.net/sinner66/blog/12066291.
[37] Z. You, W. Chen, G. He, X. Nan. “Adaptive Weight Particle Swarm Optimization Algorithm with Constriction Factor,” International Conference of Information Science and Management Engineering, pp. 245-248, 2010.
[38] F. Ye and C. Y. Chen, “Alternative KPSO-Clustering Algorithm,” Tamkang Journal of Science and Engineering, Vol. 8, No. 2, pp. 165-174, 2005.
[39] A. Ratnaweera, S. Halgamuge, and H. Watson, “Self-organizing hierarchical particle swarm optimizer with time varying accelerating coefﬁcients,” IEEE Trans. Evol. Comput., vol. 8, pp. 240–255, Jun. 2004.
[40] S. H. Ling, H. C. Herbert, K. Y. Chan, H. K. Lam, C. W. Yeung and F. H. Leung, “Hybrid Particle Swarm Optimization With Wavelet Mutation and Its Industrial Applications,” IEEE Transactions on Systems, Man, and Cybernetics, Part B 38(3):743-763 (2008).
[41] S. H. Chung, Y. Li, and Y. H. Shi, “Particle swarm optimization with an aging leader and challengers,” IEEE Trans. Evol. Comput., vol. 17, no. 2, pp. 241–258, April. 2013.
[42] T. C. Goldsmith, “The Evolution of Aging. Crownsville,” MD: Azinet Press, 2006.
[43] C. Purcaru, R. E. Precup, D. Iercan, L. O. Fedorovici, R. C David, “Hybrid PSO-GSA Robot Path Planning Algorithm in Static Environment with Danger Zones,” IEEE Transactions on Systems, Control and Computing, pp. 434–439, 2013.
[44] N. ZakeriNejad, A. H. Bakhtiary, M. R. Jahed Motlagh, “Use of Particle Swarm Optimization in path planning for rough terrain,” Proceedings of 19th International Workshop on Robotics in Alpe-Adria-Danube Region, pp. 205-209, 2010.
[45] Y. Xue, G. Tian and B. Huang, “Optimal Robot Path Besed on Danger Degree Map,” in Proc. IEEE Congr. Evol. Comput., China August 2009.

指導教授

鍾鴻源(Hung-Yuan Chung)

審核日期

2014-8-15

推文