Abstract
This paper presents a new method for computing the configuration-space map of obstacles that is used in motion-planning algorithms. The method derives from the observation that, when the robot is a rigid object that can only translate, the configuration space is a convolution of the workspace and the robot. This convolution is computed with the use of the fast Fourier transform (FFT) algorithm. The method is particularly promising for workspaces with many and/or complicated obstacles, or when the shape of the robot is not simple. It is an inherently parallel method that can significantly benefit from existing experience and hardware on the FFT.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Keywords
WorkspaceFast Fourier transformConvolution (computer science)Computer scienceComputationRobotDiscrete Fourier transform (general)Configuration spaceComputer visionSpace (punctuation)Artificial intelligenceFourier transformObject (grammar)AlgorithmComputer graphics (images)MathematicsFourier analysisFractional Fourier transformArtificial neural network
Affiliated Institutions
Related Publications
Near-optimal nonholonomic motion planning for a system of coupled rigid bodies
How does a falling cat change her orientation in midair without violating angular momentum constraint? This has become an interesting problem to both control engineers and robot...
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...
Real time inverse kinematics for general 6R manipulators
The authors present a real-time algorithm for the inverse kinematics of general 6R robot manipulators. The algorithm involves symbolic preprocessing, matrix computation and a va...
A numerical solution to the generalized mapmaker's problem: flattening nonconvex polyhedral surfaces
Methods are described to unfold and flatten the curved, convoluted surfaces of the brain in order to study the functional architectures and neural maps embedded in them. In orde...
The wavelet transform, time-frequency localization and signal analysis
Two different procedures for effecting a frequency analysis of a time-dependent signal locally in time are studied. The first procedure is the short-time or windowed Fourier tra...
Publication Info
- Year
- 1995
- Type
- article
- Volume
- 11
- Issue
- 3
- Pages
- 408-413
- Citations
- 116
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
116
OpenAlex
88
CrossRef
Cite This
Lydia E. Kavraki
(1995).
Computation of configuration-space obstacles using the fast Fourier transform.
IEEE Transactions on Robotics and Automation
, 11
(3)
, 408-413.
https://doi.org/10.1109/70.388783
Identifiers
- DOI
- 10.1109/70.388783