Sampling-based unmanned aerial vehicle air traffic integration,path planning,and collision avoidance

Abstract

Unmanned aircraft or drones as they are sometimes called are continuing to become part of more real-life applications. The integration of unmanned aerial vehicles in public airspace is becoming an important issue that should be addressed. As the number of unmanned aerial vehicles and their applications are largely increasing, air traffic with more unmanned aircraft has to be given more attention to prevent collisions and maintain safe skies. Unmanned aerial vehicle air traffic integration and regulation has become a priority to different regulatory agencies and has become of greater interest for many researchers all around the world. In this research, a sampling-based air traffic integration, path planning, and collision avoidance approach is presented. The proposed algorithm expands an existing 2D sampling-based approach. The original 2D approach deals with only two unmanned aircraft. Each of the two aircraft shares location information with a ground-based path planner computer, which would send back the avoidance waypoints after performing the 2D sampling. The algorithm proposed in this article can handle any number of drones in the 3D space by performing either 2D or 3D sampling. The proposed work shows a 10-fold enhancement in terms of the number of unmanned aerial vehicle collisions. The presented results also contribute to enabling a better understanding of what is expected of integrating more drones in dense skies.

Introduction

Unmanned aerial vehicles (UAVs) a.k.a drones are aerial vehicles that are either fully autonomous or remotely operated. They are increasingly being integrated with civil and military applications. ^{1 –4} Several governmental, commercial, and research entities are continuously working on mass integration of UAVs in commercial air traffic. ^5,6 Many challenges complicate the integration of UAVs in public airspace. The main issue is safety and collision avoidance that is of less concern when a pilot is there to decide in real time. The Federal Aviation Administration (FAA) is continuously working on the development of rules and guidelines for operating UAVs. An example is Part 107 for operating small UAVs below 25 kg. ^7,8 Commercial firms as Google’s spin-off (Wing Aviation LLC), Amazon, UPS, TV stations, and many others have received exemptions to operate small UAVs with many restrictions like maintaining visual line of sight, restricting operations at night, and flying over people. ^7,9 It was planned that new rules to be released before the end of the year of 2020 on allowing more exemptions like allowing Operations of Small Unmanned Aircraft Over People. ¹⁰ FAA, in a press release on the 28th of December 2020, announced final rules for unmanned aircraft (UA) related to remote identification (Remote ID) and operations over people. ¹¹ The first rule (Remote ID) addresses the broadcasting of the aircraft identity, its location, and ground station or takeoff information in addition to other details. The second rule addresses the categories of drones allowed to operate over people and moving ground vehicles. It also addresses the operation of UAVs at night. The new rules shall pave the way toward more UA integration in the existing airspace. ^12,13 From the first 1000 Commercial UAS Exemptions report by AUVSI, ⁹ the number of research entities is somewhere in the middle of the list of those entities that got exemptions. More research has to be done in the field to enable the traffic integration of UAVs in the public airspace which includes path planning, sense and avoid, collision avoidance, and much more. Such research typically tries to leverage collision avoidance techniques developed in the 2D domain for ground robotics and expand on them to deal with UAVs’ motion in the 3D space. ¹⁴

Sampling-based algorithms are one approach that is used in path planning. ^15,16 Sampling-based algorithms focus on creating new intermediate paths for moving autonomous crafts safely to their target destinations. These intermediate paths intend to lead mobile vehicles such as robots, cars, UAVs, and so on that are prone to possible collisions away through other safe routes. New routes pass through best-sampled points toward target locations. These algorithms are applied to avoid possible collisions with other obstacles in the operation space. The moving vehicles are supposed to be aware of their routes, current locations, target locations, and area boundaries. Furthermore, moving vehicles should be capable of sensing surrounding stationary and/or moving objects within a certain distance or what is called throughout this study “the sensing range.” Sampling-based methods iteratively direct moving vehicles away from possible collisions using active or passive algorithms. Rapidly-exploring random tree (RRT) algorithms belong to the category of the sampling-based algorithm. ^{17 –19} The process is done by randomly generating points in the 2D or 3D space. Moving vehicles are supposed to divert their routes through these points. Sampling-point algorithms choose the lowest cost point, based on time, distance, energy consumption, and so on.

This work has built on the work presented by Lin and Saripalli ¹⁶ that has used a sampling-based algorithm for UAV trajectory generation and obstacle avoidance. The authors proposed an algorithm that operates in 3D with a fixed altitude (i.e. 2D) and handles only two vehicles called the host and an obstacle. ¹⁶ The 2D algorithm builds on the RRT category of the sampling-based algorithms. In this work, we have developed a new RRT sampling-based approach that extends the work presented in Lin and Saripalli. ¹⁶ The newly presented path planning and collision avoidance approach fully supports the operation of an unlimited number of UAVs in the 3D space. The proposed work assigns priorities to different types of aircraft and deals with them accordingly. The proposed algorithm is presented in the third section.

The rest of the article is organized as follows. The second section reviews the literature on sampling-based path planning algorithms. The third section describes the proposed 3D sampling-based path planning and collision avoidance approach. The fourth section discusses the experimental setup and results. Finally, the fifth section concludes the article.

Literature review

Path planning algorithms for UAVs are covered in the literature. ^{20 –22} Some algorithms focus on creating paths that would guarantee the UAV not getting detected by enemy radars. ²³ Other studies focused on special cases like avoiding collision with the ground for UAVs equipped with cameras for reconnaissance missions. ²⁴ UAV collision avoidance with other stationary and/or moving objects has been an attractive topic for many researchers. UAVs have been restricted in their applications due to the many concerns about their safety especially when it comes to collisions with other objects. The issue is safety-critical and such collisions are risky when the life of people on the ground and on-board other human-piloted aircraft are concerned. ^25,26

Sampling-based algorithms are usually used to drive autonomous robots through safe paths into their target locations in an area with known boundaries. The literature includes many research papers that present, analyze, and optimize such algorithms. ^{27 –31}

In Goerzen et al., ²² authors classified the algorithms of path planning for UAVs into two main classes, differential, and nondifferential. Differential algorithms take the general characteristics such as velocity and acceleration and the equations of motion into consideration when calculating the paths. Nondifferential algorithms are considered simple, lower orders, and less complicated than differential algorithms. The power of differential algorithms lies in taking the realistic parameters of UAVs into account such as velocity, acceleration, energy consumption, path length, and travel time over different routes.

The sampling-based algorithm discussed in the literature ³² presented by Donald et al. proposed a sampling-based method to be used for path planning. The researchers focused on finding the fastest path to move the robot toward its destination point, by dividing the area into discrete sections. Then the algorithm calculates for the minimal time path according to the kinematic specifications of each section. The RRT algorithm is a motion planning algorithm where the sampling-based algorithm ³² was efficiently deployed. In LaValle, ³³ the authors took this sampling-based algorithm to another level. RRT algorithm continuously grows a safe path from an initial point toward a selected point. This path passes through multiple random points selected from multiple random sampled points. The points which the path passes through are supposed to be the most feasible points according to time, path length, and so on. Later in 2007 when the Defense Advanced Research Projects Agency called for a competition aiming to make an autonomous vehicle drive safely for 60 miles in an urban area within 6 h, the winning team’s algorithm extended the RRT algorithm and created the closed-loop RRT algorithm. The closed-loop RRT algorithm generates sample points to propagate the vehicle through the most time-efficient path with no possible collisions and repeats this process until the vehicle reaches its target point. ³⁴ Later, many studies focused on using and improving the closed-loop RRT algorithm like Lin and Saripalli. ¹⁶ The work in Lin and Saripalli ¹⁶ studied and expanded the algorithm to fit autonomous UAV collision avoidance in a simplified trajectory generation approach. The study also focused on utilizing intermediate waypoints to create more reliable versions of the algorithm. They focused on collision prediction using reachable sets which make UAVs capable of predicting other moving obstacles’ motion and avoid colliding with them. Sample points presented in Lin and Saripalli ¹⁶ lack the 3D maneuvering capabilities. All generated sample points and UAVs have fixed altitudes. Fixing the algorithm to work at a known altitude for all UAVs limits the use of the 3D space which should benefit the path planning and collision avoidance computations. The 3D space gives a wider set of possible sample points. Another issue with the algorithm presented in Lin and Saripalli ¹⁶ is the limited number of UAVs it can handle. It only handles two UAVs. In this research, the proposed model builds on the sampling-based algorithm with altitude-changing capabilities. The proposed model extends the work presented in Lin and Saripalli ¹⁶ to the 3D space and theoretically works with an unlimited number of UAVs.

The proposed algorithm calculates for the shortest path. This process of sense and avoid keeps repeating itself until the UAV reaches its target location or until it crashes. Crashes are more likely to happen in a very crowded environment as will be shown later in the simulation results section.

Algorithm description

The proposed algorithm is designed to run on each UAV independently from the other UAVs. It also coordinates multiple UAV paths when there is a potential collision.

Figure 1 is a flow chart that describes the proposed collision avoidance algorithm. Each UAV starts with a vector direction toward its destination in a straight line. The potential collision would happen if two or more UAVs would come within a certain distance of each other.

Figure 1.

The proposed algorithm description.

Potential collisions happen, when an obstacle, moving, or stationary lies inside a defined virtual spherical shape centered at the moving UAV. The radius of this sphere is defined as the sensing range value. The sensing range value is configurable for each UAV and it is fixed during every run. In cases where no potential collision is detected, the simulation proceeds normally advancing UAVs to the next position allocated per the time step. However, if there is a possibility for collisions, a UAV involved in the potential collision is alerted once a UAV is detected within its sensing region.

Next, the priority of the UAVs that are involved in the potential collision is calculated. If the UAV is deemed to have the highest priority, then it keeps moving in its original direction and proceeds normally. Priority is a configurable value initially allocated to UAVs before they start moving. It can be determined considering many variables like UAV type, mission, current battery status, and so on. However, if the UAV is one of the lower priority ones, then the UAV needs to find an alternate route. To find this alternate route, a customizable set of random points are generated in the 2D or 3D space according to the current scenario.

The feasibility of a random point taken by a UAV is decided based on its coordinates relative to the UAV’s current position, direction, and flight dynamics. A feasible point shall be in front of an imaginary axis crossing the UAV and perpendicular to its direction (axis A-B) as shown in Figure 2. A feasible point has to be within the allowed sampling radius and within the operation region. These numbers as to be shown in the experimental setup section are 10 m for the sampling radius and 500 m × 500 m for the operation region. They are all customizable.

Figure 2.

Feasibility of random points.

A feasible point has to be reachable according to the motion dynamics of the UAVs that are fully handled by the UTSim simulator ⁷ and regulated by the rigid body physics engine of the Unity game engine. ^35,36 The angles system used in unity internally is the Quaternions’ system, but it is represented by Euler’s method. ³⁷

The distances from the current location of the UAV to the set of waypoints and the distances from these waypoints to the target are calculated. The point that has the shortest total distance (defined as the distance from the current location to the target through a waypoint) is selected. The newly selected point is examined whether it would help avert the potential collision or not. If it can help eliminate the possibility of the collision, then the UAV is assigned a new direction vector, and it will be moved in time toward that new direction. However, if the newly selected point would still cause a potential collision, then the point is not feasible and dropped accordingly. The process is repeated to generate a new set of points. The process continues until a feasible point is reached.

The simulator starts to move the UAV toward this temporary waypoint and later switches back to the destination once it detects that the collision has been averted. Once UAVs are moved during every time step, the algorithm checks whether they have reached their destinations or not. If they did, the algorithm for that UAV is terminated and it is recorded that it has arrived at its destination safely. What makes this algorithm special is the capability to generate sample points in the 3D space rather than fixing the altitude like the work presented in Lin and Saripalli. ¹⁶

Experimentation and results

Experimental setup

The proposed algorithm is implemented using the UTSim simulator presented in Al-Mousa et al. ⁷ The simulator allows the creation of multiple UAV instances. It also allows configuring multiple attributes of UAVs and flight operations areas. UTSim was built with the Unity platform, ⁷ allowing visual observation of moving UAVs in the 3D space as well as other feedback such as the 3D localization of all objects in the region of operation. The simulator allows for configuring routes, speed, dimensions, priority, name, and sensing range for each UAV during every run. It also allows logging all information in each simulation session. Through this study, UTSim was used to run a variety of flight scenarios and log the number of collisions, diversions, and total distances crossed by each UAV. All data about the UAVs and their flights toward their destinations were logged and analyzed for several flight scenarios.

Figure 3 depicts a screenshot of the simulation environment. As the screenshot illustrates, area (1) shows a top view of the flight simulation region. The small black dots represent UAVs. A closer view of one of the UAVs is shown in area (2). Area (3) shows the current status, messaging, and other log activities going on. Physics engine and rigid body configurations are shown in area (4).

Figure 3.

UTSim simulator environment.

The flight scenarios were implemented in both the 2D and 3D dimensions having the UAVs controlled by the proposed sampling-based algorithm. Initial locations and destinations of the UAVs were randomly generated. Each run was performed in both the 2D and 3D space 35 times. The flight operation area was 500 m × 500 m. Each UAV size was fixed to a half-meter diameter for all UAVs. The UAVs had fixed speeds of 6 m/s. Due to rigid body properties, the speed decreases when changing direction or reaching the destination. The UAVs during their operation and before reaching their destinations were not allowed to hover.

The number of drones within the flight area varied from 10 to 100 drones. In each flight cycle, the following data were collected: The total number of collisions, the total number of diversions, the total passed distance, and the total flight time in multiple flight scenarios run in both the 2D and the 3D dimensions. The number of points sampled by each of the UAVs is 25 every time a reroute is computed. This number is customizable. A UAV reroute is triggered (i.e. UAV starts sampling) either once a passive obstacle is detected or when a higher priority UAV is sensed. The sample points are taken within a radius of a circle/sphere of 10 m which is also customizable.

The UAV sensing range of obstacles is the radius of a circle or sphere centered at the UAV. When an object enters inside this circle/sphere, the sampling-based algorithm is applied to avoid the possible collision. The results for this study were built on 1.5 m and 3 m sensing range scenarios. Both 2D and 3D sampling-based algorithms were studied in the case of 1.5 m and 3 m sensing ranges.

Results and discussion

The graphs shown in Figures 4 to 7 illustrate the total number of collisions, number of diversions, distance passed by all drones, the total flight time for all drones in several flight scenarios. Each of the figures displays the data mentioned in the legend and a filtered version of it. The filtered version of each of the measured values represents that they exclude the readings related to the collided drones.

Figure 4.

Simulation results for collisions between Drones. (a) Results for 2D sampling-based algorithm and 1.5 m sensing range. (b) Results for 2D sampling-based algorithm and 3 m sensing range. (c) Results for 3D sampling-based algorithm and 1.5 m sensing range. (d) Results for 3D sampling-based algorithm and 3 m sensing range.

Figure 5.

Simulation results for the total number of diversions made by all drones. (a) Results for 2D sampling-based algorithm and 1.5 m sensing range. (b) Results for 2D sampling-based algorithm and 3 m sensing range. (c) Results for 3D sampling-based algorithm and 1.5 m sensing range. (d) Results for 3D sampling-based algorithm and 3 m sensing range.

Figure 6.

Simulation results for total distance passed by all drones. (a) Results for 2D sampling-based algorithm and 1.5 m Sensing Range. (b) Results for 2D sampling-based algorithm and 3 m sensing range. (c) Results for 3D sampling-based algorithm and 1.5 m sensing range. (d) Results for 3D sampling-based algorithm and 3 m sensing range.

Figure 7.

Simulation results for total flight time for all drones. (a) Results for 2D sampling-based algorithm and 1.5 m sensing range. (b) Results for 2D sampling-based algorithm and 3 m sensing range. (c) Results for 3D sampling-based algorithm and 1.5 m sensing range. (d) Results for 3D sampling-based algorithm and 3 m sensing range.

Figure 4 shows the simulation results for the number of collisions between UAVs in multiple scenarios. The figure shows that the number of collisions dropped significantly during 3D scenarios compared to 2D scenarios. This indicates that the 3D sampling-based algorithm has improved the safety of flight scenarios by reducing the number of collisions. During the 2D sampling-based algorithm, UAV’s altitudes were fixed at the same height. This also applies to the sampled points. While in the 3D sampling-based scenario drones were allowed to change their altitudes, and sampled points were not at the same altitude. This usage of the full 3D space took the safety of flight scenarios to a better level. Increasing the sensing range for drones in both the 2D and 3D scenarios did not have a notable impact on the number of collisions. It is believed that this is because a wider sensing range limited the area where UAVs can operate safely.

Figure 5 shows the total number of diversions under different circumstances. The number of diversions indicates the number of times that UAVs had to change their routes due to possible collisions encountered due to another UAV entering its safety range area. In both the 2D and 3D scenarios, the diversions almost doubled when the safety region was 3 m compared to the 1.5 m region. Although the number of diversions in the 3D scenario did not differ a lot compared to the 2D scenario, it is worth mentioning that the number of collisions of the UAVs in operation is about 10 times less than those in the 2D scenario. The results show better performance regarding the total number of collisions in the case of the 3 m sensing range compared to the 1.5 m case in both the 2D and 3D algorithm results. This implies that increasing the sensing range would increase safety by decreasing the number of collisions.

This collision avoidance enhancement comes with the cost of the increased total number of diversions. By increasing the sensing range for drones, more drones had to change their routes during their trips due to possible collisions caused by other drones entering their safety zones. These diversions directly affected the total flight time and increased it.

Figure 6 shows the total distance traveled by all UAVs. The dashed lines are plotted for the UAVs which reached their destination without any collision. The Min Distance represented in red shows the minimum distance that the UAVs can travel to reach their destinations without any diversions. While the dashed orange line represents the same but after excluding the collided UAVs. This line would be the lower bound of the traveled distance. The reason that the Min Distance is larger than the Total Distance in the black solid line is that the distance was calculated for all drones including the ones that collided and did not complete their journey toward their destinations. This dropped the collided UAVs contribution to the Total Distance. When comparing the traveled distance in the case of the 2D scenario with the 3D scenario, it can be observed that the actual traveled distance is closer to the minimum required distance to reach the destination when the UAVs were allowed to fly in the 3D space.

This is due to the reduced number of collisions in the 3D scenario and because utilizing the 3D space enabled picking better sample points in terms of contribution to the shortest path.

Figure 7 illustrates the average flight time of the UAVs in the different simulation scenarios. The average flight time for all UAVs in the 2D space represented by the red solid lines in Figure 7(a) and (b) decreases when more drones are considered. This is because with more drones more collisions happen, resulting in more UAVs not being able to continue their flight toward their destinations. The dashed orange line represents the average for only those UAVs that reached their destinations, that is, less number of UAVs, thus a higher average.

The average flight time in the 3D scenario illustrated in Figure 7(c) and (d) shows the flight time rising with more UAVs in flight. The average is increasing with more UAVs because fewer collisions occurred resulting in more UAVs in flight that reached their destinations.

Conclusion

In this article, a 3D sampling-based algorithm for UAV collision avoidance and trajectory generation was developed and presented. Simulation results showed a great reduction in collisions between UAVs compared to the 2D sampling-based algorithm results. The reduction implies an enhancement in the safety and reliability of fully autonomous UAV transportation systems and integration within the public air traffic. The enhancement also shows promising moves toward creating more intelligent UAV automated systems. The utilization of the 3D space enabled the enhancement in the sampling of points when it comes to the length of the planned path for UAVs during collision avoidance and trajectory generation scenarios. The study also showed that the cost of utilizing the 3D space for sampling-based algorithms in terms of flight distance and flight time was not major. The cost can be considered minor especially when it is compared to the added value to flight scenarios in terms of safety measures and collision avoidance.