Algorithmic motion planning in robotics: Coordinated motion of several disks amidst polygonal obstacles
- 23 March 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 514-522
- https://doi.org/10.1109/robot.1985.1087248
Abstract
Given k ≥ 2 circular disks D1, D2...Dkin a 2-dimensional region bounded by a finite set of polygonal obstacles, an algorithm to determine the existence of a collision free coordinated motion of the disks is given. The time complexity is shown to be O(nk} where n is the number of edges composing the walls. This algorithm is believed to be optimal.Keywords
This publication has 4 references indexed in Scilit:
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- Complexity of the mover's problem and generalizationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Representation of contours and regions for efficient computer searchCommunications of the ACM, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972