Parallel distributed robot navigation in the presence of obstacles

The authors present a parallel distributed processing approach to robot navigation and path planning in unknown terrains. The method is based on massively parallel computations in a grid of simple processing elements, called cells. In the course of a relaxation process a potential distribution is created in the grid with exhibits a monotonous slope from a start cell to a cell corresponding to the robot´s destination position. A shortest path is determined by means of a gradient descent criterion which settles on the steepest descent in the potential distribution. Like high-level path planning algorithms the approach is capable of planning shortest paths through an arbitrary large-scale terrain on the basis of its current internal map. Unlike these algorithms, the approach is also high responsive to new obstacles encountered in the terrain. Obstacles immediately affect the ongoing relaxation process and cause distortions in the potential distribution which are free of local minima and lead the robot on safe detours around obstacles