Hybrid Mission Planning with Coalition Formation

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.