Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T10:11:39.401Z Has data issue: false hasContentIssue false
  • English
  • Français

Parallel computation of configuration space

Published online by Cambridge University Press:  09 March 2009

J. Solano González  and
D.I. Jonest
J. Solano González
Affiliation:
Instituto de Investigaciones en Matematicas y en Sistemas, Departamento de Electronica y Automatizacion, Universidad Nacional Autonoma de Mexico, Apartado Postal 20–276, Admon - No 20, 01000, Mexico, DF (Mexico)
D.I. Jonest
Affiliation:
School of Electronic Engineering and Computer Systems, University of Wales, Dean Street, Bangor, Gwynedd LL57IUT, North Wales (UK).
Get access Rights & Permissions [Opens in a new window]

Summary

Many motion planning methods use Configuration Space to represent a robot manipulator's range of motion and the obstacles which exist in its environment. The Cartesian to Configuration Space mapping is computationally 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 parallel 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 explained 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 of the variable task lengths in the computation.

Keywords

Configuration spaceParallel computationObstaclesMotion planning
Type
Article
Information
Robotica , Volume 14 , Issue 2 , March 1996 , pp. 205 - 212
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Latombe, J.C., Robot Motion Planning (Kluwer Academic, Amsterdam, 1991).CrossRefGoogle Scholar
2.Fujimura, K. and Samet, H., “Planning a time-minimal motion among moving obstacles” Algorithmica 10, 41–63 (1993).CrossRefGoogle Scholar
3.Fujimura, K., “Motion planning amid transient obstacles” Int. J. Rob. Res. 13 (5), 395–407 (1994).CrossRefGoogle Scholar
4.Lozano-Pérez, T., “Spatial planning: a configuration space approach” IEEE Trans Computers C-32 (2), 108–120 (02, 1983).CrossRefGoogle Scholar
5.Lozano-Pérez, T., “A simple motion-planning algorithm for general robot manipulators” IEEE Trans Robotics and Automation, RA-3 (3), 224–238 (06, 1987).CrossRefGoogle Scholar
6.Maciejewski, A.A. and Fox, J.J., “Path planning and the topology of configuration space” IEEE Trans Robotics & Automation, RA-9 (4), 444–456 (08, 1993).CrossRefGoogle Scholar
7.Fleming, P.J. (ed.), Parallel Processing in Control: the transputer and other architectures, IEE Control Engineering Series 38 (Peter Peregrinus, London, 1988).CrossRefGoogle Scholar
8.Burns, A. and Wellings, A., Real-Time Systems and their Programming Languages, Ch. 9 (Addison Wesley, Reading, Mass., 1989).Google Scholar
9.Stone, H.S., High Performance Computer Architecture (2nd ed), Ch.5 (Addison Wesley, Reading, Mass., 1990).Google Scholar
10.Sarkar, V., Partitioning and Scheduling Parallel Programs for Multiprocessors Research Monographs in Parallel Distributed Computing (Pitman, London, 1989).Google Scholar
11.Solano-Gonzalez, J., “Parallel computation of robot motion planning algorithms” PhD Thesis (University of Wales, Bangor, UK, 1992).Google Scholar
12.Doyle, A.B. and Jones, D.I., “A tangent based method for robot path planning” Proc. IEEE Conf. Robotics & Automation,San Diego(1994) pp. 1561–1566.Google Scholar
13.Doyle, A.B. and Jones, D.I., “A parallel method of robot path planning using a transputer network”, Proc. Irish Colloquium on DSP and Control,Dublin(1993), pp. 35–42.Google Scholar
14.Jones, D.I., Crummey, T.P., Fleming, P.J. and Marnane, W.P., “A hardware scheduler for parallel processing in control applications” Proc. IEE Conf. Control'94,Warwick, UK,IEE Conference Publication No 389(1994) pp. 1098–1103.Google Scholar
15.Liu, Y.H. and Arimoto, S., “Proposal of tangent graph and extended tangent graph for path planning of mobile robots” Proc. IEEE Conf. Robotics & Automation,Sacramento(1991) pp. 312–317.Google Scholar
16.Liu, Y.H. and Onda, H., “Constructing an approximate representation of a configuration space without using an intersection check” Proc. IEEE/RSJ Conf. Intelligent Robots & Systems,Yokohama(1993) pp. 644- 651.Google Scholar