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

In the last decade, many sensor-based path-planning algorithms have been proposed. These algorithms completely guarantee that a mobile robot arrives at its destination in an unknown 2-D environment if a deadlock-free path to the destination exists. However, due to no information of obstacle shape and location, a mobile robot frequently mates a very long path to its destination. To overcome this drawback, we focus on how a mobile robot selects its direction to follow an encountered obstacle. For this purpose, in an uncertain 2-D 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(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(2)=(Path length selected by Class1)/(Path length selected by Simple(Class1)). Also, we determine a competitive ratio r(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(2)=(Path length selected by Bug2)/(Path length selected by Simple(Bug2)). Because the competitive ratio r(1) is bounded by a small finite value, the new algorithms are regarded as near-optimal algorithms. On the other hand, because the worst ratio r(2) is determined by a large finite value or infinite, the new algorithms are extremely improved against the classic algorithms.