Multi-agent/robot coverage using Voronoi partition

Advances in areas such as wireless communication, autonomous vehicular technology, computation, and sensors, facilitate the use of large number of agents (UAVs, mobile robots, or autonomous vehicles), equipped with sensors, communication equipment, and computation ability, to cooperatively achieve various tasks in a distributed manner. Searching for targets of interest in a large geographic region is one of the practically relevant applications of these multi-agent/robot systems (MAS/MRS). Voronoi partition is a scheme of partitioning a space based on the concept of "nearness", and finds application in many areas such as CAD, image processing, and sensor networks. We use Voronoi partition to formulate and solve multi-agent/robot coverage problems. First a multi-agent search problem using Voronoi partition is discussed, where Voronoi partition is used for deployment of agents maximizing search effectiveness. We discuss the objective function, its critical points, and a control law ensuring deployment of robots in optimal configuration. A generalization of Voronoi partition will be discussed, which accounts for heterogeneity in sensors, and generalizes a class of multi-agent optimal deployment problems. Next, we present a Voronoi partition-based coverage (VPC) algorithm for complete coverage of an initially unknown region using multiple mobile robots, for an application such as landmine detection. Each robot computes Voronoi cell using its own position and that of other robots in the network as nodes, and covers it using any single robot complete coverage algorithm. We show that the coverage is complete and non-repeating, and also the algorithm is robust to failure of some individual robots. We present a distributed algorithm for computation of Voronoi cell, and an algorithm for exploration of the boundary of Voronoi cell by a robot, which are used by the proposed multi-robot coverage algorithm.
Dr. K.R. Guruprasad obtained his Ph.D. degree from the Department of Aerospace Engineering and master's degree from the Department of Mechanical Engineering, both from the Indian Institute of Science, Bengaluru (Bangalore), India, and his bachelor's degree in Mechanical Engineering from the Karnataka Regional Engineering College (Currently named National Institute of Technology Karnataka), Surathkal, India. He is an Assistant Professor at the Department of Mechanical Engineering, National Institute of Technology Karnataka, Surathkal, India, and is currently visiting the University of Nebraska, Omaha, NE, USA as a Visiting Research Associate. His current research interests include robotics "“ dynamics, control, and path planning; Voronoi partition "“ application to multi-agent systems and locational optimization, distributed algorithms, and generalization; multi-agent/robot systems "“ deployment, cooperative control, applications such as coverage and search, etc., and physics of musical instruments