Allocation of Multi-Robot Tasks with Task Variants
This work addresses multi-robot systems by extending task allocation to include task variants, but it is incremental as it builds on prior methods without major breakthroughs.
The paper tackles the multi-robot task allocation problem by introducing task variants, where tasks have multiple sets of requirements, and shows that the problem remains NP-complete. It adapts two existing greedy methods to this new formulation and evaluates their efficacy against a random baseline.
Task allocation has been a well studied problem. In most prior problem formulations, it is assumed that each task is associated with a unique set of resource requirements. In the scope of multi-robot task allocation problem, these requirements can be satisfied by a coalition of robots. In this paper, we introduce a more general formulation of multi-robot task allocation problem that allows more than one option for specifying the set of task requirements--satisfying any one of the options will satisfy the task. We referred to this new problem as the multi-robot task allocation problem with task variants. First, we theoretically show that this extension fortunately does not impact the complexity class, which is still NP-complete. For solution methods, we adapt two previous greedy methods for the task allocation problem without task variants to solve this new problem and analyze their effectiveness. In particular, we "flatten" the new problem to the problem without task variants, modify the previous methods to solve the flattened problem, and prove that the bounds still hold. Finally, we thoroughly evaluate these two methods along with a random baseline to demonstrate their efficacy for the new problem.