群體機器人運動的自動產生，可以應用在可移式機器人群的路徑規劃或電腦動畫中虛擬人群的模擬上。文獻上研究對此運動計劃問題，多以分離式或集中式的方法來解決。分離法是把群體的計劃，切割為多個個別機器人的連續計劃。本論文採優先順序的分離法依序解決個別機器人的計劃；而個別計畫的方法係採用位能場與A*搜尋法，我們並針對群體運動的特性提出改進方案。分離法的搜尋由於受到前面計劃結果的限制，因此缺乏計劃的完整性；相對而言，集中法同時考慮所有機器人的組態，因此可以完整地搜尋整個群體機器人的組態空間。我們首先採用的集中法是以位能場為基礎的隨機路徑計劃法。此法雖然具備完整性，但在機器人數量多時，機器人間的碰撞機會太高，所以計劃所需時間通常較長。因此，我們設計了一個採用階層式動態編隊方式的集中式計畫法。階層式動態編隊就是以球形樹組織機器人隊伍，依照搜尋時的狀況，動態地進行隊伍的分離或合併。同隊伍中的機器人會維持一致的運動方向，因此減少了機器人間發生碰撞的機會，因而改善了計劃的效率。我們實驗比較分離法、集中法、與動態編隊法，並分析各種情況下適合的計劃方法，以提出使用建議。我們並且設計了一個平滑化路徑的方法，將計劃出來的群體運動路徑調整平順，以應用在電腦動畫的製作過程中，自動產生擬真的虛擬人群運動。 / The automatic generation of crowd motions can be used in planning the path of many mobile robots and in simulating the motions of virtual humans in computer animation. In the literature, there exist two categories of approaches to this problem: decoupled and centralized approaches. The decoupled approach divides the planning problem into several sub-problems, each of which is for a robot. In this thesis we have used a prioritized planning approach with an artificial potential field and the A* search algorithm to solve each sub-problem in a given order. This decoupled approach usually is not complete because later planning must be under the constraint of previous planned results. On the other hand, the centralized approach considers the configurations of all robots and can be made complete by searching the composite configuration space. In this thesis, we use the randomized path planner (RPP) with a potential field as an example of the centralized approach. However, this planner is not very efficient for a large number of robots because of frequent inter-collisions between robots. Therefore we propose a hierarchical dynamic grouping method to improve the centralized RPP method. The robots are organized as groups enclosed by a sphere tree structure that can split or merge dynamically according to the environment. The robots in the same group always move with the same direction. Consequently the collisions between robots decrease significantly during the search and the planning efficiency is greatly improved. We have designed extensive experiments to compare the performance of the decoupled approach, the centralized approach and the dynamic grouping method. We also analyze these approaches in various scenarios in order to illustrate their tradeoffs. In addition, we have designed a path-smoothing method and apply the planning result to a production process of computer animation.
| Identifer | oai:union.ndltd.org:CHENGCHI/G0090753002 |
| Creators | 周旭騏 |
| Publisher | 國立政治大學 |
| Source Sets | National Chengchi University Libraries |
| Language | 中文 |
| Detected Language | English |
| Type | text |
| Rights | Copyright © nccu library on behalf of the copyright holders |
Page generated in 0.1161 seconds