Real Time Optimal Task Allocation in Highly Dynamic Environments

Abstract

Of the methods developed for Optimal Task Allocation, Mixed Integer Linear Programming (MILP) techniques are some of the most predominant. A new method, presented in this paper, is able to produce identical optimal solutions to the MILP techniques but in computation times orders of magnitude faster than MILP. This new method, referred to as G*TA, uses a minimum spanning forest algorithm to generate optimistic predictive costs in an A* framework, and a greedy approximation method to create upper bound estimates. A second new method which combines the G*TA and MILP methods, referred to as G*MILP, is also presented for its scaling potential. This combined method uses G*TA to solve a series of sub-problems and the final optimal task allocation is handled through MILP. All of these methods are compared and validated though a large series of real time tests using the Cornell RoboFlag testbed, a multi-robot, highly dynamic test environment.