A ROBOT NAVIGATION STRATEGY IN UNKNOWN ENVIRONMENT AND ITS EFFICIENCY

We consider a class of unknown scenes Sk(n) with rectangular obstacles aligned with the axes such that Euclidean distance between the start point and the target is n, and any side length of each obstacle is at most k. We propose a strategy called the adaptive-bias heuristic for n avigating a robot in such a scene, and analyze its efficiency. We show that a ratio of the total distance walked by a robot using the strate gy to the shortest path distance between the start point and the targe t is at most 1 + 3/5k, if k = o(square-root n) and if the start point and the target are at the same horizontal level. This ratio is better than a ratio obtained by any strategy previously known in the class of scenes, Sk(n), such that k = o(square-root n).