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

Abstract

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