標題: 藉由遺傳演算法則將人類直覺應用於依任務需求之路徑規劃
A heuristic approach to task-dependent path planning by using a genetic algorithm
作者: 許晊豪
Chi-Haur Sheu
楊谷洋
Kuu-Young Young
電控工程研究所
關鍵字: 依任務需求之路徑規劃;遺傳演算法則;人類直覺;擴張點;task-dependent path planning; genetic algorithm; heuristic; expanded node
公開日期: 1993
摘要: 本文提出一種新的靜態運動路徑的規劃方法,以進一步提昇機器人的自動 化。我們所探討的重點在於依據任務需求而異的運動路徑規劃,這大有別 於傳統上所探討的路徑規劃問題。文章中所提出的策略其最基本的觀點是 向周圍區域擴張搜尋範圍,這種方法在分類上屬於局部性質的路徑規劃方 式(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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT820327030
http://hdl.handle.net/11536/57746
Appears in Collections:Thesis