irsim.lib.path_planners.rrt_star#

RRT* (RRT-Star) path planner.

Collision precedence (inherited from RRT):

  1. Grid lookup (O(1) per cell) when env_map.grid is not None.

  2. Shapely geometry intersection when the grid is unavailable.

Reference:

S. Karaman and E. Frazzoli, “Sampling-based Algorithms for Optimal Motion Planning,” Int. J. Robotics Research, 2011.

Implementation reference:

ZJU-FAST-Lab/sampling-based-path-finding ZJU-FAST-Lab/sampling-based-path-finding (C++ implementation with kd-tree nearest-neighbour and range queries, optimised parent selection, and BFS cost propagation.)

Adapted for ir-sim.

Attributes#

logger

Classes#

RRTStar

RRT* path planner with asymptotic optimality.

Module Contents#

irsim.lib.path_planners.rrt_star.logger#
class irsim.lib.path_planners.rrt_star.RRTStar(env_map: irsim.world.map.EnvGridMap, robot: Any, expand_dis: float = 1.5, path_resolution: float = 0.25, goal_sample_rate: int = 5, max_iter: int = 500, connect_circle_dist: float = 0.5, search_until_max_iter: bool = False)[source]#

Bases: irsim.lib.path_planners.rrt.RRT

RRT* path planner with asymptotic optimality.

Extends RRT with:

  • Neighbour search — after steering, all nodes within a shrinking radius are considered as potential parents (_choose_parent).

  • Rewiring — after inserting a new node, nearby nodes are checked to see whether their cost can be reduced by re-parenting through the new node (_rewire).

  • Efficient cost propagation — _change_node_parent uses BFS through the children list for O(subtree) updates.

Initialise the RRT* planner.

Node#
connect_circle_dist = 0.5#
search_until_max_iter = False#
planning(start_pose: list[float], goal_pose: list[float], show_animation: bool = True) → numpy.ndarray | None[source]#

RRT* path planning.

Parameters:

  • start_pose – Start position [x, y].

  • goal_pose – Goal position [x, y].

  • show_animation – Render the tree during planning.

Returns:

(2, N) waypoint array or None.