藉由遺傳演算法則將人類直覺應用於依任務需求之路徑規劃

Abstract

本文提出一種新的靜態運動路徑的規劃方法，以進一步提昇機器人的自動 化。我們所探討的重點在於依據任務需求而異的運動路徑規劃，這大有別 於傳統上所探討的路徑規劃問題。文章中所提出的策略其最基本的觀點是 向周圍區域擴張搜尋範圍，這種方法在分類上屬於局部性質的路徑規劃方 式(local method)。實際上我們是以擴張點(expanded node)的延伸來表 示搜索範圍向目標區逼近，這些擴張點只有在局部最小值阻礙了搜索方向 的時候才會產生。因此搜尋樹(search tree) 不會顯得很複雜而龐大。至 於擴張點的位置，我們利用遺傳演算法來決定。其中適存函數(fitness function) 安排了人類在搜索上的一些直覺與技巧 (heuristics)。如此 可以找到大約適當的擴張點用來作為逃離局部最小值的導引。本文以486 PC對於各種不同的任務需求分別做了模擬。此外在傳統的路徑規劃問題上 我們也展現了一些應用。最後在性能方面，文中所有的模擬在時間的花費 上依其困難度而言大都可以接受。 In order to enhance integration between CAD and robot, we proposed a novel and efficient scheme for planning kinematically feasible paths in the presence of obstacles. In this thesis, we focus on the task-dependent requirements instead of conventional initial-to-goal such as the classical mover's problems. This approach is local and primarily based on the expansion of search nodes. By exploring in selected directions in the C space, we create the expanded nodes sparingly, only when the constructed cost field takes the planner to a dead-end. So the search graph do not grow too large. Using a genetic algorithm with a simple heuristic fitness function, we find an adequate suboptimal expanded node that push the search from the blind valleys. We have simulated various tasks on a 486-PC. Applications on classical mover's problems are also investigated. All simulations take reasonable amount of time.