Relative range and altitude, and the time remaining to the closest point of approach.

## Abstract

In this chapter, we propose a 3D path planning algorithm for small unmanned aircraft systems (UASs). We develop the path planning logic using a body fixed relative coordinate system which is the unrolled, unpitched body frame. In this relative coordinate system, the ownship is fixed at the center of the coordinate system, and the detected intruder is located at a relative position and moves with a relative velocity with respect to the ownship. This technique eliminates the need to translate the sensor’s measurements from local coordinates to global coordinates, which saves computation cost and removes the error introduced by the transformation. We demonstrate and validate this approach using predesigned encounter scenarios in the Matlab/Simulink environment.

### Keywords

- small unmanned aircraft systems
- path planning
- collision avoidance
- cell decomposition
- Dijkstra’s search algorithm

## 1. Introduction

The rapid growth of the unmanned aircraft systems (UASs) industry motivates the increasing demand to integrate UAS into the U.S. national airspace system (NAS). Most of the efforts have focused on integrating medium or larger UAS into the controlled airspace. However, small UASs weighing less than 55 pounds are particularly attractive, and their use is likely to grow more quickly in civil and commercial operations because of their versatility and relatively low initial cost and operating expense.

Currently, UASs face limitations on their access to the NAS because they do not have the ability to sense-and-avoid collisions with other air traffic [1]. Therefore, the Federal Aviation Administration (FAA) has mandated that UASs were capable of an equivalent level of safety to the see-and-avoid (SAA) required for manned aircraft [2, 3]. This sense-and-avoid (SAA) mandate is similar to a pilot’s ability to visually scan the surrounding airspace for possible intruding aircraft and take action to avoid a potential collision.

Typically, a complete functional sense-and-avoid system is comprised of sensors and associated trackers, collision detection, and collision avoidance algorithms. In this chapter, our main focus is on collision avoidance and path planning. Collision avoidance is an essential part of path planning that involves the computation of a collision-free path from a start point to a goal point while optimizing an objective function or performance metric. A robust collision avoidance logic considers the kinematic constraints of the host vehicle, the dynamics of the intruder’s motion, and the uncertainty in the states estimate of the intruder. The subject of path planning is very broad, and in particular collision, avoidance has been the focus of a significant body of research especially in the field of robotics and autonomous systems. Kuchar and Yang [4] provided a detailed survey of conflict detection and resolution approaches. Albaker and Rahim [5] conducted a thorough survey of collision avoidance methods for UAS. The most common collision avoidance methods are geometric-based guidance methods [6–13], potential field methods [14, 15], sampling-based methods [16, 17], cell decomposition techniques, and graph-search algorithms [18–20].

Geometric approaches to collision avoidance are straightforward and intuitive. They lend themselves to fast analytical solutions based on the kinematics of the aircraft and the geometry of the encounter scenario. The approach utilizes the geometric relationship between the encountering aircraft along with intuitive reasoning [8, 21]. Generally, geometric approach assumes a straight-line projection to determine whether the intruder will penetrate a virtual zone surrounding an ownship. Then, the collision avoidance can be achieved by changing the velocity vector, assuming a constant velocity model. Typically, geometric approaches do not account for uncertainty in intruder flight plans and noisy sensor information.

The potential field method is another widely used approach for collision avoidance in robotics. A typical potential field works by exerting virtual forces on the aircraft, usually an attractive force from the goal and repelling forces from obstacles or nearby air traffic. Generally, the approach is very simple to describe and easy to implement. However, the potential field method has some fundamental issues [22]. One of these issues is that it is a greedy strategy that is subject to local minima. However, heuristic developments to escape the local minima are also proposed in the literature [23]. Another problem is that typical potential field approaches do not account for obstacle dynamics or uncertainly in observation or control. In the context of airborne path planning and collision avoidance, Bortoff presents a method for modeling a UAS path using a series of point masses connected by springs and dampers [24]. This algorithm generates a stealthy path through a set of enemy radar sites of known locations. McLain and Beard present a trajectory planning strategy suitable for coordinated timing for multiple UAS [25]. The paths to the target are modeled using a physical analogy of a chain. Similarly, Argyle et al. present a path planner based on a simulated chain of unit masses placed in a force field [26]. This planner tries to find paths that go through maxima of an underlying bounded differentiable reward function.

Sampling-based methods like probability road maps (PRM) [16] and rapidly exploring random trees (RRTs) [17] have shown considerable success for path planning and obstacle avoidance, especially for ground robots. They often require significant computation time for replanning paths, making them unsuitable for reactive avoidance. However, recent extensions to the basic RRT algorithm, such as chance-constrained RRT^{*} [27] and close-loop RRT [28], show promising results for uncertain environments and nontrivial dynamics [28–30]. Cell decomposition is another widely used path planning approach that partitions the free area of the configuration space into cells, which are then connected to generate a graph [20]. Generally, cell decomposition techniques are considered to be global path planners that require a priori knowledge of the environment. A feasible path is found from the start node to the goal node by searching the connectivity graph using search algorithms like A^{*} or Dijkstra’s algorithm [18].

The proposed approach in this work will consider encounter scenarios such as the one depicted in Figure 1, where the ownship encounters one or more intruders. The primary focus of this work is to develop a collision avoidance framework for unmanned aircraft. The design, however, will be specifically tailored for small UAS. We assume that there exists a sensor(s) and tacking system that provide states estimate of the intruder’s track.

## 2. Local-level path planning

A collision event occurs when two aircraft or more come within the minimum allowed distance between each other. The current manned aviation regulations do not provide an explicit value for the minimum allowed distance. However, it is generally understood that the minimum allowed or safe distance is required to be at least 500 ft. to 0.5 nautical miles (nmi) [21, 31]. For example, the near midair collision (NMAC) is defined as the proximity of less than 500 ft. between two or more aircraft [32]. Similarly and since the potential UAS and intruder aircraft cover a wide range of vehicle sizes, designs, airframes, weights, etc., the choice of a virtual fixed volume boundary around the aircraft is a substitute for the actual dimensions of the intruder.

As shown in Figure 2, the choice for this volume is a * hockey-puck* of radius

In this work, we develop the path planning logic using a body-centered relative coordinate system. In this body-centered coordinate system, the ownship is fixed at the center of the coordinate system, and the intruder is located at a relative position

We call this body-centered coordinate frame the local-level frame because the environment is mapped to the unrolled, unpitched local coordinates, where the ownship is stationary at the center. As depicted in Figure 3, the origin of the local-level reference is the current position of the ownship. In this configuration, the

The detection region is divided into concentric circles that represent maneuvers points at increasing range from the ownship as shown in Figure 4, where the radius of the outmost circle can be thought of as the sensor detection range. Let the region in the space covered by the sensor be called the workspace. Then, this workspace is discretized using a cylindrical grid in which the ownship is commanded to move along the edges of the grid. The result is a directed weighted graph, where the edges represent potential maneuvers, and the associated weights represent the maneuver cost and collision risk. The graph can be described by the tuple

The path is then constructed from a sequence of nonrepeated nodes

where the total number of nodes is

Figure 5 shows an example of a discretized local-level map. In this example,

Assuming that the ownship travels between the nodes with constant velocity and climb rate, the location of the

where

For example, if

The main priority of the ownship where it is under distress is to maneuver to avoid predicted collisions. This is an important note to consider when assigning a cost of each edge in the resulting graph. The cost associated with traveling along an edge is a function of the edge length and the collision risk. The cost associated with the length of the edge

The collision cost for traveling along an edge is determined if at any future time instant, the future position of the ownship along that edge is inside the collision volume of the predicted location of an intruder. An exact collision cost computation would involve the integration of collision risk along each edge over the look-ahead time window

A simpler approach involves calculating the collision risk cost at several locations along each edge, taking into account the projected locations of the intruder over the time horizon

where

The predicted locations of each detected intruder over time horizon

where

In Eqs. (9)–(11), if

where

where

A visual illustration of the collision risk computation is shown in Figure 7. The propagated collision volume of a detected intruder and the candidate locations of the ownship over the first-time interval

To provide an increased level of robustness, an additional threat cost is added to penalize edges close to the propagated locations of the intruder even if they are not within the collision volume. At each discrete time instant, we compute the distances from the candidate locations of the ownship to all the propagated locations of the intruders at that time instant. The cost of collision threat along each edge is then given by the sum of the reciprocal of the associated distances to each intruder

where

and the total collision risk cost associated with the

For example, the edges

Another objective of a path planning algorithm is to minimize the deviation from the original path, that is, the path the ownship was following before it detected a collision. Generally, the path is defined as an ordered sequence of waypoints

where

where

where

and

Then, the cost that penalizes the deviation of an edge in

If small UASs are to be integrated seamlessly alongside manned aircraft, they may require to follow right-of-way rules. Therefore, an additional cost can be also added to penalize edges that violate right-of-way rules. In addition, this cost can be used to favor edges in the horizontal plane over those in the vertical plane. Since the positive direction of the

If we define the maneuvering design matrix to be

The costs

The overall cost for traveling along an edge comes from the weighted sum of all costs given as [35]

where

Dijkstra’s algorithm solves the problem of shortest path in a directed graph in polynomial time given that there are not any negative weights assigned to the edges. The main idea in Dijkstra’s algorithm is to generate the nodes in the order of increasing value of the cost to reach them. It starts by assigning some initial values for the distances from the start node and to every other node in the graph. It operates in steps, where at each step, the algorithm updates the cost values of the edges. At each step, the least cost from one node to another node is determined and saved such that all nodes that can be reached from the start node are labeled with cost from the start node. The algorithm stops either when the node set is empty or when every node is examined exactly once. A naive implementation of Dijkstra’s algorithm runs in a total time complexity of

The local-level path planning algorithm generates an ordered sequence of waypoints

## 3. Simulation results

To demonstrate the performance of the proposed path planning algorithm, we simulate an encounter scenario similar to the planner geometry shown in Figure 8. The aircraft dynamics are simulated using a simplified model that captures the flight characteristics of an autopilot-controlled UAS. The kinematic guidance model that we considered assumes that the autopilot controls airspeed,

where

In the following simulation, our choice of the collision volume is a cylinder of radius

At the beginning of simulation, the predicted relative range and altitude at the closest point of approach (CPA) are shown in Table 1. Imminent collisions are expected to occur with the first and second intruders as their relative range and altitude with respect to the ownship are below the defined horizontal and vertical safe distances. The time remaining to the closest point of approach

Intruder | |||
---|---|---|---|

1 | 24.90 | 25 | 15.77 |

2 | 141.33 | 20 | 16.56 |

3 | 437.14 | 4361.07 | 1982.25 |

Total run time (s) | Max. run time (one cycle) (s) | Average run time (one cycle) (s) |
---|---|---|

0.3703 | 0.1326 | 0.0206 |

Figure 9 shows the planned avoidance path by the ownship. These results show that the avoidance path safely maneuvers the ownship without any collisions with the intruders. In addition, the ownship should plan an avoidance maneuver that does not lead to a collision with intruders that were not on a collision course initially such as the case with the third intruder. Initially, the third intruder and the ownship are flying on near parallel courses. The relative range and altitude at CPA with respect to the third intruder are 437.14 and 4361.07 m, respectively, and the time remaining to the CPA is 1982.25 s. Obviously, both aircrafts are not on a collision course. However, the third intruder is descending and changing its heading toward the ownship. The path planner, however, accounts for predicted locations of the detected intruder over the look-ahead time window, allowing the ownship to maintain a safe distance from the third intruder. This example demonstrates that the proposed path planner can handle unanticipated maneuvering intruders. Once collisions are resolved the path planner returns the ownship to the next waypoint of its initial path.

The relative range between the ownship and the intruders is shown in Figure 10. The results show that no collisions have occurred, and that the ownship successfully planned an avoidance maneuver. The avoidance planner ensures that when the relative horizontal range is less than

Another important aspect to evaluate the performance of the proposed algorithm is its ability to reduce the length of the avoidance path while avoiding the intruders. This is important because it reduces the amount of deviation from the original path and ultimately the flight time, which is of critical importance for the small UAS with limited power resources. Table 3 shows that the length of the avoidance paths is fairly acceptable compared to the initial path length.

Scenario number | Initial path length (m) | Avoidance path length (m) |
---|---|---|

1 | 1500 | 1955 |

## 4. Conclusions

In this chapter, we have presented a path planning approach suitable for small UAS. We have developed a collision avoidance logic using an ownship-centered coordinate system. The technique builds a maneuver graph in the local-level frame and use Dijkstra’s algorithm to find the path with the least cost.

A key feature of the proposed approach is that the future motion of the ownship is constrained to follow nodes on the map that are spaced by a constant time. Since the path is represented using waypoints that are at fixed time instants, it is easy to determine roughly where the ownship will be at any given time. This timing information is used when assigning cost to edges to better plan paths and prevent collisions.

An advantage of this approach is that collision avoidance is inherently a local phenomenon and can be more naturally represented in local coordinates than global coordinates. In addition, the algorithm accounts for multiple intruders and unanticipated maneuvering in various encounter scenarios. The proposed algorithm runs in near real time in Matlab. Considering the small runtime shown in the simulation results, we expect that implementing these algorithms in a compiled language, such as C or C++, will show that real-time execution is feasible using hardware. That makes the proposed approach a tractable solution in particular for small UAS.

An important step forward to move toward a deployable UAS is to test and evaluate the performance of the close-loop of sensor, tracker, collision detection, path planning, and collision avoidance. Practically, the deployment of any UAS requires a lengthy and comprehensive development process followed by a rigorous certification process and further analysis including using higher fidelity models of encounter airspace, representative number of simulations, and hardware-in-the-loop simulation. Unlike existing collision manned aviation collision detection and avoidance systems, an encounter model cannot be constructed solely from observed data, as UASs are not yet integrated in the airspace system and good data do not exist. An interesting research problem would be to design encounter models similar to those developed to support the evaluation and certification of manned aviation traffic alert and collision avoidance system (TCAS).

## Acknowledgments

This research was supported by the Center for Unmanned Aircraft Systems (C-UAS), a National Science Foundation-sponsored industry/university cooperative research center (I/UCRC) under NSF Award No. IIP-1161036 along with significant contributions from C-UAS industry members.

## References

- 1.
George S. FAA Workshop on Sense and Avoid (SAA) for Unmanned Aircraft Systems (UAS). 2009 - 2.
Hottman SB, Hansen KR, Berry M. Literature review on detect, sense, and avoid technology for Unmanned Aircraft Systems. In: Technical Report. 2009 - 3.
Federal Aviation Administration. Subchapter F-Air Traffic and General Operating Rules. 2015 - 4.
Kuchar JK, Yang LC. A review of conflict detection and resolution modeling methods. IEEE Transactions on Intelligent Transportation Systems. Dec. 2000; 1 (4):179-189 - 5.
Albaker BM, Rahim NA. A survey of collision avoidance approaches for unmanned aerial vehicles. International Conference for Technical Postgraduates (TECHPOS). 2009:1-7 - 6.
Hyunjin YK. Reactive collision avoidance of unmanned aerial vehicles using a single vision sensor. AIAA Guidance, Control, and Dynamics. 2013; 36 (4):1234-1240 - 7.
Rajnikant S, Saunders JB, Randal Beard W. Reactive path planning for micro air vehicles using bearing-only measurements. International Robotic Systems. 2012; 65 (1–4):409-416 - 8.
White BA, Antonios HS. UAV obstacle avoidance using differential geometry concepts. In: 18th IFAC World Congress; Milano, Italy; 2011. Vol. 3. pp. 6325-6330 - 9.
Saunders J, Beard RW. Vision-based reactive multiple obstacle avoidance for micro air vehicles. In: IEEE American Control Conference ACC’09; St. Louis, MO, June 10–12; 2009, pp. 5253-5258 - 10.
George J, Ghose D. A reactive inverse PN algorithm for collision avoidance among multiple unmanned aerial vehicles. In: American Control Conference; St. Louis, MO; June 10–12; IEEE. pp. 3890-3895 - 11.
Bilimoria KD. A geometric optimization approach to aircraft conflict resolution. In: Proceedings of the AIAA Guidance, Navigation and Control Conference and Exhibit; 2010 - 12.
Fiorini P, Shiller Z. Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research. 1998; 17 (7):760-772 - 13.
Chakravarthy A, Ghose D. Obstical avoidance in a dynamic environment: A collision cone approach. IEEE Transactions on System, Man and Cybernitics, Part A: Systems and Humans. 1998; 28 (5):562-572 - 14.
Lam TM, Mulder M, Van Paassen M, Mulder JA, Van Der FC. Force-stiffness feedback in uninhabited aerial vehicle teleoperation with time delay. AIAA Guidance, Control, and Dynamics. 2009; 32 (3):821-835 - 15.
Sahawneh LR, Beard RW, Avadhanamz S, He B. Chain-based collision avoidance for UAS sense and avoid systems. In: AIAA Guidance, Navigation, and Control (GNC) Conference; Boston, MA; 2013 - 16.
Kavraki LE, Svestka P, Latombe JC, Overmars MH. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation. 1996; 12 (4):566-580 - 17.
LaValle SM. Rapidly-exploring random trees: A new tool for path planning. Technical Report TR 98–11. Computer Science Department, Iowa State University; October 1998 - 18.
Dijkstra EW. A note on two problems in connection with graphs. Numerische Mathematik. 1959; 1 :269-271 - 19.
Dechter R, Pearl J. Generalized best-first search strategies and the optimality of a ^{*}. Journal of the ACM (JACM). 1985;32 (3):505-536 - 20.
Mirolo C, Pagello E. A cell decomposition approach to motion planning based on collision detection. In: Proceedings of the 1995 International Conference on Advanced Robotics. 1995. pp. 481-488 - 21.
Angelov P. Sense and Avoid in UAS: Research and Applications. Chichester, West Sussex, United Kingdom: John Wiley & Sons, Ltd; 2012 - 22.
Koren Y, Borenstein J. Potential field methods and their inherent limitations for mobile robot navigation. In IEEE International Conference On Robotics And Automation; IEEE. 1991; 2 :1398-1404 - 23.
LaValle SM. Planning Algorithms. Cambridge University Press; 2006 - 24.
Bortoff SA. Path planning for UAVs. In: Proceedings of the American Control Conference. Chicago, Illinois; June 2000. pp. 364-368 - 25.
McLain TW, Beard RW. Trajectory planning for coordinated rendezvous of unmanned air vehicles. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference. AIAA Reston, VA; 2000. Vol. 4369. pp. 1-8 - 26.
Argyle ME, Chamberlain C, Beard RW. Chain-based path planning for multiple UAVs. In: 50th IEEE Conference on Decision and Control and European Control Conference, Orlando, FL, USA. Dec. 2011 - 27.
Luders BD, Karaman S, How JP. Robust sampling-based motion planning with asymptotic optimality guarantees. In: AIAA Guidance, Navigation, and Control Conference (GNC), Boston, MA. 2013 - 28.
Luders BD, Karaman S, Frazzoli E, How JP. Bounds on tracking error using closed-loop rapidly-exploring random trees. In: American Control Conference (ACC). IEEE; 2010. pp. 5406-5412 - 29.
Luders B, Karaman S, How JP. Robust sampling-based motion planning with asymptotic optimality guarantees. In Guidance, Navigation, and Control (GNC) Conference, Boston, MA. 2013. AIAA - 30.
Kothari M, Postlethwaite I. A probabilistically robust path planning algorithm for UAVs using rapidly-exploring random trees. International Robotic Systems. 2013; 71 :231-253 - 31.
Standard Specification for Design and Performance of an Airborne Sense-and-Avoid System. Tech. Rep. TR F2411-07. West Conshohocken, PA: ASTM International; 2007 - 32.
US Department of Transportation and Federal Aviation Adminstration. Aeronautical Information Manual Official Guide to Basic Flight Information and ATC Procedures - 33.
Lee SM, Park C, Johnson MA, Mueller ER. Investigating effects of well clear definitions on UAS sense-and-avoid operations. In: Aviation Technology, Integration, and Operations Conference, Los Angeles, CA. AIAA. 2013 - 34.
Consiglio M, Chamberlain J, Munoz C, and Hoffler K. Concept of integration for UAS operations in the NAS. In: 28th International Congress of the Aeronautical Sciences (ICAS); Brisbane, Australia; 2012 - 35.
Sahawneh LR, Airborne Collision Detection and Avoidance for Small UAS Sense and Avoid Systems [PhD Thesis] Brigham Young University; 2016 - 36.
Beard RW, McLain TW. Small Unmanned Aircraft: Theory and Practice. New Jersey, USA: Princeton University Press; 2012 - 37.
Sahawneh LR, Argyle ME, Beard RW. 3D path planning for small UAS operating in low-altitude airspace. In International Conference on Unmanned Aircraft Systems (ICUAS). IEEE, 2016. pp. 413-419