Using Path Transforms to Guide the Search for Findpath in 2D
Author:
- 1 August 1994
- journal article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 13 (4) , 315-325
Abstract
This article will present a new approach to the 2D findpath problem for robots that have three degrees of freedom of move ment (3 DOF). This approach is based on a new extension to distance transform planning called the path transform. Path transforms have the desirable potential field property of taking into account clearance from obstacles without suffering the problem of local minima. Because path transforms guide the search for a 3-DOF path where solution paths are likely to lie, the computational burden of the new approach is low compared with that in previously reported results. The low computational burden is also due to efficient collision detection. A new hier archical collision checking based on distance space bubbles is presented. The new approach to findpath is guaranteed to find a solution path if it exists. Computer simulation results of solving the findpath problem in nontrivial environments are presented.Keywords
This publication has 11 references indexed in Scilit:
- Robot Motion Planning: A Distributed Representation ApproachThe International Journal of Robotics Research, 1991
- New heuristic algorithms for efficient hierarchical path planningIEEE Transactions on Robotics and Automation, 1991
- Internalized plans: A representation for action resourcesRobotics and Autonomous Systems, 1990
- 2D Path Planning: A Configuration Space Heuristic ApproachThe International Journal of Robotics Research, 1990
- Motor Schema — Based Mobile Robot NavigationThe International Journal of Robotics Research, 1989
- A search algorithm for motion planning with six degrees of freedomArtificial Intelligence, 1987
- Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsThe International Journal of Robotics Research, 1986
- A subdivision algorithm in configuration space for findpath with rotationIEEE Transactions on Systems, Man, and Cybernetics, 1985
- On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriersCommunications on Pure and Applied Mathematics, 1983
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968