PARALLEL COMPUTATION OF CONFIGURATION-SPACE

Many motion planning methods use Configuration Space to represent a ro bot manipulator's range of motion and the obstacles which exist in its environment. The Cartesian to Configuration Space mapping is computat ionally intensive and this paper describes how the execution time can be decreased by using parallel processing. The natural tree structure of the algorithm is exploited to partition the computation into parall el tasks. An implementation programmed in the occam2 parallel computer language running on a network of INMOS transputers is described. The benefits of dynamically scheduling the tasks onto the processors are e xplained and verified by means of measured execution times on various processor network topologies. It is concluded that excellent speed-up and efficiency can be achieved provided that proper account is taken o f the variable task lengths in the computation.