A decentralized spatial partitioning algorithm based on the minimum control effort metric

We consider the problem of characterizing a spatial partition of the position space of a team of vehicles with double integrator kinematics. The proximity relations between the vehicles and an arbitrary target point in the partition space is the minimum control effort required for each vehicle to reach the latter point with zero miss distance and exactly zero velocity at a prescribed final time (both the finite and the infinite horizon are considered). We show that the solution to the generalized Voronoi partitioning problem can be associated with a class of affine diagrams whose combinatorial complexity is comparable to the standard Voronoi diagram. For the computation of the latter class of affine diagrams, we utilize a partitioning algorithm, which is decentralized in the sense that each vehicle can compute an approximation of its own cell independently from the other vehicles from the same team. Numerical simulations that illustrate the theoretical developments are also presented.