Optimal Configurations in Coverage Control with Polynomial Costs
For robotic coverage control, it provides a method to guarantee global optimality, though limited to polynomial costs and simple motion.
The paper uses numerical algebraic geometry to find global minima for coverage control with polynomial costs, outperforming Lloyd descent which only finds local minima.
We revisit the static coverage control problem for placement of vehicles with simple motion on the real line, under the assumption that the cost is a polynomial function of the locations of the vehicles. The main contribution of this paper is to demonstrate the use of tools from numerical algebraic geometry, in particular, a numerical polynomial homotopy continuation method that guarantees to find all solutions of polynomial equations, in order to characterize the \emph{global minima} for the coverage control problem. The results are then compared against a classic distributed approach involving the use of Lloyd descent, which is known to converge only to a local minimum under certain technical conditions.