Keywords

1 Introduction

Autonomous Unmanned Aerial Vehicles (UAVs) are being used for multiple missions like aerial surveillance, transport, in the military for an attack, and reconnaissance regularly. So, designing a path planner for a UAV has been a great challenging problem. Either standalone UAV or swarm of UAVs.

The RRT algorithm has been generated as the new tool for path planning where the new concept for designed a randomized data structure for a board class of path planning [1]. The RRT algorithm specifically includes the path planning problems of the nonhomlic and kinodynamic, where RRT is a data construction and its algorithm is well organized for a nonconvex in a high-dimensional space. The RRT algorithm path planner has been commonly used in the robotics field to deal with the kinodynamic problem but Kothari [3] described the multiple path planning by using the RRT algorithm in a real time with conditions of kinematic constraints.

Kala [4] presented a path planning of multiple vehicles by using RRT algorithm where it increased the overall efficiency and safe driving of vehicles. The paper [5] generated a path planning for robotic by using the RRT algorithm. Then in the paper Zhen and Alejo [6, 7] proposed a cooperative path planning for multiple UAVs formation by using online path planning method. Furthermore, Yang [8] proposed 3D path planning of RRT algorithm and did a comparison with other algorithms. The RRT algorithm selected for a single query forms a path planning.

In this work, improvement has been done in the RRT algorithm and formed a multiple path planning for multiple UAVs based on RRT algorithm because it is faster than other algorithms, and can be used for nonconvex geometry and worked in a high-dimensional space. For autonomous operation, path planning is of most importance and in the case of multiple UAVs flying in the same area, path planning, avoiding a collision, is a challenging problem. A number of path planning algorithms for single UAV have been reported in the literature and one of the algorithms is based on RRT. The basic concept of path planning is to join a starting point and target point in a 2D configuration space, denoted by C and parameters used (x, y). The path planning method is classified into two categories: local and global approach. Local planning method is faster, but due to lack of information about replanning, the path and fail in the trap. Global can ignore these problems but computationally costly [2].

The paper is organized as: Sect. 2 deals with RRT algorithm and its modification. Section 3 presents the simulation results, where improve RRT Path planning and multiple path formations for a UAVs tested result shown. Section 4 Conclusion.

2 Path Planning with RRT Algorithm

2.1 Basic RRT Algorithm

There are number of ways to approach path planning either go through graph search like A*, RRT, D*, Dijkstra algorithm, Probabilistic Road Map (PRM), cell decomposition, potential field method, or directly approach through evolutionary algorithms [6]. The study focuses in RRT algorithm because it is very fast in formatting route, there is no complex calculation required, path continuous plan in configuration space (RRT algorithm work in a high-dimensional space), capable to handle large and randomly in search space, work for nonconvex geometry, and have kinodynamic planning. The basic principle of RRT algorithm depends on the tree structure, tree generated randomly, or deterministic in a given specific area. An incremental sampling is based on single query planer form an RRT, where it allows to build a tree of a feasible path by extending the branches toward a randomly approaching target node without any parameter tuning [4]. The standard RRT algorithm tree construction or node extension for path planning is given in Fig. 1.

Fig. 1
figure 1

RRT algorithm node extension

Full size image

The tree begins with the initial state, Xinit as the root node of the UAV. A node is randomly approaching in space, denoted by state Xrand, in which choices the possibility of the target node, represented by Xtarget, and the nearest point (Xnear) in the RRT to the random node has choices. From a node nearest neighbor (Xnear), the tree moves one footstep forward (with predefined length δ), move toward the existing random node Xrand and after that added new nodes and new arc, represented by Xnew. The extending nearest-neighbor point moves toward Xrand, and a collision test is performed so that Xnew is not added to RRT. The above procedure is repeated until the branches reach a target point Xtarget or maximum nodes achieve. A feasible path planning has been done by RRT algorithm (pseudocode is given below) to generate a path from starting node to target node [2].

  • Select initial starting node Xinit

  • Generation of free in a loop

    • for i: k

    • generate random number Xrand

    • set a distance δ

  • Select the point nearest Xnear to Xinit and Xrand by δ distance δ is a length to select the input between Xrand and Xnear

    • Xnew generated a new state with the help of parameter Xnear and δ Vertex point generated

    • Joined the initial and final nodes

    • end the loop

  • find the completed node from Xinit to Xtarget

2.2 Modification in RRT Algorithm Based on Path Planning

To use the RRT algorithm for multiple UAVs path planning, a modification has been done by using the RRT algorithm where for each path, it chooses different δ and a vertex index array is generated for the path. Further, these vertexes are deleted when using RRT algorithm for another UAV path planning. This leads to nonavailability of nodes (vertex) for the path generation for multiple UAVs.

The problem has solved for multiple path planning of UAVs without colliding with each other and optimal trajectory formation in the 2D configuration space. Here, from the initial point the tree vertex continues searching for a target node and once the target node finds out by tree vertex, path gets generated by a UAV 1, after that the tree vertex of UAV 1 gets deleted, so that it is no longer available for other UAV path and then go to initial point of UAV 2, from initial point of UAV 2 again the tree vertex generates and continues searching for the target node, once the target node finds out, path gets generated and vertex gets deleted. Similarily, the path planning has been done for UAV 3, UAV 4, and UAV 5, without colliding with each other in 2D configuration space (Fig. 2).

Fig. 2
figure 2

Flowchart of multiple path planning for UAVs

Full size image
Fig. 3
figure 3

a, b Represents a path planning of RRT algorithm where the black node is the starting point and the green node is the target point, as shown in the figure every time, the path change in every iteration because nodes help in generating the path planning

Full size image
Fig. 4
figure 4

a, b Represents an improvement in RRT algorithm, as shown that there is no change in the path planning of a UAV, the starting and target nodes are same and configuration space is the same and same path with optimal formation of path take place because reduces the length of tree vertex and the convergence of tree vertex take place

Full size image

3 Simulation of the Modified Algorithm Has Been Done in MATLAB

The effective and validity of the algorithm is tested under a MATLAB software in 2D configuration space. It represents an improvement in path generated as shown in Fig. 5. The black and green node represents the starting and target position, respectively. The curve denoted the path planned in 5000 iterations, and each dot represents a single iteration. The maximum or minimum time required to complete a single iteration is about, 0.2 and 0.03 s (Figs. 3 and 4).

Fig. 5
figure 5

a–c Represents multiple path planning of UAVs Here, the black color is the starting node and the green color is the destination nodes for a UAVs in a 2D configuration space. The multiple path formations with differences in color, these all path are not colliding from each other (if there are less or more distances) or allowed the UAVs to move from the same point and move to the different destinations or allowed the UAVs to move from the different starting point to the same destination. In each case, the path generated by multiple UAVs is not colliding with each other and form the optimal trajectory

Full size image

The second problem is to approach the path planning for a multiple UAVs with the help of RRT algorithm, where the multiple path planning of multiple UAVs is done in 2D configuration space (with a high-dimensional formation, in a kinodynamic environment). Path forming by a multiple UAVs are different in color, moving symmetrically without colliding with each other. There are around five path planning has been done between UAVs, with 5000 in iterations.

4 Conclusion

In this paper, RRT algorithm has been modified to solve the problem for multiple path planning of UAVs in 2D configuration space, where it got an appropriate result for an optimal path planning for multiple autonomous. UAVs have been based on RRT by using RRT algorithm, which helps to form path planning for multiple UAVs without colliding with each other, generate the minimum distance between the nodes, and also help to give an optimal path trajectory. The improvement has been done in the RRT algorithm to generate a path with minimum distance and the same path for each iteration. In future scope, the obstacle has been formed in the RRT algorithm for 2D configuration space, where to avoid the obstacles of multiple path planning for multiple UAVs by using RRT algorithm.