Keywords

1 Introduction

Coverage path planning (CPP) is a type of path planning where the generated trajectory ensures the robot footprint covers all open spaces in the area of interest (AOI). It is key to autonomous robotics and differs from start-to-goal path planning where a path from a start point to a goal is sought. These path planners find application in mobile ground robotics like vacuum cleaning, lawn mowing, security and surveillance, deicing of airports, and harvesting or seeding, among others, and mobile aerial robotics like crop sensing, geological documentation, urban planning, wetland management, search and rescue, land-use monitoring, mapping and remote sensing among others.

Literature has many elegant solutions to the coverage problem. Unfortunately, most of these solutions are specific to mobile ground robotic applications and do not scale optimally to aerial robotics. This limited generalizability together with advances in aerial robotics and remote sensing have fueled intense research in the field of aerial coverage path planning (ACPP).

According to PwC global report [1] on commercial applications of unmanned aerial vehicle technology, the two leading industries, infrastructure and agriculture, account for more than a half of the global market share Fig. 1. Clearly, all involved industrial application are large-scale and coverage in nature.

Fig. 1.
figure 1

Predicted market value for UAV powered industrial solutions in US dollars [1]

Full size image

These applications call for close proximity flights to the subject of interest, which favors micro aerial vehicles (MAVs) as opposed to medium and large size vehicles. Unfortunately, large coverage industrial applications oftentimes exceed the coverage capability of most modern MAVs. Luckily, dropping prices have enabled acquisition of multiple platforms, whose aggregate capability can easily satisfy most of the large-scale coverage applications. It should be noted that even with a single platform and a path planner, multiple flights can be systematically conducted in a short period of time, owing to maneuverability and low operating costs of these aerial platforms.

To harness the cumulative power in numbers, partitioning schemes are necessary for partitioning of large areas into manageable portions and assigning them to a fleet of aerial platforms or flying them with one platform multiple times. To this point, we are not aware of any coverage path planning methods capable of planning paths for large areas exceeding the coverage capability of modern MAVs.

The problem overview is as follows, given a large-scale input area (impossible to cover in one flight), partition it into manageable subareas coverable by a multirotor MAV with limited endurance in multiple flights or a fleet of multirotor MAVs, and then plan trajectories to cover each subarea whilst adhering to coverage requirements.

We propose an approach that partitions large input areas into manageable cells with respect to endurance and flight speed, then plans coverage paths and assigns each cell to the most suitable MAV (with minimum coverage time).

The planner is applicable to a single platform, homogeneous (similar endurance and camera properties) and heterogeneous (varying endurance and camera properties) multirotor fleets. Furthermore, it guarantees complete coverage and resolution constraints. Guarantee of coverage is through exact cellular decomposition of the input area, and designing paths that ensure coverage of each cell. This work strives to achieve a good enough result but does not guarantee optimality.

2 Related Work

Generally, coverage path planning (CPP) considers four main set of factors, environmental, robot, actuator/sensor and algorithmic factors. Table 1 highlights the properties underlying each of the factors. Literature contains CPP algorithms based on permutations of these properties. We refer readers to a survey of coverage path planning in robotics [2] for a comprehensive characterization of the different approaches.

Table 1. Classification factors of coverage path planners
Full size table

Two CPP surveys [2, 3] spread over a decade apart report the most influential approaches up until 2013. Surveys [3] and [2] have 0% and <5% mention of ACPP respectively. This could have been a consequence of the under-developed state of unmanned aerial technology. The recent past has seen a surge in ACPP research works, but mostly for fixed-wing type MAVs. Next, we cover some of the influential works.

To cover concave polygonal areas, the authors of [4] proposed four convex decomposition strategies that yield minimum polygon altitude sub-regions. The decomposition works by drawing edges at concave vertices oriented to yield minimum width sum convex polygons. Entire adjacent cells with similar directions are then combined into one cell to shorten coverage paths. The resulting cells are then transformed into a minimum traversal undirected graph on which the minimum weight path to all cells is generated. Individual cells are covered with boustrophedon paths.

Interesting work from marine robotics in [5] proposed a coverage method for seabed using autonomous underwater vehicles (AUVs). K-means clustering segments the area into a user-defined number of sub-regions within predefined depth ranges. Morse exact cellular decomposition is applied to each cluster. Morse decomposition applies a Morse function contour at critical points to divide the clusters further into cells. Therefore, the number of cells depends on the number of critical points contained within a cluster, which may result into impractically small cells. The cells form an adjacency graph, where traveling-salesman algorithm plans a path to all cells. Each cell is covered using boustrophedon sweep lines oriented perpendicular to surface gradient.

A spiral-like method proposed in [6] plans paths for a fleet of heterogeneous unmanned aerial systems (UASs). The area is decomposed into triangular cells whose size depend on the sensor field of view (FOV) and platform orientation. The cells are transformed into an undirected graph whose vertices are assigned costs with the highest cost at the root (border) and lowest at the leaves (center). Based on cost, a path is generated from the border covering the entire area. Lloyd iterations and valley sensitivity settings were applied to improve the path.

An application specific, complete coverage yet non-optimal algorithm in [7], decomposes the area into triangular cells using Constrained Delaunay Triangulation (CDT). It starts by assigning each platform an initial cell at the border from which all the other cells are visited in a spiral-like pattern depending on their depth cost. This work assumes the starting point to lie within the area of interest.

To address endurance limitations, some researchers have adopted energy minimization objectives to maximize coverage per battery charge. In [8], a digital elevation model combined with a power consumption model created an energy consumption map, from which genetic algorithms generated an optimal coverage path. Although the generated path is complete, it is highly convoluted and self-intersecting. The approach in [9] generates a minimum energy complete coverage path using an energy model derived from real measurements with resolution constraints. Here an active gimbal stabilized camera is used, hence, the assumption of camera-ground parallelism. For coverage, boustrophedon motion pattern is applied with flight lines oriented parallel to the longest borderline. This approach performs poorly for areas with more than four edges, especially when the longest side is nearly parallel to the minor axis of variation of vertices.

Decomposition is a key step in most coverage approaches and one popular form of decomposition is grid-based decomposition. In [10], a gradient ascending algorithm tracks wavefront gradients on a grid-map selecting a sequence of waypoints that completely covers the area of interest while minimizing completion time. In case of multiple waypoints with similar potentials, a backtracker keeps record of these waypoints.

The work presented in [11], implemented the dual of Delaunay Triangulation, voronoi partitioning to partition the overlapping workspace of manipulator robots into appropriate cells. A coverage path plan for each is then generated covering its specific area plus the overlapping portion closest to it. We share the choice of partitioning algorithm with this work, but differ in the way voronoi sites are treated. In our case, the sites are user inputs whereas in [11] the site locations are the optimization variables. Most usage of voronoi diagrams have been centered around generating paths through narrow operating regions [12].

For complete coverage, spiral and boustrophedon trajectories are the most commonly used flight trajectories for both fixed-wing and multirotor micro aerial vehicles. An empirical performance assessment based on three metrics: energy, time and distance showed that spiral trajectories were more suitable for fixed wing platforms, whereas boustrophedon trajectories for multirotor platforms [13]. Based on this conclusion, boustrophedon trajectories are applied in our work for partition coverage.

The path planner describes in this paper involves techniques like home point-based area decomposition as opposed to number of platforms, and path generation and path splitting constrained by map resolution and platform endurance. The flexible placement of home points ensures accessibility to all areas whereas path splitting ensured complete coverage of even large cells. This level of flexibility, which is key to handling of large-scale areas, lacks in most of the available path planners.

3 Aerial Coverage

Aerial maps support many data–driven processes. Satellites and manned airplanes have for long been the main techniques for capturing raw aerial data. As depicted in Table 2, these techniques exhibit low revisit cycles and generate low-resolution maps compared to MAVs. Thus, MAVs provide a great alternative to satellite and manned mapping, but their sensors have a limited field of view that is compensated for by capturing numerous geo-referenced images at spatially distributed points within the input area. The images are then stitched together to generate an orthorectified mosaic. Here, the challenge is generating a path to all imaging geo-locations for completeness.

Table 2. Comparison of MAV and satellite remote sensing solutions
Full size table

3.1 Mapping Process

We adopted a mapping process consisting of three sub-steps, input area preparation, area partitioning and coverage path planning. The input area is defined by a set of mouse selected unordered geo-coordinates from a customized interactive digital map in Ardupilot Mission Planner software by Michael Oborne. The input area can be convex, concave or complex in geometry. Operations on complex and nonconvex polygons for tasks of aerial coverage add unnecessary levels of complexity.

Since mapping sensors have a nonzero footprint, a collage of such footprints automatically converts complex polygons into nonconvex ones as illustrated in Figs. 2 and 3. Interesting for aerial mapping is moving the imaging sensor to all geo-locations regardless of the overall area geometry. This reduces the problem to visiting a set of waypoints as opposed to planning at the geometric level. This transformed problem is solvable as a graph traversal problem or like in our case, with boustrophedon coverage paths. Next, we look at input area preparation.

Fig. 2.
figure 2

Complex area of interest covered with sensor footprints

Full size image
Fig. 3.
figure 3

Complex AOI automatically transformed into a non-convex polygon by sensor footprint coverage

Full size image
Fig. 4.
figure 4

Sample cell with coverage paths

Full size image

Input Area Preparation

Using the abundant arithmetic tools necessitated projecting the coordinates into a planar space, this transformation and its inverse are implemented using Lambert azimuthal equal area projection [14]. Counter clockwise coordinates sorting done in the polar space simplifies complex input areas to convex or concave areas. For concave areas, a convex approximation is determined using the Quickhull algorithm [15].

Area Partitioning

Comparison of the input area to the platform’s endurance determines the need for partitioning. The conditions for partitioning are expressed as follows,

$$ \frac{{D_{BB} }}{{60 \cdot v_{N} }} > T_{E} \;\text{AND}\;T_{C} > T_{E} $$
(1)

where \( D_{BB} \) is perimeter of the oriented bounding box around the area of interest (m), \( v_{N} \) is ground speed (m/s), \( T_{E} \) is endurance (min) and \( T_{C} \) is coverage time (min).

After ascertaining the necessity for partitioning, we then determine the number of partitions \( n_{P} \). A partition is approximated by an oriented bounding box of area \( A_{N} \).

$$ n_{P} = \frac{{A_{T} }}{{A_{N} }} = \frac{{16A_{T} }}{{D_{N}^{2} }},\;n_{P} \in {\mathbf{Z}} $$
(2)

where \( A_{T} \) is area of interest, \( A_{N} \) is the maximum area associated with endurance \( T_{E} \), i.e. the perimeter of \( A_{N} \) is equal to the nominal coverage distance \( D_{N} \) of a quadcopter.

Since the area is too huge to survey from the current home point, \( n_{P} \) new home points (discarding the original home point) are needed. These are the sites upon which voronoi partitioning is based. Voronoi cells are generated based on Euclidean distance and voronoi sites. Then, the final partitions are the regions of intersection between voronoi cells and or input area. The result is an exact cellular decomposition where,

$$ AOI = \sum\limits_{i = 1}^{{n_{P} }} {P_{i} } $$
(3)

where \( P_{i} \) is the area of partition \( i \). It should be noted that site placement plays a key role in partitioning. For better results, the sites should be distributed spatially evenly within and or around the area of interest. Most optimal locations for sites are near vertices of the intersection between bounding box and convex hull. If only \( T_{C} > T_{E} \) is true in Eq. 1, no area partitioning is necessary, but path splitting.

Coverage Path Planning

Before planning the actual path, let us look at optimal travel orientation determination and system specifications, as they are key to quality path plans.

Optimal Travel Lines Orientation

The choice of sweep direction greatly influences the number of turns and number of traversal lines and coverage distance [9, 16, 17]. The number of turns is proportional to number of traversal lines. Therefore, minimizing number of turns minimizes coverage distance, number of images and completion time.

Approaches for flight line heading determination include orientation of longest edge of input polygon [9, 17], longest edge of an axis aligned minimum area-bounding box, longest edge of an oriented minimum area bounding box and principal direction of variation of convex hull vertices. Aligning flight lines parallel to the longest edge of an oriented minimum area bounding box is the only method proven to yield optimal number of turns [16]. We empirically ascertained this optimality assertion by monitoring the variations in coverage path length with respect to path orientation. Figure 5 shows distance variation as the coverage path in Fig. 4 is rotated through 180°. Such characteristic is typical of a diameter function with global minima corresponding to optimal flight lines orientation.

Fig. 5.
figure 5

Distance variation as a function of path orientation. Critical point occurs at 13.90 km

Full size image

Specifications Elicitation

The following parameters constitute the independent variables for analysis:

  • Camera parameters: focal length \( f \), pixel pitch \( p \), pixel count (\( m \times n \) pixels) and shutter speed, \( T_{S} \)

  • Quadrotor specifications: ground nominal speed \( v_{N} \), endurance \( T_{E} \)

  • Mission specifications: an interactive digital map, desired ground sample distance (\( GSD \)), forward overlap \( f_{OVLP} \) and side overlap \( s_{OVLP} \), area of interest \( AOI \).

From the above independent variables, dependent variables are derived as follow:

  1. (a)

    Flight height

    $$ AGL = \frac{GSD*f}{p} $$
    (4)
  2. (b)

    Image footprint/ground coverage/image size on the ground is the actual area on the ground captured in an image.

    $$ D_{w} \times D_{h} = GSD \cdot m \times GSD \cdot n = GSD \cdot (m \times n) $$
    (5)
  3. (c)

    Side gain, \( s_{gain} \) and forward gain, \( f_{gain} \)

    $$ s_{gain} = D_{w} \cdot \frac{{\left( {100 - s_{OVLP} } \right)}}{100},\;f_{gain} = D_{h} \cdot \frac{{\left( {100 - f_{OVLP} } \right)}}{100} $$
    (6)
  4. (d)

    Number of images per flight line \( (NIM) \) and number of flight lines \( (NFL) \)

    $$ NIM = NFL + ceil\left( {\sum\limits_{i = 1}^{NFL} {\frac{{l_{i} }}{{f_{gain} }}} } \right)\;\text{and}\;NFL = ceil\left( {\frac{b}{{s_{gain} }} + 1} \right) $$
    (7)

where \( b \) is the diameter of convex hull and \( l_{i} \) is the length of flight line \( i \)

  1. (e)

    Camera trigger time \( T_{T} \) is given by the expression,

    $$ T_{T} = \frac{{f_{gain} }}{{v_{N} }}\text{,}\;\text{subject}\;\text{to}\;T_{T} > T_{S} $$
    (8)

To guarantee adjacency and stereoscopic coverage, images are captured with overlapping fields of view. Near vertical photos for aerial map generation overlap along direction of flight (forward overlap) and between adjacent flight lines (side overlap).

Spatial resolution determines not only image quality, but also the amount of imagery data needed for map generation. The amount of imagery data scales exponentially with ground spatial resolution [18, 19], as indicated in Fig. 6. The dependence of GSD on AGL and camera properties introduces a level of flexibility in terms of hardware selection, as the required map quality is achievable through strategic selection of camera properties and flight height. Flight altitude is upper bounded by air traffic regulations, which for North Rhine-Westphalia in Germany is limited to 100 m [20].

Fig. 6.
figure 6

Number of images scales exponentially with ground resolution. Results are based on a Sony NEX-5 camera with 25 mm focal length, 5.07 µm pixel pitch and 4595 × 3056 pixel count

Full size image

Coverage Path

We generate coverage paths for each cell as a series of parallel flight lines oriented towards the optimal travel direction. The generated coverage path may exceed the nominal endurance of available aerial platforms, in which case a splitter function automatically divides the area further into manageable paths. All planned paths are cyclic in nature. This approach is generalizable to multiple homogeneous MAVs with no modification whatsoever. Heterogeneous fleets require systematic scheduling.

Heterogeneous MAVs

Path planning for fleets of heterogeneous quadrotors is not as trivial as planning for a single or homogenous fleet. To accommodate the variation in platform capabilities, the previous planning steps are modified as follows:

Partitioning decision is based on minimum coverage quadrotor, Eq. 9. This ensures accessibility to even the furthest imaging points by all aerial platform.

$$ \frac{{D_{BB} }}{{60 \cdot v_{N,E\hbox{min} } }} > T_{E\hbox{min} } $$
(9)

where \( T_{E\hbox{min} } \) and \( v_{N,E\hbox{min} } \) are endurance and velocity of minimum coverage quadcopter. For the definitions of other parameters see Eq. 1.

For each platform \( i \), a coverage path is planned on each cell \( j \), resulting in coverage time \( T_{C,ij} \) and number of flights \( n_{F,j} \). A scheduler then allocates cells to available quadrotors with priority given to high endurance quadrotors and longest coverage time cells.

4 Simulation Results

The approach presented in this paper has been incorporate into the C# based Ardupilot Mission Planner to take advantage of the abundant functions available, and tested with software in the loop (SITL) simulator. In the following test, we used DJI Matrice 100 (M100) quadcopter with endurance TE = 20 min and nominal (minimum camera vibration) speed vN = 5 m/s, microdrones md4-1000 with endurance 45 min and nominal speed 6 m/s, a gimbal stabilized Sony nex-5 camera with focal length 25 mm, image size of 4595 × 3056 pixels, pixel pitch = 5.07 µm and sensor size of 23.5 × 15.6 mm. The flight altitude was set to 100 m, giving a ground resolution of 2.03 cm. The overlaps were set to 50% and 60% for forward and side overlap respectively. On analyzing, the input area AT = 9838175 m2, DBB = 12.6 km, partitions nP = 5.

Figure 7 shows the input area and the resultant coverage paths. The details for each of the cells are available in Table 3.

Fig. 7.
figure 7

(left) Input area partitioned into five cells according to the big green home points. (right) complete coverage paths for the five cells (Color figure online)

Full size image
Table 3. Results of AOI partitioning
Full size table

For the homogeneous case, only M100 was considered. Since the cell coverage paths exceeded the platform endurance, the paths were automatically split into segments matching quadrotor’s nominal coverage, which was 6000 m and output as waypoint files. The individual mission files have been tested on SITL simulator.

For the heterogeneous case, M100 and md4-1000 were considered. Each platform planned a coverage path for each cell. The resulting completion times are tabulated in Table 3. The cells were then scheduled on the quadrotors with priority given to high coverage quadrotors and longest completion time cells. Cells 2, 1, 3 were assigned to md4-1000 and 4, 5 to M100. The total completion time and total number of flights are 843 min and 20, 751 min and 39 for md4-1000 and M100 respectively.

5 Conclusion and Future Work

This paper has described and tested an offline large-scale aerial path planner that breaks endurance barriers on the deployment of MAVs for large-scale mapping applications. The planner uses voronoi exact cellular decomposition to partition large input areas into manageable cells. The approach is applicable to tasks involving a single MAV, heterogeneous and a homogeneous fleet of MAVs.

The planner accounts for location of home points, map resolution and multirotor capabilities in the process of planning coverage paths. The resulting plans can support decision-making processes, ensure recoverability of platforms and mission success.

SITL simulation tests conducted ascertained the feasibility and deploy-ability of the conceptualized method. Assumptions of perfect waypoint tracking, constant endurance and zero influence of environmental factors like wind on endurance do not hold in the real world and may lead to performance degradation in the field.

Regarding future work, further improvements on Mission Planner will be conducted to allow simultaneous tracking of multiple MAVs. Home points optimization will be incorporated to minimize user inputs and improve coverage performance. Last but not least, terrain effect on the performance of MAVs and map quality will be studied.