Efficient Multi-Robot Task Allocation with Nonsmooth Objective Functions for Persistent Monitoring in Large Dispersed Areas

Abstract

This paper considers the multi-robot task allocation problem for persistent monitoring over large dispersed areas. The problem is formulated as a binary optimization problem with nonsmooth objective functions. To solve this optimization problem, we first propose quadratic objective functions to approximate the original nonsmooth objective functions. Inspired by the nature of the constraint of the problem, a simple strategy is presented to ensure the concavity of the quadratic functions. Finally, the fact that the constraint matrix of the optimization problem is totally unimodular allows us to relax the binary decision variables into continuous ones without changing the optimal solutions. We demonstrate using a case study that compared to the original problem, the proposed approximation provides less computational burden for small-size problems with occasional negligible trade-offs in the optimality of the solution. The comparison of the two objective functions for task allocation is also provided.