AI summary
Problem
Existing multi-robot task allocation methods assume robots handle one task at a time, ignoring the complex physical constraints that arise during multitasking, which often leads to inefficient or impossible assignments in constrained environments.
Approach
The authors introduce TAMPiC, a framework that models interdependent physical constraints and compiles the allocation problem into weighted MAX-SAT, supplemented by a greedy heuristic for efficient solving.
Key results
- Formalizes multitasking task allocation under physical constraints (TAMPiC)
- Compiles constraints to weighted MAX-SAT for solver-based optimization
- Outperforms single-tasking baselines in synthetic task efficiency
- Demonstrates scalability and complex interaction handling in realistic simulations
Why it matters
Allows multi-robot systems to automatically identify feasible multitasking synergies and operate effectively in space-constrained or physically complex real-world scenarios.
Abstract
One simplifying assumption in existing and well- performing task allocation methods is that the robots are single-tasking: each robot operates on a single task at any given time. While this assumption is harmless to make in some situations, it can be inefficient or even infeasible in others. In this paper, we consider assigning multi-robot tasks to multitasking robots. The key contribution is a novel task alloca- tion framework that incorporates the consideration of physical constraints introduced by multitasking. This is in contrast to the existing work where such constraints are largely ignored. After formulating the problem, we propose a compilation to weighted MAX-SAT, which allows us to leverage existing solvers for a solution. A more efficient greedy heuristic is then introduced. For evaluation, we first compare our methods with a modern baseline that is efficient for single-tasking robots to validate the benefits of multitasking in synthetic domains. Then, using a site-clearing scenario in simulation, we further illustrate the complex task interaction considered by the multitasking robots in our approach to demonstrate its performance. Finally, we demonstrate a higher-complexity simulation to demonstrate the scalability and applicability of our approach.