Main Content

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.

PlannerType and ScopeCollision CheckingState Connection and PropagationBenefitsUsed For
Grid-Based A* — plannerAStarGridGlobal path plannerOccupancy 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* — plannerHybridAStarGlobal path plannerOccupancy 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) — plannerRRTGlobal path plannerGeneral state validator

Connection: General state space

Propagation: Not supported

  • Customizable

Manipulators, omnidrive robots, vehicles with a min turning radius
RRT* — plannerRRTStarGlobal path plannerGeneral state validator

Connection: General state space

Propagation: Not supported

  • Customizable

  • Asymptotically optimal

Manipulators, omnidrive robots, vehicles with a min turning radius
Frenet Trajectory — trajectoryOptimalFrenetLocal trajectory generatorGeneral state validator

Connection:Quintic polynomials or clothoids

Propagation: Not applicable

  • Customizable collision checking

  • Self-defined optimality

Ackermann type vehicles for highway driving

Related Topics