A Robot Navigation Strategy in Unknown Environment and Its Efficiency

Aohan MEI  Yoshihide IGARASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.4   pp.646-651
Publication Date: 1994/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
robot navigation,  unknown environment,  rectangular obstacles,  on-line algorithms,  competitive algorithms,  

Full Text: PDF>>
Buy this Article

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 navigating 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 strategy to the shortest path distance between the start point and the target is at most 1+(3/5) k, if k=o(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(n).