A Conceptual Framework and a Review of Conflict Sensing, Detection, Awareness and Escape Maneuvering Methods for UAVs

1. Introduction

Because of the key characteristics of Unmanned Aerial Vehicles (UAVs), removal of pilot, UAVs will be highly suited for repetitive, dirty, and dangerous operations. A wide range of civil and military applications are being explored in the community (Clapper et al., 2007). As a result, UAVs are given serious considerations in worldwide, making them the next step in evolution of aviation. Whatever missions are chosen for UAVs, their number and use will significantly increase in future.

Currently, UAVs do not have convenient access to civil and military operation theatres due to their inability to provide an equivalent level-of-safety comparable to see-and-avoid requirements for manned aircraft. The current procedure requires a certificate of authorization be applied for every mission. Obtaining such an authorization may take more than a month. This lengthy process is not in line with increasing number of UAVs development. Therefore, an autonomous collision sensing, detection, awareness and avoidance system will be a key enabler for the integration of unmanned with manned aircraft in a shared airspace. The main objective of the Collision Avoidance System (CAS) is to allow UAVs to operate safely within non segregated civil and military airspace on a routinely basis. For this purpose, the UAV must be able to identify and be identified by the surrounding traffic.

The diversity of UAVs and their missions involve a wide-range of system operating concept. Current unmanned aircraft range in size from small hand launch vehicles to large fixed-wing UAV with a wing span similar to Boeing 737. In addition, some UAV autonomously, semiautonomous or completely guided by ground pilot. Furthermore, unmanned vehicles cruise speed, climb/dive rate, turn rate and operating altitudes are similarly varied. Therefore, many CAS methods were proposed to account for that variation and to ensure that the unmanned aircraft efficiently avoids other cooperative traffic while also avoids fixed and moving obstructions such as terrain, obstacles and no flying zones.

Numerous technologies are being explored in the community addressing CAS systems. Much of the research in collision avoidance methods for UAVs had been imparted from the air traffic management, maritime and mobile ground robot research communities. However, aircraft complicates the avoidance problem by added dynamic constraints that must be fulfilled for adequate separation. Although large efforts have been done to address collision detection and avoidance problem to manned and unmanned aircraft, however there had been little survey and comparative discussion of the techniques and methods deployed to resolve conflicts.

Some efforts towards describing and understanding the differences among proposed approaches have been introduced in the literature. The majority of conflict detection and resolution methods review tried to highlight the differences among different methods. Warren (Warren, October 1997) conducted an evaluation among three conflict detection methods. Zeghal (Zeghal, August 1998) provides a review of the differences among force field collision avoidance methods. In the last decade, Krozel et al. (Krozel et al., 1997) and Kuchar and Yang (Kuchar & Yang, 2000) presented a comprehensive survey of conflict detection and resolution methods for manned aircraft. Current technology advances allow for innovative CAS systems to be more effective in reducing the number of collisions and utilizing airspace more efficiently. Those new systems need to be addressed and compared.

Recently, Utt et al. (Utt et al., 2005) addressed some of the lessons learned in development of a sense and avoid system for UAVs. Karhoff et al. (Karhoff et al., 2006) identified see and avoid requirements necessarily to avoid collisions and defined criteria specific to the warrior UAVs consistent with Federal Aviation Administration (FAA) guidelines. That is to obtain routine access to airspace. Lacher et al. (Lacher et al., 2007) investigated the challenges associated with UAV collision avoidance from a civil aviation perspective and presented results from MITRE’s research addressing collision avoidance technologies and systems performance analysis. Albaker and Rahim (Albaker & Rahim, 2010b) proposed a generic collision avoidance system and presented a survey of some methods in the air traffic domain.

A little explanation is given in the literature addressing the problem of how complete collision sensing and avoidance system is functioning to solve conflicts. Towards addressing these problems, this chapter has three main goals: (1) To explore the fundamental concept of operation and presents up-to-date literatures review of the collision sensing, detection, awareness and avoidance methods those deployed for aircraft, especially for unmanned aircraft. (2) To introduce a conceptual framework to assist in the design of context-aware application in collision avoidance domain. This is done by providing a better understanding of what context is and how it can be used in the conflict resolution domain. (3) To categorize methods into what type it is designed as well as point out its advantages and disadvantages. Furthermore, this work identifies common issues that should be considered in avoidance systems design process.

The following sections are organized as follows: Firstly, the main functions carried by the collision avoidance system with an introduction on how to get knowledge of incoming threats are presented. Secondly, each function in CAS system is discussed in details, pointing out the significant researches done in each function. A context-awareness engine is explored as one of the functions in CAS system design. Next, the major design factors of collision avoidance systems are addressed. Finally, the developed trajectory escape maneuvering methods are classified.

2. Generic process functional model of collision avoidance system

A general collision avoidance system must detect and predict traffic conflicts. A conflict is defined as the event in which the Euclidean distance between two aircraft is less than the minimum desired separation distance. Collision avoidance system must be able to detect conflicting traffic in sufficient time to perform an avoidance maneuver and then propose a course of action and maneuver so as not to create collision. Depending on the level of autonomy inherent in the UAV, these functions could fall into wide range from simple conflict detection and warning to full autonomous conflict detection and avoidance.

The basic idea of CAS is composed of two main phases. These phases are collision sensing and collision avoidance. Sensing operation involves monitoring the environment for any encounter including cooperative aircraft as well as stationary and/or moving obstacles in a shared airspace. As an example, a UAV performing an operation within a shared airspace segment that includes both manned and unmanned aircraft together with no flying zone, as depicted in Figure 1. When a UAV gets too close to any moving or stationary obstacles, less than a predefined protection zone, a potential collision will occur.

Figure 1.

A scenario illustrating shared Airspace as viewed from UAV

A fully autonomous CAS system is composed of six key functions. These functions include monitoring the environment, broad conflict detection, awareness, escape trajectory selection, maneuver realization and interception. Figure 2 illustrates the generic functional architecture of the CAS system for autonomous UAV.

Figure 2.

Functional units implemented in the autonomous Sense & Avoid System

The sensing function refers to the ability of the system to monitor the environment and collect appropriate current state information for encounters, e.g. aircraft position, velocity and heading, about the environment surrounding UAV. This is done through the utilization of active and/or passive sensors and communication equipments.

The detection function is the ability of the system to acquire the sensed data, process it to extract useful information and discover collision risks to the UAV. Whereas, awareness function is used to dynamically projects the states into the future to check whether a potential conflict will occur in the near future or not. It also extracts the collision parameters in case of a potential conflict detected. In addition, it handles the process of when action should be taken.

The main role of avoidance function is to evade from a possible collision. This function will be invoked after detection of a near future collision. It determines how and what action should be performed. The maneuvering of the UAV will be performed based on the scheduled flight plan along with the level of responsibility assigned by the ground controller, which is further depends on the level of UAV autonomy (Asmat et al., 2006). Conflict interception handles the process of returning back to original UAV’s course path after the conflicting object is resolved by the avoidance algorithm.

A fully automated collision avoidance system must address these six key functions, as stated earlier. For each function there were one or more design factor(s) that should be taken into account when consider selecting a suitable method for conflict resolution. The key functions together with its design factors will be discussed in the following sections. These factors represent principal categories by which approaches differ. Figure 3 shows the main and subdivisions of these factors

Figure 3.

Main CAS design factors.

Many methods have been proposed by various researchers to address collision avoidance problem. These methods have been developed not only for aerospace, but also for ground vehicles, robotics, and maritime applications. That is because the fundamental collision avoidance issues are similar across different transportation systems.

Some of the existing operational systems in use or which have been evaluated in the field are: Airborne Information for Lateral Spacing (AILS)(Waller & Scanlon, 1996), County Technical Assistance Service (CTAS)(Isaacson & Erzberger, 1997), Ground Proximity Warning System (GPWS)(RTCA, 1976), and its enhanced version (EGPWS) (Bateman, 1999), Precision Runway Monitor (PRM)(Federal_Aviation_Administration, 1991), Traffic alert and Collision avoidance system (TCAS) (RTCA, 1983; Ford, 1986; Ford & Powell, 1990; Committee147, 1997), Traffic and Collision Alert Device (TCAD)(Ryan & Brodegard, 1997), User Request Evaluation Tool (URET)(Brudnicki et al., 1997), and a prototype conflict detection system for Cargo Airline Association(Kelly, 1999). The other approaches range from abstract concepts to prototype conflict detection and resolution systems being evaluated and used in laboratories. Some approaches were developed for robotics, automobile or naval applications (Coenen et al., 1989; Iijima et al., 1991; Taylor, 1990), but are still not applicable to aviation (Chakravarthy & Ghose, 1998; Kuchar & Yang, 2000).

3. Monitoring the environment

The monitoring function refers to the ability of the system to provide traffic information about surrounding environment around unmanned aircraft. Determining the type of sensor that is appropriate for the UAV and environment is a challenging multidimensional problem. The fundamental information that a sensor or group of sensors need to acquire is the range, azimuth and elevation of all targets of interest (Lacher et al., 2007).There are a wide variety of sensors those were deployed for aircraft, which is mainly divided into two main categories: cooperative and non-cooperative traffic sensors.

3.1. Cooperative monitoring

Collision avoidance systems employed among UAVs usually assumes cooperative behavior in which inter-agent communication of position, heading, waypoints, and proposed trajectory is allowed. This is a common trait in collision avoidance methods for cooperative UAV systems, cooperative mobile ground robots and air traffic management systems.

Cooperative traffic Sensors includes all communication equipments those enable exchange information between the cooperative agents like position, heading, speed and waypoints. These devices like transponders mode S or emerging technologies like Airborne Separation Assistance Systems (ASAS) and Automatic Dependant Surveillance Broadcast (ADS-B) (Gazit, 1996; RTCA, 1997; Koencke et al., 1997; Holdsworth, 2003). As an example, ADS-B transfers the information: location, speed, UAV identification from UAV to other agents and Air Traffic Controllers. The data update rate received from other aircraft is important, so that the aircraft are working on timely data.

3.2. Non-cooperative monitoring

UAVs not fitted with such communication equipment may use non-cooperative traffic sensors to get knowledge about surrounding environment. In this case, the solution needs new sensors to replace communication links. Another case when a UAV use this kind of sensors to detect non-cooperative conflicts which include moving and/or stationary obstacles. Sensing the environment can be done in a variety of ways from the available technologies for non cooperative traffic including laser range finders, optical flow sensors Electro-Optical/Infra-Red (EO/IR), radar systems, acoustic or stereo camera pairs or moving single camera. Laser range finders are commonly used as an active sensor to detect obstacles. The use of a single fixed laser range finder is of limited capabilities to detect conflicts in the environment. Moreover, this type of sensors is considered costly.

Alternatively, the utilization of radar system for active sensor detection is used to detect any moving/stationary obstacles whether they are cooperative or not. However, it is not used in small scale UAV due to its weight and size. Some of the research conducted in this field can be found in (Kumar & Ghose, 2001; Hyeon-Cheol & In-Kyu, 2004; Ariyur et al., 2005; Tatkeu et al., 2006; Kwag & Chung, 2007; Kemkemian et al., 2009). An efforts toward extracting radar parameters for continuous and interrupt driven data acquisition techniques were covered by Albaker and Rahim (Albaker & Rahim, 2009a; Albaker & Rahim, 2011b). Acoustic sensors can also be used for perceiving the target by passively listening.

As the advances of new powerful processing units, cameras can be used as a passive sensor to detect the obstacles around UAV. Many efforts are already being conducted to use camera in CAS systems such as the research found in (Matthies et al., 1998; Oh, 2004; Boon Kiat et al., 2004; Muratet et al., 2005; Mehra et al., 2005; De Wagter & Mulder, 2005; Zhihai et al., 2006; Ortiz & Neogi, 2006; Prazenica et al., 2006; Frew et al., 2006; Subong et al., 2008; Moore et al., 2009; Zufferey et al., 2010). Video cameras are light and inexpensive and thereby fit to the UAV requirements especially the small one. Video camera can be configured for obstacle detection as a stereo pair, or a moving single camera. However, video cameras provide information in a way that requires significant data processing for autonomous unmanned aircraft CAS system implementation.

Accurate monitoring and tracking of conflicting aircraft is an essential step in CAS systems. Erroneously identified conflicts would reduce the overall effectiveness of a CAS system. Simply, the accuracy of the information feed to the CAS system specifies how they are good. The accuracy of data available from sensors is limited and depends on the type of sensor used. The accuracy required also depends on aircraft packing density. The safety distance between aircraft can be increased to account for sensor inaccuracy.

4. Conflict detection and context awareness implementation

The detection function is the ability of the system to acquire the sensed data, process it to extract useful information and conflicts reporting to the UAV. The output of this function is to provide primary course collision detection in case of any intruder enters its detection zone around the UAV. If an encounter is detected, the detection function will acquire its state information and pass it to awareness function.

The needs behind context awareness engine comes from its importance for CAS algorithm where the UAV’s surrounding environment context is changing rapidly. The goal behind introducing this function is to make interacting handle and manage conflict easier. In order to facilitate the building of context aware function, it needs to understand fully what constitutes a context aware application and what context is. The increase in mobility creates situations where CAS’s context such as location of aircraft and cooperative/non-cooperative objects around it is more dynamic.

The detected conflicts, in the detection function, will be refined by reading out the reported threat position upon threat presence and project the states into the near future. In order to implement that requirement, the computing aircraft either tries to subscribe the conflicting aircraft in case of cooperative conflict detection or acquiring threats data registered by the sensing and detection functions in case for any moving and/or stationary obstacle. Depending on the type of conflict, different types of avoidance will be activated. The escape trajectory generation and maneuver realization functions will be invoked after detection of future potential collision is detected. After resolving the conflict, the aircraft can return to its original course. Figure 4 illustrates the subunits that the collision detection and awareness should address.

Figure 4.

A block diagram illustrating the tasks executed in the Conflict detection and awareness functions.

4.1. Context definition and context-awareness

Realizing the need for context is only the first step forward using it effectively in order to efficiently use context. A better understanding of what context is should be handled first. According to Webster’s dictionary, context is the whole situation, backround or environment relevant to some happening or personality. This definition is too general to be useful in context-aware computing. Schilit et al. (Schilit et al., 1994 ; Schilit & Theimer, 1994 ) who first defined the term context-aware; refered to context as location, identities of nearby people and objects and changes to those objects. This definition is difficult to apply. When considering a potential new type of context information, it is not clear how the definition can help in deciding whether to classify the information as context or not (Dey et al., 2001).

Dey and Abowd (Dey & Abowd, 2000) defined context awareness as ‘any information that can be used to characterize the situation of an entity, where an entity can be a person, place, or physical or computational object’. They went on to define context-awareness or context-aware computing as ‘the use of context to provide task-relevant information and/or services to a user, wherever they may be’. Morse et al. (Morse et al., 2000) and Dey et al. (Dey et al., 2001) defined the context as any information that can be used to categorize the situation of entities whether a person, place or object that are considered relevant to the interaction between a user and an application themselves. Context is typically the location, identity and state of people, groups and computational and physical objects.

Based on these prior attempts to define context and following on from that, the context in conflict avoidance domain is defined as any information that can be used to characterize the situation around the UAV. Context-aware looks at who’s, when’s, where’s and what’s of entities and use this information to determine why the situation is occurring. The activity answers a fundamental question of what is occurring in the situation. Basically, the general model of context-awareness is divided into three main units, which are: generation, in which the contextual information is obtained from sensors and cooperative communication; processing, which process raw data acquired by the sensors and communication systems to obtain meaningful information and finally the usage, which use of context to activate the reaction as output and handles the process of when action should be taken.

The characteristics of context given by Dey et al. (Dey et al., 2001) is closest in spirit to the operational context characteristics that we seek. Four essential characteristics of context information are identified to get a more extensive assessment of a situation. These characteristics are: identity, location, status and time stamp. Identity refers to the ability to assign a unique identifier to a UAV. The identifier has to be unique in the namespace that is used by the CAS system. Location is more than just position information in three dimensional space. It is expanded to include the three degree orientation of an object, as well as all information that can be used to deduce spatial relationships between UAVs. Status identifies current negotiation situation of the UAV with other cooperative conflicting objects in the shared airspace. It also shows whether the UAV that is involved in resolving cooperative conflict is busy or ready for negotiation. Finally, time stamp helps to characterize a situation, used in conjunction with other pieces of context. It enables to leverage off the richness and value of historical information for the purpose of projecting states of the encounter into the future to check for collision risk.

4.2. Awareness engine in collision avoidance systems

The implementation of the context-awareness function in the collision avoidance system is utilized for monitoring surrounding situations and overtaking aircraft management in critical conditions and return control when flight conditions become normal. The context awareness engine involves the sub-functions: estimation of the current traffic situation, refining the reported encounters, computing the collision parameters in case of a potential collision is detected to occur in the near-future, and invoking avoidance function at a suitable time. The main objective of this function is to detect the protection zones violation raised between conflicting aircraft and measure the conflicting parameters in case of potential collision event is detected. A conflict between aircraft and encounter occurs when the protective zone of an aircraft overlaps with protective zone of an encounter.

Information from aircraft in the vicinity is used to create track files and projections of intention on the three dimensional map. This map provides a situational awareness of all neighboring aircraft, surrounding obstacles and no flying zones. The profiles in three dimensional space establish future intersection points that will results in a collision.

Once a potential collision is predicted, the Time To collision and Maneuver (TTC and TTM) for the avoidance phase is calculated. When TTM reaches zero, an automatic escape maneuver is realized by the awareness function and continues until the aircraft is no longer in danger.

The awareness function is based on the estimation of future UAV position and the application of predefined metrics such as time, distance, cost …etc., on the conflict situation to decide whether or not a potential conflict is exist. Although many studies were conducted focusing on the required detection matrices, collision risk assessment technique, maneuver execution time and so on, however the work in this chapter introduces the new concept, awareness engine, that handles these factors to simplify the problem specially in case of dense environment. The design factors associated with the collision detection and awareness are explored in the following subsections.

4.2.1. Conflicting aircraft’s state extractor

The first important factor for encounter’s state acquisition is the encounter sensing dimension in which the UAV will get knowledge about encounter‘s state vector. This dimension demonstrates whether the monitoring of the environment used in a given approach is in two dimensional horizontal plane (2D-H), two dimensional Vertical Plane (2D-V) or three dimensional state information (3D). The majority of the developed CAS approaches cover either 3D or 2D-H. However GPWS focuses on the 2D-V.

The coverage of a certain dimension doesn’t necessary mean complete description of the situation in that dimension is available. For example, TCAS uses range measurements and range rate estimates to determine if a conflict exists in the horizontal plane. A better prediction of the threat condition could be obtained if additional information were available such as bearing.

4.2.2. Conflicting aircraft’s state projection

Another collision detection and awareness design factor is the prediction of the encounter’s future state vector. That is because it specifies the way of dynamic projecting states of UAV and encounter into the near future and check for collision risk. Four fundamental prediction methods have been identified. These methods are, as illustrated in figure 5: straight projection, worst case, probabilistic and flight plan sharing.

Figure 5.

Projection types of encounter’s state vector

In the straight projection method, the states are projected into the future along a single straight trajectory, without direct consideration for uncertainties, as shown in Figure 5.a. This will simplify the problem but it is can be only used in situations in which aircraft trajectories is very predictable or used for short period of time. That is because the CAS approach that uses straight projection doesn’t account for the possibility that an encounter can do any maneuvering in predicted time. Albaker and Rahim(Albaker & Rahim, 2009d) developed a new functional architecture for unmanned aircraft collision avoidance system with an avoidance algorithm utilized for deciding the collision criteria upon straight state projection in the near future.

The other extreme is the worst case projection illustrated in Figure 5.b, which assumes an aircraft will perform any range of maneuvers bounded by its physical limitation. If anyone of these trajectories could cause a conflict, then a conflict is predicted. It should be limited to a short period projection time to limit the computation requirement for risk assessment. Tomlim et al. (Tomlim et al., 2000) approached the collision avoidance problem from non-cooperative game theoretical angle. These approaches often solve for solutions that work in worst case scenarios. Although, these methods may provide an acceptable solution, they are far from optimal solution.

In the probabilistic method, the uncertainties are modeled to describe risk variation in the future trajectory of aircraft, as shown in Figure 5.c. This method is based on developing a complete set of possible future trajectories, each weighted by a probability of occurring, making a probability density function. The advantages of this method is that decisions can be made on the fundamental likelihood of conflict; safety and false alarm rate can be assessed and considered directly. However, the disadvantage is that the logic behind this method may be difficult to model the probabilities of future trajectories. Moreover, it requires heavy processing to cope calculations in case of large number of aircraft in a given shared airspace.

Most other methods of escape trajectory maneuvering rely on trajectory estimation filters based on previous intruder path history, position versus time. However, actual intended intruder path data, such as position; heading; and future waypoints, offers a much more reliable basis for path planning than trying to estimate where the intruder might go given its previous history.

The advancement of the technology allows for the forth method of encounters‘ states projection using path plan sharing, as depicted in Figure 5.d. It is a method of providing path trajectory (flight plan segment) and aircraft specific information (like position, heading and velocity) to all other aircraft in the vicinity. As an example, Albaker and Rahim (Albaker & Rahim, 2009c) and Sislak et al. (Sislak et al., 2008) use flight path sharing method for the assessment of collision risk then provide a solution for conflicting senario. Data from each aircraft will be sent to ground stations for monitoring and all neighboring aircraft as a broadcast. This will leads give all aircraft a 3D picture of neighboring aircraft movements, precise projection of encounters’ states and exact collision parameters extraction. As an example ADS-B that is proposed to be fully deployed in aircraft by the year 2020 to support free flight capability (Asep et al., 1996). Other examples support free flight concept can be found in the references (K. Bilimoria, 1996; Holdsworth, 2003; J. Hill, July 2005; Christodoulou & Kodaxakis, 2006). However, the focus needs to be on removing the complexity of data exchanges and the quantity of data required to ensure safe maneuvers. Clearly, the more data needed to be exchanged in collision situation, the more complex and prone to error the system becomes.

4.2.3. Assessment of collision risk and collision parameters extraction

The design of any collision avoidance system should include some form of collision risk assessment. This is a complex issue that receives considerable attention in the literature. An example is given by Carlson and Lee (Carlson & Lee, 1997). Merz (Merz, 1991) describes a method of avoiding collision given the increased likelihood of collision as aircraft numbers and packing densities increase. The limit on packing density where these algorithms no longer work is examined by Bowers and smith et al. (Bowers, 1996; Smith et al., Mar 1998).

Approaches may use an extremely simple criterion like range information to determine when a conflict exists or may use a more complex threshold or set of logic. Some of them uses concept of a simple threat detection zone around each aircraft and determines a maneuver that ensures adequate separation even if one aircraft does not maneuver. This provides safe separation even if the link to one aircraft fails.

A determination of potential collision and request for trajectory maneuvering are done by utilizing relative position information, its rate of change and/or trajectory information between conflicting aircraft. When a potential conflict is reported, the context awareness engine is then estimates the collision parameters. These parameters include the estimation of Time-To-Collision (TTC), Collision Interval (CI), time to activate the escape trajectory and collision angle (See Figure 6). Albaker and Rahim (Albaker & Rahim, 2009c) developed a method to extract collision parameters based on flight trajectory sharing.

Figure 6.

Separation distance between two aircraft demonstrating some of the collision parameters in a future course collision scenario.

5. Escape maneuver algorithms

Various approaches have been proposed in the collision avoidance literature for choosing escape trajectories that generate solution to a conflict. Six main categories of the escape trajectory approaches are introduced in this paper, which are: predefined, negotiation protocol based, optimized, force-filed, game theory, automotive and hybrid systems. These approaches will be discussed in details in the next subsections.

To provide insight into different CAS algorithms, a literature review of previous research models and current developmental and operational systems is performed. Based on the collision avoidance system design factors as illustrated in Figure 3, the algorithms were catalogued according to their fundamental approaches to each phase of CAS function. The major collision avoidance algorithms for UAVs are categorized into four main methods. These methods are explained together with their advantages and disadvantages in the following subsystems.

5.1. Predefined trajectory escape

This type of collision avoidance is based on a fixed set of predefined rules without performing any additional computation to determine an escape trajectory. The advantage is on minimizing the response time to avoid the conflict. On the other hand the disadvantages will be on less effectiveness and less optimal than the maneuvers which are computed in online. That is because there is no way to alter the commanded maneuver, which is very essential to account for unexpected events. As an example, Ground Proximity Warning System (GPWS) issues a standard climb warning when a conflict with terrain exists (Bateman, 1999).

5.2. Optimized trajectory based algorithms

In this type, the collision avoidance problem is often formulated as an optimization problem. Algorithms using this kind of trajectory escape are generally combining a kinematic model with a set of constraints. An optimal resolution strategy is then computed based on most desired optimization constraint. For example, the TCAS system does not seek to define an escape trajectory, instead requesting a climb or dive maneuver(RTCA, 1983; Committee147, 1997). It searches through a set of potential climb or descent maneuvers and selects the least-aggressive maneuver that provides adequate protection. The idea implies that somehow the system knows that the path planned towards the goal without taking account of intruders would be unsafe. An aircraft will head for its goal until a collision threat is detected and then find a trajectory that will avoid the collision. Path planning should be more elegant, that is finding a safe trajectory that still reaches the goal.

Tomilin et al. (Tomlim et al., 2000), Zhang and Sadtry (Zhang & Sastry, 2001) and Bayen et al. (Bayen et al., 2003) presented an optimization approach using game theorical technique for controller design that covers moving obstacles. In this technique, a pursuer’s trajectories are examined based on all possible plans and the evader seek for collision free paths those are not intersecting with pursuer’s trajectories. Although it is interesting, it does not appear practical at present. Archibald et al. (Archibald et al., 2008) described a multiagent solution to aircraft conflict resolution based on satisficing game theory. A key feature of the theory is that satisficing decision makers form their preferences by taking into consideration the preferences of others. The results in behavior is attractive both in terms of safety and performance. Mixed Integer Nonlinear Programming is also used as an optimization problem to solve traffic conflicts. However, this algorithm is hard to be extended to consider many maneuvering commands.

Another well-known safe navigation method originating from mobile ground robot research community is the dynamic window approach, presented by Fox et al. (Fox et al., 1997). This approach takes into account the dynamic model and kinematic constraints of aircraft to determine a safe control action. Nguyen (Nguyen, 2007), in his thesis, proposed collision avoidance system using horizon escape windows for UAVs. His proposal was based on proposing asymmetrical collision risk assessment metrics. Then an optimization is formulated to solve conflict based on possible trajectories for each UAV that can follow. Albaker and Rahim (Albaker & Rahim, 2011a) introduced a new collision avoidance algorithm based on geometrical intersection method for the estimation of collision risk. When a potential conflict along the trajectory exists, the collision avoidance is activated to take the action of filtering the possible trajectories to avoid the conflict and the best option to consider based on optimization problem. Van Dam et al. (Van Dam et. al, 2008) defined the workspace key functions required by the airborne separation assistance tool. A geometrical approach, supporting free flight concept, is proposed for conflict avoidance without the need to communicate among the conflicting aircraft. The authors based on implicit coordination among aircraft in a shared airspace. Speed and heading travel functions is utilized as resolution maneuvers to clear incoming threats.

Other optimized conflict resolution algorithms utilize techniques such as genetic algorithms, expert systems, or fuzzy control to the problem (Zengin, 2007; Tseng, 2008; Holdsworth, 2003). These techniques may be complex and therefore would require a large number of rules to completely cover all possible encounter scenarios. This leads to demanding high computational processing power. Resulting in difficult to certify that the system will always operate as intended.

Pre-mission path planning is often formulated as an optimization problem and many different optimization problems can be applied. Path planning for UAVs is difficult problem because it requires the ability to create paths in environments containing obstacles or no-flying zones. Additionally, UAVs are constrained by minimum turning radius, minimum speed, and maximum climb rate constraints. Generally, CAS algorithms are used to sparsely search the space for solutions and then the best solution is chosen.

5.3. Negotiation protocol based maneuvers

This type offers a very elegant solution to conflict free navigation for a team of agents, each agent represent an aircraft. Inter-agent communication includes sharing position, velocities, waypoints and heading. Agents make decisions based on a common set of rules decided priori. This method is decentralized, highly scalable and guarantees safety. However, the trade off is that unnecessary long trajectories can be generated long mission completion times. (Albaker & Rahim, 2010a; Albaker & Rahim, 2009b; Wollkin et al., 2004; Wangermann & Stengel, 1999; Sislak et al., 2011; Sislak et al., 2010; Pechoucek & Sislak, Jan 2009) are examples use this kind of collision avoidance approach.

5.4. Force-field based collision avoidance

Many methods have been proposed for safe navigation in static obstacle strewn environment. Most popular obstacle avoidance methods are artificial potential field methods. Researchers have considered the force field to map the volume between aircraft in terms of a potential field. The methods treat each aircraft as a charged particle and the repulsive forces between aircraft are used to generate maneuvering trajectories. This type is considered as a path planning technique that estimates the trajectories by creating trajectory estimation filters based on the previous paths. Trajectories with low flex densities can be then selected as the preferred courses. The method shows some success through the sense that conflict avoidance is continuously available using simple electrostatic equations. However, the algorithms presented have limited relevance due to sharp discontinuities in the commanded maneuvers that may occurs. Furthermore, it requires a high level of flight guidance, leads to increase in complexity beyond issuing simple maneuvering commands.

Artificial potential field methods were first presented by Khatib (Khatib, 1985). Other methods utilize same escape method can be found in references (Miura et al., 1995; Jen-Hui, 1998; McQuade & McInnes, 1997; Veelaert & Bogaerts, 1999). Obstacle and other agents are modeled as repulsive forces and waypoints as attractive forces; the gradient of the summation of these forces yields the control command. These methods provide very simple and elegant solutions to general collision avoidance scenarios. However, the existence of local minima could trap an aircraft for infinite time (Krogh & SME., 1984). Potential field like methods that didn’t have local minima were later demonstrated (Rimon & Koditschek, 1992; Kim & Khosla, 1992). The design for multi-agent systems presented in (Chang et al., 2003), in which the repulsion force from neighboring agents is replaced by a gyroscopic force from the nearest neighbor. This force will enable an agent to spin free in symmetrical conflict scenarios.

5.5. Other escape maneuvering algorithms

In addition to the above most famous approaches, there are several other CAS approaches to be considered. Like automotive collision avoidance, that offers some interesting analogies for aircraft but does not appear to have been considered for this purpose in the literature. It attempts to predict the vehicle trajectory using historical information or forward looking sensors (Min Young et al., 1996).

Another method uses hybrid CAS algorithm as presented by Tomlin et al. (Tomlin et al., 1998; Tomlim et al., 2000) and Pappas et al. (Pappas et al., 1996). This type of realization is concerned with the modeling and control of systems combining continuous and discrete states. In this method, vehicle and its maneuver is modeled as a hybrid system and its reachable sets of states is filtered based on safety specifications to get a safe subset of the reach set. Then Hamilton-Jacobi equations are employed to calculate control commands that can guarantee UAV will remain in its safe set. Although this method is decentralized and guarantees safety, it scales poorly for large UAVs.

6. Trajectory maneuvering realization

A maneuver is the combination of actions by all conflicting aircraft in the vicinity. Initiating a resolution maneuver requires at least one aircraft to change its flight trajectory. Maneuver realization can implement all degree of freedom of aircraft control. Three maneuvers dimensions are identified for maneuver realization. These maneuvers include: horizontal plane, turn left/right; vertical maneuver, climb/dive; and/or speedup slowdown commands. The maneuvers depends on the CAS approach used, limited by the physical constraints of the aircraft as given by its flight dynamics. It may be issued separately (e.g. change of only one dimension) or combined maneuvers may be performed (e.g. speed and vertical and horizontal planes). Furthermore, the combined maneuvers can be performed simultaneously or in sequence.

Issues such as coordinated and uncoordinated maneuvers also need to be addressed. Coordinated maneuver refers to the choice of the direction when there is a choice of two alternative versions of maneuver. As an example in TCAS in which the preferred maneuver might be for aircraft A to climb while aircraft B descends. While the uncoordinated maneuver refers to the worst case scenario, in which the other aircraft does not respond and only the computing aircraft should do all the maneuvering commands.

7. Other collision avoidance factors

One of the other important CAS design factors is that, complex computation performed by an approach versus time requirement to resolve the conflict. The designed approaches should take into consideration finding the solution in real time. This means compromise between two factors must be done. That is the complexity of the calculation needs to be bounded, to provide an approach that is effective and robust but reasonably simple.

Collision avoidance systems are also differ by their system architecture those designed for. Basically, there are four type of CAS architecture, which are: Centralized, layered, predictive and decentralized. Centralized approaches, such as current air traffic management, are considered easy, one system controls all. Therefore, this type will improve the overall global performance. However, it is considered computationally expensive and the whole system fails in case if centralized controller failed. Furthermore, this type fails to prevent collisions among conflicting aircraft when their number increases. On the other hand, modular layered CAS architecture type is scalable but it adds design interfaces that may delay the response to solve the conflicts. Such a system can be found in (Casalino et al., 2009). Predictive control type is interesting as it handle time delay and packet loss. However, it design for uncertainties which much complicates the problem. Therefore it may fail to provide solution in a dense environments. Some of the research addressing this type can be found in (Lapp & Singh, 2004; Boivin et al., 2008). Most of the research done in this field based on decentralized CAS architecture (Borrelli et al., 2004; Lalish & Morgansen, 2008; Keviczky et al., 2008; Roozbehani et al., 2009; Sislak et al., 2011). This is a critical requirement for autonomous UAVs. That is for implementing a self decision in which each UAV handles its own avoidance. A comparison of centralized and decentralized conflict resolution strategies were presented in (Bilimoria et al., 2000).

Another important design factor is the consideration of the CAS system for detection and accordingly resolving conflicts in multiple encounters scenarios. It describes how an approach handles traffic situations with multiple aircraft. It is divided into two types: Single conflict management approaches in which multiple sequential conflicts are avoided sequentially in pairs, and multiple conflict management approaches in which the entire situation is handled simultaneously. The general problem raises questions such as does this maneuver work on multi aircraft? Is there a maximum packing density where maneuvers no longer work and is it dependent on aircraft type or separation criteria?

Cooperative and non-cooperative collision avoidance algorithm can be also considered as one of the factors affacting CAS design. Technically, cooperative has equiped with ATC transponder or the recent ADS-B technology. In general, the case for which aircraft can communicate together resolves the conflicts more efficiently in term of their flight paths as compared with non-cooperative collision avoidance algorithms.

8. Conclusion

In this chapter, the fundamental concept and the key functions of the unmanned aircraft collision avoidance system are carried out. Special attention is given to the context-aware implementation in the collision avoidance domain. The intent of this chapter is to introduce a new conceptual framework for CAS system to handle conflicts more efficiently. Accordingly, providing an up-to-date review of collision avoidance algorithms based on the main CAS design factors those which also handled in details.

Building collision avoidance capability into flight controller requires detailed knowledge of the aircraft dynamics and deployment. In theory, CAS algorithms for UAVs like to assume that their models and methods are working efficiently. However in reality, due to system weaknesses and sensor error compound over time their systems may fail to prevent collisions. Due to a wide variety of UAVs types, their operating conditions, environment and missions, leads to the need for different degrees and types of collision avoidance algorithms. Therefore, no one sensing method and one CAS algorithm should be expected to cover all types and conditions. However, two or more fused sensors may be required to provide a complete picture of the surounding environment. Thereby resolve conflicts more efficiently. Availability of new techniques and sensors will lead to new and exciting CAS algorithms to be continually developed.