A sufficient condition for designing a family of sensor-based deadlock-free path-planning algorithms
Hiroshi Noborio · Advanced Robotics · 1992
An intelligent automaton should always arrive at its goal automatically while avoiding the obstacles in a two-dimensional (2D) world. If the automaton does not know the shape or location of any obstacle in the world, it gathers information on its neighbourhood from some sensor, and according to the sensor information, it avoids the closer obstacles. In this situation, a sensor-based path-planning algorithm is used to determine the automaton's action flexibly according to changes in the sensor information. By this method, the automaton usually avoids the closer obstacles on the basis of the local information but it may circulate around some of the obstacles in the world because of the locality of the sensor information. If deadlock occurs, the automaton does not arrive at the goal at all. To overcome this drawback, we address a sufficient condition for designing a family of deadlock-free sensor-based path-planning algorithms in an uncertain world. Within this family, the automaton basically goes straight to the goal. If the automaton occasionally finds a hit point against an unfamiliar obstacle via the touch sensor, it traces the obstacle by touch and in time it finds a way to go straight to the goal again around the obstacle. Even under those conditions the automaton continues to trace the obstacle until its Euclidean distance to the goal is smaller than a distance index which is decreasing asymptotically. This is the sufficient condition, under which the automaton leaves the obstacle to go straight to the goal. This asymptotical approach of the leave point to the goal guarantees that the algorithm family will be deadlock-free. In the family, the automaton always goes straight to the goal if it does not trace any obstacle in the world. Thus, if the leave point comes asymptotically close to the goal, the circular space where the automaton can hit some obstacle in future decreases asymptotically. Therefore the circular space finally goes out of existence and consequently the automaton arrives at the goal. As a result, the family ensures the convergence of the automaton to the goal in an uncertain 2D world.