2016: Safe navigation for micro and mini UAVs

I have worked on this project during my stay at the Center for Research in Computer Vision (CRCV) of UCF, Orlando, FL, under the supervision of Dr. Mubarak Shah.

The project aims to increase safety in regards to UAV operation in urban areas.

Our method uses geodetically accurate dataset images with Geographical Information System (GIS) data of road networks and buildings provided by Google Maps, to compute a weighted A* shortest path from start to end locations of a mission. Weights represent the potential risk of injuries for individuals in all categories of land-use, i.e. flying over buildings is considered safer than above roads. We enable safe UAV operation in regards to 1- land-use by computing a static global path dependent on environmental structures, and 2- avoiding flying over moving objects such as cars and pedestrians by dynamically optimizing the path locally during the flight. As all input sources are first geo-registered, pixels and GPS coordinates are equivalent, it therefore allows us to generate an automated and user-friendly mission with GPS waypoints readable by consumer drones’ autopilots.
We simulated 54 missions and show significant improvement in maximizing UAV’s standoff distance to moving objects with a quantified safety parameter over 40 times better than the naive straight line navigation.

Paper on arXiv.

Video summary of our method:

 


Weight map

Weights in our cost function for computing the flight path are defined using land-use summarized in three classes: most dangerous areas are roads and paths where people are prone to the danger the UAV represents, safest are buildings and water, and the rest is in between.

Below is a visualization of the weight map overlaid on the corresponding satellite image, for WPAFB dataset. Colors represent costs in the weight map, red, transparent and green respectively represent dangerous, neutral, and safer areas.

MAP_WPAFB_Final

Weight map

MAP_WPAFB_maskMaybeGo

Road network

MAP_WPAFB_maskGo

Buildings

 


Static path planning

We find the safest route between two GPS coordinates by converting them into image pixels and computing a weighted shortest path algorithm using A* algorithm. The segments’ lengths between two adjacent pixels are the Euclidian distance multiplied by the weight defined by the map class. Pixels that are in red have a weight of 100, green is at 5, and the rest is at 20. Those values have been determined empirically. This process ensures that the red areas are avoided but also makes sure the UAV wouldn’t take a long detour to reach its destination, thus keeping the loss of flight time to a minimum.

As the map is geo-registered, the outputted path can easily be converted into GPS coordinates, and put in KML an TXT files to be readable by mapping software and ground control stations.

Path4

White: typical straight line path, Blue: our method

Path_MP1

Path converted to GPS waypoints for mission planner software

 


Dynamic path planning

For increased safety, the path needs to be adapted dynamically during the flight to avoid moving objects detected in the field of view of the UAV’s embedded camera.
In order to ensure a sufficient distance margin between each object and the UAV, the weight map used for shortest path is modified according to the objects’ location, trajectory and velocity.
We compute the new weights of the map by applying at chosen locations a multivariate normal probability density function.

 

Obj_avoidance1

Images (left) and their corresponding weight map (right). The multivariate distribution is applied in regards to moving objects, the optimized weighted shortest path (in blue) deviates from the static path (in red or black) to avoid moving objects

 


Experiments

We use two datasets to run our safe navigation pipeline, Wright-Patterson Air Force Base WPAFB and PVLabs. They are wide-area motion imagery (WAMI), and provide ground truth for moving objects on ortho-rectified images captured by UAVs. Both of those datasets have been captured at high altitude with embedded sensors and a matrix of multiple cameras. We use the provided regions of interest outputted by a geo-registration step that has rectified images and data, thus giving the illusion of a fixed camera.
For each dataset we run the different steps of the pipeline. We first create the weight map, videos are then precisely geo-registered onto the map via homography transformation. The global path is generated before the simulated flight and adapted dynamically on the way.

For both WPAFB and PVLabs datasets, we defined 9 different pairs of start and end GPS coordinates based on the environment and busyness of the roads to create challenging situations that will require global path adaptation. And each path is executed at three different UAV velocities: 5, 8, and 11 m/s.
The total traveled distance by using the global path compared to the classic straight line path, for each dataset executed for all paths at three above velocities, is 20% higher or 5:13 min longer for WAPAFB and 6% or 32 s for PVLabs, making our safety increased path an affordable measure in term of autonomy.

pathsPVLabs_num

PVLabs paths

pathsWPAFB_num1

WPAFB paths

 


Results

To quantify the performance of the proposed method we introduce a metric assimilated to safety. We consider the UAV to object proximity, the closer the UAV is to an object the more danger it represents for it, we therefore compute a total cost for each dataset.

Capture1

Metric

 

Capture

Results

We can clearly see that our proposed method encounters more objects in the FOV, but it has the means to keep the UAV afar from them. Objects which are over 20m away are not in danger, but having a car or pedestrian closer than 5m to the UAV represents a very concerning situation in terms of safety for people. This is why we have chosen to compute the global cost with a negative exponential weight function, that way the shorter the distance, the more cost is applied to the global metric. The proposed method encounters over twice the amount of moving objects but safely keeps away from them, making the resulting safety parameter much better than global path and, most of all, better than classic straight line path.

plotObjDist

WPAFB

plotObjDist1

PVLabs

 


Example runs

 

1_5_0.5_5_5_50_97.4_248_metrics_all_obj

Distance to objects at every frame (in X)

1_5_0.5_5_5_50_97.4_248_path

Static path

1_5_0.5_5_5_50_97.4_248_pathFinal

Dynamic path


6_5_0.5_5_5_50_97.4_248_pathFinal6_5_0.5_5_5_50_97.4_248_path


7_8_0.5_5_5_50_97.4_248_metrics_all_obj7_8_0.5_5_5_50_97.4_248_path7_8_0.5_5_5_50_97.4_248_pathFinal