A unified solution to coverage and search in explored and unexplored terrains using indirect control

Abstract

An algorithm which solves the coverage and search problems in either explored or unexplored terrains is described. The coverage problem requires that the robot pass over all parts of the terrain that are free of obstacles. The search problem requires that the robot seek a specified target in a given terrain. The target need not be present in the terrain; in that case, the algorithm will realize the fact after a thorough search. In an explored terrain problem, a model of the terrain is available indicating which regions of the terrain are traversable. In an unexplored terrain problem, such a model is not available, thus forcing the robot to build the model by the use of sensors. It is proved that the algorithm guarantees complete coverage and a thorough search if physically possible. Due to its use of indirect control, the algorithm is not complicated and is thus simple to implement.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>