Real-time optimal time-critical target assignment for UAVs

Yoonsoo Kim, Da-Wei Gu, Ian Postlethwaite

    Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

    5 Citations (Scopus)


    In the literature, e.g. [10], one can find the so-called basic UAV mission target assignment in which m UAVs each with a capacity limit q visit n targets in a cooperative manner (and return to their departure points) such that the cost incurred by each UAV’s travel is minimized. In [10], we proposed a mixed integer linear program (MILP) formulation which exactly solves the problem, as well as four alternative MILP formulations which are computationally less intensive (and therefore suited for real-time purposes) yet yield a theoretically guaranteed sub-optimal solution. In this chapter, we further consider timing constraints imposed on some p of the targets, so-called prime targets. This consideration is often required for scenarios in which prime targets must be visited in a pre-defined time interval, and mathematically results in the addition of several integer linear constraints to the previous MILP formulation making the problem computationally intractable. We propose a novel procedure of adding these cumbersome timing constraints to the previous MILP formulation, in order to avoid increasing too much computational cost under practically valid assumptions. We first show that the proposed procedure still guarantees the previously claimed theoretical solution quality associated with the basic mission. We then show through extensive numerical simulations that under certain conditions, our algorithms return solutions which are still computationally manageable.
    Original languageEnglish
    Title of host publicationAdvances in Cooperative Control and Optimization
    EditorsPanos Pardalos, Robert Murphey, Don Grundel, Michael Hirsch
    Place of PublicationLondon
    Number of pages422
    ISBN (Print)978-3540743545
    Publication statusPublished - 2007

    Publication series

    NameLecture Notes in Control and Information Sciences


    Dive into the research topics of 'Real-time optimal time-critical target assignment for UAVs'. Together they form a unique fingerprint.

    Cite this