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.

To design an online or sensor-based path-planning algorithm, we should decrease its search cost (the number N of visited points of a robot in a known map or the sum S of moving distances of it in an uncertain map). For this purpose, the optimal algorithm, e.g. an A* algorithm is not suitable. Because in order to select an optimal path between start and goal points, the algorithm requests a huge set of visited points or driving distances. On the observation, by decreasing the sum S, we design a new sensor-based path-planning algorithm HD-I. In almost all the sensor-based algorithms, e.g. Class 1, convergence of a robot to its goal is ensured by decreasing the distance. Also in a famous algorithm, best-first (BF), the convergence is also kept by visiting a node whose distance to its goal is the smallest. They are similar because a robot does not take a distance from a start into account. Therefore, their modified versions can be mixed. Especially, BF can investigate around an unknown obstacle whose dimensions are over two. As a result, by mixing modified BF and Class 1, we obtain a three or more dimensional algorithm HD-I.

We propose a near-optimal sensor-based motion-planning algorithm for parts mating. In part mating, only a deadlock-free path to a target point exists around the configuration space obstacle of a point robot. Because the number of unknown obstacles is only one, our algorithm is able to seek for a complicated deadlock-free path efficiently, whose upper bound of the worst path length is exactly evaluated by p+2D (p: the perimeter of the configuration space obstacle; and D: the Euclidean, distance between initial and target points). In this type of sensor-based motion-planning, the lower bound of the worst path length is described by p+D. On the other hand, an upper bound of the worst path length was given by 1.5p+D in the previous algorithm Bug1, and also it was obtained by 2p+D in the previous algorithms Alg1 and Alg2. Comparing our new algorithm with these previous algorithms, if D is fully smaller than p, we ascertain our algorithm's superiority theoretically and experimentally. The proposed algorithm is a significant algorithm because there is only a configuration space obstacle for practical parts mating.