Abstract

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.

Degree

MS

College and Department

Ira A. Fulton College of Engineering and Technology; Mechanical Engineering

Rights

http://lib.byu.edu/about/copyright/

Date Submitted

2004-03-22

Document Type

Thesis

Handle

http://hdl.lib.byu.edu/1877/etd400

Keywords

uav, coordinated control, multiple agent, task allocation, path planning

Share

COinS