A new sensor-based path-planning algorithm whose path length is shorter on the average

Abstract

In many sensor-based path-planning algorithms, the worst path length has been theoretically evaluated, but the average path length will not be theoretically and experimentally evaluated at all. In general, shorting average path length is worth much than shorting worst path length in the practical use. Therefore, we propose a new sensor-based path-planning algorithm whose path length is exactly shorten on the average. The algorithm always expands the best crack of a spanned graph from an initial position. All cracks mean all tips of routes traced from hit and/or leave points and also all neighbors of hit and/or leave points not to trace. The evaluation and expansion work by A* in the spanned graph. By selection of the best node, a mobile robot frequently reverses its direction following an uncertain obstacle. For this reason, the robot frequently passes through a shorter interval around an unknown obstacle three times or more. As a result, the worst path length cannot be bounded as any small value. However, a total driving distance is completely saved by following a short boundary three times or more, which is faster than following a long boundary two times. In this paper, we ascertain the superiority of our algorithm experimentally by a huge number of unknown environments.