Parallel Search Algorithms for Robot Motion Planning

In this paper we show that parallel search techniques derived from their sequential counterparts can enable the solution of instances of the robot motion planning problem that are computationally infeasible on sequential machines. We present a simple parallel version of a robot motion planning algorithm based on "quasi best first" search with randomized escape from local minima and random backtracking and discuss its performance on two problem instances, one of which was computationaUy infeasible on a single processor of an nCUBE21 multicomputer. We then discuss the limitations of parallel robot motion planning systems, and suggest a course for future work.