General introduction to recent advancements in path and trajectory planning for robots and autonomous machines

Abstract

This article examines robot motion planning, comprising path and trajectory planning, which represents one of the most challenging aspects of robot software architecture. These functionalities enable robots to determine optimal movement paths according to specified criteria while avoiding obstacles. This introductory survey presents a comprehensive general review of path and trajectory planning approaches and a state-of-the-art analysis of recent developments in this area, with particular emphasis on the optimality of planned paths and trajectories. The article provides a general literature review that categorizes motion planning algorithms into four primary families: random sampling-based methods (such as rapidly exploring random trees), optimal control methods (such as model predictive control), artificial potential field methods, and graph search methods (such as Dijkstra and A*). Additional approaches, including simulated annealing, genetic algorithms, and particle swarm optimization, are also addressed. Finally, features of the reviewed algorithms are discussed, and a comparative analysis of selected features for specific algorithms is presented in the conclusion.

Introduction

Robotics and automation in industry have become increasingly significant, particularly in the context of persistent workforce shortages. According to the United States National Association of Manufacturers, 71% of manufacturers reported that attracting and retaining employees was their most significant challenge in 2023. ¹ This situation necessitates increasingly automated manufacturing facilities. Robots address this requirement by providing a workforce that does not require rest or additional training, excels in high-precision and repetitive tasks, and is generally more economical compared to human labor. As reported in Adaptive Innovations Corp., ² robots typically achieve cost parity with human laborers within six months to five years, depending on geographic location, investment scale, and other factors. Countries with higher labor costs, such as the United States, tend to approach the lower end of this range.

Robotics technology is used in almost every type of industry including manufacturing,^3,4 logistics,^5,6 surgery,^7–9 space missions,^10,11 and autonomous vehicles (e.g. Unmanned Ground Vehicle (UGV), ¹² Unmanned Underwater Vehicle (UUV), ¹³ and Unmanned Aerial Vehicle (UAV)^14,15). Robots are complex systems with many challenges, such as mechanical design, power electronics design, and Software (SW). A block diagram of the principal SW functionalities is presented in Figure 1. The primary focus of this review is robot motion planning, which encompasses both path and trajectory planning. These two capabilities enable robot movement by determining not only the goal state but also the specific manner in which the robot should navigate toward the goal while avoiding obstacles and satisfying other constraints. These concepts are formally defined in Section “Problem definition.”

Figure 1.

Common robot Software (SW) stack composes of multiple functionalities.

Trajectory and path planning

Trajectory and path planning constitute some of the most complex and computationally demanding tasks within the robot SW stack. These functionalities are also among the most critical, as they directly influence the robot’s ability to perform its tasks effectively and safely. Consequently, this topic has garnered substantial interest from both researchers and practitioners in the field of robotics.

This article provides a comprehensive introduction and general review of the state-of-the-art in path and trajectory planning. Existing reviews in the literature are either outdated, given the rapid evolution of the field, such as the sampling-based planners review by Elbanhawi and Simic, ¹⁶ or focused on specific algorithm categories, such as sampling-based methods^17,18 or Artificial Intelligence (AI) methods. ¹⁹ To the best of the authors’ knowledge, no comprehensive and current general review of path and trajectory planning exists in the literature.

Motion planning space

Generally, the methods used in motion planning are not restricted to a specific configuration space (state space). Moreover, most planning approaches specific to other application fields, for example, autonomous vehicles, can often be generalized to robot motion planning and vice versa.

Motion planning methods

An overview of the principal algorithms employed in motion planning is presented in Figure 2. This figure illustrates the relationships and categorizations among the main algorithm families, organizing them according to their primary characteristics, such as feasible planning methods versus locally and globally optimal methods. All methods and their characteristics are discussed in detail in subsequent sections, with particular emphasis on the following main algorithm branches, which are most prevalent in the literature:

Random sampling-based methods includingRapidly exploring Random Trees (RRT) ²⁰ or Probabilistic Roadmap (PRM). ²¹

Optimal control methods originating in optimal control field includingModel Predictive Control (MPC).^22,23

Artificial Potential Field (APF) methods, ²⁴ which transform the obstacles to a repulsive and goal to attractive potential.

Graph search methods including Dijkstra graph search algorithm ²⁵ or A*. ²⁶

Figure 2.

Overview of the most frequently used motion planning algorithms. The figure categorizes the algorithms based on their primary characteristics, such as feasible planning methods or locally and globally optimal methods. It shows the main algorithm families, which are later detailed in this article. All the technical terms are defined in Section “Problem definition.”

All terminologies used in the figure are defined in Section “Problem definition.” The figure also includes additional methods, such as Simulated Annealing (SA), ²⁷ Genetic Algorithm (GA), ²⁸ and Particle Swarm Optimization (PSO), ²⁹ which are discussed in greater detail in Section “Other methods.” This review primarily focuses on works within these four main branches and concentrates on recent developments for the sake of brevity and relevance.

An alternative categorization of planning tasks is based on their complexity and dimensionality. Local planning tasks are typically applied to confined spaces and less complex environments, whereas global planning tasks may involve highly complex constraints, nonconvexity in the problem formulation, and additional considerations. To manage computational costs, global plans typically address path planning exclusively, which can subsequently be translated to local spaces, thereby enabling trajectory planning to proceed in a less complex environment with reduced computational burden.

Article outline

This review presents a comprehensive summary of state-of-the-art developments in path and trajectory planning. The remainder of this article is organized as follows. Section “Problem definition” provides formal problem definitions. Subsequently, the main algorithm families are described in detail:

Random sampling-based methods in Section “Sampling-based methods.”

Optimal control methods in Section “Optimal control-based methods.”

APF methods in Section “Artificial potential field methods.”

Graph search methods in Section “Graph methods.”

Other methods in Section “Other methods.”

A comparative analysis of algorithm features is presented in Section “Discussion and results.” Section “Conclusion” provides concluding remarks. Finally, a glossary of acronyms employed throughout this article is provided in Section “Acronyms.”

Problem definition

The space within which motion planning tasks are formulated is inherently continuous; that is, the state space (or configuration space) is not discrete. Examples of state space variables include position coordinates in the $x$ and $y$ directions, heading angle of an Autonomous Mobile Robot (AMR), and similar quantities. Due to the computational complexity associated with continuous state space motion planning, the space is typically discretized using method-specific approaches to reduce computational costs. Additionally, the motion planning problem is commonly decomposed into path planning and trajectory planning subproblems. Furthermore, motion planning can be categorized into two principal problem types: the feasible path/trajectory planning problem and the optimal path/trajectory planning problem.

Path planning problem

This review adheres to the definition provided in Karaman and Frazzoli. ³⁰

Definition 1 (Path, path planning problem ³⁰ )

Let $\mathcal{X}=(0,1{)}^s$ be the configuration space (or state space), where $s\in \mathbb{N}$ is the dimension of the configuration space. Let ${\mathcal{X}}_{\text{obs}}$ represent the obstacle region, such that $\mathcal{X}\mathrm{\setminus }{\mathcal{X}}_{\text{obs}}$ is an open set. Denote the obstacle-free space as ${\mathcal{X}}_{\text{free}}=\text{cl}(\mathcal{X}\mathrm{\setminus }{\mathcal{X}}_{\text{obs}})$ , where $\text{cl}(\cdot )$ denotes the closure of a set. The initial condition $x_{\text{init}}$ is an element of ${\mathcal{X}}_{\text{free}}$ , and the goal region ${\mathcal{X}}_{\text{goal}}$ is an open subset of ${\mathcal{X}}_{\text{free}}$ .

A path planning problem is defined by a triplet $({\mathcal{X}}_{\text{free}},x_{\text{init}},{\mathcal{X}}_{\text{goal}})$ .

Let $\sigma :[0,1]\to {\mathbb{R}}^s;$ the total variation of $\sigma$ is defined as

$$TV(\sigma )=\underset{\{n\in \mathbb{N},0={\tau }_0<{\tau }_1<\cdots <{\tau }_n=1\}}{sup}\sum _{i=1}^n|\sigma ({\tau }_i)-\sigma ({\tau }_{i-1})|.$$

(1)

A function $\sigma$ with $TV(\sigma )<\mathrm{\infty }$ is said to have bounded variation.

A function $\sigma :[0,1]\to {\mathbb{R}}^s$ of bounded variation is called a

Path, if it is continuous.

Collision-free path, if it is a path, and $\sigma (\tau )\in {\mathcal{X}}_{\text{free}}$ , for all $\tau \in [0,1]$ .

Feasible path, if it is a collision-free path, $\sigma (0)=x_{\text{init}}$ , and $\sigma (1)\in \text{cl}({\mathcal{X}}_{\text{goal}})$ .

Feasible path planning problem

The feasible path planning problem is the oldest of the studied motion planning problems. It focuses on finding a sequence of states from the start state to the goal state (or goal region) while avoiding collisions with obstacles.

Problem 1 (Feasible path planning ³⁰ )

Given a path planning problem $({\mathcal{X}}_{\text{free}},x_{\text{init}},{\mathcal{X}}_{\text{goal}})$ , find a feasible path $\sigma :[0,1]\to {\mathcal{X}}_{\text{free}}$ such that $\sigma (0)=x_{\text{init}}$ and $\sigma (1)\in cl({\mathcal{X}}_{\text{goal}})$ , if one exists. If no such path exists, report failure.

Optimal path planning problem

The optimal path planning problem extends the feasible path planning problem by adding optimality, that is, it minimizes a given criterion defined by the cost function. Formally, it is defined as follows. ³⁰

Let $\mathrm{\Sigma }$ denote the set of all paths, and ${\mathrm{\Sigma }}_{\text{free}}$ the set of all collision-free paths. Given two paths ${\sigma }_1,{\sigma }_2\in \mathrm{\Sigma }$ , such that ${\sigma }_1(1)={\sigma }_2(0)$ , let ${\sigma }_1|{\sigma }_2\in \mathrm{\Sigma }$ denote their concatenation, that is, $({\sigma }_1|{\sigma }_2)(\tau ):={\sigma }_1(2\tau )$ for all $\tau \in [0,1/2]$ and $({\sigma }_1|{\sigma }_2)(\tau ):={\sigma }_2(2\tau -1)$ for all $\tau \in (1/2,1]$ . Both $\mathrm{\Sigma }$ and ${\mathrm{\Sigma }}_{\text{free}}$ are closed under concatenation. Let $c:\mathrm{\Sigma }\to {\mathbb{R}}_{\ge 0}$ be a function, called the cost function, which assigns a strictly positive cost to all nontrivial collision-free paths, that is, $c(\sigma )=0$ iff $\sigma (\tau )=\sigma (0),\mathrm{\forall }\tau \in [0,1]$ . The cost function is assumed to be monotonic, in the sense that $\mathrm{\forall }{\sigma }_1,{\sigma }_2\in \mathrm{\Sigma },c({\sigma }_1)\le c({\sigma }_1|{\sigma }_2)$ , and bounded, in the sense that $\mathrm{\exists }{k}_c;c(\sigma )\le k_{c}TV(\sigma ),\mathrm{\forall }\sigma \in \mathrm{\Sigma }$ .

Problem 2 (Optimal path planning ³⁰ )

Given a path planning problem $({\mathcal{X}}_{\text{free}},x_{\text{init}},{\mathcal{X}}_{\text{goal}})$ and a cost function $c:\mathrm{\Sigma }\to {\mathbb{R}}_{\ge 0}$ , find a feasible path $\sigma *$ such that $c(\sigma *)=minc(\sigma ):\sigma$ is a feasible path. If no such path exists, report failure.

Trajectory planning problem

A trajectory defines the time parameterization for a given path. ³¹ Let $\mathcal{U}=(0,1{)}^m$ be the input space, where $m\in \mathbb{N}$ is the dimension of the input space.

Definition 2 (Trajectory ³² )

Let $\pi (\tau )$ be a tuple $\pi (\tau )=(\sigma (\tau ),t(\tau )),\tau \in [0,1]$ , where $t$ is time, and $\sigma \in \mathrm{\Sigma }$ is path. The trajectory is defined by $\pi (\tau )$ , and it is constrained subject to state space dynamics, which is, for the purpose of this article, defined as

$$\dot{x}=f(x,u),$$

(2)

where $x\in \mathcal{X}$ and $u\in \mathcal{U}$ . A function $\pi (\tau ):[0,1]\to ({\mathbb{R}}^s,\mathbb{R})$ of bounded variation is called a

Trajectory, if $\sigma (\tau )$ is a path and $t(\tau )$ is continuous and monotonically increasing.

Collision-free trajectory, if it is a trajectory, and $\sigma (\tau )\in {\mathcal{X}}_{\text{free}}$ , for all $\tau \in [0,1]$ .

Feasible trajectory, if it is a collision-free trajectory, $\sigma (0)=x_{\text{init}}$ , and $\sigma (1)\in \text{cl}({\mathcal{X}}_{\text{goal}})$ .

Let $\mathrm{\Pi }$ be the set of all trajectories and ${\mathrm{\Pi }}_{\text{free}}$ the set of collision-free trajectories defined as:

$$\pi (\tau )=(\sigma (\tau ),t(\tau ))\in {\mathrm{\Pi }}_{\text{free}},$$

(3)

iff $\sigma (\tau )$ is a collision-free path. Trajectory planning problem (see Problem 3) is defined analogously to the path planning problem (see Problem 1). The same holds for the feasible trajectory planning problem (see Problem 4) and optimal trajectory planning problem (see Problem 5).

Problem 3 (Trajectory planning problem)

A trajectory planning problem is given by the state space dynamics $\dot{x}=f(x,u)$ and a quadruplet $({\mathcal{X}}_{\text{free}},x_{\text{init}},t_{\text{init}},{\mathcal{X}}_{\text{goal}})$ , where $t_{\text{init}}$ is initial time.

Problem 4 (Feasible trajectory planning problem)

Given a trajectory planning problem, find a feasible trajectory $\pi :[0,1]\in {\mathrm{\Pi }}_{\text{free}}$ such that $\pi (\sigma (0),t(0))=(x_{\text{init}},t_{\text{init}})$ and $\sigma (1)\in cl({\mathcal{X}}_{\text{goal}})$ , if one exists. If no such trajectory exists, report failure.

Problem 5 (Optimal trajectory planning problem)

Given a trajectory planning problem and a cost function $d:\mathrm{\Pi }\to {\mathbb{R}}_{\ge 0}$ , find a feasible trajectory $\pi *$ such that $d(\pi *)=\underset{\pi }{min}d(\pi ):\pi$ is a feasible trajectory. If no such trajectory exists, report failure.

The optimal path/trajectory planning problem can be further extended to the globally optimal planning problem and the locally optimal planning problem. The definition of the optimal path and optimal trajectory planning problem from the perspective of global and local optimality is defined the same for both. The definition for the globally optimal planning problem is given as follows:

Definition 3 (Globally optimal trajectory planning problem)

The globally optimal trajectory planning problem is the optimal trajectory planning problem where the cost function $d$ is defined over the set of all trajectories, that is, $d:\mathrm{\Pi }\to {\mathbb{R}}_{\ge 0}$ , and the solution is the optimal solution within the set of all trajectories.

Then, the locally optimal trajectory planning problem is defined as follows:

Definition 4 (Locally optimal trajectory planning problem)

The locally optimal trajectory planning problem is the optimal trajectory planning problem where the cost function $d$ is defined over a subset of the configuration space $\phi \subseteq \mathrm{\Pi }$ , that is, $d:\phi \to {\mathbb{R}}_{\ge 0}$ , and the solution is the optimal solution $\phi *$ within that subset.

The locally and globally optimal path planning problems are defined analogously to the trajectory planning problem, with the cost function $c$ defined over the set of paths $\mathrm{\Sigma }$ instead of the cost function $d$ defined over the set of trajectories $\mathrm{\Pi }$ .

Sampling-based methods

Sampling-based methods are among the most widely employed and extensively studied algorithms for path planning. Typically, this family of methods is not applied to trajectory planning due to computational constraints; however, certain variations, including kinodynamic planners, are utilized in specialized applications. A recent comprehensive study of sampling-based path planning methods is presented in Zhang et al. ¹⁷ Readers interested in topics beyond the scope of this article are encouraged to consult that work for additional information. Sampling-based methods are probabilistic approaches that transform the continuous space problem into a discrete formulation by stochastically sampling the state space, which is subsequently represented as a graph. Typically, a specialized graph structure known as a tree ³³ is constructed.

Sampling-based algorithms find application across diverse domains. For instance, Albee et al. ¹¹ propose employing both global and local planners based on RRT for legged robotic planetary exploration.

In principle, all algorithms in this family can be applied to both trajectory and path planning. However, from a practical standpoint, many are suitable only for kinematic constraints. Incorporating dynamic constraints typically increases the computational runtime of these algorithms substantially.

Algorithm feasibility and optimality

Sampling-based algorithms are predominantly employed to solve feasible path planning problems, with prominent examples including RRT ²⁰ and its derivatives,^14,34–39 as well as PRM ²¹ and its derivatives.^40–45 These algorithms are generally probabilistically complete, as formally defined in Definition 5.

Definition 5 (Probabilistic completeness ¹⁷ )

An algorithm is said to be probabilistically complete if the probability of finding a feasible path/trajectory, assuming it exists, converges to 1 as the number of samples $n$ goes to infinity, expressed as

$$\underset{n\to \mathrm{\infty }}{lim}infp({\mathrm{\Sigma }}_{\text{feas}}^n\ne \mathrm{\varnothing })=1,$$

(4)

where $p$ denotes the probability, and ${\mathrm{\Sigma }}_{\text{feas}}^n$ is set of all feasible trajectories found using $n$ samples.

Additionally, algorithms with proven asymptotic optimality exist, primarily based on Rapidly exploring Random Trees* (RRT*) ³⁰ or Probabilistic Roadmap* (PRM*). ³⁰ Other significant asymptotically optimal planning algorithms, predominantly derived from RRT* or PRM*, include.^13,46–59 Asymptotic optimality is formally defined in Definition 6.

Definition 6 (Asymptotic optimality—path planning ¹⁷ )

An algorithm is said to be asymptotically optimal if, for any positive number $ϵ$ , the following holds:

$$\underset{n\to \mathrm{\infty }}{lim}p(\underset{\sigma \in {\mathrm{\Sigma }}_{\text{feas}}^n}{min}c(\sigma )-c*<ϵ)=1,$$

(5)

where $p$ denotes the probability, ${\mathrm{\Sigma }}_{\text{feas}}^n$ is set of all feasible trajectories found using $n$ samples, and $c$ is the cost function as defined in Section “Optimal path planning problem.”

An analogous definition can be formulated for asymptotically optimal trajectories.

Graph type

Sampling-based methods can be classified according to the type of graph structure they construct. One approach involves generating a generic graph prior to issuing motion commands to the robot. Subsequently, when the robot receives a motion command, only graph search is executed at runtime, given the start position $x_{\text{init}}$ and goal region ${\mathcal{X}}_{\text{goal}}$ . Methods following this paradigm are represented by probabilistic roadmaps.^{13,30,40–45,59} The alternative approach generates tree-structured graphs, with methods primarily based on RRT. ²⁰ Recent works^{14,34–38,54–58} in this category.

Anytime planning

Algorithms are classified as anytime planners if they can produce suboptimal solutions before completing their execution. This initial suboptimal plan is subsequently refined until a termination condition is satisfied, such as a non-decreasing cost function or reaching a time threshold. This characteristic can provide significant advantages over non-anytime planners, which require the full planning duration to produce the optimal plan. Most sampling-based planning algorithms exhibit the anytime property. However, there exists a family of batch sampling algorithms originating from Fast Marching Trees* (FMT*) ⁴⁶ that does not possess this property. Subsequent research has partially addressed this limitation by combining FMT* with informed RRT*,^48,51 resulting in Batch Informed Trees* (BIT*).^49,52

RRT and its derivatives

For completeness, the principal steps of the RRT algorithm are presented in Algorithm 1. The RRT algorithm operates iteratively. In each iteration, a random sample $x_{\text{rand}}$ is drawn from the continuous state space using the sample() function. The nearest node $x_{\text{nearest}}$ in the tree $\mathcal{T}$ is then identified using the nearest() function. Subsequently, the algorithm attempts to connect $x_{\text{rand}}$ to $x_{\text{nearest}}$ using the steer() function. In certain cases, $x_{\text{rand}}$ cannot be reached due to various limitations, such as excessive distance or dynamic constraints. In such instances, the steer() function selects the closest achievable node $x_{\text{new}}$ to $x_{\text{rand}}$ . If the resulting path is collision-free, as verified by collisionFree() , the algorithm extends the tree $\mathcal{T}$ with the $x_{\text{new}}$ node via the extend() function. The RRT derivatives build upon this basic algorithm (presented in Algorithm ??) by modifying specific functions such as steer() or sample() , or by incorporating additional enhancements.

Algorithm 1.

Rapidly exploring random tree (RRT)²⁰

Input:	Initial state $x_{init}$ , goal region ${\chi }_{\mathrm{goal}}$
Output:	Tree $\mathcal{T}$ with feasible path
1:	V ← $x_{\mathrm{init}}$ , E ← ∅;, $\mathcal{T}$ = (V, E)
2:	for i ← 1 to N do
3:	$x_{\mathrm{rand}}$ ← sample(i)
4:	$x_{\mathrm{nearest}}$ nearest( $\mathcal{T}$ , $x_{\mathrm{rand}}$ )
5:	xnew ← steer( $x_{\mathrm{nearest}}$ , $x_{\mathrm{rand}}$ )
6:	if collisionFree( ${\mathrm{x}}_{\mathrm{nearest}},{\mathrm{x}}_{\mathrm{new}}$ ) then
7:	$\mathcal{T}$ ← extend( $\mathcal{T}$ , $x_{new}$ )
8:	if $x_{\mathrm{new}}$ ∈ $X_{\mathrm{goal}}$ then return $\mathcal{T}$
9:	end if
10:	end if
11:	end for

The asymptotically globally optimal variant RRT* ³⁰ identifies the nearest node based on the cost function $c$ rather than Euclidean distance. Additionally, it introduces a rewire() function immediately following the extend() call (line 7 in Algorithm ??). The purpose of this function is to determine whether rewiring the current tree $\mathcal{T}$ would enable individual nodes to be reached with lower cost by traversing through $x_{\text{new}}$ . Derivatives of RRT/RRT* that modify individual functions are discussed in the following sections, organized according to the functions they modify.

Additional research has addressed when and how planning should be initiated and restarted. For example, Naderi et al. ⁵⁰ propose Real Time Rapidly exploring Random Trees* (RT-RRT*), wherein the planned tree is preserved with only the root being repositioned. The tree is then reconstructed during the replanning phase.

Function sample()

Numerous techniques have been developed to accelerate algorithm performance. Most approaches concentrate on biased sampling strategies, such as goal-biased sampling, wherein the portion of state space oriented toward the goal state is more likely to be sampled as $x_{\text{rand}}$ . Selected works employing this approach.^{14,35,36,38,47,54,58} Additional approaches based on heuristics have also been proposed. Typically, problem-specific heuristics yield the best performance; however, such heuristics are frequently unavailable. Consequently, generic heuristic approaches such as informed RRT* ⁴⁸ and their derivatives have been developed.^{37,52,53,56,57} This approach minimizes exploration of state space regions that are unlikely to contain optimal path/trajectory between the start and goal configurations.

An alternative approach is presented in Qureshi et al., ⁶⁰ which proposes MPNet, a Neural Network (NN) system comprising two networks: an encoder and a planner. The encoder processes sensor data into a network state, and the planner subsequently proposes the next sample. This approach biases sampling toward the goal and potential optimal paths, thereby reducing computation time.

Function nearest()

In RRT*, the nearest() function is modified to search for multiple nodes using near() . Enhancements to these functions are proposed in Izaty and Rusmin, ⁵⁵ which selects neighboring nodes based on a grid structure, thereby promoting more uniform sampling throughout the state space. Tahirovic and Ferizbegovic ³⁹ introduce Rapidly exploring Random Vines (RRV), which selects new nodes based on whether $x_{\text{rand}}$ lies within an obstacle region. If the sample is located within an obstacle, the algorithm relocates the sample to the nearest obstacle-free point. This approach effectively reduces computation time by deferring the obstacle avoidance verification to a subsequent stage. The method is particularly advantageous for exploring narrow passages, as such regions become more likely to be sampled.

Function steer()

For many complex systems, the steer() function is the most computationally intensive component. Systems with dynamic constraints particularly pose challenges, as they naturally give rise to a two-point boundary value problem whose solution is computationally demanding. Consequently, numerous approaches introduce motion primitives^61,62 and modify the tree expansion procedure. Rather than attempting to steer directly to the randomly sampled node, a motion primitive is appended to $x_{\text{nearest}}$ , thereby obtaining $x_{\text{new}}$ . An alternative approach incorporates an Image Based Visual Servoing (IBVS) controller into the steer() function. ³⁴ Yavari et al. ⁶³ propose a lazy steering mechanism that defers the steering function evaluation to a later stage, enabling many node connection evaluations to be bypassed. Further details on lazy steering are provided in Section “Function collisionFree().”

Function extend()

Lindqvist et al. ¹⁵ introduce multiple branches of the extension process that are explored concurrently in separate algorithm threads.

Function collisionFree()

The collisionFree() evaluation is typically computationally demanding. To address this, evaluation may be deferred to a later stage through an approach known as lazy steering. The fundamental concept involves executing RRT* or any other applicable algorithm without performing collision detection. Collision detection is subsequently evaluated only for nodes that could potentially lie on the optimal path. This approach substantially reduces the number of collisionFree() function evaluations. Lazy connection approaches are documented in the literature.^37,53,56,63 An illustration of selected approaches is presented in Figure 3.

Figure 3.

Overview of the recent sampling-based algorithms and how they solve the planning problem. AIT* and EIT* algorithms are employing the idea of lazy steering to reduce the calculation time. For more details, please refer to the paper from which this figure was adopted from Strub and Gammell. ⁵⁶ Note. AIT* = adaptive informed trees*; EIT* = effort informed trees*.

Dynamic constraints

For systems with dynamic constraints, a family of algorithms known as kinodynamic planners is employed for motion planning. Several approaches have been developed to address this challenge. One approach involves sparse sampling, with the foundational algorithm being Sparse Sampling Trees (SST). ⁶⁴ Sparse sampling reduces the number of steer() function evaluations.^64,65 Wang and Sanfelice ⁶⁶ propose Hybrid Sparse Sampling Trees (HySST), which adapts SST for hybrid systems. Another approach to circumvent the evaluation of dynamic constraints involves using motion primitives, as described in the literature.^61,62

Additional approaches are presented in Zhao et al., ⁶⁷ which introduces dynamic RRT, and in the literature,^68,69 which present KinoDynamic motion planning via Funnel control (KDF). These works employ various strategies to reduce computation time for systems with dynamic constraints. Wang and Sanfelice ⁷⁰ propose an RRT-connect algorithm featuring simultaneous bidirectional search from both start and goal positions for systems with hybrid dynamics. However, many of these algorithms address feasible path planning rather than optimal path planning.

PRM and its derivatives

Ojha and Thakur ⁴¹ propose utilizing PRM with A* in the query phase for mobile robots operating in the presence of dynamic obstacles that were not identified during graph construction. In Fuad and Wahyuni, ⁴² a smoothing approach is presented wherein a virtual non-holonomic robot navigates through a path planned using PRM to generate a smoother trajectory. Another application of PRM with A* in the query phase is presented in Imran Chowdhury and Schwartz ¹³ for UUV. Mbemba et al. ⁴³ employ the Ant Colony Optimization (ACO) algorithm for the query phase. Several fusion algorithms have been proposed, primarily for path smoothing. For example, the works^40,44,45 integrate PRM with APF. Hartmann et al. ⁵⁹ propose an approach similar to Effort Informed Trees* (EIT*) for PRM, termed Effort Informed Roadmaps* (EIRM*).

Minimum Violation Planning (MVP) framework

The MVP framework ⁷¹ addresses environments with complex constraints that require prioritization. Furthermore, MVP can accommodate cases where constraints are contradictory. Although originally developed for autonomous vehicle applications, this framework applies to general motion planning problems. Extensions of the original algorithm are documented in the literature.^61,72,73 The principal benefit of this framework lies in its systematic approach to prioritizing and handling complex rule-based constraints, analogous to the lazy steering approach discussed in Section “RRT and its derivatives.” MVP also accommodates dynamic constraints and is therefore suitable for trajectory planning. As a framework, MVP formulates an optimal sampling-based planning problem. Consequently, any of the aforementioned RRT*, PRM*, or their derivatives may be employed to solve this problem.

An alternative to MVP is proposed in Vasile et al., ⁷⁴ wherein the authors also employ logical statements; however, in contrast to MVP, these statements are used to define the goal rather than the constraints. The authors propose an RRT-based algorithm for local planning and an Random Regular Graph (RRG)-based algorithm for global planning (refer to Diestel ³³ for details).

Sampling-based methods evaluation

Sampling-based methods are extensively employed for path planning in complex environments. They are particularly effective in high-dimensional spaces and can address non-convex problems. However, they can be computationally expensive, especially for systems with dynamic constraints. Furthermore, they do not always guarantee any optimality, although certain variants such as RRT* and PRM* provide asymptotic optimality guarantees. Path smoothness can also present challenges, particularly for algorithms that do not consider this criterion during the planning phase. Nevertheless, various approaches exist to address this limitation, including the use of motion primitives or the integration of sampling-based methods with complementary approaches such as APF.

Artificial potential field methods

The APF approach, grounded in electromagnetic principles from physics, has been extensively studied for path planning since its introduction in the 1980s. ²⁴ The fundamental concept involves representing the environment as a field of forces. Obstacles generate repulsive forces, while the goal generates attractive forces. Navigation is then achieved by following the direction of these forces, typically employing methods such as gradient descent. A representative artificial potential field is illustrated in Figure 4. A recent survey on these methods is available in Chen et al. ⁷⁵

Figure 4.

The Artificial Potential Field (APF) method turns an environment into a force field, with obstacles pushing away and the goal pulling towards. The figure is adopted from Zhai et al. ⁴⁵

APF is recognized for its computational efficiency and its ability to generate smooth, high-quality paths, in contrast to certain alternative methods that require additional post-processing steps for path smoothing (such as Section “Sampling-based methods” or Section “Graph methods”). However, the approach exhibits several notable limitations:

Goal unreachability: The goal may be in an unfavorable position, especially near obstacles, preventing the algorithm from reaching it using the gradient descent method. ⁴⁵

Local minimum: By following the gradient, the algorithm may become trapped in a local minimum rather than finding the globally optimal path. ⁴⁵

Zigzagging: In certain situations, particularly when the potential field gradient is flat, the resulting path may exhibit oscillatory behavior, as shown in Figure 5. ⁴⁵

Figure 5.

The Artificial Potential Field (APF) can have oscillatory movement in areas where the potential field is level. The figure is adopted from Zhai et al. ⁴⁵

Recent research has primarily focused on addressing these limitations, resulting in novel enhancements to APF, which are discussed in the following sections.

Fusion methods

Researchers have explored combining APF with other algorithms to achieve improved performance. For instance, Zhai et al. ⁴⁵ combine APF with an enhanced PRM variant called Circle Probabilistic Roadmap (CPRM) to escape local optima. Similarly, Ravankar et al. ⁴⁰ present a fusion of PRM and APF. A hybrid approach utilizing PSO for initial path generation, which is subsequently refined with APF, is proposed in Zheng et al. ²⁹ Chen and Zhang ⁷⁶ suggest transitioning to RRT* when APF either becomes trapped in a local minimum or encounters an unreachable goal. Zhang et al. ⁴⁴ introduce a biased sampling PRM to accelerate the planning process, while Zhu et al. ⁷⁷ augment RRT with APF to smooth the resulting RRT path. Chen et al. ⁷⁸ integrate ACO for global planning with APF for local navigation.

Improving the potential field

Another research direction focuses on enhancing the potential field algorithm itself. Hua et al. ⁷⁹ propose effective methods for calculating potentials that avoid goal unreachability and local minima by implementing bidirectional search from both start and goal states. Chen et al. ⁷⁵ introduce novel rules for APF, including additional repulsive forces and virtual obstacles. The works^80–83 propose new formulations for potential force calculation to address the issues of local optima entrapment and unreachable targets. A rotating potential field approach to escape local optima and reduce oscillations for multiple UAV robots is introduced in Pan et al. ⁸⁴

Modulated dynamical system

Koptev et al. ⁸⁵ propose a combination of modulated dynamical systems and sampling-based MPC. The modulated dynamical system is a technique similar to APF but incorporates the dynamics of the robot. The authors demonstrate rapid replanning (500 Hz) and smooth local trajectories using the modulated dynamical system. They employ sampling-based MPC to resolve local minima and unreachable goal problems.

APF methods evaluation

APF methods are computationally efficient and capable of generating smooth paths. However, they can encounter difficulties with local minima, oscillatory behavior, and unreachable goals, which may result in suboptimal paths or complete failure to find a solution. The integration of APF with complementary methods can help mitigate these issues, albeit at the cost of increased algorithmic complexity. Improving the potential field formulation itself represents another promising research direction, though it may require additional computational resources and does not always guarantee a solution. Furthermore, compliance with kinematic and dynamic constraints is generally not guaranteed for APF methods. Overall, APF methods are most suitable for simpler environments where local minima and unreachable goals are less likely to occur.

Optimal control-based methods

Optimal control-based methods originate from the field of dynamic systems control. Optimal control has garnered significant research attention since the first industrial applications of MPC in the 1980s, ⁸⁶ and it remains an active area of research. Optimal control methods, including single-shooting and multiple-shooting methods, ⁸⁷ as well as MPC, are employed not only for dynamics control but also for trajectory and path planning.^88–90

As the name suggests, these algorithms minimize a given cost function $J$ subject to constraints imposed on the states and inputs. The problem can be generally formulated as

$$\underset{u}{min}J(x(t),u(t),t),$$

(6a)

$$\text{subject to}x(t+1)=f_D(x(t),u(t)),$$

(6b)

$$u(t)\in \mathcal{U},$$

(6c)

$$x(t)>x_{\text{min}},$$

(6d)

$$x(t)<x_{\text{max}},$$

(6e)

where $f_D$ is a time-discrete model function and other symbols are as previously defined. Trajectories generated by optimization-based techniques are inherently smooth and optimal with respect to the specified cost function. The principal advantages of these methods include the smoothness of planned trajectories and real-time executability. ⁹¹ Additionally, these methods typically do not suffer from the curse of dimensionality that affects other approaches, depending on the optimization solver employed. However, in most cases, they rely on locally optimal solvers, such as Quadratic Programming (QP) solvers. ⁹² Finding the global optimum requires a convex problem formulation, which is generally not valid for complex path or trajectory planning scenarios. In other words, complex motion planning problems are typically non-convex. ⁷² Consequently, heuristics are typically introduced to constrain the planning to a selected convex subspace. ⁷³ These heuristics can be either problem-specific or problem-independent cost-to-go heuristics, as employed in the literature^73,93,94 and illustrated in Figure 6. Alternatively, other algorithms can provide heuristic guidance for the optimization process.

Figure 6.

Example of how the convex subspace is selected from the non-convex planning problem with the help of cost-to-go heuristics. The figure is adopted from Vosahlik et al. ⁷³

Fusion algorithms

Zeng et al. ⁹⁰ employ graph-search-based A* for waypoint generation, with subsequent refined trajectory generation using MPC. Zuo et al. ⁹⁵ propose a fusion of PSO and MPC methods to gain ability to solve non-convex optimization problems. Lim et al. ⁹⁶ propose a fusion of sampling-based and optimal control-based strategies. They address the autonomous vehicle trajectory planning task by decomposing the problem into lateral and longitudinal dynamics planning subproblems. The lateral dynamics are first solved using a sampling-based method, followed by optimization of the longitudinal dynamics using MPC. This approach has been validated through real-world experiments. Huang et al. ⁹⁷ propose autonomous motion planning and tracking, suggesting an APF-like decision-making method, followed by longitudinal dynamics planning with MPC, lateral dynamics planning with MPC, and a lower-level sliding mode controller for trajectory tracking. Dixit et al. ⁹⁸ propose an APF-like algorithm to identify safe zones within which tube-based robust MPC is employed for combined longitudinal and lateral motion planning for autonomous vehicles.

Optimization problem enhancements

Valli et al. ⁸⁸ propose a specialized cost function for autonomous vehicles that considers only position and heading. A decoupled path and trajectory planning approach for autonomous overtaking is proposed in Liu et al. ⁹⁹ The path is first generated using a B-spline curve, and velocities are subsequently calculated through optimization employing QP and Dynamic Programming (DP) approaches. Zhou et al. ¹⁰⁰ propose a novel robust prediction algorithm for surrounding vehicles and demonstrate its incorporation into MPC. A unified optimal control framework based on MPC for locomotion and manipulation tasks is presented in Sleiman et al. ⁹¹ The authors demonstrate real-time performance of the planner, which produces smooth, high-quality trajectories for 28 state variables and 31 inputs, representing a significantly complex problem. Son et al. ¹⁰¹ propose an augmented Lagrangian formulation for an UAV system with slung load to calculate the trajectory, which is subsequently tracked using MPC. Romero et al. ¹⁰² propose Model Predictive Contouring Control (MPCC) to generate a time-optimal trajectory for an UAV. The objective of their work is to plan a trajectory based on a given geometric 3D path. The authors implement MPCC for real-time execution and report that the resulting trajectory is nearly optimal compared to the offline computed solution (for that specific use case), which requires hours to calculate due to the complex dynamics considered.

An enhancement to time-optimal control, termed time-optimal switching, is introduced in He et al. ¹⁰³ This approach employs a bang–bang time-optimal trajectory using only minimum, maximum, and zero input values. Zhang et al. ¹⁰⁴ propose a novel representation of obstacle polytopes through dual problem introduction, rendering the problem differentiable and solvable by available convex solvers without any obstacle approximation. They effectively minimize an augmented Lagrangian of the system. MPC with the Proximal Averaged Newton-type method for Optimal Control (PANOC) solver is introduced in Sathya et al. ¹⁰⁵ for robotic arm motion planning. PANOC is a nonlinear first-order solver that employs a projected gradient approach for cost function minimization and utilizes the multiple-shooting method for trajectory planning. Luis et al. ¹⁰⁶ propose Distributed Model Predictive Control (DMPC) for multi-robot trajectory generation. Collision avoidance planning for two manipulators using splines is presented in Riboli et al.. ¹⁰⁷ When no collision between the two arms is detected, a path smoothed with Bézier curves is employed. Upon collision detection in the plan, optimization of spline curves using QP is proposed to adjust the trajectory away from potential collisions. Model Predictive Inversive Control (MPIC)-based trajectory generation is introduced in He et al. ⁸⁹ for robotic manipulators.

Another common approach involves calculating optimal motion primitives offline and subsequently using them for online trajectory planning. This way, the problem is per partes optimal, which, however, does not guarantee global optimality. This approach is presented in Effati et al. ¹⁰⁸ for a skid-steer rover, where the authors calculate 29 optimal trajectory structures for different conditions.

Optimal control methods evaluation

Optimal control methods, particularly those based on MPC, are powerful tools for generating high-quality trajectories that respect system dynamics and constraints. They provide a systematic approach to optimizing performance criteria such as time, energy, or safety. These methods can be applied to path planning in certain scenarios where complexity is high and execution time is constrained. However, the principal advantage of these methods lies in their ability to handle complex dynamic constraints. Nevertheless, these methods can be computationally intensive, especially for high-dimensional systems or extended planning horizons. Real-time implementation often requires simplifications, approximations, or efficient solvers. Typically, only local optima are guaranteed; consequently, these methods are more suitable for local planning tasks where the existence of multiple local minima is less probable. Despite these challenges, optimal control methods are highly versatile and applicable to a broad range of robotic systems, from autonomous vehicles to robotic manipulators.

Graph methods

Similar to the sampling-based methods discussed in Section “Sampling-based methods,” graph-based methods operate on discretely sampled state spaces. The principal distinction is that the space is not sampled randomly; it is typically sampled using grid structures, although other sampling patterns are also employed. These grids are subsequently searched using classical graph theory methods such as Dijkstra’s algorithm ²⁵ or its improvement, A*. ²⁶ Research in this area typically follows two main directions: improving the search methods themselves or improving the space sampling approach. Once the graph representation is constructed, graph search methods are generally highly efficient. The principal limitation is the curse of dimensionality for higher Degree of Freedom (DOF) planning tasks, such as robotic motion planning for robots with complex geometries. An example of path planning using the A* algorithm is illustrated in Figure 7.

Figure 7.

Example of path planning with A* algorithm. The figure is adopted from Han et al. ¹⁰⁹

The fundamental principle of A* is to maintain two lists of nodes (states): an open list and a closed list. The algorithm operates iteratively; in each iteration, it selects the node with the lowest cost from the open list, adds its unexplored child nodes to the open list, removes the selected node from the open list, and adds it to the closed list. The algorithm continues until the goal is reached. The cost of a node is typically determined by the path cost incurred thus far and a heuristic estimate of the remaining cost to the goal.

A*- and Dijkstra-based planners

An improved Dijkstra algorithm, termed Convex Dissection Topology-Dijkstra (CDT-Dijkstra), is introduced in Liu et al. ¹¹⁰ The CDT-Dijkstra algorithm plans a two-dimensional path in continuous space without requiring discretization. The planning is capable of real-time implementation; however, the planned path does not guarantee optimality with respect to a user-specified cost function. Han et al. ¹⁰⁹ focus on improving A* for distant targets, where heuristics play a significant role in the initial stages of the search. They employ the Dynamic Window Algorithm (DWA) method for local path replanning. Improvements specific to wheeled autonomous robots are proposed in Sun et al., ¹¹¹ which presents an improved A* with non-conventional graph construction featuring additional edges compared to conventional approaches, coupled with planned path post-processing to remove unnecessary nodes, resulting in smoother paths. Tang et al. ¹¹² present geometric A*, an A* variant with a post-processing step that smooths the planned path. Furthermore, Sun et al. ¹¹³ introduce an improved A* with a problem-specific heuristic for mining Autonomous Ground Vehicle (AGV) applications.

ACO planners

ACO is a biologically inspired algorithm wherein multiple agents traverse randomly until reaching a goal. It is an iterative algorithm in which the most recently visited locations are more likely to be utilized in subsequent iterations. Through this process, ACO tends to converge to the shortest path. Wang et al. ¹¹⁴ propose ACO for optimizing the path of a grinding robotic arm, where ACO determines the order of points to be ground, thereby minimizing operation time. He et al. ¹¹⁵ employed the A* algorithm for initial UAV path planning. However, for situations involving unexpected obstacles not identified in advance, real-time replanning is conducted using the ACO algorithm within a predetermined spatial ellipsoid. Guo et al. ¹¹⁶ address multi-goal planning scenarios. The goals are first ordered using ACO, and subsequently, the A* algorithm performs inter-point motion planning. The resulting plan is then post-processed to enhance smoothness.

Fusion algorithms

Zheng and Yu ¹¹⁷ propose using the D* algorithm for coarse planning, which is similar to A* but focuses on dynamic replanning. D* typically plans in reverse from goal to start, enabling replanning of only a small portion of the path when encountering a dynamic obstacle or other disturbance. Following the coarse path computation, Zheng and Yu ¹¹⁷ propose using APF to achieve smoother paths with safe clearance from obstacles. A fusion of improved ACO for global path planning with APF for local navigation is presented in Chen et al. ⁷⁸ Mbemba et al. ⁴³ sample the space using the PRM approach. The ACO algorithm is then employed to optimize the path plan, which is subsequently smoothed using Bézier curves.

Graph search methods evaluation

Graph search methods are powerful tools for path planning in discrete spaces. These methods inherently require representing the state space with a finite number of nodes and are not directly applicable to continuous spaces. The smaller the number of nodes, the faster the algorithm executes. These methods can provide optimal paths with respect to a specified cost function in the discretized space, particularly when heuristics are well-designed (admissible). However, they may encounter difficulties in high-dimensional spaces due to the curse of dimensionality. Furthermore, the quality of the planned path can be affected by the space discretization, and additional post-processing steps may be required to smooth the path. The integration of graph search methods with complementary approaches, such as APF or ACO, can help mitigate some of these limitations and improve the quality of planned paths.

Other methods

Additional methods exist for motion planning that are less prevalent than the four primary approaches discussed in the preceding sections. These methods are presented here for completeness. For instance, Zhu et al. ¹² employ Markov Decision Process (MDP) with a dynamic programming approach and pre-calculated motion primitives to determine the optimal subsequent state from the set of available states reached by moving along the motion primitives. Another approach involves simple linear interpolation between start and goal states, assuming these have been carefully selected to ensure no collision is possible between them. This approach is employed in Brockdorff et al., ⁷ which applies this technique to surgical robot path planning.

Genetic algorithms

GA is an optimization solver. The GA is a biologically inspired algorithm wherein a population of individual solutions is evaluated based on a given cost function, and only the fittest individuals are selected to participate in producing the next generation. The subsequent generation is obtained by executing operations such as mutation or crossover. The GA may converge to a local optimum when using a small population size. However, increasing the population size correspondingly increases computational time.

An improved GA is proposed in Ning et al. ¹¹⁸ to plan paths for multiple inspection robots. Fan et al. ¹¹⁹ address multi-robot motion planning using GA. They propose decomposing the problem into two stages: in the first stage, each robot plans its own path independently without considering other robots, while in the second stage, lower-priority robots replan their trajectories to avoid potential collisions with higher-priority robots.

NNs

The NN approach is typically combined with Reinforcement Learning (RL). Various modifications and enhancements have been proposed in the literature. A fundamental challenge with NNs is their inability to provide safety guarantees for their solutions, unlike conventional mathematically based approaches. Chu et al. ¹²⁰ propose Q-learning with convolutional NNs to plan paths for underwater vehicles. Additional RL-based trajectory planning approaches for multi-agent UAV environments are presented in the literature.^121,122 A time-optimal trajectory generation method for highly dynamic UAV maneuvers is proposed in Song et al., ¹²³ where the authors develop a Deep Reinforcement Learning (DRL) strategy for learning optimal policies. An alternative approach is presented in Hu et al., ¹²⁴ where the authors employ a NN to learn robot model equations, which can subsequently be utilized for trajectory planning and control.

PSO

PSO is another biologically inspired algorithm. It consists of a swarm of individuals that collectively search for the optimal solution given a cost function. The PSO algorithm is straightforward to implement and is capable of solving a non-convex optimization problem. However, it frequently converges to local optima and therefore does not guarantee finding the global optimum. ¹²⁵ An SDPSO algorithm that addresses the limitations of conventional PSO is presented in Yu et al., ¹²⁵ employed for three-dimensional UAV path planning. The core concept involves combining the SA algorithm with PSO such that initially, the algorithm performs large solution updates following the SA approach to identify promising regions. Subsequently, standard PSO refines the solution within that region. Liang et al. ⁸ propose applying the PSO algorithm to a six-axis robot for medical applications. An optimized PSO variant that addresses the stuck at a local minimum problem is employed in Zheng et al. ²⁹ as a coarse path generator, which is subsequently refined using APF.

DWA

DWA is similar to the DP approach. It generates a set of dynamically feasible trajectories, typically by discretizing the velocity space and calculating trajectories based on system dynamics, and evaluates them according to a cost function. The best trajectory (according to the cost function criterion) is subsequently selected as the plan. This approach is commonly employed for local path replanning when encountering dynamic obstacles.^109,111 Tan et al. ¹²⁶ propose an enhancement to the conventional DWA method that improves the quality of planned trajectories. DWA is susceptible to the stuck at local optimum problem and additionally faces the curse of dimensionality for more complex planning problems involving additional states or finer discretization grids.

Discussion and results

The approaches presented in this review exhibit various advantages and limitations. A simplified comparison of selected important features for various algorithm families is provided in Table 1. Features in which a particular algorithm outperforms others are marked as ✓✓, neutral features as o, and underperforming features as ××. A comparison of algorithms is inherently challenging, as algorithm performance is highly dependent on the specific problem definition, robot type, environment, and other factors. Therefore, the comparison in Table 1 is based on general trends observed in the literature and may not apply to every specific case.

Table 1.

Comparison of selected trajectory and path planning algorithms’ features. Legend for the given assessment is from outperforming ✓✓ through neutral o to underperforming ××. Planning time might be slower upfront, but it shall be faster during operation when the robot is moving. Global optimality capability identifies the optimal convex subset; local optimality finds the exact solution within a given subset.

Algorithm	Local optimality	Global optimality	Planning time	Anytime available	Dynamic constraints	Kinematic constraints	Smoothness	Real-time executable	Curse of dimensionality	Real-time replanning time	Generic✓/specific×applicability	Suitable for trajectory planning	Low✓✓/high××complexity
RRT 20	××	××	o	✓✓	××	×	××	o	o	×	✓✓	××	✓
PRM 21	××	××	o	✓✓	××	×	××	✓	o	o	✓✓	××	✓
RRT* 30	✓	✓✓	××	✓	××	×	×	×	×	××	✓✓	××	o
PRM* 30	✓	✓✓	××	✓✓	××	×	×	o	×	o	✓✓	××	o
RRT-Connect 37	××	××	✓✓	✓✓	××	××	××	✓✓	o	✓✓	✓✓	××	✓
FMT* 46	✓	✓✓	×	××	××	×	×	o	o	××	✓✓	××	o
Informed RRT* 48	✓	✓✓	o	✓	××	×	×	o	×	×	✓✓	××	×
BIT* 49	✓	✓✓	✓	✓	××	×	×	✓	✓	×	✓✓	××	×
Adaptive Informed Trees* (AIT*) 53	✓	✓✓	✓✓	✓✓	××	×	×	✓✓	✓✓	o	✓✓	××	×
EIT* 56	✓	✓✓	✓✓	✓✓	××	×	×	✓✓	✓✓	o	✓✓	××	×
RT-RRT* 50	✓	✓✓	✓✓	✓✓	××	×	×	✓	×	✓	✓✓	××	o
N-sliced informed RRT* 57	✓	✓✓	✓	✓	××	×	×	o	×	×	✓✓	××	o
EIRM* 59	✓	✓✓	✓✓	✓✓	××	×	×	✓✓	✓✓	✓	✓✓	××	×
RRV 39	××	××	✓	✓✓	××	×	×	o	o	××	✓✓	××	o
MVP 61	✓	✓✓	×– ✓	✓	✓✓	✓✓	×	×– o	✓	×– ✓	✓✓	✓	×
Lazy steering RRT* 63	✓	✓✓	✓	✓✓	✓✓	✓✓	×	o	×	×	✓✓	✓	o
Dynamic RRT 67	✓	✓	✓	✓	××	×	×	✓	×	×	✓✓	××	×
KDF 68	✓	✓✓	o	✓	✓	✓	✓	✓	o	o	✓✓	✓✓	×
HySST 66	××	××	o	o	✓	✓	o	o	o	o	✓✓	✓✓	×
APF 24	✓	××	✓✓	✓✓	××	×	✓✓	✓	✓	✓	✓✓	××	✓✓
APF-CPRM 45	✓	✓✓	✓	✓✓	××	×	✓✓	✓	o	✓	✓✓	××	✓
APF-PSO 29	✓	✓	✓	✓	××	×	✓✓	✓	o	✓	✓✓	××	o
APF-RRT* 76	✓	✓✓	o	✓✓	××	×	✓✓	✓	o	o	✓✓	××	o
APF-PRM 44	✓	✓	✓	✓✓	××	×	✓✓	✓	o	✓	✓✓	××	✓
ACO-APF 78	✓	✓	✓	o	××	×	✓✓	o	o	o	✓✓	××	o
MPC 91	✓✓	××	✓✓	✓✓	✓✓	✓✓	✓✓	✓✓	✓✓	✓	✓✓	✓✓	o
MPC with cost-to-go 94	✓✓	×	✓✓	✓✓	✓✓	✓✓	✓✓	✓✓	✓✓	✓	o	✓✓	o
MPC-PSO 95	✓✓	o	o	✓	✓✓	✓✓	✓✓	×	✓	××	✓✓	✓✓	×
MPC with motion primitives 96	✓	××	✓	✓	✓✓	✓✓	o	✓✓	✓✓	o	o	✓✓	o
MPIC 89	✓	××	✓	✓✓	✓✓	✓✓	✓✓	✓	✓✓	o	×	✓✓	×
MPCC 102	✓✓	××	✓✓	✓✓	✓✓	✓✓	✓✓	✓✓	✓	✓✓	×	✓✓	×
A* 26	o	✓✓	×	××	××	×	××	×	××	××	✓✓	××	✓
Dijkstra 25	o	✓✓	××	××	××	×	××	×	××	××	✓✓	××	✓✓
CDT-Dijkstra 110	✓	✓	✓✓	×	✓	✓	o	o	××	×	×	✓✓	✓
Geometric A* 112	✓	✓	×	×	××	×	××	×	××	××	✓✓	×	✓
ACO 114	o	✓	o	✓	××	×	××	×	××	××	✓✓	××	o
D*-APF 117	✓	✓✓	o	✓	××	×	✓	o	××	o	✓✓	××	✓
MDP with Motion Primitives and DP 12	✓	✓✓	o	o	✓✓	✓✓	✓	o	o	×	o	✓	o
Improved GA 118	✓	✓	o	✓	✓✓	✓✓	o	×	×	×	o	✓	✓
Q-learning – RL 120	✓	✓✓	×	o	✓✓	✓✓	✓	✓	×	✓	✓	✓	×
DRL 123	✓	✓✓	×	o	✓✓	✓✓	✓	✓	×	✓	✓	✓	×
Hybrid PSO 125	✓	✓	o	o	××	×	o	o	×	×	✓✓	×	o
Improved DWA 126	✓	××	✓✓	✓✓	✓✓	✓✓	✓✓	✓✓	×	✓	✓	✓✓	✓✓

Generally, motion planning algorithm applications can be categorized into two main groups:

Global motion planning algorithms, which are employed for complex environments involving typically non-convex problems where global optimality is often required. These algorithms are generally more computationally expensive due to environmental complexity. However, they can provide superior paths and/or trajectories in terms of optimality and safety compared to local motion planning algorithms.

Local motion planning algorithms, which are employed for less complex environments involving typically convex problems where global optimality is not required, and local optimality is often sufficient. These algorithms are generally less computationally expensive; however, they may not provide optimal paths and/or trajectories in terms of global optimality and safety.

Global motion planning algorithms

Complex, frequently non-convex motion planning tasks are typically addressed using sampling-based methods, graph search methods, AI-based methods, and their fusion approaches. These algorithms are generally more computationally expensive; however, they can provide superior paths and/or trajectories in terms of optimality and safety. Recently, sampling-based methods have attracted considerable research attention, as they can provide asymptotic global optimality while maintaining reasonable computational speed for path planning. However, their application to trajectory planning remains an active research topic. The principal limitation of sampling-based methods is computational cost, which also affects the closely related graph search algorithms. Graph search algorithms are generally faster than sampling-based methods for low-complexity environments that can be easily represented by graph structures; however, they generally produce suboptimal paths and/or trajectories in terms of path and trajectory smoothness. AI-based methods have demonstrated substantial potential across various domains, including robotics. However, their principal limitations include a lack of explainability and the requirement for large amounts of training data. Furthermore, they are not yet suitable for safety-critical applications, which is a fundamental requirement for most robotic systems.

Generally, feasible-only algorithms within the aforementioned algorithm families tend to be computationally less expensive and are therefore employed in complex environments where optimality is not required but computational speed is critical.

Local motion planning algorithms

All global motion planning algorithms can be applied to local motion planning tasks; however, they may not represent the best choice in terms of computational cost. For local motion planning tasks, optimal control methods (particularly MPC) and APF can provide high-quality trajectories with low computational complexity. However, these methods generally find only local optima and are therefore typically employed for local trajectory planning tasks. AI-based methods constitute a special category, as they can be applied to both local and global motion planning tasks.

Fusion algorithms

To overcome individual algorithm limitations, numerous fusion approaches have been proposed. These fusion approaches attempt to combine the advantageous properties of different methods with varying degrees of success. For example, the integration of sampling-based methods with APF methods can produce smoother trajectories than sampling-based methods alone. Similarly, fusion methods seek to leverage the strengths of the combined methods to mitigate their respective weaknesses.

Trajectory from path plan

Once the path is planned, the trajectory can be generated using various methods, such as time parameterization, interpolation, or optimization-based approaches. The choice of method depends on the specific application requirements, including the desired trajectory smoothness, the dynamic constraints of the robot, and the available computational resources. Typically, the path is planned for the entire mission, while the trajectory is generated for a short horizon and then replanned as the robot moves and acquires new environmental information. This approach is discussed, for example, in Section “DWA.”

The classical approach involves using waypoints from the path plan and fitting a smooth function to them, such as polynomials or other suitable functions, as demonstrated in Lim et al., ⁹⁶ where the authors employ motion primitives to generate a dynamically feasible trajectory from a planned path. For example, Huh et al. ⁹⁴ use a cost-to-go function to generate a trajectory from a planned path, while Zuo et al. ⁹⁵ employ an MPC-based approach. He et al. ⁸⁹ utilize an MPIC approach, while Romero et al. ¹⁰² employ an MPCC approach. Liu et al. ⁹⁹ use QP solver to generate locally optimal trajectory from a planned path.

Future outlook

Currently, the most promising and extensively studied direction for complex tasks involves sampling-based methods, which generally provide asymptotic global optimality while maintaining reasonable computational speed. Implementing sampling-based methods for trajectory planning problems that satisfy dynamic constraints in real-time remains an active research topic. The primary limiting factor for sampling-based method deployment is hardware performance, which is expected to improve progressively. Among their most significant advantages is the theoretical possibility of certification for safety-critical applications, which is essential for most robotic systems. Another research direction for sampling-based methods that could accelerate computation is algorithm parallelization. Some work in this area already exists, such as Thomason et al. ¹²⁷ ; however, substantial room for improvement remains.

Another promising direction involves AI-based methods, which have demonstrated substantial potential across various domains, including robotics. Their principal limitations include a lack of explainability and the requirement for large training datasets. However, research in this area is evolving rapidly. A considerable distance remains before AI-based methods can be certified for safety-critical applications. A potential future direction for these methods involves their use in hybrid approaches with a safety guardian that can ensure robot safety while still benefiting from the advantages of AI-based methods.

For lower-complexity tasks, optimal control methods (particularly MPC) and APF are well-suited. These methods can produce high-quality trajectories, which future research may leverage through fusion with other approaches to further improve planned trajectory quality.

Conclusion

This work has presented a comprehensive review of recent path and trajectory planning approaches as applied to robotics. As evidenced throughout this survey, this represents a highly important, extensively studied, and rapidly evolving topic with numerous recent advancements. This introductory general review serves as a valuable starting point for researchers interested in this topic, providing an overview of state-of-the-art approaches along with their respective advantages and limitations. Furthermore, it can serve as a guide for selecting the most suitable approach for a specific problem definition, robot type, environment, and other relevant factors.