Simultaneous Exploration and Coverage with Multiple Robots using Generalized Voronoi Partition

Abstract

The problem of area coverage by mobile robots is very useful in several applications such as vacuum cleaning, lawn mowing, landmine detection and de-mining, planetary exploration, etc. Using multiple robots to cover a specified region is expected to reduce the coverage time, apart from possible robustness to failure of a (or a few) robot(s). In this work we address a multi-robotic area coverage problem. When multiple robots need to cover a given area, the main concern is of avoiding repetitive coverage apart from complete coverage of the given area. Partitioning the area to be covered into cells and allotting one each cell to each of the robots for coverage solves the problem of duplicity, thus avoiding repetitive coverage, in a very simple and elegant manner. However, the spatial partitioning may lead to additional problems leading to either incomplete coverage or coverage overlap near the partition boundary, and possible non-contiguous partitioned cells in the presence of obstacles. Also, the coverage algorithms reported in the literature are either off-line, using complete prior knowledge about the arena, or online, using no a priori knowledge, but there is no provision for using any partial knowledge (of map) when available. In this thesis we address a problem of coverage path planning for multiple cooperative autonomous mobile robots. We consider a \partition and cover" approach to the multi-robotic coverage problem due to its inherent advantages of i) independent of the underlying single robot coverage algorithm, ii) reduced memory requirement due to spatial task partitioning, iii) minimal or no communication requirement during performance of the coverage task, and iv) no requirement of special collision avoidance again due the spatial task partitioning. Among the \partition and cover" approaches reported in the literature, we used Voronoi partition based coverage due to its main advantage of possible distributed implementation. One of the challenges associated with a multi-robot coverage problem is uniform load distribution among the robots. In the context of a \partition and cover" strategy employed in this thesis, this problem boils down to uniformpartitioning assuming that the coverage load is proportional to the are of the coverage. This is a classical problem of equatable partitioning that is addresses in locational optimization or sensor coverage problems. In this work, we provide a very simple solution to this problem by using the concept of the centroidal Voronoi configuration used in the locational optimization/sensor coverage literature. We introduce the concept of deploying \virtual nodes" rather than the robots and partitioning the space based on the \virtual nodes" locations. With this, we avoid unnecessary robot motion (in the sense that motion without performing coverage). We demonstrate with examples that with this approach, the areas of all the cells are approximately same, thus ensuring a uniform coverage load distribution among the individual robots. We propose Manhattan-VPC, a Manhattan distance based Voronoi Partition coverage algorithm that decomposes a 2D×2D gridded region completely avoiding partition boundary issues such as coverage gap and coverage overlap, that arise with the use of the standard Voronoi partition. Here, the robot footprint is assumed to be D × D square. We have established both by formal analysis and simulation and experiments with physical robots, that the proposed ManhattanVPC provides complete and non-overlapping coverage even in the presence of simple obstacles and completely avoids the partition boundary induced coverage gap and overlap. We also propose Geodesic-VPC, a Voronoi partition based coverage algorithm using the Geodesic distance in the place of the standard Euclidean distance. With this approach we ensure that the cells that individual robots have to cover are contiguous even in the presence of arbitrary obstacles. However, here, unlike in the case of Manhattan VPC (or the basic VPC), we assume that the map of the environment is available a priori to the planner. We then combine the Manhattan metric over the 2D × 2D grid and Geodesic metric and propose a GM-VPC algorithm. We establish both by formal analysis and simulation experiments that with the GM-VPC algorithm robots provide complete and non-overlapping coverage in the presence of arbitraryknown obstacles. Finally we combine exploration and coverage problems to address a novel SimExCoverage problem. Here, the primary task of the robots is coverage while it uses intermittent exploration to generate partial map that is used by coverage path planner. This approach combines the advantages of both the off-line and online coverage strategies. We first present a single robot SimExCoverage problem and then extend it to a multi-robotic scenario. While the Manhattan-VPC and SimExCoverage algorithms are suitable for scenarios when map of the area is not available, the Geodesic-VPC and GM-VPC strategies are useful when map of the region is available. We use a Boustrophedon-like coverage algorithm and the spanning tree based coverage algorithm which represent the approximate cellular decomposition based coverage algorithms and exact cellular decomposition based coverage algorithms reported in the literature as underlying single-robot coverage algorithms for demonstrating the proposed generalized Voronoi partition based coverage strategies and the SimExCoverage algorithms.