Sparsity Structure and Optimality of Multi-Robot Coverage Control

Abstract

The structure of the Hessian matrix obtained from the locational cost used in coverage control is investigated to provide conditions on the optimality of coverage control solutions. It is shown that in arbitrary dimensions, the Hessian matrix is composed of the direct sum of three well-structured matrices: 1) a diagonal matrix; 2) a block-diagonal matrix; and 3) block-Laplacian matrix. This structure is exploited in the one-dimensional case, where an alternative proof of a sufficient condition for optimality is given. A relationship is shown between centroidal Voronoi tessellation (CVT) configurations and the sufficient condition for optimality via the spatial derivative of the density provided in the cost. A decomposition is used to provide insight into the terms which most affect optimality. Several classes of density functions are analyzed under the proposed condition. Experiments on a multi-robot team are shown to verify theoretical results.