Coverage path planning for drones

Imagine you felt an unpleasant smell on the way home. You want to handle the problem but your motivation to determine its source and the hazard level is undermined by a self-preservation instinct. This is a suitable situation to exploit UAV (Unmanned Aerial Vehicle) services to take care of the occasion. To know more about how these services may be organised and operate, please visit a Simlab's blog on blockchain framework for drone market.

In the described case, a drone or a drone fleet responsible for air measuring would receive data on the area where the smell is distinct. The area, or a polygon, may have holes. For example, drones cannot access buildings or people might feel extremely uncomfortable noticing drones circling above playgrounds. This polygon is the input for a CPP algorithm. The output is a route flying through which the drone would reach each point of the polygon with the attached equipment.

There is a bunch of reasons why it is unacceptable to make some route that allows reaching each point of a polygon. First, drone's charge is too limited to waste it on long suboptimal routes. Second, the definition of 'long route' is a bit tricky regarding drones. While for ground vehicles it is mostly the matter of distance, a remarkably power-consuming element of routes for drones is turns. To make drone missions cheap, fast and effective, it is crucial to optimise the distance and the number of turns while path planning.

The first conventional approach to CPP is called the cellular decomposition. This method includes splitting an inputted polygon into several convex polygons, covering them all with a Boustrophedon path and finally determining in what order they should be flight over.

The math behind the first two steps is aimed to optimize the number of turns. Consequently, the overall solution is flawless in this regard. However, a complex shape of an inputted area with numerous holes may interfere with the process of finding the optimal route in terms of distance which is also of great importance. For more details on this approach, we recommend you to read a paper
of Li et al. (2011).

The second common way to perform CPP is spanning tree-based coverage. According to this approach, the inputted polygon is covered with a grid which induces a graph that further serves as a basis for a spanning tree. The route is created around the tree and the final result represents a Hamiltonian cycle.

The Hamiltonian cycle is an optimal solution distance-wise. However, no optimization is conducted for the number of turns. This approach is described in detail in a paper of Gabriely and Rimon (2001).

Simlabs found the spawning tree covering algorithm more promising for CPP. After a thoughtful evaluation, we decided that it has more room for improvement than the cellular decomposition. It is indeed not a universal solution but with our goals taken into account, it turned up to be a worthy approach.

We reworked the algorithm by making it more inclined to extend existing branches rather than creating new ones while generating a spanning tree. This compounded with a set of additional slight adjustments improved the performance of the algorithm significantly regarding the number of turns. Moreover, we considered how a drone gets to a place where an accident has occurred and how to split the coverage between several drones or the same drone that need to return to base to charge at some points. Now, you can see this full-fledged CPP algorithm in action as a part of U-traffic.