uavCoveragePlanner

Path planner for UAV space coverage

Since R2023a

Description

The uavCoveragePlanner object plans an optimal path that a UAV can follow to cover an region of interest with a sensor such as a camera for precision agriculture and image mapping applications. The object finds the optimal path by finding a sweep angle that minimizes the number of turns in each polygon and uses one of two specified solver algorithms to optimize the connecting path between regions.

Creation

Syntax

planner = uavCoveragePlanner(coverageSpace)

planner = uavCoveragePlanner(coverageSpace,Name=Value)

Description

planner = uavCoveragePlanner(coverageSpace) creates a coverage planner planner from a coverage space coverageSpace and sets the CoverageSpace property.

planner = uavCoveragePlanner(coverageSpace,Name=Value) sets properties using one or more name-value arguments.

Properties

CoverageSpace — Coverage space for planner

uavCoverageSpace object

Coverage space for the planner, specified as a uavCoverageSpace object.

SolverAlgorithm — Solver algorithm for path planning

"MinTraversal" (default) | "Exhaustive"

Solver algorithm for path finding, specified as either "MinTraversal" or "Exhaustive".

• "Exhaustive" — The planner exhaustively iterates through all permutations of sweep options to find the optimal one that minimizes connection distance between regions. See [1] for more details.

• "MinTraversal" — The planner uses a recursive minimum traversal approach through a graph of adjacent polygons to minimize the connection distances between the polygons from takeoff to landing. When a coverage path has no more immediate neighbors, the UAV flies to the nearest node in the graph and continues the optimality criteria. See [2] for more details.

  Note

  The number of polygons must be less than 12 when using the exhaustive solver. If you have 12 or more polygons to survey, consider merging polygons or setting SolverAlgorithm to "MinTraversal".

Generally, the exhaustive planner algorithm is better suited for smaller regions or separated regions where the distance optimality of the path is a high priority. Whereas the minimum traversal planner algorithm is faster focuses more on providing an intuitive solution for interconnected regions.

Data Types: char | string

SolverParameters — Solver algorithm parameters

structure

State space for the planner, specified as a structure containing these fields depending on the value of SolverAlgorithm:

When SolverAlgorithm is "Exhaustive", specify a structure with these fields:

• MinAdjacencyCount — Minimum number of adjacent polygons that a sequence must have for the planner to consider the sequence as a valid solution, specified as a nonnegative integer.

  For example, consider a coverage space that has three polygons. Polygon 1 is adjacent to polygon 2, and polygon 2 is adjacent to polygon 3.

  • If the visiting sequence is [1 2 3], there are two adjacencies in the sequence: one adjacency between 1 and 2, and another between 2 and 3. The uavCoveragePlanner object considers this sequence as valid when MinAdjacencyCount is either 1 or 2.

  • If the visiting sequence is [1 3 2], then the only adjacency in the sequence is between polygon 2 and polygon 3. So the uavCoveragePlanner object can only consider this sequence as valid when MinAdjacencyCount is 1.

  Default is 1.

• VisitingSequence — Order of traversal of polygons, specified as an N-element row vector, where N is the total number of polygons in the coverage space. For example, a visiting sequence of [1 3 2], specifies that the polygons must be traversed in the order, polygon 1, polygon 3, and then polygon 2. An empty row vector specifies no visiting sequence, enabling the solver algorithm to determine the visiting sequence.

  Default is [].

  Note

  The number of polygons must be less than 12 when using the exhaustive solver. If you have 12 or more polygons to survey, consider merging polygons or setting SolverAlgorithm to "MinTraversal".

When SolverAlgorithm is "MinTraversal", specify a structure with these fields:

• StartingArea — Index of polygon, where the UAV starts coverage specified as an integer scalar in the range [1, N]. N is the total number of polygons in the coverage space.

  Default is 1.

• VisitingSequence — Order of traversal of polygons, specified as an N-element row vector, where N is the total number of polygons in the coverage space. For example, a visiting sequence of [1 3 2], specifies that the polygons must be traversed in the order, polygon 1, polygon 3, and then polygon 2. An empty row vector specifies no visiting sequence, enabling the solver algorithm to determine the visiting sequence.

  When VisitingSequence is specified, the planner ignores the startingArea.

  Default is [].

Object Functions

plan	Plan coverage path between takeoff and landing
exportWaypointsPlan	Export waypoints to file

Examples

Plan Coverage Path Using Geodetic Coordinates

This example shows how to plan a coverage path that surveys the parking lots of the MathWorks Lakeside campus.

Get the geodetic coordinates for the MathWorks Lakeside campus. Then create the limits for our map.

mwLS = [42.3013 -71.375 0];
latlim = [mwLS(1)-0.003 mwLS(1)+0.003];
lonlim = [mwLS(2)-0.003 mwLS(2)+0.003];

Create a figure containing the map with the longitude and latitude limits.

fig = figure;
g = geoaxes(fig,Basemap="satellite");
geolimits(latlim,lonlim)

Get the outline of the first parking lot in longitude and latitude coordinates. Then create the polygon by concatenating them.

pl1lat = [42.3028 42.30325 42.3027 42.3017 42.3019]';
pl1lon = [-71.37527 -71.37442 -71.3736 -71.37378 -71.375234]';
pl1Poly = [pl1lat pl1lon];

Repeat the process for the second parking lot.

pl2lat = [42.30035 42.2999 42.2996 42.2999]';
pl2lon = [-71.3762 -71.3734 -71.37376 -71.37589]';
pl2poly = [pl2lat pl2lon];

Create the coverage space with both of those polygons, set the coverage space to use geodetic coordinates, and set the reference location to the MathWorks Lakeside campus location.

cs = uavCoverageSpace(Polygons={pl1Poly,pl2poly},UseLocalCoordinates=false,ReferenceLocation=mwLS);

Set the height at which to fly the UAV to 25 meters, and the sensor footprint width to 20 meters. Then show the coverage space on the map.

ReferenceHeight = 25;
cs.UnitWidth = 20;
show(cs,Parent=g);

Set the sweep angle for polygons 1 and 2 to 85 and 5 degrees, respectively, to have paths that are parallel to the roads in the parking lots. Then create the coverage planner for that coverage space with the exhaustive solver algorithm.

setCoveragePattern(cs,1,SweepAngle=85)
setCoveragePattern(cs,2,SweepAngle=5)
cp = uavCoveragePlanner(cs,Solver="Exhaustive");

Set the takeoff position to a location in the courtyard, then plan the coverage path.

takeoff = [42.30089 -71.3752, 0];
[wp,soln] = plan(cp,takeoff);
hold on
geoplot(wp(:,1),wp(:,2),LineWidth=1.5);
geoplot(takeoff(1),takeoff(2),MarkerSize=25,Marker=".")
legend("","","Path","Takeoff/Landing")
hold off

Plan Coverage Path for Defined Region

This example shows how to plan a coverage path for a region in local coordinates and compares the results of using the exhaustive solver with the results of using the minimum traversal solver.

Define the vertices for a coverage space.

area = [5 8.75; 5 27.5; 17.5 22.5; 25 31.25; 35 31.25; 30 20; 15 6.25];

Because vertices define a concave polygon and the coverage planner requires convex polygons, decompose the polygon into convex polygons. Then create a coverage space with the polygons from decomposition.

polygons = coverageDecomposition(area);
cs = uavCoverageSpace(Polygons=polygons);

Define the takeoff and landing positions at [0 0 0] and [32.25 37.25 0], respectively. Then show the coverage space and plot the takeoff and landing positions.

takeoff = [0 0 0];
landing = [32.25 37.25 0];
show(cs);
exampleHelperPlotTakeoffLandingLegend(takeoff,landing)

Create a coverage planner with the exhaustive solver algorithm and another coverage planner with a minimum traversal solver algorithm. Because Polygon 2 is closer to the takeoff position, set the visiting sequence of the solver parameters such that we traverse Polygon 2 first.

cpeExh = uavCoveragePlanner(cs,Solver="Exhaustive");
cpMin = uavCoveragePlanner(cs,Solver="MinTraversal");
cpeExh.SolverParameters.VisitingSequence = [2 1];
cpMin.SolverParameters.VisitingSequence = [2 1];

Plan with both solver algorithms using the same takeoff and landing positions.

[wptsExh,solnExh] = plan(cpeExh,takeoff,landing);
[wptsMin,solnMin] = plan(cpMin,takeoff,landing);

Show the planned path for both the exhaustive and the minimum traversal algorithms.

figure
show(cs);
title("Exhaustive Solver Algorithm")
exampleHelperPlotTakeoffLandingLegend(takeoff,landing,wptsExh)

figure
show(cs);
title("Minimum Traversal Solver Algorithm")
exampleHelperPlotTakeoffLandingLegend(takeoff,landing,wptsMin)

Export the waypoints from the minimum traversal solver to a .waypoints file with the reference frame set to north-east-down.

exportWaypointsPlan(cpMin,solnMin,"coveragepath.waypoints",ReferenceFrame="NED")

Execute Coverage Plan Using UAV Mission

Initialize the settings to use for the coverage planner, coverage space, and mission. Set a coverage width to 65 meters, the region as polygon vertices, takeoff and landing locations, the UAV elevation during flight to 150 meters, and a geocenter.

coverageWidth = 65;
region = [-210 130; 10 130; 10 20; 110 20;
          110 -130; -140 -130; -140 -20; -210 -20];
takeoff = [-250 150 0];
landing = [0 -200 0];
uavElevation = 150;
geocenter = [-45 71 0];

Create the coverage space with those UAV coverage space settings.

cs = uavCoverageSpace(Polygons=region, ...
                      UnitWidth=coverageWidth, ...
                      ReferenceHeight=uavElevation, ...
                      ReferenceLocation=geocenter);

cs.show;
title("Coverage Space")

Create a coverage planner for the coverage space and plan the coverage path with the specified takeoff and landing locations.

cp = uavCoveragePlanner(cs);
[waypoints,solnInfo] = cp.plan(takeoff,landing);

Plot the waypoints, and the takeoff and landing locations on the coverage space.

hold on
plot(waypoints(:,1),waypoints(:,2))
scatter(takeoff(1),takeoff(2),"filled")
scatter(landing(1),landing(2),"filled")
legend("","Path","Takeoff","Landing")
hold off

Export the waypoints to a waypoints file and create a UAV mission from that file with a speed of 10 meters per second and an initial yaw of 90 degrees.

exportWaypointsPlan(cp,solnInfo,"customCoverage.waypoints");
mission = uavMission(PlanFile="customCoverage.waypoints",Speed=10,InitialYaw=90);

Use the exampleHelperSimulateUAVMission helper function to visualize the UAV mission with a simulation time of 60 seconds.

exampleHelperSimulateUAVMission(mission,geocenter)

References

[1] Torres, Marina, David A. Pelta, José L. Verdegay, and Juan C. Torres. “Coverage Path Planning with Unmanned Aerial Vehicles for 3D Terrain Reconstruction.” Expert Systems with Applications 55 (August 2016): 441–51. https://doi.org/10.1016/j.eswa.2016.02.007.

[2] Li, Yan, Hai Chen, Meng Joo Er, and Xinmin Wang. “Coverage Path Planning for UAVs Based on Enhanced Exact Cellular Decomposition Method.” Mechatronics 21, no. 5 (August 2011): 876–85. https://doi.org/10.1016/j.mechatronics.2010.10.009.

Extended Capabilities

C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

Generating code containing the uavCoveragePlanner requires you to enable dynamic memory allocation. For more information about enabling dynamic memory allocation, see Set Dynamic Memory Allocation Threshold (MATLAB Coder).

Deploying to embedded real time (ERT) targets is not supported.

Version History

Introduced in R2023a

R2023b: Code generation support with dynamic memory allocation

uavCoveragePlanner now supports code generation with dynamic memory allocation enabled. For more information about enabling dynamic memory allocation, see Set Dynamic Memory Allocation Threshold (MATLAB Coder).

Deploying to embedded real time (ERT) targets is not supported.