Balancing Deployment Costs in Multi-Robot Task Assignment
Nils Wilde, Javier Alonso-Mora
AI summary
Problem
Common multi-robot task assignment objectives minimize total or maximum tour length, leading to highly imbalanced workloads where some robots are overworked while others remain underutilized or redundant. The paper addresses how to simultaneously minimize individual robot costs to achieve equitable and resource-efficient fleet deployment.
Approach
The authors formulate task assignment as a multi-objective optimization problem and introduce a p-norm heuristic to scalarize the objectives, enabling flexible trade-offs between total and maximum costs. This solver-agnostic formulation is integrated into existing algorithms without increasing computational complexity.
Key results
- Formulated generalized MRTA as a multi-objective optimization problem for simultaneous tour cost minimization
- Established theoretical guarantees that p-norm objectives approximate Pareto-optimal trade-offs between sum and max costs
- Demonstrated seamless integration of the heuristic into large neighborhood search and group assignment solvers
- Achieved balanced workloads and reduced deployment costs in offline and online multi-robot simulations
Why it matters
Enables roboticists and fleet operators to deploy multi-robot systems more equitably and efficiently without sacrificing performance or requiring complex algorithm redesign.
Abstract
Multi-Robot Task Assignment (MRTA) studies the problem of allocating spatially distributed tasks to a fleet of cooperative robots as well as determining the optimal task sequence for each robot. Common objectives include minimizing the task waiting times and robot tour lengths or maximizing the number of serviced tasks within given time windows. However, this does not consider an equitable distribution of the workload among the fleet. Uneven workloads are often undesirable when few robots may service most tasks while parts of the fleet remain underused. On the other hand, fully balanced workloads may insufficiently consider the total operation cost and thus can deploy robots in a redundant manner. In this paper, we study MRTA from the viewpoint of multi-objective optimization (MOO), formulating the problem of simultaneously minimizing the costs of all individual robot tours. This treatment allows for attaining more balanced solutions than common formulations using the sum or maximum of tour costs. We present a generalist formulation using a scalar objective and establish theoretical guarantees on the attainable trade-offs. Further, we derive an effective heuristic based on a p-norm of tour lengths that is able to find balanced workloads among robots. Our approach is agnostic to the specific choice of MRTA solver and we show how it can be incorporated into two state-of-the- art algorithms. We demonstrate our approach in experiments for offline and online MRTA setups, including servicing tasks as well as pickup and delivery, and highlight its advantages compared to state-of-the-art formulations.