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
Grid-Based A* — plannerAStarGrid	Global path planner	Occupancy map (validatorOccupancyMap)	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 min 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 min 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

Related Topics

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