What Is Path Planning?

Path planning lets an autonomous vehicle or a robot find the shortest and most obstacle-free path from a start to goal state. The path can be a set of states (position and/or orientation) or waypoints. Path planning requires a map of the environment along with start and goal states as input. The map can be represented in different ways such as grid maps, state spaces, and topological roadmaps. Maps can be multilayered for adding bias to the path.

A few popular categories of path planning algorithms for autonomous vehicles include:

• Grid-based search algorithms, which find a path based on minimum travel cost in a grid map. They can be used for applications such as mobile robots in a 2D environment. However, the memory requirements to implement grid-based algorithms could increase with the number of dimensions, such as for a 6-DOF robot manipulator.
• Sampling-based search algorithms, which create a searchable tree by randomly sampling new nodes or robot configurations in a state space. Sampling-based algorithms can be suitable for high-dimensional search spaces such as those used to find a valid set of configurations for a robot arm to pick up an object. Generating dynamically feasible paths for various practical applications make sampling-based planning popular, even though it does not provide a complete solution.
• Trajectory optimization algorithms, which formulate the path planning problem as an optimization problem that considers the desired vehicle performance, relevant constraints, and vehicle dynamics. Along with generating dynamically feasible trajectories, they can also be applied for online path planning in uncertain environments. However, depending on the complexity of the optimization problem, real-time planning can be prohibitive.

Path planning, along with perception (or vision) and control systems, comprise the three main building blocks of autonomous navigation for any robot or vehicle. Path planning adds autonomy in systems such as self-driving cars, robot manipulators, unmanned ground vehicles (UGVs), and unmanned aerial vehicles (UAVs).

MATLAB^®, Simulink^®, Navigation Toolbox™, and Model Predictive Control Toolbox™ provide tools for path planning, enabling you to:

• Implement sampling-based path planning algorithms such as RRT and RRT* using a customizable planning infrastructure.
• Plan paths in occupancy grid maps, such as automated parking, using Hybrid A*.
• Generate local trajectories for indoor dynamic replanning and automated highway lane change.
• Compare path validity and optimality using path metrics such as smoothness and clearance.
• Generate waypoints and send control commands to follow them using pure pursuit controller.
• Generate and follow dynamically feasible trajectories for online path planning with linear and nonlinear model predictive control.
• Plan collision-free trajectories in Simulink with the Vehicle Path Planner System block.
• Deploy the path planning algorithm as a standalone ROS node or C/C++ code on an embedded platform.