The visit problem: visibility graph-based solution

Abstract

An algorithm to navigate a point robot through a sequence of destination points amid unknown stationary polygonal obstacles in a two-dimensional terrain is presented. The algorithm implements learning in the course of building a global terrain model by integrating the sensor information obtained during navigation. This global model is used in planning future navigational paths. This approach prevents the robot from making localized detours, and results in better navigation, in an average case, than obtained using algorithms without learning. The proposed algorithms are implemented in the C language on a simulator for a HERMIES-II robot running on an IBM PC.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>