Competitive searching in a generalized street

We consider the problem of a robot which has to find a target in an unknown simple polygon, based only on what it has seen so far. A street is a polyg on for which the two boundary chains from start to target are mutually weak ly visible. A target inside a street can be found by walking a path that is at most a constant times longer than the shortest path in the street from start to target. We define a strictly larger class of polygons, called gene ralized streets or G-streets, which are characterized by the property that every point on the boundary of a G-street is visible from a point on a hori zontal line segment connecting the two boundary chains. We present an on-li ne strategy for a robot to find the target in an unknown rectilinear G-stre et; the length of its path is at most 9 times the length of the shortest pa th in the L-1 metric, and 9.06 times the length of the L-2-shortest path. T hese bounds are optimal. (C) 1999 Elsevier Science B.V. All rights reserved .