NAVIGATING IN UNKNOWN ENVIRONMENT WITH RECTANGULAR OBSTACLES

We study robot navigation in unknown environment with rectangular obst acles aligned with the x and y axes. We propose a strategy called the modified-bian heuristic, and analyze its efficiency. Let n be the dist ance between the start point and the target of robot navigation, and l et k be the maximum side length among the obstacles in a scene. We sho w that if k = (o(square-root n) and if the summation of the widths of the obstacles on the line crossing the target and along the y axis is o(n), then the ratio of the total distance walked by the robot to the shortest path length between the start point and the target is at most arbitrarily close to 1+k/2, as n grows. For the same restrictions as above on the sizes of the obstacles, the ratio is also at most arbitra rily close to 1 + 3 hBAR/4n, as n grows, where hBAR is the summation o f the lengths of the obstacles in y axis direction.