Main Content

plannerBiRRT

Create bidirectional RRT planner for geometric planning

    Description

    The plannerBiRRT object is a single-query planner that uses the bidirectional rapidly exploring random tree (RRT) algorithm with an optional connect heuristic for increased speed.

    The bidirectional RRT planner creates one tree with a root node at the specified start state and another tree with a root node at the specified goal state. To extend each tree, the planner generates a random state and, if valid, takes a step from the nearest node based on the MaxConnectionDistance property. The start and goal trees alternate this extension process until both trees are connected. If the EnableConnectHeuristic property is enabled, the extension process ignores the MaxConnectionDistance property. Invalid states or connections that collide with the environment are not added to the tree.

    Creation

    Description

    example

    planner = plannerBiRRT(stateSpace,stateVal) creates a bidirectional RRT planner from a state space object, stateSpace, and a state validator object, stateVal. The state space of stateVal must be the same as stateSpace. The stateSpace and stateVal arguments also set the StateSpace and StateValidator properties, respectively, of the planner.

    Properties

    expand all

    State space for the planner, specified as a state space object. You can use state space objects such as stateSpaceSE2, stateSpaceDubins, and stateSpaceReedsShepp. You can also customize a state space object using the nav.StateSpace class.

    State validator for the planner, specified as a state validator object. You can use state validator objects such as validatorOccupancyMap and validatorVehicleCostmap.

    Maximum length between planned configurations, specified as a positive scalar.

    If the EnableConnectHeuristic property is set to true, the object ignores this distance when connecting the two trees during the connect stage.

    Data Types: single | double

    Maximum number of iterations, specified as a positive integer.

    Data Types: single | double

    Maximum number of nodes in the search tree, specified as a positive integer.

    Data Types: single | double

    Directly join trees during the connect phase of the planner, specified as a logical 0 (false) or 1 (true).

    Setting this property to true causes the object to ignore the MaxConnectionDistance property when attempting to connect the two trees together.

    Data Types: logical

    Object Functions

    planPlan path between two states
    copyCreate deep copy of planner object

    Examples

    collapse all

    Use the plannerBiRRT object to plan a path between two states in an environment with obstacles. Visualize the planned path with interpolated states.

    Create a state space.

    ss = stateSpaceSE2;

    Create an occupancyMap-based state validator using the created state space.

    sv = validatorOccupancyMap(ss);

    Create an occupancy map from an example map and set map resolution as 10 cells per meter.

    load exampleMaps
    map = occupancyMap(ternaryMap,10);
    sv.Map = map;

    Set the validation distance for the validator.

    sv.ValidationDistance = 0.01;

    Update the state space bounds to be the same as the map limits.

    ss.StateBounds = [map.XWorldLimits; map.YWorldLimits; [-pi pi]];

    Create the path planner and increase the maximum connection distance.

    planner = plannerBiRRT(ss,sv);
    planner.MaxConnectionDistance = 0.3;

    Specify the start and goal states.

    start = [20 10 0];
    goal = [40 40 0];

    Plan a path. Due to the randomness of the RRT algorithm, set the rng seed for repeatability.

    rng(100,'twister')
    [pthObj,solnInfo] = plan(planner,start,goal);

    Display the number of iterations taken for the tree to converge.

    fprintf('Number of iterations: %d\n',solnInfo.NumIterations)
    Number of iterations: 346
    

    Visualize the results.

    show(map)
    hold on
    plot(solnInfo.StartTreeData(:,1),solnInfo.StartTreeData(:,2),'.-','color','b') % Start tree expansion
    plot(solnInfo.GoalTreeData(:,1),solnInfo.GoalTreeData(:,2),'.-','color','g') % Goal tree expansion
    plot(pthObj.States(:,1),pthObj.States(:,2),'r-','LineWidth',2) % draw path
    hold off

    Replan the path with the EnableConnectHeuristic property set to true.

    planner.EnableConnectHeuristic = true;
    [pthObj,solnInfo] = plan(planner,start,goal);

    Display the number of iterations taken for the tree to converge. Observe that the planner requires significantly fewer iterations compared to when the EnableConnectHeuristic property is set to false.

    fprintf('Number of iterations: %d\n',solnInfo.NumIterations)
    Number of iterations: 135
    

    Visualize the results.

    figure
    show(map)
    hold on
    plot(solnInfo.StartTreeData(:,1),solnInfo.StartTreeData(:,2),'.-','color','b') % Start tree expansion
    plot(solnInfo.GoalTreeData(:,1),solnInfo.GoalTreeData(:,2),'.-','color','g') % Goal tree expansion
    plot(pthObj.States(:,1),pthObj.States(:,2),'r-','LineWidth',2) % draw path

    References

    [1] Kuffner, J. J., and S. M. LaValle. “RRT-Connect: An Efficient Approach to Single-Query Path Planning.” In Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), 2:995–1001. San Francisco, CA, USA: IEEE, 2000. https://doi:10.1109/ROBOT.2000.844730.

    See Also

    Objects

    Functions

    Introduced in R2021a