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.

3689607996?profile=original

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.

3689608039?profile=original

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.

3689607910?profile=original3689608065?profile=original

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.

3689607927?profile=original3689608048?profile=original

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.

E-mail me when people leave their comments –

You need to be a member of diydrones to add comments!

Join diydrones

Comments

  • What airframe is this?

  • Developer

    Really interesting research.  Thanks for sharing!

This reply was deleted.