A Gridmap-Path Reshaping Algorithm for Path Planning
Open Access
- 17 December 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 7, 183150-183161
Abstract
Path planning is a vital function of robotic systems. Different from existing roadmap algorithms which first determine the free space and then determine the collision-free path, researchers recently proposed several convex relaxation based smoothing algorithms which first select an initial path to link the starting configuration and the goal configuration and then reshape this path to meet other requirements (e.g., collision-free conditions) by using convex relaxation. However, convex relaxation based smoothing algorithms often fail to give a satisfactory path, since the initial paths are selected improperly. Moreover, the curvature constraints were not considered in many existing convex relaxation based smoothing algorithms. In this paper, we show that we can first grid the whole configuration space to pick a candidate path and reshape the shortest path to meet our goal. This new algorithm inherits the merit of roadmap algorithms and a convex feasible set algorithm. We further discuss how to meet the curvature constraints by using both the Beamlet algorithm to select a better initial path and an iterative optimization algorithm to adjust the curvature of a path. Theoretical analysis and numerical testing results show that our algorithm can almost surely find a feasible path and require a short computation time.Keywords
All Related Versions
Funding Information
- Science and Technology Innovation Committee of Shenzhen (JCYJ20170818092931604)
- National Natural Science Foundation of China (61790565, 61771281)
- “New Generation Artificial Intelligence” major Project of China (2018AAA0101605)
- 2018 Industrial Internet Innovation and Development Project
- Tsinghua University
This publication has 32 references indexed in Scilit:
- On the Complexity of a Mehrotra-Type Predictor-Corrector AlgorithmLecture Notes in Computer Science, 2012
- LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state informationThe International Journal of Robotics Research, 2011
- Constrained Nonlinear Control Allocation With Singularity Avoidance Using Sequential Quadratic ProgrammingIEEE Transactions on Control Systems Technology, 2004
- Beamlets and Multiscale Image Analysis2002
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Motion planning in a plane using generalized Voronoi diagramsIEEE Transactions on Robotics and Automation, 1989
- Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"ACM SIGART Bulletin, 1972
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and TangentsAmerican Journal of Mathematics, 1957
- Individual Comparisons by Ranking MethodsBiometrics Bulletin, 1945