異質性組合式機器人路徑規畫之研究

A Study on Motion Planning Algorithm of Heterogeneous Combinatorial Robots

饒瑞鈞(Jui-Chun jao)

指導教授 ： 何宏發

國立臺灣師範大學/科技學院/工業教育學系在職進修碩士班/碩士(2006年)

摘要

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

並列關鍵字

Motion planning ； Heterogeneous combinatorial robots ； Algorithm

參考文獻

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