A parallel processor algorithm for robot route planning

Abstract

This paper presents a fast, uniform, parallel search algorithm for robot route planning and obstacle avoidance. The algorithm is equally applicable to real or synthetic data and overcomes many problems associated with other route finding methods. The time taken to generate a route through a an arbitrarily complex environment has been reduced to an insignificant fraction of the time taken for the robot to traverse the route. Furthermore the time taken to create the route is independent of environment complexity and only linearly proportional to route length. Actual results and timings from running the algorithm on the ICL Distributed Array Processor and executing the resultant path on a mobile robot are presented.