Range-limited, Distributed Algorithms on Higher-Order Voronoi Partitions in Multi-Robot Systems

Abstract

This paper studies the problem of distributed computation of higher order Voronoi partition over a bounded region by a group of robots with both range-limited visibility sensors and communication devices. We model the sensing and communication capabilities by discs with limited radius. Motivated by the concept of dominating region in higher-order Voronoi partition, we propose a detecting ray based algorithm, which computes the boundary points of the dominating region of a robot in an omnidirectional manner, with local position information of its neighbors within the communication range. Simulations are provided to demonstrate the performance of our proposed algorithm by using a thirteen-robot group.