Choose Path Planning Algorithms for Navigation

The Navigation Toolbox™ provides multiple path or motion planners to generate a sequence of valid configurations that move an object from a start to an end goal. The toolbox supports both global and local planners. Global planners typically require a map and define the overall state space. Local planners typically take a globally planned path and adjust the path based on obstacles in the environment. Planners check for collisions with the environment, connect and propagate states, and use cost functions for optimality. The table below details the key differences between the different planners and when to use a certain one.

Planner	Type and Scope	Collision Checking	State Connection and Propagation	Benefits	Used For
Graph-Based A* — plannerAStar	Type: Graph search Scope: Global path planner	During graph construction	Connection: Graph links Propagation: Not applicable	Customizable cost and heuristics Create custom graphs using navGraph Adaptable to any number of dimensions Route planner for HD maps	Manipulators and omnidrive robots, where distinct states can be formulated as a graph.
Grid-Based A* — plannerAStarGrid	Global path planner	Occupancy map (binaryOccupancyMap or occupancyMap)	Connection: XY linear motion primitives Propagation: Not supported	Customizable cost and heuristics Optimality if heuristics are consistent and admissible	Omnidrive robots
Hybrid A* — plannerHybridAStar	Global path planner	Occupancy map (validatorOccupancyMap or validatorVehicleCostmap)	Connection: Reeds-Shepp motion primitive Propagation: Circular arc motion primitive	Differential constraints for state propagation	Nonholonomic vehicles with a minimum turning radius
Rapidly-exploring Random Tree (RRT) — plannerRRT	Global path planner	General state validator	Connection: General state space Propagation: Not supported	Customizable	Manipulators, omnidrive robots, vehicles with a minimum turning radius
RRT* — plannerRRTStar	Global path planner	General state validator	Connection: General state space Propagation: Not supported	Customizable Asymptotically optimal	Manipulators, omnidrive robots, vehicles with a minimum turning radius
Bidirectional RRT — plannerBiRRT	Global path planner	General state validator	Connection: General state space Propagation: Not supported	Customizable	Manipulators, omnidrive robots, vehicles with a minimum turning radius
Control-Based RRT — plannerControlRRT	Type: Control based planner Scope: Global path planner	Occupancy map (binaryOccupancyMap, occupancyMap, or vehicleCostmap (Automated Driving Toolbox))	Connection: General State Space Propagation: General State Propagator	Returns a sequence of states, controls, and references that comprise a kinematically or dynamically feasible path Useful in complex maneuvers for complex vehicles, such as reversing into a narrow space for a truck-trailer	Manipulators, omnidrive robots, vehicles with a minimum turning radius
Frenet Trajectory — trajectoryOptimalFrenet	Local trajectory generator	General state validator	Connection: Quintic polynomials or clothoids Propagation: Not applicable	Customizable collision checking Self-defined optimality	Ackermann type vehicles for highway driving
Frenet Trajectory — trajectoryGeneratorFrenet	Local trajectory generator	General state validator	Connection: Quintic polynomials or clothoids Propagation: Not applicable	Customizable collision checking Custom defined optimality	Ackermann type vehicles for highway driving

Related Topics

• Plan Mobile Robot Paths Using RRT
• Dynamic Replanning on an Indoor Map
• Highway Lane Change
• Highway Trajectory Planning Using Frenet Reference Path