### Multiple UAV Path Planning and Optimization

I have recently finished my Master studies in electrical engineering and robotics. The focus of my thesis are UAVs and the title is UAV Navigation for Area Coverage and Time Optimization. One of the goals of this study was to answer two questions:

1. What is the best path that will reduce each UAV flight time and the overall mission time?
2. Does using multiple UAV will always reduce mission time? In which conditions?

To answer these questions, I proposed a two step algorithm. The inputs for this algorithm are the location to be covered, flight altitude, speed, battery duration, camera sensor dimensions and focal length.

Step 1 - Finding sweep direction and position of sweep lines

To cover a region with a fixed wing aircraft, the plane must fly performing a sweep like pattern above the area. This pattern consists of straight lines connected by turns at the edge of the region. While the UAV is flying above these sweep lines, it will take pictures of the area below. Generally, the pictures used in 3D reconstruction are best if taken with the sensor plane parallel to the ground, so the pictures taken during turns are not useful. The objective of this step, is to reduce the number of turns and therefore also reduce the time that the UAV is not taking pictures.

The sweep direction is the direction above the coverage area which will give the minimum number of sweep lines. The distance between each of these lines is calculated taking the width of the area below the UAV that is projected in the camera sensor and the desired overlapping of the taken pictures.

Step 2 - Multiple UAV Path Planning

This step uses the position of the sweep lines, the number of available UAVs, UAV setup time and battery duration to plan the path of each UAV used to accomplish the mission. All this information is modeled as a Mixed-Integer Linear Programming (MILP) problem that is programmed in Matlab (www.mathworks.com), using the frontend Yalmip (http://users.isy.liu.se/johanl/yalmip/) and solved with Gurobi (http://www.gurobi.com/).

Results:

This algorithm was tested to plan the path to cover an area of approximately 150 hectares (1.6 x 0.9 km) which is shown in the picture bellow.

I did two different tests. The first one was to set a benchmark and used only one UAV. This UAV took 27.7 minutes, flying at 55km/h, to complete the coverage mission. The flight path of the UAV is in the first image and the altitude profile is shown in the second image bellow. The setup time is shown in red and flight time is shown in green.

In the second test, three UAV were provided to the algorithm. That means that I had three UAVs ready to fly if needed. But the algorithm chose to use only two UAVs. The total mission time for this test was 24.2 minutes. The second UAV was used to cover only two of the nine sweep lines, as can be seen in the images bellow. UAV 1 is represented by dashed lines and UAV 2 is represented by solid lines.

Conclusions:

The efficiency of the use of more than one UAV has to take into consideration the time that each equipment takes to be ready to fly, with GPS lock and safety measures. If you have a limited number of people to operate the equipment, the area has to be huge to make it worth to use more than one UAV. As can be seen from the second test, the gain in my case was only 3 minutes, considering that each UAV had 8 minutes of setup time.

Another interesting conclusion is that sometimes, the fastest path to finish the coverage mission, doesn't start and end on the first or last sweep lines. Depending on the ground control station and take off position, starting from one of the middle sweep lines can lead to a faster route.

During these tests, I also used the flights to take some pictures for a 3D model. But this is for another blog post.

• The idea is to trace the route the same way we would do by hand : we won't calculate every lengths but see a global shape and immediatelly purpose a good solution, not the best but a fairly good one. I'm sure it's much harder to program it!

• @Gustavo, yeah these kinds of computation take a lot of time as our computers have to compute every cases.

To save time, you could maybe identify and precompute models. Even if the result won't be the best one, it would be given quickly with a decent efficiency.

Second solution, get a quantum computer... should be even harder ;)

• Nice experiment, well done!

I would like to Mission Planner does this algorithm for calculate which of the best grid or number of drones for execute the mission. Would be great!

Congratulations, Master!

Brazil!

• @Julien,

I can't predict when it will take longer to execute the algorithm. In this example, which also has 10 sweep lines, the algorithm took less than 20 seconds.

Even though the other example also had 10 sweep lines, the optimization had to search in 184K nodes. In this case, there were 'only' 47K nodes.

• @Julien, yes I really think so.

Actually, as the number of sweep lines and available UAVs increases, the step 2 of the algorithm takes longer to find an answer, even minutes sometimes. Even if I limit the number of available UAVs to one, sometimes it takes more than a minute to find the best path, due to the number of sweep lines.

In the image above you can see an example in which the shortest path starts from the third sweep line from the top, then heads north. After passing through sweep lines 2 and 1, the UAV heads towards the fourth sweep line and goes south until the end. The algorithm took more than 80 seconds tho find this path, so its unusable in a real life application.

But the first step is really easy to execute and has a low order of complexity, so it would be nice to see it on APM Planner, Mission Planner and DroidPlanner.

• Very interesting results, do you think your algo could be integrated to mission planner? Could me a very nice feature!

• Thanks Daniel!

• I like the airframe.

• @Seth This is a modified flying wing from the standard Zagi design. My friends from the Center for Aeronautical Studies UFMG (http://www.demec.ufmg.br/cea/principal_eng.htm) did some modifications:

1. Longer wingspan: 1.8 m
2. Modified sweep angle for a more stable flight dynamic
3. Included wing washout to avoid wingtip stall
4. This modifications makes the UAV fly levelled with minimum elevon deflections, thus minimizing drag.

It has a Micropilot 2128g for an autopilot and a Xtend 900MHz as the telemetry link. And it can carry a GoPro Hero 2 or a Canon ELPH 130.

@Johann_van_de_Venter Yes, we could carry a gimbal. But that would add weight to the airframe and complexity to the hole operation. One of the objectives was to be as simple as possible. But thanks for your suggestion.

Centro de Estudos Aeronauticos - UFMG
• This actually got me thinking....

Since photo's taken from a turn is not usable, will it not be possible to use a camera gimbal to tilt the camera in a direction when the craft is banking in a turn and therefor keeping the lens perpendicular to the ground and optimizing the process somewhat?