Development of collision avoidance system for unmanned aerial vehicles
This paper is focused about fi nding an optimal solution for the collision avoidance of UAV in a busy airspace with both stationary and moving obstacles present in it, using Indian Navigation and Remote Sensing satellites
Satellite Navigation service is an emerging satellite based system with commercial and strategic applications. To meet the user requirements of the positioning, navigation and timing services based on the indigenous system, ISRO is establishing a regional satellite navigation system called Indian Regional Navigation Satellite System (IRNSS). ISRO is also jointly working with Airport Authority of India (AAI) in establishing the GPS Aided Geo Augmented Navigation (GAGAN) system to meet Civil Aviation requirements. ISRO is already one of the leaders in Remote Sensing satellites. High resolution images received from these satellites are used for various sectors such as agriculture, land and water resources, forestry, environment, natural disasters, urban planning and infrastructure development, rural development, and forecasting of potential fishing zones.
Unmanned Aerial Vehicles [UAV] are complex systems engineered to substitute humans in missions deemed as dirty, dangerous or dull. Advancement in MEMS based low-cost sensor technologies has resulted in the availability of a range of Commercial Off-the-Shelf [COTS] Flight Control Systems [FCS] / Autopilot Systems. It lend them readily to integrate with model scale aircraft and in turn provide excellent platforms to UAV for application enthusiasts, researchers and operators. Due to the increase in UAV applications, the need to develop Collision Avoidance System is becoming a major area of research.
This paper is focused about finding an optimal solution for the collision avoidance of UAV in a busy airspace with both stationary and moving obstacles present in it, using Indian Navigation and Remote Sensing satellites. To achieve this, different algorithms were explored. Dijkstra’s algorithm was implemented as a method to avoid stationary obstacles. Automatic Dependence Surveillance-Broadcast (ADS-B) technology and Kalmann filtering was studied for object tracking whereas Inverse Proportional-Navigation [PN] Guidance law was applied as a method to maneuver in collision conditions.
The whole system was simulated in Matlab under different scenarios, and results were found satisfactory.
An over-simplistic view of an Unmanned Aerial Vehicle (UAV) is that it is an aircraft with its aircrew removed and replaced by a computer system and a radio-link and is either controlled autonomously by on-board computers, or with the help of a remote pilot.
Today, many different types of UAV are easily available in the market and are used for various applications ranging from defense and surveillance to food and grocery delivery, aerial photography etc.
Working of UAVs
Similar to different aircrafts, Navigation. Control and Guidance constitute the key blocks of UAV, but here the manual pilot is replaced by a Computer or technically a Digital Autopilot, which controls the vehicle. NGC system for a typical UAV is shown in figure 1.
The target points for the UAV is provided either before the fl ight or in the course of flight. These target points are called Way-points. Now the Guidance algorithm calculates the desired fl ight parameters i.e. Bearing, Altitude, Airspeed etc. for the aircraft to follow the Way-points in an optimal fashion. Navigation system provides the attitude parameters of the aircraft using different sensors (GPS, Accelerometer, Gyroscope, Magnetometer, Pitot-tube, Barometer etc.). Difference between desired fl ight parameters (calculated by Guidance algorithms) and input navigation data are fed to the Digital Autopilot for the corrective action. Output of the Digital Autopilot is fed to the Control Surfaces (Aileron, Elevator and Rudder) to make the correction in their actual fl ight parameters.
Flight and post flight analysis of UAV
The UAV is assembled with all the required navigational sensors, surface actuators and communication tool. If Auto Take Off function is not available for the UAV, then it is fl own manually and after securely clearing the ground it is switched into Auto mode. The Autopilot interface shows all the attitude parameters of the UAV as well as the desired and actual path of the UAV. Control parameters of the Autopilot can be tuned offl ine before flight as well as real-time during the fl ight using the interface. It also records the attitude parameters for post fl ight analysis which plays an important roles especially in the case of any fl ight failure.
Figure 2 shows GUI for an Open-source autopilot system Ardupilot . Figure 3 shows an UAV Slybird and its trajectory data obtained using Xigbee transmitters.
Why collision avoidance system for UAV’s are required?
The need for Collision Avoidance Systems (CAS) has come about due to the increasing numbers of Unmanned Air Systems that are being operated now, as well as those that will be operated in the future. In order for commercial entities to be able to operate these vehicles, they must demonstrate a very high level of autonomy, as well as safety. Especially, where these aircraft will be operating in a commercial airspace environment, a greater deal of safety must be ensured.
The collision avoidance system
The proposed UAV Collision Avoidance System works in two steps:
Step1: Calculating the optimal path to reach the target avoiding stationary obstacles only.
Step2: Following the optimal path avoiding moving obstacles and once the obstacle is clear getting back to the optimal path.
Avoiding stationary obstacles
The GIS data derived from the Remote Sensing Satellite imagery is used to predict the stationary obstacles coming in the path of the UAV. The Data is used to create a 3D model.
Dijkstra’s Algorithm is used to calculate the optimal path avoiding these stationary obstacles. Dijkstra’s Algorithm solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. If there are several nodes in a mesh with points marked as a, a1, a2……..z, where a is the initial point and z is the final point then Figure 4 shows the fl ow diagram of Dijkstra’s algorithm to get the shortest path from a to z. Figure 5 shows the application of Dijkstra’s algorithm to avoid stationary obstacles which are mapped using GIS data obtained from Remote Sensing Satellites.
Avoiding moving obstacles
To avoid the moving obstacle it is required to track them first. For the purpose following two methods are found suitable: 1) ADS-B technology: 2) Kalmann Filtering Method: ADS-B technology  is a GNSS based system, where all the airborne fl ights transmit their own attitude parameters and receive the parameters of other flights in the given sensor range. Same data is received by the Ground station to monitor all the flights. Working of ADS-B technology is shown in figure 6. In Kalmann Filtering method the Attitude parameters of the moving object is predicted using continuous still image camera feed  as shown in figure 7.
Modelling the airspace
To simulate the CAS, it is required to model the airspace. It is assumed that n number of aerial vehicles are fl ying in a given area with random velocity of V1, V2…..Vn.
If for an aerial vehicle initial position and final position are Pi and Pf respectively, then the heading angle as shown in Figure 8,
Putting the value of tCPA to distance equation gives the minimum distance of the two aerial vehicles, technically called as Zero Effort Miss (ZEM) distance. If this distance is less than the minimum safe distance between the vehicles, there is a probability of collision and collision avoidance maneuver is applied.
Collision avoidance maneuver
To avoid a probable collision inverse of Proportional-Navigation (PN) Guidance law is used. PN Guidance law is extensively used in Homing missiles to intercept the target. In Proportional- Navigation Guidance law  the missile is provided lateral acceleration such that the rate of rotation of Line Of Sight (LOS) is minimized.
As the purpose here is opposite to the Homing Missiles, i.e. here we want to avoid the probable collision the applied guidance law is inverse of the PN-Guidance law  i.e. here the lateral acceleration on the UAV is applied such that the rate of rotation of Line Of Sight (LOS) is increased.
So, increase the rate we have put a lateral acceleration on the UAV as shown in the figure. If 01 > 02 then the lateral acceleration will be applied to the opposite direction.
The proposed system was simulated in Matlab for different scenarios. Figure 10 shows the result when no obstacles were present in the path of the UAV. In this condition, the UAV followed the optimum straight line path from start point to the target point.
Figure 11 shows the result in the condition when only stationary obstacles were present. In this condition the Guidance algorithm applies the Dijkstra’s algorithm to calculate the optimal path avoiding the obstacles. Heading angle of the plane is changed accordingly to follow the calculated path.
Figure 12 shows the result in the condition when both stationary as well as moving type of obstacles were present. The guidance system first calculates the optimal path avoiding the stationary obstacles, and simultaneously continues with background execution of algorithm to predict any probable collision with moving obstacles. If any collision is detected the collision avoidance maneuver is applied with the help of PN-Guidance method. Once the obstacle is avoided, Dijkstra’s algorithm provides the new optimum path to get to the target point.
The algorithm was simulated with different number of moving obstacles and types of stationary obstacles.
The algorithm can be integrated with the open-source autopilots like Ardu-pilot for real-time tests. To simulate the moving obstacle scenario different UAVs can be used. GNSS data can be used for tracking different UAVs and post fl ight trajectory data can be used to verify the algorithm.
 APM Planner: code.google.com/p/ ardupilot-mega/wiki/Mission
 DIY Drones : http://diydrones.com/
 Neil F. Plaumbo, Ross A. Blauwkamp and Justin M. Lloyd ‘Basic Principles of Homing Guidance’
 George J. and Ghose D., 2009, ‘A Reactive Inverse PN Algorithm for Collision Avoidance among Multiple Unmanned Aerial Vehicles’, in 2009 American Control Conference, St.Louis, MO, USA, pp.3890-3895
 Mathworks: http://in.mathworks.com/
 Automatic Dependent Surveillance – Broadcast (ADS-B) Out Based Ats Surveillance Services, Aai/ Atm/Ais/09-09/2014