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

No Thumbnail Available

Date

2007

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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

Description

Keywords

動態規畫, 異質性組合式機器人, 演算法, Motion planning, Heterogeneous combinatorial robots, Algorithm

Citation

Collections