Walking an unknown street with bounded detour
Rolf Klein · 2002
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.>