Parallel search algorithms for robot motion planning
- 31 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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.Keywords
This publication has 11 references indexed in Scilit:
- Parallel robot motion planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- PRA*: a memory-limited heuristic search procedure for the Connection MachinePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the efficiency of parallel backtrackingIEEE Transactions on Parallel and Distributed Systems, 1993
- Robot Motion Planning: A Distributed Representation ApproachThe International Journal of Robotics Research, 1991
- Automatic test pattern generation on parallel processorsParallel Computing, 1991
- Heuristic search in restricted memoryArtificial Intelligence, 1989
- Parallel depth first search. Part I. ImplementationInternational Journal of Parallel Programming, 1987
- Spatial Planning: A Configuration Space ApproachIEEE Transactions on Computers, 1983
- Complexity of the mover's problem and generalizationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Validity of the single processor approach to achieving large scale computing capabilitiesPublished by Association for Computing Machinery (ACM) ,1967