This thesis addresses the improvement of cooperative task allocation to vehicles in multiple-vehicle, multiple-target scenarios through the use of more effective preplanned tours. Effective allocation of vehicles to targets requires knowledge of both the team objectives and the contributions that individual vehicles can make toward accomplishing team goals. This is primarily an issue of individual vehicle path planning --- determining the path the vehicles will follow to accomplish individual and team goals. Conventional methods plan optimal point-to-point path segments that often result in lengthy and suboptimal tours because the trajectory neither considers future tasks nor the overall path. However, cooperation between agents is improved when the team selects vehicle assignments based on the ability to complete immediate and subsequent tasks. This research demonstrates that planning more efficient tour paths through multiple targets results in better use of individual vehicle resources, faster completion of team objectives, and improved overall cooperation between agents. This research presents a method of assigning unmanned aerial vehicles to targets to improve cooperation. A tour path planning method was developed to overcome shortcomings of traditional point-to-point path planners, and is extended to the specific tour-planning needs of this problem. The planner utilizes an on-line learning heuristic search to find paths that accomplish team goals in the shortest flight time. The learning search planner uses the entire sensor footprint, more efficiently plans tours through closely packed targets, and learns the best order for completion of the multiple tasks. The improved planner results in assignment completion times that range on average between 1.67 and 2.41 times faster, depending on target spread. Assignments created from preplanned tours make better use of vehicle resources and improve team cooperation. Path planning and assignment selection are accomplished in near real-time through the use of path heuristics and assignment cost estimates to reduce the problem size to tractable levels. Assignments are ordered according to estimated or predicted value. A reduced number of ordered assignments is considered and evaluated to control problem growth. The estimates adequately represent the actual assignment value, effectively reduce problem size, and produce near-optimal paths and assignments for near-real-time applications.

近年來，在電腦動畫的應用中，虛擬人群模擬的需求越來越多；但人群運動的模擬對於動畫設計師而言，仍是一件十分繁瑣耗時的工作。過去有許多研究曾以虛擬力場模擬簡單的生物群聚行為，但所模擬出的動畫品質與虛擬力場的參數及虛擬環境息息相關，因此經常需要以人工的方式耗時地調整出適當的虛擬力場參數。因此，我們提議以此問題定義成一個基因演算法的問題，針對不同的移動行為，定義適切的適應函數，再由系統根據不同環境自動演化出適當的虛擬力權重組合，以供產生不同人群移動行為之動畫時參考。在本篇論文中，我們已完成基因演算法的設計及人群動畫模擬系統，並設計了不同的典型環境進行電腦模擬實驗，以驗證此方法的可行性。 / The demands for virtual crowd simulation have been increasing in recent years but creating realistic crowd motions remains a complex and time-consuming task for a computer animator. In the literature、much work has been proposed to use virtual forces to simulate the motion of a group of virtual creatures such as birds and fishes. However、the quality of the simulations largely depends on the weights of the component virtual forces as well as the scene where the agents are situated. Usually it requires the animator to tune these parameters for a specific scene in order to obtain the desired result. In this thesis、we propose to use genetic algorithm to generate an optimal set of weighting parameters for composing virtual forces according to the given environment and desired movement behavior. We have implemented the proposed genetic algorithm as well as the crowd simulation system. Extensive experiments have also been conducted to study the effects of typical scenes and behaviors on the parameter sets and verify the feasibility of the approach.