Autonomous and Semi-Autonomous Control of Multi-Agent Task Allocation Systems

Other Titles


The ever increasing need to solve a wide variety of NP-Hard task allocation problems effectively and in computation times acceptable for real-time application has motivated the development of new optimal and large scale approximation methods presented in this dissertation. The chief new optimal method presented, referred to as GTA, utilizes a minimum spanning forest algorithm to generate optimistic predictive costs within an A framework, and a greedy approximation method to create upper-bound estimates. The GTA method is shown to run on average two orders of magnitude faster than a traditional Mixed Integer Linear Programming (MILP) technique, and a combined approach of GTA and MILP, referred to as GMILP, is also presented for its scaling potential. The GTA method is then improved further through the development of a new optimistic predictive cost function which leads to computational runtimes that are five times faster still, while using up to an order of magnitude less memory. The GTA method is also presented as an any-time solution capable approximation method, which then motivates the development of a GTA based hierarchical approximation method called H-GTA. The H- GTA method is built upon and validates the premise that since these task allocation problems are NP-Hard, faster solutions to large scale problems can be obtained by partitioning these large problems into a hierarchy of smaller sub-problems that can be solved within a reasonable amount of time. Details are provided on the integration within H-GTA of a newly developed adaptive K-means partitioning technique, incorporation of GTA to solve sub-problems optimally, combining the sub-problem solutions to obtain a final solution to the original problem, and on applying a K-Opt post-optimization technique. As task allocation research is commonly associated with the applied field of robotics, this dissertation also presents a description of the Cornell RoboFlag system; a high fidelity, robotic testbed and simulation environment that was utilized for validating the computational runtime and the solution quality of all of the task allocation methods discussed. Finally, this dissertation presents a chapter on the educational robotics research that was carried out within the NASA Robotics Alliance independently of the task allocation research.

Journal / Series

Volume & Issue



Date Issued




Task Allocation; Traveling Salesman Problem; Multiple Salesman Traveling Salesman Problem; Robotics; TSP; Linear Programming; MILP; Engineering Education; RoboFlag


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record