本研究之主要目的為探討異質性組合式機器人(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