For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Robot Navigation Strategy in Unknown Environment and Its Efficiency
Aohan MEI Yoshihide IGARASHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/04/25
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>>
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).