Decentralized spatial partitioning algorithms for multi-vehicle systems 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 linear time-varying kinematics. The generalized metric that determines 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. We show that the solution to the generalized Voronoi partitioning problem can be associated with a special class of spatial partitions known as affine diagrams. Because the combinatorial complexity of the affine diagrams is comparable to the one of the standard Voronoi diagrams, their computation does not pose a significant challenge in applications of multi-vehicle systems. Subsequently, we propose an algorithm for the computation of the spatial partition, 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 without utilizing a common spatial mesh. Numerical simulations that illustrate the theoretical developments are also presented.