Multiple Task Allocation Problems with Team Formation

We address a problem in which multiple agents are assigned tasks, some of which can be accomplished cooperatively by teams. This task allocation problem is an NP-hard hierarchical combinatorial optimization problem. We consider procedures for imposing restrictions on task and team combinations. Through task classification, imposing restrictions on the number of tasks that an agent can perform, and the number of agents that a team can have, the set of feasible allocations is significantly reduced. Based on these restrictions, we apply a first step in which we apply n apriori algorithm to generate all tasks that an agent can perform. Second, we devise a breadth-first search algorithm to generate all teams that can perform the given tasks, and then construct all team configurations that can perform the given task classification. Third, through least cost calculations, we produce the optimal team configuration and the corresponding task classification. Advantages of the method are that it significantly reduces the calculation of the cost function, and generates an optimal task classification while forming a high performance team configuration. Finally, we discuss the application of the method to the command and control of multiple Unmanned Air Vehicles (UAV).