時變環境中的同質性組合式機器人

A Study on Motion Planning Algorithm of Homogeneous Combinatorial Robots in Time-Varying Environment

劉文正(Wen-Cheng Liu)

指導教授 ： 何 宏 發

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

摘要

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

並列關鍵字

Motion Planning ； Homogeneous Combinatorial Robots ； Time-Varying Environment

參考文獻

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