Main Content

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

    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.

    example

    Properties

    expand all

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

    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

    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

    planPlan coverage path between takeoff and landing
    exportWaypointsPlanExport waypoints to file

    Examples

    collapse all

    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);

    Figure contains an axes object with type geoaxes. The geoaxes object contains 4 objects of type line, text.

    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

    Figure contains an axes object with type geoaxes. The geoaxes object contains 6 objects of type line, text. These objects represent Path, Takeoff/Landing.

    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)

    Figure contains an axes object. The axes object contains 6 objects of type polygon, text, scatter. These objects represent Polygon 1, Polygon 2, 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 contains an axes object. The axes object with title Exhaustive Solver Algorithm contains 7 objects of type polygon, text, scatter, line. These objects represent Polygon 1, Polygon 2, Takeoff, Landing, Path.

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

    Figure contains an axes object. The axes object with title Minimum Traversal Solver Algorithm contains 7 objects of type polygon, text, scatter, line. These objects represent Polygon 1, Polygon 2, Takeoff, Landing, Path.

    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")

    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")

    Figure contains an axes object. The axes object with title Coverage Space contains 2 objects of type polygon, text.

    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

    Figure contains an axes object. The axes object with title Coverage Space contains 5 objects of type polygon, text, line, scatter. These objects represent Path, Takeoff, Landing.

    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)

    Figure contains an axes object. The axes object with title Survey Coverage Space Mission, xlabel East (m), ylabel North (m) contains 435 objects of type patch, line, text.

    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

    Version History

    Introduced in R2023a

    expand all