Balancing Deployment Costs in Multi-Robot Task Assignment

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, minimizing the robot tour lengths and maximizing the number of serviced tasks within given time windows. However, this does not consider an equitable distribution of the workload among the fleet. Yet, uneven workloads are often undesirable since it can incur solutions where few robots service most tasks while parts of the fleet remain underused. On the other hand, under fully balanced workloads robots may insufficiently consider the total operation cost and thus can be deployed 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 individual robot tours. We explore how 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 multi-objective 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 provide insights into 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 with respect to balanced workloads compared to state-of-the-art formulations.