臺灣博碩士論文加值系統

本文提出有關同質性組合式機器人(Homogeneous Combinatorial Robots，縮寫成HmCR)的概念和特性，有關路徑規畫(Motion Planning, 縮寫成MP)的演算問題，論文中所稱HMCR是一組能夠自由組合和分離的點狀機器人(Point Robots，縮寫成PR)，HmCR在時變環境（Time-Varying Environment，縮寫成TVE)，研究初步結果獲得如下：
一、定義一組 HmCR 基本模型，能夠自由組合和分離的點狀機器人及不同的組合成本。
二、HmCR 在 TVE 中之路徑規畫及與其演算問題符合最佳化原則(Principle of Optimality.) 及可以使用動態規畫演算法(Dynamic programming algorithm)來解決此HMCR在TVE中之MP問題。
三、若有n 個HmCR 在TVE圖形中，由起點抵達終點，假設HmCR在TVE圖形中總共經過 個端點(vertices)，所走路徑規畫步數為k個步驟。本文以最差狀況下分析及經過初步計算所花費時間的複雜度 (complexity analysis)為 。
本研究已初步完成HmCR的單步模擬器及HmCR在TVE中多個端點及週期性變化預測的MP的程式模擬器，能夠隨時進行模擬、實驗分析及理論驗證，將來再進一步的研究，能夠朝向HmCR的實際應用。

This paper is going to introduce the concept of homogeneous combinatorial robots and some properties and algorithms of their motion planning problem. There are three important concepts, As follows:
First, The so-called “homogeneous combinatorial robots,” in this paper, are a set of robots that can be combined and separated freely in motion.
Second, The motion planning problem of homogeneous combinatorial robots in a discrete environment is compliant to the principle of optimality. Additionally, dynamic programming algorithm is used to solve this problem.
Third, Suppose is the maximum number of vertices of the time-varying graph, n is the number of robots, and k is the number of step of the motion planning. The time complexity of this problem is .
Motion Planning 、Homogeneous Combinatorial Robots 、Time-Varying Environment

目錄
謝誌 II
摘要 III
ABSTRACT IV
目錄 1
表目錄 3
圖目錄 4
第一章 緒論 6
第一節 研究動機及背景 6
第二節 研究目的 7
第三節 研究方法 8
第二章 文獻探討 9
第一節 機器人的演進及分類 9
第二節 路徑規畫的分類法 11
第三節 組合式的路徑規畫(COMBINATORIAL MOTION PLANNING) 14
第四節 AOV網路與拓樸排序 16
第三章 模型的建立 18
第四章 證明HMCR在TVE中符合最佳化原則 22
第五章 實驗結果與分析 31
第一節 單步模擬 31
第二節 完整時變圖形模擬器 33
第三節 實驗模擬結果及驗證 39
第六章 結論與建議 52
第一節 結論 52
第二節 建議 55
參考文獻 56
附錄A 變數查詢一覽表 58
附錄B 個人研究背景資料 59
附錄C MATRIX.JAVA 60
附錄D FRM_ROBSTER_MAP.JAVA 69

[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] 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.
[6] A. Abrams and R. Ghrist, “Finding topology in a factory: Configuration spaces,” The American Mathematics Monthly Vol. 109, pp. 140-150, February 2002.
[7] J. Cortés. “Motion Planning Algorithms for General Closed-Chain Mechanisms,” PHD thesis Institut National Polytechnique de Toulouse France, 2003.
[8] H. F. Ho and H. S. Tai, “Motion Planning Algorithm for Homogeneous Combinatorial Robots,” Proceedings of CACS Automatic Control Conference, 2006.
[9] T. Lozano-Perez and M. A. Wesley, “An algorithm for planning collision-free paths among polyhedral obstacles,” Commun. ACM, Vol. 22, Oct. 1979, pp. 560-570.
[10] 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, Jun. 1988, pp. 329-340.
[11] 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.
[12] 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, May 1983, pp. 345-398.
[13] R. A. Brooks, “Solving the Findpath problem by good representation of free space,” IEEE Trans. Syst., Man, and Cybernetics SMC-13, 1983, pp. 190-197.
[14] 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, 1985, pp.168-173
[15] B. R. Donald. “A search algorithm for motion planning with six degree of freedom,” Aritf. Intell., vol. 31,pp.295-353,1987.
[16] L. Kavraki, P.Svestka, J. Latombe, and M. Overmars,"Probabilistic Roadmaps for Fast Path Planning inHigh-Dimensional Configuration Spaces," IEEETransaction on Robotics and Automation, 12:566-580,1996.
[17] S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” TR 98-11, Computer Science Dept., Iowa State University, 1998.
[18] J. J. Kuffner and S. M. LaValle, “RRT-connect: An efficient approach to single-query path planning,” In Proc. IEEE International Conf. on Robotics and
Automation, pp. 995-1001, 2000.
[19] Hollane, J. H., “Adaptation in natural and artificial systems”, The University of Michingan Press, Ann Arbor, 1975.
[20] 明亮, “機器人當道成為經濟新引擎”, 臺灣區電子電機公會出版品。2006
[21] 蔡宗漢, “演算法使用c++虛擬碼”, 碁峰資訊, P.9-37, 2004.
[22] 吳勁華, “資料結構教學範本使用c語言”, 金禾資訊, P.4-6, 2005.
[23] 林銀議, “信號與系統”, 五南書局, P.95, 2004.
[24] 張紹勳, “資料結構與演算法, 旗標資訊, P.0-14；P.P23-25, 2004.
[25] 河西朝雄, “Java 於演算法與資料結構之時習應用”, 博碩文化, P.2-6, 2003.
[26] UDI MANBER原著, 鍾俊仁, 巫坤品和余宗恩譯,“建構式演算法”, 碁峰資訊, P.235, 2005.
[27] REBORT LAFORE, 胡銘珍譯, “JAVA在資料結構及演算法的應用”, 全華科技, P.561, 2003.
[28] 臺灣拜耳新聞,”拜耳多項研發將可助於減少心肌梗塞形成和中風的危險”　參考網址http://www.bayer.com.tw/news/content.asp?new_id=265
[29] Inside the body, 王紹婷譯,” 人體驚異大奇航”,新世紀家圖書,2005.