Abstract
Free space is represented as a union of (possibly overlapping) generalized cones. An algorithm is presented which efficiently finds good collision-free paths for convex polygonal bodies through space littered with obstacle polygons. The paths are good in the sense that the distance of closest approach to an obstacle over the path is usually far from minimal over the class of topologically equivalent collision-free paths. The algorithm is based on characterizing the volume swept by a body as it is translated and rotated as a generalized cone, and determining under what conditions one generalized cone is a subset of another.
Keywords
ObstaclePath (computing)Cone (formal languages)Representation (politics)MathematicsSpace (punctuation)Regular polygonFree spaceCombinatoricsGeometryComputer scienceAlgorithmPhysics
Affiliated Institutions
Related Publications
Redundant Sensors for Mobile Robot Navigation
Abstract : Redundant sensors are needed on a mobile robot so that the accuracy with which it perceives its surroundings can be increased. Sonar and infrared sensors are used her...
Reentrant polygon clipping
A new family of clipping algorithms is described. These algorithms are able to clip polygons against irregular convex plane-faced volumes in three dimensions, removing the parts...
Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes
The Delaunay tessellation in n-dimensional space is a space-filling aggregate of n-simplices. These n-simplices are the dual forms of the vertices in the commonly used Voronoi t...
A unified approach to loop-free routing using distance vectors or link states
We present a unified approach for the dynamic computation of shortest paths in a computer network using either distance vectors or link states. We describe a distributed algorit...
A method for registration of 3-D shapes
The authors describe a general-purpose, representation-independent method for the accurate and computationally efficient registration of 3-D shapes including free-form curves an...
Publication Info
- Year
- 1983
- Type
- article
- Volume
- SMC-13
- Issue
- 2
- Pages
- 190-197
- Citations
- 602
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
602
OpenAlex
Cite This
Rodney A. Brooks
(1983).
Solving the find-path problem by good representation of free space.
IEEE Transactions on Systems Man and Cybernetics
, SMC-13
(2)
, 190-197.
https://doi.org/10.1109/tsmc.1983.6313112
Identifiers
- DOI
- 10.1109/tsmc.1983.6313112