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

Simple item page
dc.contributor.authorSchneider, David
dc.date.accessioned2008-01-07T14:40:20Z
dc.date.available2008-01-07T14:40:20Z
dc.date.issued2008-01-07T14:40:20Z
dc.description.abstractThe 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.en_US
dc.format.extent3897005 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.otherbibid: 6475920
dc.identifier.urihttps://hdl.handle.net/1813/9426
dc.language.isoen_USen_US
dc.subjectTask Allocationen_US
dc.subjectTraveling Salesman Problemen_US
dc.subjectMultiple Salesman Traveling Salesman Problemen_US
dc.subjectRoboticsen_US
dc.subjectTSPen_US
dc.subjectLinear Programmingen_US
dc.subjectMILPen_US
dc.subjectEngineering Educationen_US
dc.subjectRoboFlagen_US
dc.titleAutonomous and Semi-Autonomous Control of Multi-Agent Task Allocation Systemsen_US
dc.typedissertation or thesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
DRS_Dissertation_1_4_08.pdf
Size:
3.72 MB
Format:
Adobe Portable Document Format
Download
Collections
Cornell Theses and Dissertations