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.
Examples and How To
Software Reference
Path Planning FAQs
Path planning enables an autonomous vehicle or robot to find the shortest and most feasible obstacle-free path from a start to a goal state, using a map of the environment represented as grid maps, state spaces, or topological roadmaps.
The main categories are grid-based search algorithms (like A*), sampling-based search algorithms (like RRT and RRT*), and trajectory optimization algorithms that formulate path planning as an optimization problem considering vehicle dynamics and constraints.
MATLAB supports sampling-based algorithms like RRT and RRT*, grid-based search algorithms like Hybrid A* and A*, and trajectory optimization methods through Navigation Toolbox and Model Predictive Control Toolbox.
Path metrics evaluate planned paths for characteristics such as smoothness, clearance, validity, and optimality, helping you compare different path planning algorithms.
You can generate waypoints from the planned path and use controllers such as a pure pursuit controller to compute control commands, or generate dynamically feasible trajectories using model predictive control.
Yes, MATLAB can generate local trajectories for dynamic replanning in scenarios like indoor environments and automated highway lane changes.
Path planning adds autonomy to systems such as self-driving cars, robot manipulators, autonomous agriculture vehicles, unmanned ground vehicles (UGVs), and unmanned aerial vehicles (UAVs).
Yes, you can deploy path planning algorithms as standalone ROS nodes or C/C++ code on embedded platforms using MATLAB Coder.
See also: MATLAB and Simulink for robotics, Navigation Toolbox, Robotics System Toolbox, UAV Toolbox, ROS Toolbox, Automated Driving Toolbox, Model Predictive Control Toolbox, MATLAB Coder, Stateflow, Reinforcement Learning Toolbox, Lidar Toolbox, robot programming, simultaneous localization and mapping, Sensor Fusion and Tracking Toolbox, drone programming
