A shortest path algorithm in robotics and its implementation on the FPS T20 hypercube

A broad class of problems involving the optimal control of robot arms can be formulated as dynamic programming problems whose structure is particularly attractive for parallel processing. For certain simple cost functions the dynamic programming formulation reduces to determining the shortest path through a network. This algorithm has been implemented on a Floating Point Systems’ T20 hypercube computer. An analysis of the performance of the algorithm provides several important insights into the interplay between problem size and the number of processors in a parallel computer. The results also underscore the potential for parallel computers in real-time control applications.