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 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.
Path planning techniques include two major types of algorithms used for autonomous vehicles.
Grid-based search algorithms 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 requirement to implement grid-based algorithms increases with the number of dimensions, such as for a 6 DOF robot manipulator.
Sampling-based search algorithms create a searchable tree by randomly sampling new nodes or robot configurations in a state space. Sampling-based algorithms are suitable for both low and high dimensional search spaces.
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, UGVs, and UAVs.
MATLAB®, Simulink®, and Navigation 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
- Deploy the path planning algorithm as a standalone ROS node or C/C++ code on an embedded platform