plan

Find shortest path between two states in graph

Since R2023a

collapse all in page

    Syntax

    path = plan(planner,start,goal)
    [path,solutionInfo] = plan(___)

    Description

    path = plan(planner,start,goal) finds the shortest path path between a specified start and goal in the graph using the specified A* path planner planner.

    example

    [path,solutionInfo] = plan(___) returns the solution information of the path planning solutionInfo.

    Examples

    collapse all

    Open Live Script

    Load the Queensland road network.

    load("queenslandRoutes","places","routes")

    Specify states, links, and weights for a navGraph object.

    states = places.utm;               % UTM coordinates of cities
names = places.name;               % Names of cities
links = [routes.start routes.end]; % Adjacent cities
weights = routes.time;             % Travel time between adjacent cities

    Create a navGraph object.

    graphObj = navGraph(states,links,Weight=weights, ...
                    Name=names);

    Create a graph-based A* path planner.

    planner = plannerAStar(graphObj);

    Create a deep copy of the plannerAStar object.

    planner2 = copy(planner)
    planner2 = 
  plannerAStar with properties:

    HeuristicCostFcn: @nav.algs.distanceManhattan
          TieBreaker: 0
               Graph: [1×1 navGraph]

    Specify a heuristic function returns an estimated time to reach the goal.

    planner.HeuristicCostFcn = @(state1,state2) ...
    sum(abs(state1-state2),2)/100;

    Define the start and goal cities.

    start = "Hughenden";
goal = "Brisbane";

    Find the shortest path using the graph-based A* algorithm.

    [pathOutput,solutionInfo] = plan(planner,start,goal);

    Visualize the results.

    h = show(graphObj);
set(h,XData=graphObj.States.StateVector(:,1), ...
      YData=graphObj.States.StateVector(:,2))
pathStateIDs = solutionInfo.PathStateIDs;
highlight(h,pathStateIDs,EdgeColor="#EDB120",LineWidth=4)
highlight(h,pathStateIDs(1),NodeColor="#77AC30",MarkerSize=5)
highlight(h,pathStateIDs(end),NodeColor="#D95319",MarkerSize=5)

    Figure contains an axes object. The axes object contains an object of type graphplot.

    Input Arguments

    collapse all

    A* path planner, specified as a plannerAStar object.

    Start state of the path, specified as a positive integer, string scalar, character vector, or numeric vector.

    • Positive integer — Specify the state ID of the start state. The state ID is the index of the state in the navGraph object in the Graph property of planner.

    • String scalar or character vector — Specify the name of the state.

    • Numeric vector — Specify the coordinates of the state.

    Example: 1

    Example: "Brisbane"

    Example: [1095.91458671447 6947.04365801860]

    Data Types: single | double | char | string

    Goal state of the path, specified as a positive integer, string scalar, character vector, or numeric vector.

    • Positive integer — Specify the state ID of the start state. The state ID is the index of the state in the navGraph object in the Graph property of planner.

    • String scalar or character vector — Specify the name of the state.

    • Numeric vector — Specify the coordinates of the state.

    Example: 5

    Example: "Hughenden"

    Example: [208.622393818849 7691.91766093269]

    Data Types: single | double | char | string

    Output Arguments

    collapse all

    Shortest path between states, returned as a numeric matrix.

    Data Types: double

    Solution information, returned as a structure. The fields of the structure are:

    FieldDescription
    IsPathFound

    Indicates whether a path has been found. Returns true if a path has been found. Otherwise, returns false.

    PathStateIDs

    List of IDs of the states along the path found by A*. By default, the IDs are the numeric indices of the states in the graph object. If you specify names for the states while constructing the graph object, this field contains the names instead.

    PathCost

    Total cost of the path. If no path is found, then the cost is NaN.

    ExploredStateIDs

    List of IDs of the states explored by A* during the search. By default, the IDs are the numeric indices of the states in the graph object. If you specify names for the states while constructing the graph object, this field contains the names instead.

    NumExploredStates

    Number of states explored during the search. Equal to the length of the ExploredStateIDs list.

    Data Types: struct

    Extended Capabilities

    expand all

    C/C++ Code Generation
    Generate C and C++ code using MATLAB® Coder™.

    Version History

    Introduced in R2023a

    See Also

    | |