On the near-optimality of sensor-based navigation in a 2D unknown environment with simple shape

Abstract

We focus on how a mobile robot selects its direction to follow an encountered obstacle. For this purpose, in an uncertain 2D environment with simple shape, we propose new sensor-based navigation algorithms Simple(Class1) and Simple(Bug2) based on classic algorithms Class1 and Bug2. Moreover, in order to show a near-optimality of the proposed algorithms, we determine a competitive ratio r/sub 1/=(path length selected by Simple(Class1))/(the shortest path length selected by the model-based path-planning), and also determine a worst ratio r/sub 2/=(path length selected by Class1/(path length selected by Simple(Class1)). Also, we determine a competitive ratio r/sub 1/=(path length selected by Simple(Bug2))/(the shortest path length selected by the model-based path-planning), and also determine a worst ratio r/sub 2/=(path length selected by Bug2)/(path length selected by Simple(Bug2)). Since the competitive ratio r/sub 1/ is bounded by a small finite value, the new algorithms are regarded as near-optimal algorithms. On the other hand, since the worst ratio r/sub 2/ is determined by a large finite valve or infinite, the new algorithms are greatly improved against the classic algorithms.