A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-03272017-142516


Type of Document Dissertation
Author Dukeman, Anton Leo
Author's Email Address anton.dukeman@vanderbilt.edu
URN etd-03272017-142516
Title Hybrid Mission Planning with Coalition Formation
Degree PhD
Department Computer Science
Advisory Committee
Advisor Name Title
Gautam Biswas Committee Co-Chair
Julie A. Adams Committee Co-Chair
Eugene Vorobeychik Committee Member
Maithilee Kunda Committee Member
Mark Ellingham Committee Member
Keywords
  • coalition formation
  • multi-agent planning
  • robotics
  • planning
  • multi-agent systems
Date of Defense 2017-03-20
Availability unrestricted
Abstract
Robotic systems have proven effective in many domains. Some robotic domains, such as mass casualty response, require close coupling between the humans and robots that are able to adapt to the environment and tasks. The coalition formation problem allocates coalitions to each task, but does not produce executable plans. The planning problem creates executable plans, but problem difficulty scales with the number of agents and tasks in the problem. A hybrid solution to solve both problems will produce executable plans for the assigned tasks, while satisfying computational resource constraints. Four solution tools are presented and evaluated using four test domains, including a novel domain simulating the immediate response to a tornado by local government agencies. Each domain and problem was implemented in a new problem description language combining planning and coalition formation.

Planning alone is an existing tool to produce high quality plans by considering all possible interactions between tasks and agents simultaneously. However, planning alone requires large amounts of time and memory, both of which are constrained in real world applications. The coalition formation then planning tool factors the problem to reduce the required computational resources, but coalition formation cannot be relied upon to produce executable coalitions in all cases. The relaxed plan coalition augmentation tool addresses nonexecutable coalitions by selecting the agent(s) required to produce an executable coalition. The final tool, task fusion, addresses reduced solution quality by selecting tasks and coalitions for which planning together will increase solution quality. The relaxed plan coalition augmentation tool solved at least as many problems as planning alone and averaged much less computational resource usage. The task fusion tool solved more problems than planning alone, but plan quality and computational resource usage was mixed when compared to relaxed plan coalition augmentation.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  dukeman_dissertation.pdf 8.18 Mb 00:37:53 00:19:29 00:17:02 00:08:31 00:00:43

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.