Partitioning algorithms for homogeneous multi-vehicle systems with planar rigid body dynamics

We consider a generalized Voronoi partitioning problem for a team of vehicles with planar rigid body dynamics. The proximity metric, that is, the generalized metric that determines the proximity relations between the vehicles and arbitrary points in the configuration space, corresponds to the decrease of a generalized energy metric that takes place during the transfer of each vehicle to its goal configuration. In particular, the employed proximity metric is induced by a quasi-Lyapunov function of a corresponding stabilization problem. One of the main motivations for the choice of this proximity metric is to obtain a class of spatial partitions whose computational cost is significantly lower than the one of spatial partitions whose proximity metric is the cost-to-go function of a corresponding optimal control problem, which were studied in our previous work. In particular, the structure of the generalized proximity metric utilized in this work allows us to develop simple and easily implementable partitioning algorithms that are applicable to problems involving vehicles with nonlinear dynamics. More importantly, the proposed partitioning algorithms can be implemented, under some mild assumptions, in a decentralized fashion that allows each vehicle to compute its own cell independently from its teammates. Numerical simulations that illustrate the theoretical developments are also presented.