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.