Create an optimal RRT path planner (RRT*)
plannerRRTStar object creates an asymptotically-optimal RRT
planner, RRT*. The RRT* algorithm converges to an optimal solution in terms of the state space
distance. Also, its runtime is a constant factor of the runtime of the RRT algorithm. RRT* is
used to solve geometric planning problems. A geometric planning problem requires that any two
random states drawn from the state space can be connected.
creates an RRT* planner from a state space object,
planner = plannerRRTStar(
stateSpace, and a
state validator object,
stateVal. The state space of
stateVal must be the same as
stateVal also sets the
StateValidator properties of
BallRadiusContant— Constant used to estimate the near neighbors search radius
100(default) | positive scalar
Constant used to estimate the near neighbors search radius, specified as a positive scalar. With a larger ball radius, the searching radius reduces slower as the number of nodes in the tree increases. The radius is estimated as following:
d — Dimension of the state space
n — Number of nodes in the search tree
η — The value of the
Vd — Volume of the unit ball in the dth dimension
ContitnueAfterGoalReached— Continue to optimize after goal is reached
Decide if the planner continues to optimize after the goal is reached, specified as
true. The planner also terminates
regardless of the value of this property if the maximum number of iterations or maximum
number of tree nodes is reached.
StateSpace— State space for the planner
MaxNumTreeNodes— Maximum number of nodes in the search tree
1e4(default) | positive integer
Maximum number of nodes in the search tree, specified as a positive integer.
MaxIterations— Maximum number of iterations
1e4(default) | positive integer
Maximum number of iterations, specified as a positive integer.
MaxConnectionDistance— Maximum length of motion
0.1(default) | positive scalar
Maximum length of a motion allowed in the tree, specified as a scalar.
GoalReachedFcn— Callback function to determine whether goal is reached
@nav.algs.checkIfGoalIsReached| function handle
Callback function to determine whether the goal is reached, specified as a function handle. You can create your own goal reached function. The function must follow this syntax:
function isReached = myGoalReachedFcn(planner,currentState,goalState)
planner — The created planner object, specified as
currentState — The current state, specified as a three
element real vector.
goalState — The goal state, specified as a three element
isReached — A boolean variable to indicate whether the
current state has reached the goal state, returned as
GoalBias— Probability of choosing goal state during state sampling
0.05(default) | real scalar in [0,1]
Probability of choosing the goal state during state sampling, specified as a real
scalar in [0,1]. The property defines the probability of choosing the actual goal state
during the process of randomly selecting states from the state space. You can start by
setting the probability to a small value such as
Create a state space.
ss = stateSpaceSE2;
occupancyMap-based state validator using the created state space.
sv = validatorOccupancyMap(ss);
Create an occupany map from an example map and and set map resolution as 10 cells/meter.
load exampleMaps.mat map = occupancyMap(simpleMap, 10); sv.Map = map;
Set validation distance for the validator.
sv.ValidationDistance = 0.01;
Update state space bounds to be the same as map limits.
ss.StateBounds = [map.XWorldLimits; map.YWorldLimits; [-pi pi]];
Create RRT* path planner and allow further optimization.
planner = plannerRRTStar(ss,sv); planner.ContinueAfterGoalReached = true;
Reduce max iterations and increase max connection distance.
planner.MaxIterations = 2500; planner.MaxConnectionDistance = 0.3;
Set the start and goal states.
start = [0.5, 0.5 0]; goal = [2.5, 0.2, 0];
Plan a path with default settings.
rng(100, 'twister') % repeatable result [pthObj, solnInfo] = plan(planner,start,goal);
Visualize the results.
map.show; hold on; plot(solnInfo.TreeData(:,1),solnInfo.TreeData(:,2), '.-'); % tree expansion plot(pthObj.States(:,1),pthObj.States(:,2),'r-','LineWidth',2); % draw path
 Karaman, S. and E. Frazzoli. "Sampling-Based Algorithms for Optimal Motion Planning." International Journal of Robotics Research . Vol. 30, Number 7, 2011, pp 846 – 894.