A motion planner for multiple mobile robots

4 December 2002

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 8-13 vol.1
https://doi.org/10.1109/robot.1990.125937

Abstract

An algorithm is described for planning the motions of several mobile robots which share the same workspace. Each robot is capable of independent translational motion in two dimensions, and the workspace contains polygonal obstacles. The algorithm computes a path for each robot which avoids all obstacles in the workspace as well as the other robots. It is guaranteed to find a solution if one exists. The algorithm takes a cell decomposition approach, where the decomposition used is based on the idea of a product operation defined on the cells in a decomposition of a two-dimensional free space. This algorithm is being implemented for the case of two robots as part of ongoing research into useful algorithms for task-level programming of the RobotWorld system.

Keywords

This publication has 11 references indexed in Scilit:

Algorithmic motion planning in robotics
Computer, 1989
Coordinated motion planning for two independent robots
Published by Association for Computing Machinery (ACM) ,1988
On multiple moving objects
Algorithmica, 1987
Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams
Discrete & Computational Geometry, 1987
Algorithms in Combinatorial Geometry
Published by Springer Nature ,1987
Computational Geometry
Published by Springer Nature ,1985
Computational Geometry and Motion Planning
Published by Elsevier ,1985
On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE- Hardness of the "Warehouseman's Problem"
The International Journal of Robotics Research, 1984
On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds
Advances in Applied Mathematics, 1983
Spatial Planning: A Configuration Space Approach
IEEE Transactions on Computers, 1983