M.Sc Thesis

M.Sc StudentEugene Edison
SubjectTask Assignment and Path Optimization for Cooperating
Uninhabited Aerial Vehicles
DepartmentDepartment of Aerospace Engineering
Supervisor Professor Shima Tal
Full Thesis textFull thesis text - English Version


In this thesis we address the problem of assigning a group of uninhabited aerial vehicles to cooperatively perform tasks on multiple stationary ground targets. A specific set of consecutive tasks needs to be performed on each target. We distinguish between two cases of UAV group composition. The first case involves a group of homogeneous UAVs in which all UAVs are identical in terms of their operational capabilities and kinematic constraints. The second group consists of a heterogeneous set of UAVs with different characteristics in their capabilities and kinematic constraints. To take into account each vehicle's specific constraint of minimum turning radius, a Dubins car model is used for motion planning. By discretizing the possible heading angle of a vehicle while flying over a target we pose the coupled problem of task assignment and path optimization in the form of a graph. This new technique obtains suboptimal trajectory assignments that tend towards an optimal solution when increasing the resolution of the visit heading angles. This new method constitutes an alternative to the common approach of hierarchical problem decoupling that always results in a suboptimal solution. Due to the high computational burden of this coupled problem, which is analytically derived through the complexity computation, we propose a centralized genetic algorithm for the stochastic search of the space of solutions. Results show that the algorithm quickly provides good feasible solutions that improve monotonically and is applicable to heterogeneous and homogeneous UAVs. To increase the effectiveness of the solution search process, a distributed genetic algorithm is developed, and several results obtained through this algorithm are compared with the results from the centralized algorithm. The performance of the genetic algorithms is demonstrated through a number of Monte Carlo simulation studies.