Efficient and Adaptable Task Assignment for UAS Considering the MDMTSP

As the use of Unmanned Aerial Systems (UAS) in large-scale operations, such as those involved in disaster response, becomes increasingly more common, a method which efficiently assigns tasks to a fleet of UAS becomes critical. The environment may change rapidly, resulting in UAS and tasks which quickly become available or unavailable. As such, this research develops a task assignment method for UAS with a focus on the ability to respond to changes in the scenario. The goal is to assign UAS to tasks such that all tasks can be accomplished in the minimum amount of time. This problem can be represented as a version of the multiple-depot multiple traveling salesman problem (MDMTSP) with a MinMax objective function. An iterative, market-based algorithm was used to solve the MDMTSP and is shown to be effective when compared to two other solution methods. It was proposed that resuming the market-based algorithm from its most recent state could be an effective way of responding to tasks or UAS being added or removed from the scenario. The results showed that there was an advantage to resuming the market when adding or removing tasks, but not when adding or removing UAS.