Walking an unknown street with bounded detour

Abstract

A polygon with two distinguished vertices, s and g, is called a street if the two boundary chains from s to g are mutually weakly visible. For a mobile robot with onboard vision, a strategy for finding a short path from s to g in a street not known in advance is described, and it is proved that the length of the path created does not exceed 1+3 pi /2 times the length of the shortest path from s to g. Experiments suggest that the strategy is much better than this, as no ratio bigger than 1.8 has yet been observed. This is complemented by a lower bound of 1.41 for the relative detour each strategy can be forced to generate.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>