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

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.