Evaluation of path length made in sensor-based path-planning with the alternative following

Abstract

As the sensor-based path-planning algorithm whose upper bound of path length is the smallest, Alg1 and Alg2 have been well known. In these algorithms, after encountering a visited point (that is, enters into a loop), a mobile robot follows an uncertain obstacle by an opposite direction until it can leave the obstacle. We call this as the "reverse procedure". Independently, if a robot always changes a direction following an uncertain obstacle alternatively, the robot arrives at a destination earlier on average (a probability for the robot to join a loop around a destination decreases). We call this as the "alternative following". In this paper, by mixing the reverse procedure and alternative following, we design new sensor-based path-planning algorithms Rev1 and Rev2. The upper bound 2D+2/spl Sigma//sub i/P/sub i/ in Rev1 and Rev2 is slightly longer than the upper bound D+2/spl Sigma//sub i/P/sub i/ in Alg1 and Alg2 (P/sub i/: the perimeter of an i-th encountered obstacle, D: the Euclidean distance between start and goal points). However, the average bound of path lengths in Rev1 and Rev2 will be shorter than that in Alg1 and Alg2. The former is fortunately evaluated by mathematical proofs, but the latter is unfortunately ascertained by several simulation results.