簡易檢索 / 詳目顯示

研究生: 饒瑞鈞
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
論文種類: 學術論文
相關次數: 點閱:173下載: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.

    摘要................................................i Abstract...........................................ii 目錄...............................................iii 圖目錄..............................................vi 表目錄............................................viii 第一章 緒論 第一節 研究背景與動機..................................1 第二節 研究目的.......................................4 第三節 研究方法.......................................5 第二章 文獻探討 第一節 機器人種類分析..................................8 第二節 路徑規畫的分類法...............................10 第三節 MP的近似解(Motion Planning of Approach).......11 第四節 著名的搜尋法與演算法............................12 第五節 時間複雜度分析.................................23 第三章 建立模型 第一節 異質性組合式機器人環境模型......................25 第二節 異質性組合式機器人基本定義......................28 第三節 HeretroCR 基因演算法的設計.....................29 第四章 HeteroCR路徑規畫分析 第一節 HeteroCR最佳化分析............................31 第二節 HeteroCR路徑規畫的複雜度計算...................33 第三節 單一種機器人時間複雜度分析......................34 第四節 q種獨立異質性機器人複雜度分析...................36 第五節 q種相依異質性組合式機器人時間複雜度..............38 第五章 實驗設計 第一節 實驗目的......................................42 第二節 實驗條件設定...................................42 第三節 實驗方式......................................46 第四節 量測方法......................................48 第五節 實驗結果與分析.................................49 第六章 研究結論與建議 第一節 研究結論......................................65 第二節 研究建議......................................67 參考文獻............................................69 附錄一 實驗數據 變數說明............................................73 HereCR 行進模擬圖...................................73 1,2種機器人數各500個執行環境地圖(a)之實驗數據...........74 3~5種機器人數各500個執行環境地圖(a)之實驗數據 ..........76 1,2種機器人數各1000個執行環境地圖(a)之實驗數據..........79 3~5種機器人數各1000個執行環境地圖(a)之實驗數據..........81 1,2種機器人數各500個執行環境地圖(b)之實驗數據...........84 3~5種機器人數各500個執行環境地圖(b)之實驗數據...........86 1,2種機器人數各1000個執行環境地圖(b)之實驗數據..........88 3~5種機器人數各1000個執行環境地圖(b)之實驗數據..........91 1,2種機器人數各500個執行環境地圖(c)之實驗數據...........93 3~5種機器人數各500個執行環境地圖(c)之實驗數據...........96 1,2種機器人數各1000個執行環境地圖(c)之實驗數據..........98 3~5種機器人數各1000個執行環境地圖(c)之實驗數據..........101 附錄二 模擬程式 Homogeneos.java....................................105 Matrix.java........................................105 Frm_robster_map.java...............................113 GeneticAlgorithm.java..............................135 TestChromosome.java................................137 Graph.java.........................................138 Eage.java..........................................139 Dijkstra.java......................................139 ILine.java.........................................141 Mp_plan.java.......................................141 Mp_set.java........................................142 Node.java..........................................143 Obstacle.java......................................144 Robots_record.java.................................145 Status_step.java...................................146 Vertex_robots.java.................................147 Vtx_sum.java.......................................148

    [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

    QR CODE