
For FullText 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.

Navigating in Unknown Environment with Rectangular Obstacles
Aohan MEI Yoshihide IGARASHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E77A
No.7
pp.11571162 Publication Date: 1994/07/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms, Data Structures and Computational Complexity Keyword: robot navigation, unknown environment, rectangular obstacles, online algorithms, competitive algorithms,
Full Text: PDF>>
Summary:
We study robot navigation in unknown environment with rectangular obstacles aligned with the x and y axes. We propose a strategy called the modifiedbian heuristic, and analyze its efficiency. Let n be the distance between the start point and the target of robot navigation, and let k be the maximum side length among the obstacles in a scene. We show that if k=(o(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 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 arbitrarily close to 1+3/4n, as n grows, where is the summation of lengths of the obstacles in y axis direction.

