Skip to main content
Article
A Fast Algorithm for Planning Collision-Free Paths With Rotations
Journal of Mechanical Design
  • S.-F. Chen, Hong Kong University of Science and Technology
  • James H. Oliver, Iowa State University
  • David Fernández-Baca, Iowa State University
Document Type
Article
Publication Date
3-1-1998
DOI
10.1115/1.2826676
Abstract

Motion planning is a major problem in robotics. The objective is to plan a collision-free path for a robot moving through a workspace populated with obstacles. In this paper, we present a fast and practical algorithm for moving a convex polygonal robot among a set of polygonal obstacles with translations and rotations. The running time is O(c((n + k)N + n log n)), where c is a parameter controlling the precision of the results, n is the total number of obstacle vertices, k is the number of intersections of configuration space obstacles, and N is the number of obstacles, decomposed into convex objects. This work builds upon the slabbing method proposed by Ahrikencheikh et al. [2], which finds an optimal motion for a point among a set of nonoverlapping obstacles. Here, we extend the slabbing method to the motion planning of a convex polygonal robot with translations and rotations, which also allows overlapping configuration space obstacles. This algorithm has been fully implemented and the experimental results show that it is more robust and faster than other approaches.

Comments

This article is from Journal of Mechanical Design 120 (1998): 52–57, doi:10.1115/1.2826676. Posted with permission.

Copyright Owner
ASME
Language
en
File Format
application/pdf
Citation Information
S.-F. Chen, James H. Oliver and David Fernández-Baca. "A Fast Algorithm for Planning Collision-Free Paths With Rotations" Journal of Mechanical Design Vol. 120 Iss. 1 (1998) p. 52 - 57
Available at: http://works.bepress.com/james_oliver/21/