Application of Rapidly Exploring Random Tree Star-Smart and G2 Quintic Pythagorean Hodograph Curves to the UAV Path Planning Problem

Authors: Luiz G. Véras, Felipe L. Medeiros, Lamartine F. Guimarães

Abstract:

This work approaches the automatic planning of paths for Unmanned Aerial Vehicles (UAVs) through the application of the Rapidly Exploring Random Tree Star-Smart (RRT*-Smart) algorithm. RRT*-Smart is a sampling process of positions of a navigation environment through a tree-type graph. The algorithm consists of randomly expanding a tree from an initial position (root node) until one of its branches reaches the final position of the path to be planned. The algorithm ensures the planning of the shortest path, considering the number of iterations tending to infinity. When a new node is inserted into the tree, each neighbor node of the new node is connected to it, if and only if the extension of the path between the root node and that neighbor node, with this new connection, is less than the current extension of the path between those two nodes. RRT*-smart uses an intelligent sampling strategy to plan less extensive routes by spending a smaller number of iterations. This strategy is based on the creation of samples/nodes near to the convex vertices of the navigation environment obstacles. The planned paths are smoothed through the application of the method called quintic pythagorean hodograph curves. The smoothing process converts a route into a dynamically-viable one based on the kinematic constraints of the vehicle. This smoothing method models the hodograph components of a curve with polynomials that obey the Pythagorean Theorem. Its advantage is that the obtained structure allows computation of the curve length in an exact way, without the need for quadratural techniques for the resolution of integrals.

Keywords: Path planning, path smoothing, Pythagorean hodograph curve, RRT*-Smart.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1316688

References:

[1] Farouki, Rida T. Pythagorean—hodograph Curves. Springer Berlin Heidelberg, 2008.
[2] Farouki, Rida T. The conformal map z → z2 of the hodograph plane. Computer Aided Geometric Design, v. 11, n. 4, p. 363-390, 1994.
[3] Farouki, Rida T. et al. Path planning with Pythagorean-hodograph curves for unmanned or autonomous vehicles. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 2017.
[4] Islam, Fahad et al. RRT*-Smart: Rapid convergence implementation of RRT* towards optimal solution. In: Mechatronics and Automation (ICMA), 2012 International Conference on. IEEE, 2012. p. 1651-1656.
[5] Lavalle, Steven M. Rapidly-exploring random trees: A new tool for path planning. 1998.
[6] Karaman, Sertac; Frazzoli, Emilio. Sampling-based algorithms for optimal motion planning. The international journal of robotics research, v. 30, n. 7, p. 846-894, 2011.
[7] Fabri, Andreas; Pion, Sylvain. CGAL: The computational geometry algorithms library. In: Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. ACM, 2009. p. 538-539.
[8] Dong, Bohan; Farouki, Rida T. Algorithm 952: PHquintic: A library of basic functions for the construction and analysis of planar quintic Pythagorean-hodograph curves. ACM Transactions on Mathematical Software (TOMS), v. 41, n. 4, p. 28, 2015.
[9] Farouki, Rida T.; Sakkalis, Takis. Pythagorean hodographs. IBM Journal of Research and Development, v. 34, n. 5, p. 736-752, 1990.