Fast path planning using modified A* method
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
An algorithm is presented for planning the path of an object (robot) through an obstacle cluttered space by using a modified A* method for searching through the free space. The A* method can be extremely slow for large numbers of cells to be searched. The alternative presented is to use trial vectors that span several cells to aid in the planning. The fine resolution of the obstacle mapping is maintained. A loose search is performed on the fine grid. The paths that are found using this method are slightly sub-optimal. The speed of the searching algorithm is significantly increased. Solution times for three-dimensional problems are typically below 100 milliseconds, while the traditional A* search for the same problem is several minutes. The trade-off is a large speed increase for a slight degradation in path length optimality. Two-dimensional problems are solved very quickly.Keywords
This publication has 10 references indexed in Scilit:
- A vector based approach to robot path planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An Approach To Manipulator Path PlanningThe International Journal of Robotics Research, 1989
- Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsThe International Journal of Robotics Research, 1986
- On multiple moving objectsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Continuous motion planning in unknown environment for a 3D cartesian robot armPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- A subdivision algorithm in configuration space for findpath with rotationIEEE Transactions on Systems, Man, and Cybernetics, 1985
- Motion Planning with Six Degrees of Freedom. RevisionPublished by Defense Technical Information Center (DTIC) ,1984
- Solving the find-path problem by good representation of free spaceIEEE Transactions on Systems, Man, and Cybernetics, 1983
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968