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

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.

Authors:

• Luiz G. Véras
• Felipe L. Medeiros
• Lamartine F. Guimarães

Keywords:

• Path planning
• path smoothing
• Pythagorean hodograph curve
• RRT*-Smart.

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.