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

Schneider, David

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

Abstract

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 G*TA, 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 G*TA 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 G*TA and MILP, referred to as G*MILP, is also presented for its scaling potential. The G*TA 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 G*TA method is also presented as an any-time solution capable approximation method, which then motivates the development of a G*TA based hierarchical approximation method called H-G*TA. The H- G*TA 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-G*TA of a newly developed adaptive K-means partitioning technique, incorporation of G*TA 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.

Date Issued

2008-01-07T14:40:20Z

Keywords

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

Types

dissertation or thesis