plan

Find shortest path between two states in graph

Since R2023a

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.

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

Examples

Plan Shortest Path Between Two States in Graph Using A-Star Path Planner

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: [1x1 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)

Input Arguments

planner — A* path planner

plannerAStar object

A* path planner, specified as a plannerAStar object.

start — Start state of path

positive integer | string scalar | character vector | numeric vector

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 — Goal state of path

positive integer | string scalar | character vector | numeric vector

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

path — Shortest path between states

numeric matrix

Shortest path between states, returned as a numeric matrix.

Data Types: double

solutionInfo — Solution information

structure

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

Field	Description
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

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

Version History

Introduced in R2023a