Optimal on-line algorithms for walking with minimum number of turns in unknown streets

Abstract

A simple polygon P with two distinguished vertices s and t is said to be a street if the clockwise and counterclockwise boundary of P from s to t are mutually weakly visible. We consider the problem of traversing a path from s to t in an unknown street P for a mobile robot with on-board vision system such that the number of links in the path is as small as possible. To our knowledge, this problem has not been studied before. We present an algorithm for this problem that requires at most 2m - 1 links to reach from s to t, where m denotes the link distance between s and t in P. Hence the competitive ratio of our algorithm is 2-1/m. We also show that any on-line algorithm for the above problem will require 2m - 1 links in the worst case which establishes that our algorithm is optimal. We next consider the above problem for the special case when P is a rectilinear street and the path is required to be a rectilinear path. We propose an algorithm for this problem that requires at most m + 1 links to reach from s to t, where m denotes the rectilinear link distance between s and t in P. Hence the competitive ratio of our algorithm is 1+1/m. We also show that any on-line algorithm for this problem will require m + 1 links in the worst case which establishes that our algorithm is optimal.