Parallel computation of robot motion planning algorithms

Abstract

The work described in this thesis addresses the problem of planning collision-free paths for a robot working in the presence of obstacles. It investigates the complexity usually found in algorithms for solving this problem, focusing on exploiting the inherent parallelism that some of these algorithms may possess and also proposing new or modified techniques which may be amenable to computation in parallel.
A new parallel implementation of an algorithm for the construction of a robot configuration space is presented. The computationally expensive algorithm is partitioned exploiting its inherent parallel structure and mapped onto a network of transputers for parallel computation. Various topologies and allocation strategies are investigated in order to speed up the execution time.
A path planning method based on an analogy with fluid mechanics is developed. The method, in particular, possesses the advantage of being able to generate multiple collision-free paths from a single stream function. The algorithm which is based on relatively simple computations, is partitioned for parallel implementation. Performance analysis using the processor farm computational model is conducted.
The development of an algorithm which may generate near-optimal paths is introduced. The method, based on a Genetic Algorithm (GA), possesses an inherent parallelism in searching for optimal points belonging to a collision-free path. Evaluation of the GA parameters and their behaviour is undertaken to determine the most suitable values in this context. Study cases involving a mobile robot and a revolute robot manipulator working in the presence of multiple obstacles are presented. A time complexity study of a sequential-GA against a parallel-GA is carried out with a view of further exploitation of the GA' s potential for parallel computation.

Date of Award	Sept 1992
Original language	English
Awarding Institution	University College of North Wales, Bangor
Sponsors	Universidad Nacional Aut´onoma de Mexico & Consejo Nacional de Ciencia y Tecnologia (CONACYT)