This two years research effort was concerned with the efficient solution of combinatorial optimization problems that arise in the task assignment and motion planning of unmanned aerial vehicles in complex operations. In the first year of the research we have concentrated on the high level task assignment problem. A genetic algorithm that utilizes process algebra for coding of solution chromosomes and for defining evolutionary based operators was presented. The algorithm is applicable to a general class of mission planning and optimization problems. In the second year of the research we paid special attention to the interaction between the high level mission planning (task assignment) and the low level motion-planning for unmanned aerial vehicles. We considered an unmanned aerial vehicle modeled as a Dubins vehicle: a vehicle with a minimum turn radius and the inability to go backward. Given a starting position and orientation for a Dubins vehicle and a set of stationary targets, the main problem is to determine the shortest flyable path that visits each target. This problem is called the Dubins traveling salesman problem, an extension of the well-known traveling salesman problem. A number of algorithms with different approaches, including a hierarchical approach, a generalized traveling salesman problem reformulation approach, and a search with an upper bound Dubins cost approach, is developed and contrasted. Monte Carlo simulations were performed for a range of vehicle turn radii. Simulations results show that integrating two plausible kinematic satisfying paths as an upper bound to determine the cost-so-far into a search algorithm generally improves performance in terms of the shortest path cost and search complexity. Furthermore, when a suitable trajectory for traversing an ordered set of targets has been found, the applicability of using proportional navigation guidance is examined.


    Access

    Access via TIB

    Check availability in my library


    Export, share and cite



    Effective Task Assignment for Complex UAV Operations Using Genetic Algorithms

    Karaman, S. / Shima, T. / Frazzoli, E. et al. | British Library Conference Proceedings | 2009


    Effective Task Assignment for Complex Uav Operations Using Genetic Algorithms

    Karaman, Sertac / Shima, Tal / Frazzoli, Emilio | AIAA | 2009


    OPERATIONS TASK CREATION, PRIORITIZATION, AND ASSIGNMENT

    SHAH AKASH GAURAV / BRUGGEMAN CAMERON PHILIP / CHEN LINWEI et al. | European Patent Office | 2025

    Free access

    OPERATIONS TASK CREATION, PRIORITIZATION, AND ASSIGNMENT

    SHAH AKASH GAURAV / BRUGGEMAN CAMERON PHILIP / CHEN LINWE et al. | European Patent Office | 2022

    Free access

    Integrating Task Assignment and Guidance via Motion Planning for Unmanned Aerial Vehicles

    Cons, M. / Shima, T. / Domshlak, C. et al. | British Library Conference Proceedings | 2011