Parallel search algorithms for robot motion planning

Abstract

The authors show that parallel search techniques derived from their sequential counterparts can enable the solution of instances of the robot motion planning problem which are computationally infeasible on sequential machines. A parallel version of a robot motion planning algorithm based on quasibest first search with randomized escape from local minima and random backtracking is presented. Its performance on a problem instance, which was computationally infeasible on a single processor of an nCUBE2 multicomputer, is discussed. The limitations of parallel robot motion planning systems are discussed, and a course for future work is suggested.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>