研究生: |
饒瑞鈞 Jui-Chun jao |
---|---|
論文名稱: |
異質性組合式機器人路徑規畫之研究 A Study on Motion Planning Algorithm of Heterogeneous Combinatorial Robots |
指導教授: |
何宏發
Ho, Hong-Fa |
學位類別: |
碩士 Master |
系所名稱: |
工業教育學系 Department of Industrial Education |
論文出版年: | 2007 |
畢業學年度: | 95 |
語文別: | 中文 |
論文頁數: | 149 |
中文關鍵詞: | 動態規畫 、異質性組合式機器人 、演算法 |
英文關鍵詞: | Motion planning, Heterogeneous combinatorial robots, Algorithm |
論文種類: | 學術論文 |
相關次數: | 點閱:155 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本研究之主要目的為探討異質性組合式機器人(Heterogeneous Combinatorial Robots, HeteroCR),在有向圖中以最佳化原則(Principle of Optimality)為基礎,求出最低成本的路徑規畫;為了達到此一目的,本研究於過程中探討動態規畫演算法(Dynamic programming algorithm)、Dijkstra最短路徑演算法、隨機演算法及遺傳基因演算法,並透過電腦模擬實際設計地圖模型、機器人種類、機器人數量、機器人成本等相關條件建構此一理論系統。
本研究設計出Dijkstra 、隨機法及遺傳基因法系統進行分析與測試,定義異質性組合式機器人的組合成本及地圖條件設定,分析地圖複雜度與機器人組合、進行最佳化路徑規畫,根據結果顯示透過遺傳基因法的模式能有效地組合出可能的最佳移動組合路線達到較少步驟時間與較低成本。研究成果可用於規畫貨物配發路線或大區域旅行團分工式領隊或導遊調度之用,以利最佳成本的運用。
以異質性組合式機器人做為考量的情況,在G = <V, E>,假設有n個最大數量端點(vertices)及q種不同種類數量異質性組合式機器人,所有能走的路徑規畫步數為k個步驟。本文以最複雜的狀況下分析及經過複雜度分析計算 (complexity analysis)為 。
Some properties and an algorithm of motion planning problem of heterogeneous combinatorial point robots are presented. Heterogeneous combinatorial point robots can be combined and separated freely during moving. It is proven that the problem in a static discrete environment is compliant to the principle of optimality. Dynamic programming algorithms are used to solve this problem. The superposition property of the problem is presented. The time complexity of this problem is . The motion planning problem of homogeneous combinatorial point robots is a special case of that of heterogeneous ones. A probabilistic roadmap method is used in the experiments and it finds feasible motion plans efficiently.
[1] S. M. Lavalle Planning Algorithms. University of Illinois, 2005, Ch. 1.
[2] Y. K. Hwang and N. Ahuja, “Gross Motion Planning---A Survey,” ACM Computing Surveys, Vol. 24, No. 3, pp. 219–291, Sept. 1992.
[3] Y. K. Hwang and N. Ahuja, “Potential field approach to path planning,” IEEE Trans. Robotics Auto. Vol. 8, pp.23-32, Feb. 1992.
[4] F. Avnaim, J. D. Boissonnat, and B. Faverjon, “A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp.1656-1661, Apr. 1988.
[5] Hollane, J. H., “Adaptation in natural and artificial systems”, The University of Michingan Press, Ann Arbor, 1975.
[6] H. Noborio, T. Naniwa, and S. Arimoto, “A feasible motion planning algorithm for a mobile robot on a quad tree representation,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp.327-332, May 1989.
[7] BLAST Support Office, “Building load and system thermodynamics user manual and source code,” University of Illinois, Urbana, 1995.
[8] R. Bellman, Dynamic Programming, Princeton University Press, 1957.
[9] Indraneel Das and John E. Dennis, Jr. in "Normal-Boundary Intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems" published in SIAM J. Optimization 8(1998), pp 631-657. July, 1996
[10] T. Lozano-Perez and M. A. Wesley, “An algorithm for planning collision-free paths among polyhedral obstacles,” Commun. ACM, Vol. 22, pp. 560-570, Oct. 1979.
[11] K. Kedem and M. Sharir, “An automatic motion planning system for a convex polygonal mobile robot in 2-D polygonal space,” in Proceedings of the 4th Annual ACM Symposium on Computational Geometry, pp. 329-340, Jun. 1988.
[12] K. Kedem and M. Sharir, “An efficient algorithm for planning collision-free motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles,” in Proceedings of the 1st Annual ACM Symposium on Computational Geometry, Jun. 1985, pp. 75-80.
[13] F. Avnaim, J. D. Boissonnat, and B. Faverjon, “A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp.1656-1661, Apr. 1988.
[14] J. T. Schwartz and M. Sharir, “On the piano movers’ problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers,” Commun. Pure Appl. Math., Vol. 36, pp. 345-398, May 1983.
[15] R. A. Brooks, “Solving the Findpath problem by good representation of free space,” IEEE Trans. Syst., Man, and Cybernetics SMC-13, pp. 190-197, 1983.
[16] D. T. Kuan, J. C. Zamiska, and R. A. Brooks, “Natural decomposition of free space for path planning,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp.168-173, 1985.
[17] J. Cortés. “Motion planning algorithms for general closed-chain mechanisms,” PHD thesis, Institute National Polytechnique de Toulouse, Toulouse, France, 2003.
[18] B. R. Donald. “A search algorithm for motion planning with six degrees of freedom,” Artif. Intell., Vol. 31, pp.295-353, 1987.
[19] A. Abrams and R. Ghrist, “Finding topology in a factory: configuration spaces,” The American Mathematics Monthly, Vol. 109, pp. 140-150, Feb. 2002.
[20] H. F. Ho and H. S. Tai, “Motion planning algorithm for homogeneous combinatorial robots,” in Proceedings of CACS Automatic Control Conference, St. John’s University, Tamsui, Taiwan, Nov., pp.10-11, 2006.
[21] H. F. Ho and H. S. Tai, ”Algorithm for optimal notion planning Problem of homogeneous robots within a vertex,” in Proceedings of the CACS International Conference on Automatic Control, St. John’s University, Tamsui, Taiwan, Nov., 2006.
[22] H. F. Ho and H. S. Tai, ”Time complexity of motion planning algorithm for homogeneous combinatorial robots,” in Proceedings of the SICE - ICCAS International Joint Conference, Korea, 2006.
[23] H. F. Ho and W.C. Liu, “Motion planning algorithm for homogeneous combinatorial robots in time-varying environment,” in Proceedings of the IEEE International Symposium on Intelligent Control, Singapore, Oct., 2007
[24] Sniedovich, M., “A new look at Bellman's principle of optimality,“ Journal of Optimization Theory and Applications 49, pp.161-176. 1986.
[25] N.M. Amato, O. Bayazit, L. Dale, C. Jones, D. Vallejo, “Choosing good distance metrics and local planners for probabilistic roadmap methods,” in IEEE Int. Conf. on Robotics and Automation, 1998, pp. 630–637.
[26] N.M. Amato, Y. Wu, “A randomized roadmap method for path and manipulation planning,” in IEEE Int. Conf. on Robotics and Automation, 1996, pp. 113–120.
[27] L. Kavraki, P.Svestka, J. Latombe, and M. Overmars, “Probabilistic roadmaps for fast path planning in high-dimensional configuration spaces,” IEEE Transaction on robotics and Automation, 12:566-580, 1996.
[28] P. Svestka, Robot motion planning using probabilistic road maps. Ph.D., Thesis, Utrecht University, 1997.
[29] 明亮 (民95)。機器人當道成為經濟新引擎。臺灣區電子電機公會出版品
[30] http://www.teema.org.tw/publish/moreinfo.asp?autono=2743