Distributed partitioning algorithms for multi-agent networks with quadratic proximity metrics and sensing constraints

We consider a class of Voronoi-like partitioning problems, in which a multi-agent network seeks to subdivide a subset of an affine space into a finite number of cells in the presence of sensing constraints. The cell of this subdivision that is assigned to a particular agent consists exclusively of points that can be sensed by this agent and are closer to it than to any other agent that can also sense them. The proximity between an agent and an arbitrary point is measured in terms of a non-homogeneous quadratic (generalized) distance function, which does not, in general, enjoy the triangle inequality and the symmetry property. One of the consequences of this fact is that the structure of the sublevel sets of the utilized proximity metric does not conform with that of the sensing region of an agent. Due to this mismatch, it is possible that a point may be assigned to an agent which is different from its “nearest” agent simply because the nearest agent cannot sense this point, unless special care is taken. We propose a distributed partitioning algorithm that enables each agent to compute its own cell independently from the other agents when the only information available to it is the positions and the velocities of the agents that lie inside its sensing region. The algorithm is based on an iterative process that adjusts the size of the sensing region of each agent until the associated cell of the latter corresponds to the intersection of its sensing region with the cell that would have been assigned to it in the absence of sensing constraints. The correctness of the proposed distributed algorithm, which successfully handles the aforementioned issues, is studied in detail.