Qualitative topological coverage of unknown environments by mobile robots

Abstract

This thesis considers the problem of complete coverage of unknown environments by a mobile robot. The goal of such navigation is for the robot to visit all reachable surfaces in an environment. The task of achieving complete coverage in unknown environments can be broken down into two smaller sub-tasks. The first is the construction of a spatial representation of the environment with information gathered by the robot’s sensors. The second is the use of the constructed model to plan complete coverage paths. A topological map is used for planning coverage paths in this thesis. The landmarks in the map are large scale features that occur naturally in the environment. Due to the qualitative nature of topological maps, it is rather difficult to store information about what area the robot has covered. This difficulty in storing coverage information is overcome by embedding a cell decomposition, called slice decomposition, within the map. This is achieved using landmarks in the topological map as cell boundaries in slice decomposition. Slice decomposition is a new cell decomposition method which uses the landmarks in the topological map as its cell boundaries. It decomposes a given environment into non-overlapping cells, where each cell can be covered by a robot following a zigzag pattern. A new coverage path planning algorithm, called topological coverage algorithm, is developed to generate paths from the incomplete topological map/slice decomposition, thus allowing simultaneous exploration and coverage of the environment. The need for different cell decompositions for coverage navigation was first recognised by Choset. Trapezoidal decomposition, commonly used in point-to-point path planning, creates cells that are unnecessarily small and inefficient for coverage. This is because trapezoidal decomposition aims to create only convex cells. Thus, Choset proposed boustrophedon decomposition. It introduced ideas on how to create larger cells that can be covered by a zigzag, which may not necessarily be convex. However, this work is conceptual and lacking in implementation details, especially for online creation in unknown environments. It was later followed by Morse decomposition, which addressed issues on implementation such as planning with partial representation and cell boundary detection with range sensors. The work in this thesis was developed concurrently with Morse decomposition. Similar to Morse decomposition, slice decomposition also uses the concepts introduced by boustrophedon decomposition. The main difference between Morse decomposition and slice decomposition is in the choice of cell boundaries. Morse decomposition uses surface gradients. As obstacles parallel to the sweep line are non-differentiable, rectilinear environments cannot be handled by Morse decomposition. Also, wall following on all side boundaries of a cell is needed to discover connected adjacent cells. Therefore, a rectangular coverage pattern is used instead of a zigzag. In comparison, slice decomposition uses topology changes and range sensor thresholding as cell boundaries. Due to the use of simpler landmarks, slice decomposition can handle a larger variety of environments, including ones with polygonal, elliptical and rectilinear obstacles. Also, cell boundaries can be detected from all sides of a robot, allowing a zigzag pattern to be used. As a result, the coverage path generated is shorter. This is because a zigzag does not have any retracing, unlike the rectangular pattern. The topological coverage algorithm was implemented and tested in both simulation and with a real robot. Simulation tests proved the correctness of the algorithm; while real robot tests demonstrated its feasibility under inexact conditions with noisy sensors and actuators. To evaluate experimental results quantitatively, two performance metrics were developed. While there are metrics that measure the performance of coverage experiments in simulation, there are no satisfactory ones for real robot tests. This thesis introduced techniques to measure effectiveness and efficiency of real robot coverage experiments using computer vision techniques. The two metrics were then applied to results from both simulated and real robot experiments. In simulation tests, 100% coverage was achieved for all experiments, with an average path length of 1.08. In real robot tests, the average coverage and path length attained were 91.2% and 1.22 respectively.