Parallel Search Algorithms for Robot Motion Planning

Daniel J. Challou, Maria Gini, and Vipin Kumar

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.