1

1

10008996

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.

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