本文提出有關同質性組合式機器人(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

[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.