Three or more dimensional sensor-based path-planning algorithm HD-I

Abstract

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.