Hubbry Logo
Motion planningMotion planningMain
Open search
Motion planning
Community hub
Motion planning
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Motion planning
Motion planning
Motion planning
View on Wikipedia
from Wikipedia

Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used in computational geometry, computer animation, robotics and computer games.

For example, consider navigating a mobile robot inside a building to a distant waypoint. It should execute this task while avoiding walls and not falling down stairs. A motion planning algorithm would take a description of these tasks as input, and produce the speed and turning commands sent to the robot's wheels. Motion planning algorithms might address robots with a larger number of joints (e.g., industrial manipulators), more complex tasks (e.g. manipulation of objects), different constraints (e.g., a car that can only drive forward), and uncertainty (e.g. imperfect models of the environment or robot).

Motion planning has several robotics applications, such as autonomy, automation, and robot design in CAD software, as well as applications in other fields, such as animating digital characters, video game, architectural design, robotic surgery, and the study of biological molecules.

Concepts

[edit]
Example of a workspace
Configuration space of a point-sized robot. White = Cfree, gray = Cobs.
Configuration space for a rectangular translating robot (pictured red). White = Cfree, gray = Cobs, where dark gray = the objects, light gray = configurations where the robot would touch an object or leave the workspace.
Example of a valid path
Example of an invalid path
Example of a road map

A basic motion planning problem is to compute a continuous path that connects a start configuration S and a goal configuration G, while avoiding collision with known obstacles. The robot and obstacle geometry is described in a 2D or 3D workspace, while the motion is represented as a path in (possibly higher-dimensional) configuration space.

Configuration space

[edit]

A configuration describes the pose of the robot, and the configuration space C is the set of all possible configurations. For example:

  • If the robot is a single point (zero-sized) translating in a 2-dimensional plane (the workspace), C is a plane, and a configuration can be represented using two parameters (x, y).
  • If the robot is a 2D shape that can translate and rotate, the workspace is still 2-dimensional. However, C is the special Euclidean group SE(2) = R2 SO(2) (where SO(2) is the special orthogonal group of 2D rotations), and a configuration can be represented using 3 parameters (x, y, θ).
  • If the robot is a solid 3D shape that can translate and rotate, the workspace is 3-dimensional, but C is the special Euclidean group SE(3) = R3 SO(3), then the configuration requires 6 parameters: (x, y, z) for translation, and Euler angles (α, β, γ).
  • If the robot is a fixed-base manipulator with N revolute joints (and no closed-loops), C is N-dimensional.
  • If gimbal lock is not acceptable (eg. in RN where N ≥ 3 ) then the use of quaternions or other workarounds may be required, increasing the rotational dimensions or solution's complexity.

Free space

[edit]

The set of configurations that avoids collision with obstacles is called the free space Cfree. The complement of Cfree in C is called the obstacle or forbidden region.

Often, it is prohibitively difficult to explicitly compute the shape of Cfree. However, testing whether a given configuration is in Cfree is efficient. First, forward kinematics determine the position of the robot's geometry, and collision detection tests if the robot's geometry collides with the environment's geometry.

Target space

[edit]

Target space is a subspace of free space which denotes where we want the robot to move to. In global motion planning, target space is observable by the robot's sensors. However, in local motion planning, the robot cannot observe the target space in some states. To solve this problem, the robot goes through several virtual target spaces, each of which is located within the observable area (around the robot). A virtual target space is called a sub-goal.

Obstacle space

[edit]

Obstacle space is a space that the robot can not move to. Obstacle space is not opposite of free space.

Algorithms

[edit]

Low-dimensional problems can be solved with grid-based algorithms that overlay a grid on top of configuration space, or geometric algorithms that compute the shape and connectivity of Cfree.

Exact motion planning for high-dimensional systems under complex constraints is computationally intractable. Potential-field algorithms are efficient, but fall prey to local minima (an exception is the harmonic potential fields). Sampling-based algorithms avoid the problem of local minima, and solve many problems quite quickly. They are unable to determine that no path exists, but they have a probability of failure that decreases to zero as more time is spent.[citation needed]

Sampling-based algorithms are currently[when?] considered state-of-the-art for motion planning in high-dimensional spaces, and have been applied to problems which have dozens or even hundreds of dimensions (robotic manipulators, biological molecules, animated digital characters, and legged robots).

[edit]

Grid-based approaches overlay a grid on configuration space and assume each configuration is identified with a grid point. At each grid point, the robot is allowed to move to adjacent grid points as long as the line between them is completely contained within Cfree (this is tested with collision detection). This discretizes the set of actions, and search algorithms (like A*) are used to find a path from the start to the goal.

These approaches require setting a grid resolution. Search is faster with coarser grids, but the algorithm will fail to find paths through narrow portions of Cfree. Furthermore, the number of points on the grid grows exponentially in the configuration space dimension, which make them inappropriate for high-dimensional problems.

Traditional grid-based approaches produce paths whose heading changes are constrained to multiples of a given base angle, often resulting in suboptimal paths. Any-angle path planning approaches find shorter paths by propagating information along grid edges (to search fast) without constraining their paths to grid edges (to find short paths).

Grid-based approaches often need to search repeatedly, for example, when the knowledge of the robot about the configuration space changes or the configuration space itself changes during path following. Incremental heuristic search algorithms replan fast by using experience with the previous similar path-planning problems to speed up their search for the current one.

[edit]

These approaches are similar to grid-based search approaches except that they generate a paving covering entirely the configuration space instead of a grid.[1] The paving is decomposed into two subpavings X−,X+ made with boxes such that X− ⊂ Cfree ⊂ X+. Characterizing Cfree amounts to solve a set inversion problem. Interval analysis could thus be used when Cfree cannot be described by linear inequalities in order to have a guaranteed enclosure.

The robot is thus allowed to move freely in X−, and cannot go outside X+. To both subpavings, a neighbor graph is built and paths can be found using algorithms such as Dijkstra or A*. When a path is feasible in X−, it is also feasible in Cfree. When no path exists in X+ from one initial configuration to the goal, we have the guarantee that no feasible path exists in Cfree. As for the grid-based approach, the interval approach is inappropriate for high-dimensional problems, due to the fact that the number of boxes to be generated grows exponentially with respect to the dimension of configuration space.

An illustration is provided by the three figures on the right where a hook with two degrees of freedom has to move from the left to the right, avoiding two horizontal small segments.

Motion from the initial configuration (blue) to the final configuration of the hook, avoiding the two obstacles (red segments). The left-bottom corner of the hook has to stay on the horizontal line, which makes the hook two degrees of freedom.
Decomposition with boxes covering the configuration space: The subpaving X− is the union all red boxes and the subpaving X+ is the union of red and green boxes. The path corresponds to the motion represented above.
This figure corresponds to the same path as above but obtained with many fewer boxes. The algorithm avoids bisecting boxes in parts of the configuration space that do not influence the final result.

Nicolas Delanoue has shown that the decomposition with subpavings using interval analysis also makes it possible to characterize the topology of Cfree such as counting its number of connected components.[2]

Geometric algorithms

[edit]

Point robots among polygonal obstacles

Translating objects among obstacles

Finding the way out of a building

  • farthest ray trace

Given a bundle of rays around the current position attributed with their length hitting a wall, the robot moves into the direction of the longest ray unless a door is identified. Such an algorithm was used for modeling emergency egress from buildings.

Artificial potential fields

[edit]

One approach is to treat the robot's configuration as a point in a potential field that combines attraction to the goal, and repulsion from obstacles. The resulting trajectory is output as the path. This approach has advantages in that the trajectory is produced with little computation. However, they can become trapped in local minima of the potential field and fail to find a path, or can find a non-optimal path. The artificial potential fields can be treated as continuum equations similar to electrostatic potential fields (treating the robot like a point charge), or motion through the field can be discretized using a set of linguistic rules.[3] A navigation function[4] or a probabilistic navigation function[5] are sorts of artificial potential functions which have the quality of not having minimum points except the target point.

Sampling-based algorithms

[edit]

Sampling-based algorithms represent the configuration space with a roadmap of sampled configurations. A basic algorithm samples N configurations in C, and retains those in Cfree to use as milestones. A roadmap is then constructed that connects two milestones P and Q if the line segment PQ is completely in Cfree. Again, collision detection is used to test inclusion in Cfree. To find a path that connects S and G, they are added to the roadmap. If a path in the roadmap links S and G, the planner succeeds, and returns that path. If not, the reason is not definitive: either there is no path in Cfree, or the planner did not sample enough milestones.

These algorithms work well for high-dimensional configuration spaces, because unlike combinatorial algorithms, their running time is not (explicitly) exponentially dependent on the dimension of C. They are also (generally) substantially easier to implement. They are probabilistically complete, meaning the probability that they will produce a solution approaches 1 as more time is spent. However, they cannot determine if no solution exists.

Given basic visibility conditions on Cfree, it has been proven that as the number of configurations N grows higher, the probability that the above algorithm finds a solution approaches 1 exponentially.[6] Visibility is not explicitly dependent on the dimension of C; it is possible to have a high-dimensional space with "good" visibility or a low-dimensional space with "poor" visibility. The experimental success of sample-based methods suggests that most commonly seen spaces have good visibility.

There are many variants of this basic scheme:

  • It is typically much faster to only test segments between nearby pairs of milestones, rather than all pairs.
  • Nonuniform sampling distributions attempt to place more milestones in areas that improve the connectivity of the roadmap.
  • Quasirandom samples typically produce a better covering of configuration space than pseudorandom ones, though some recent work argues that the effect of the source of randomness is minimal compared to the effect of the sampling distribution.
  • Employs local-sampling [7] by performing a directional Markov chain Monte Carlo random walk with some local proposal distribution.
  • It is possible to substantially reduce the number of milestones needed to solve a given problem by allowing curved eye sights (for example by crawling on the obstacles that block the way between two milestones[8]).
  • If only one or a few planning queries are needed, it is not always necessary to construct a roadmap of the entire space. Tree-growing variants are typically faster for this case (single-query planning). Roadmaps are still useful if many queries are to be made on the same space (multi-query planning)

List of notable algorithms

[edit]

Completeness and performance

[edit]

A motion planner is said to be complete if the planner in finite time either produces a solution or correctly reports that there is none. Most complete algorithms are geometry-based. The performance of a complete planner is assessed by its computational complexity. When proving this property mathematically, one has to make sure, that it happens in finite time and not just in the asymptotic limit. This is especially problematic, if there occur infinite sequences (that converge only in the limiting case) during a specific proving technique, since then, theoretically, the algorithm will never stop. Intuitive "tricks" (often based on induction) are typically mistakenly thought to converge, which they do only for the infinite limit. In other words, the solution exists, but the planner will never report it. This property therefore is related to Turing completeness and serves in most cases as a theoretical underpinning/guidance. Planners based on a brute force approach are always complete, but are only realizable for finite and discrete setups.

In practice, the termination of the algorithm can always be guaranteed by using a counter, that allows only for a maximum number of iterations and then always stops with or without solution. For realtime systems, this is typically achieved by using a watchdog timer, that will simply kill the process. The watchdog has to be independent of all processes (typically realized by low level interrupt routines). The asymptotic case described in the previous paragraph, however, will not be reached in this way. It will report the best one it has found so far (which is better than nothing) or none, but cannot correctly report that there is none. All realizations including a watchdog are always incomplete (except all cases can be evaluated in finite time).

Completeness can only be provided by a very rigorous mathematical correctness proof (often aided by tools and graph based methods) and should only be done by specialized experts if the application includes safety content. On the other hand, disproving completeness is easy, since one just needs to find one infinite loop or one wrong result returned. Formal Verification/Correctness of algorithms is a research field on its own. The correct setup of these test cases is a highly sophisticated task.

Resolution completeness is the property that the planner is guaranteed to find a path if the resolution of an underlying grid is fine enough. Most resolution complete planners are grid-based or interval-based. The computational complexity of resolution complete planners is dependent on the number of points in the underlying grid, which is O(1/hd), where h is the resolution (the length of one side of a grid cell) and d is the configuration space dimension.

Probabilistic completeness is the property that as more "work" is performed, the probability that the planner fails to find a path, if one exists, asymptotically approaches zero. Several sample-based methods are probabilistically complete. The performance of a probabilistically complete planner is measured by the rate of convergence. For practical applications, one usually uses this property, since it allows setting up the time-out for the watchdog based on an average convergence time.

Incomplete planners do not always produce a feasible path when one exists (see first paragraph). Sometimes incomplete planners do work well in practice, since they always stop after a guarantied time and allow other routines to take over.

Problem variants

[edit]

Many algorithms have been developed to handle variants of this basic problem.

Differential constraints

[edit]

Holonomic

  • Manipulator arms (with dynamics)

Nonholonomic

  • Drones
  • Cars
  • Unicycles
  • Planes
  • Acceleration bounded systems
  • Moving obstacles (time cannot go backward)
  • Bevel-tip steerable needle
  • Differential drive robots

Optimality constraints

[edit]

Hybrid systems

[edit]

Hybrid systems are those that mix discrete and continuous behavior. Examples of such systems are:

Uncertainty

[edit]

Environmental constraints

[edit]
  • Maps of dynamics [10]

Applications

[edit]

See also

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Motion planning

View on Grokipedia
from Grokipedia
Motion planning is a fundamental problem in and that involves computing a collision-free path or for a or mechanical system to move from an initial configuration to a desired goal configuration within an environment containing obstacles. This process is typically formulated in the robot's configuration space (C-space), which represents all possible positions and orientations of the system, excluding invalid states due to collisions. The core challenge lies in navigating high-dimensional C-spaces efficiently while ensuring the path adheres to kinematic, dynamic, and environmental constraints. The origins of motion planning trace back to the 1970s with the formulation of the "Piano Mover's Problem," which sought exact solutions for moving rigid objects in 2D or 3D spaces. In the 1980s, researchers developed combinatorial algorithms, such as visibility graphs and cell decomposition, providing complete and exact solutions but suffering from exponential computational complexity in higher dimensions. The 1990s marked a breakthrough with the advent of sampling-based methods, like probabilistic roadmaps (PRM) and rapidly-exploring random trees (RRT), which enabled practical planning in complex, high-dimensional spaces by probabilistically exploring the C-space. Key aspects of motion planning include distinguishing between geometric planning (focusing on position and orientation) and kinodynamic planning (incorporating velocity, acceleration, and control inputs for dynamic systems). Algorithms are evaluated on properties such as completeness (guaranteed solution if one exists), optimality (finding the best path), and resolution completeness (handling discretization errors). Challenges persist in handling narrow passages in C-space, real-time computation for dynamic environments, and integration with sensing and control systems. Motion planning finds essential applications in industrial for assembly tasks, autonomous vehicles for , surgical robots for precise interventions, and unmanned aerial vehicles for avoidance. Recent advances incorporate learning-based techniques, such as neural networks for , to address scalability in unstructured environments. Despite progress, ongoing research focuses on optimality guarantees and adaptability to uncertain or changing worlds.

Introduction

Definition and scope

Motion planning is the computational process of determining collision-free paths or trajectories for a , such as a , from an initial configuration to a configuration while respecting environmental and constraints. This involves finding a sequence of valid motions that avoid collisions with obstacles and satisfy kinematic or dynamic limitations of the . The core problem of motion planning is formulated as follows: given an initial state qstartq_{\text{start}}, a state qgoalq_{\text{goal}}, and a description of obstacles, compute a valid motion plan that connects qstartq_{\text{start}} to qgoalq_{\text{goal}}. This is achieved through a search in the configuration space CC, which represents all possible configurations of the system. The scope of motion planning includes kinematic planning, which addresses constraints on position and orientation without considering forces, and dynamic planning, which incorporates and limits arising from the system's and control inputs. It further distinguishes path planning, which yields a static geometric path in space, from full motion planning, which produces a time-parameterized accounting for temporal aspects. Formally, a path in motion planning is defined as a π:[0,1]→Cfree\pi: [0,1] \to C_{\text{free}}, where CfreeC_{\text{free}} denotes the collision-free subset of the configuration , with π(0)=qstart\pi(0) = q_{\text{start}} and π(1)=qgoal\pi(1) = q_{\text{goal}}. Motion planning originated in but has interdisciplinary roots and applications in for and , for geometric problem-solving, for decision-making under uncertainty, and for trajectory generation.

Historical overview

The origins of motion planning trace back to the and , when researchers began exploring problems related to for rigid bodies amid obstacles. Early work focused on theoretical foundations, such as determining feasible motions for objects in constrained environments. A pivotal contribution came in 1977 with S. M. Udupa's introduction of the configuration space concept, which transformed the into a point while expanding obstacles accordingly, enabling systematic collision avoidance analysis. This approach laid the groundwork for geometric methods. In 1979, Tomás Lozano-Pérez and Michael A. Wesley advanced the field by developing algorithms for planning collision-free paths among polyhedral obstacles, incorporating visibility graphs to connect tangent points on obstacles and cell decomposition to partition free space into navigable regions. The 1980s marked a shift toward exact algorithmic solutions for complex scenarios, exemplified by the "piano movers' problem," which involves translating and rotating a rigid object like a through a cluttered 2D or 3D environment. Jacob T. Schwartz and Micha Sharir provided seminal exact methods in a series of papers from 1981 to 1983, analyzing the topological properties of configuration spaces and developing algorithms with polynomial-time complexity for polygonal bodies amid barriers. These works established rigorous complexity bounds and influenced subsequent research in for motion planning. Advancements in the 1990s introduced probabilistic sampling-based techniques to handle high-dimensional spaces intractable for exact methods. In 1996, Lydia E. Kavraki, Petr Svestka, Jean-Claude Latombe, and Mark H. Overmars proposed the Probabilistic Roadmap (PRM) method, which builds a graph of random configurations connected by straight-line paths, enabling efficient query resolution for diverse environments. Building on this, Steven M. LaValle introduced Rapidly-exploring Random Trees (RRT) in 1998, an incremental tree-growing algorithm that biases exploration toward unexplored areas, proving effective for nonholonomic systems and dynamic constraints. The 2000s saw consolidation and optimization of sampling-based planners, alongside growing community infrastructure. In 2011, Sertac Karaman and Emilio Frazzoli extended RRT to RRT*, an asymptotically optimal variant that refines paths over time through rewiring, integrating seamlessly with optimization frameworks. Around 2000, the IEEE and Automation Society formed the Technical Committee on Algorithms for Planning and Control of Robot Motion to foster research collaboration. Biennial workshops, such as the International Workshop on the Algorithmic Foundations of Robotics (WAFR) since 1994, have further promoted advancements. Post-2010, the field shifted toward learning-based paradigms, with gaining prominence for adaptive planning in uncertain settings from 2015 to 2020. By 2025, data-driven approaches increasingly incorporated large language models (LLMs) for high-level task decomposition and integration with low-level planners, enhancing human-robot interaction in complex scenarios.

Fundamental Concepts

Configuration space

In motion planning, the configuration space, often denoted as CC, is the mathematical abstraction that represents all possible states or configurations of a robotic system. Formally, C={q∣qC = \{ q \mid q represents a complete specification of the system's pose, including positions and orientations of all relevant components}. This space encapsulates the (DOF) inherent to the , allowing the complex physical motion problem to be reduced to geometric queries in an abstract domain. The concept was pioneered in the work of Tomas Lozano-Pérez, who introduced configuration space as a tool for among obstacles. The dimensionality of CC is determined by the number of DOF, which corresponds to the minimal parameters needed to define any configuration. For a in , this typically yields 6 DOF: three for translational position (x, y, z) and three for rotational orientation (e.g., roll, pitch, yaw). In multi-joint manipulators, such as a 2D planar robot arm with two revolute joints, a configuration qq might be specified as q=(θ1,θ2)q = (\theta_1, \theta_2), where θ1\theta_1 and θ2\theta_2 are joint angles, resulting in a 2-dimensional CC. More complex systems, like a , can have dozens or hundreds of DOF, leading to high-dimensional spaces that pose significant computational challenges. Configuration space is distinct from task space, which focuses on the end-effector's position and orientation in the workspace, often a T⊂R3T \subset \mathbb{R}^3 for positional tasks. The mapping from CC to task space is provided by forward , a function f:C→Tf: C \to T that computes the end-effector pose from parameters qq. This separation enables motion to operate in the full CC, where joint limits and self-collisions are naturally represented, while task specifications constrain the problem to desired regions in TT. Inverse then seeks qq such that f(q)f(q) achieves a target in TT, highlighting the non-trivial relationship between the spaces. A critical aspect of CC involves obstacle representation for collision avoidance. A configuration qq lies in the obstacle subset CobsC_{\text{obs}} if the robot, when placed at qq, intersects any environmental obstacles; otherwise, it belongs to the free space Cfree=C∖CobsC_{\text{free}} = C \setminus C_{\text{obs}}. This partitioning transforms physical collisions into point queries in CC, simplifying detection algorithms. For instance, in a 2D example of a disk-shaped robot navigating among polygonal obstacles, CobsC_{\text{obs}} appears as "grown" regions around the obstacles, expanded by the robot's radius, while the robot itself reduces to a point in this space. Such visualizations aid intuition, revealing how obstacles in the workspace "sweep" forbidden volumes in CC. The structure of CC often forms a manifold, a smooth, differentiable space that supports continuous paths between configurations, essential for feasible motions. However, in high dimensions—common for advanced robots—the curse of dimensionality arises, exponentially increasing volume and complicating exploration and collision checking. This geometric foundation underpins subsequent partitioning into free and obstacle regions, enabling path planning as a search for collision-free routes within CfreeC_{\text{free}}.

Free and obstacle spaces

In motion planning, the configuration space CC is partitioned into the free space CfreeC_\text{free} and the obstacle space CobstacleC_\text{obstacle}, which delineate allowable and forbidden configurations for the . The free space consists of all configurations q∈Cq \in C such that the robot, placed at qq, does not intersect with any in the workspace or itself, assuming a static environment with fixed . Formally, Cfree={q∈C∣A(q)∩O=∅}C_\text{free} = \{ q \in C \mid A(q) \cap O = \emptyset \}, where A(q)A(q) represents the region occupied by the robot at configuration qq and OO denotes the set of obstacle regions in the workspace. This partition ensures that motion plans remain confined to CfreeC_\text{free} to avoid collisions, a foundational step before applying any path-searching techniques. The obstacle space, or CobstacleC_\text{obstacle}, is the complement of the free space in the full configuration space: Cobstacle=C∖CfreeC_\text{obstacle} = C \setminus C_\text{free}. To construct CobstacleC_\text{obstacle}, the 's geometry is incorporated via the Minkowski sum, which expands workspace obstacles to account for the robot's extent, effectively treating the robot as a point in this augmented space. For a translating rigid with shape RR (relative to a reference point) and workspace obstacles OO, the corresponding configuration obstacle is given by the expanded form O′=O⊕(−R)O' = O \oplus (-R), where ⊕\oplus denotes the Minkowski sum defined as A⊕B={a+b∣a∈A,b∈B}A \oplus B = \{ a + b \mid a \in A, b \in B \}. This operation captures all configurations where the reference point placement would cause overlap, enabling efficient representation of collision constraints in higher-dimensional CC. Collision detection is essential for verifying whether a configuration or path segment lies in CfreeC_\text{free}, often serving as a bottleneck in planning algorithms due to repeated queries. Common methods include bounding volume hierarchies (BVH), which organize object geometries into tree structures of enclosing volumes (e.g., axis-aligned bounding boxes or oriented bounding boxes) to prune unnecessary intersection tests, and the Gilbert-Johnson-Keerthi (GJK) algorithm, which iteratively computes the minimum distance between convex shapes using support functions without full shape representation. For simple convex like spheres or boxes, these algorithms achieve constant-time O(1)O(1) per query, though more complex polyhedral models may require O(log⁡n)O(\log n) time with hierarchical acceleration, where nn is the number of . In practice, BVH-based approaches are widely adopted in for their balance of preprocessing cost and query speed in dynamic scenes. Challenges arise at the boundaries of CfreeC_\text{free}, particularly in narrow passages where the clearance between obstacles is comparable to the robot's size, complicating the discovery of feasible paths due to the thin connectivity of the space. For multi-link manipulators, self-collision must also be modeled within CobstacleC_\text{obstacle}, treating links as separate bodies whose intersections are forbidden, often increasing the dimensionality and detection overhead. These formulations typically assume holonomic systems with non-penetration constraints, meaning the robot can move freely in all directions without velocity limits or interpenetration allowances during .

Paths and trajectories

In motion planning, a path is defined as a continuous, collision-free curve in the configuration space that connects an initial configuration qstartq_{\text{start}} to a goal configuration qgoalq_{\text{goal}}. Formally, it is represented as a mapping γ:[0,1]→Cfree\gamma: [0,1] \to \mathcal{C}_{\text{free}}, where Cfree\mathcal{C}_{\text{free}} denotes the free configuration space, ensuring γ(0)=qstart\gamma(0) = q_{\text{start}} and γ(1)=qgoal\gamma(1) = q_{\text{goal}}, with the image of γ\gamma lying entirely within Cfree\mathcal{C}_{\text{free}} to avoid obstacles. Paths are primarily geometric constructs that do not account for timing or dynamics, making them suitable for kinematic planning in static environments where the robot is fully actuated. A extends the path concept by incorporating time parameterization, specifying the robot's configuration as a function of time while respecting , , and other dynamic constraints. It is typically denoted as τ:[0,T]→Cfree\tau: [0,T] \to \mathcal{C}_{\text{free}}, where TT is the total duration, τ(0)=qstart\tau(0) = q_{\text{start}}, and τ(T)=qgoal\tau(T) = q_{\text{goal}}, with the trajectory satisfying differential equations such as τ˙(t)=f(τ(t),u(t))\dot{\tau}(t) = f(\tau(t), u(t)), where ff models the and u(t)∈Uu(t) \in U is the control input from the admissible set UU. This ensures feasibility under mechanical limits, distinguishing trajectories from paths by adding temporal and kinematic considerations essential for real-world execution. Trajectories can be parameterized in various ways, such as uniform speed along the path for simplicity or minimum-time profiles to optimize duration while adhering to bounds on and . Smoothing techniques, like representations, are often applied to refine raw paths into feasible trajectories by ensuring continuity in position, , and , which helps avoid abrupt changes that could violate joint limits or cause . Paths and trajectories may be resolved in discrete or continuous forms; discrete representations use a of waypoints connected by methods, such as linear for basic straight-line segments or cubic polynomials for smoother velocity profiles that preserve C2C^2 continuity. In approximate scenarios, the is treated as a G⊂CfreeG \subset \mathcal{C}_{\text{free}} rather than a single point, allowing the endpoint γ(1)\gamma(1) or τ(T)\tau(T) to lie anywhere within GG to accommodate or computational efficiency.

Classical Algorithms

Combinatorial methods

Combinatorial methods provide , complete solutions to motion planning problems by systematically decomposing the free configuration Cfree\mathcal{C}_{free} or constructing graphs that capture its connectivity, primarily for low-dimensional (2D or 3D) geometric with rigid bodies and polygonal or polyhedral obstacles. These approaches, developed in the , offer optimality guarantees but suffer from high that grows exponentially with dimensionality. Visibility graphs address the problem of finding the shortest collision-free path among polygonal obstacles in 2D by constructing a graph whose nodes are the start, , and obstacle vertices, with edges connecting pairs that have line-of-sight (tangent segments not intersecting obstacles). The shortest path in this graph, found via , corresponds to an optimal Euclidean path that "hugs" obstacle boundaries. Construction requires O(n2)O(n^2) time for nn vertices using rotational sweeps, making it complete and optimal for simply connected environments but impractical beyond 3D due to . Cell decomposition partitions Cfree\mathcal{C}_{free} into a finite number of non-overlapping cells (e.g., trapezoids in 2D via vertical decomposition), from which an adjacency graph is built by connecting adjacent cells. A search on this graph (e.g., using A*) yields a sequence of cells from start to goal, with a local path planner connecting centers within each cell. Exact decompositions ensure completeness and allow optimality with appropriate costs, but require solving Minkowski sums for robot-obstacle interactions and scale poorly (single exponential in dimension). Approximate variants reduce complexity at the cost of resolution completeness.

Grid-based methods

Grid-based methods discretize the continuous configuration space C\mathcal{C} into a finite grid of cells, transforming the motion planning problem into a discrete graph search over feasible cells in Cfree\mathcal{C}_{free}. This approach represents states at cell centers or lattice points, with edges adjacent cells that satisfy motion constraints, allowing exhaustive via graph algorithms. Such enables deterministic , particularly effective in low-dimensional spaces like 2D or 3D environments for mobile robots or manipulators. Grid types include uniform grids, which apply fixed-resolution cells across C\mathcal{C}, such as 2D occupancy grids dividing space into equal squares or cubes for straightforward collision checking. Adaptive grids, like octrees in 3D, refine resolution in complex regions near obstacles while coarsening elsewhere, reducing overall cell count through hierarchical subdivision. The resolution trade-off is critical: coarse grids enable fast computation but yield suboptimal, approximate paths due to limited detail, whereas fine grids provide higher accuracy at the cost of exponential memory and time demands. A key algorithm is A*, which performs informed search on the grid graph to find an optimal path by minimizing the f(n)=g(n)+h(n)f(n) = g(n) + h(n), where g(n)g(n) is the exact cost from the start to node nn, and h(n)h(n) is an estimating the cost from nn to the goal. For admissibility in velocity-bounded systems, the is often h(q)=∥q−qgoal∥vmaxh(q) = \frac{\|q - q_{goal}\|}{v_{max}}, where ∥q−qgoal∥\|q - q_{goal}\| is the and vmaxv_{max} is the maximum velocity, ensuring h(n)≤h∗(n)h(n) \leq h^*(n) to guarantee optimality in the . Dijkstra's algorithm serves as a special case without heuristics, suitable for uniform costs. These methods are complete and optimal in the discrete grid, offering guaranteed solutions when they exist, but they suffer from the curse of dimensionality, with cell counts growing exponentially (e.g., approximately 10610^6 cells for a 6D space at modest resolution), rendering them impractical for high beyond 3-4 DOF. Variants include propagation, which computes distance fields by iteratively expanding from the using a or , akin to Dial's , to generate smooth potential-based paths while avoiding local minima in grid representations. Hybrid approaches combine grid search with methods, such as refining grid paths via boundary-value solvers for precise avoidance.

Sampling-based methods

Sampling-based methods in motion planning are probabilistic algorithms that generate collision-free paths by randomly sampling points in the configuration (C-space) and constructing an approximate graph or representation of the free (C_free). These approaches are particularly effective for high-dimensional problems where exhaustive search is infeasible, as they avoid discretizing the entire and instead focus on exploring feasible regions through random exploration. By leveraging local planners to connect samples, they build a roadmap or that can be queried for paths between start and goal configurations. The Probabilistic Roadmap (PRM) method, introduced by Kavraki et al., operates in two phases: a preprocessing phase where nodes are uniformly sampled in C_free, and a query phase where paths are found by searching the resulting graph. In the preprocessing phase, a set of N random configurations q1,q2,…,qNq_1, q_2, \dots, q_N are generated in C-space, retaining only those that lie in C_free after collision checking. Edges are then added between nearby nodes: specifically, an edge exists between qiq_i and qjq_j if ∥qi−qj∥<ϵ\|q_i - q_j\| < \epsilon (for some connection radius ϵ\epsilon) and the straight-line path between them is collision-free, verified using a local planner. For query resolution, the start and goal configurations are added to the graph, connected to nearby nodes, and a search (e.g., A* or Dijkstra) finds a path if one exists. This graph approximates the connectivity of C_free, with denser sampling improving coverage. In contrast to PRM's global preprocessing, the Rapidly-exploring Random Tree (RRT) algorithm, developed by LaValle, builds an exploration tree incrementally from the start configuration qstartq_{start} without a separate query phase, making it suitable for single-query planning. The process begins with the tree containing only qstartq_{start}. For each iteration, a random configuration qrandq_{rand} is sampled uniformly in C-space. The nearest node qnearq_{near} in the tree to qrandq_{rand} is found, and a local planner extends from qnearq_{near} toward qrandq_{rand} by a fixed step size to produce qnewq_{new}, which is added to the tree if collision-free. This biased exploration toward unoccupied regions ensures rapid coverage of C_free, with the goal reached when a node is sufficiently close to qgoalq_{goal}. RRT is probabilistically complete, meaning the probability of finding a solution (if one exists) approaches 1 as the number of samples n→∞n \to \infty. Variants of these methods address specific limitations. RRT-Connect extends RRT bidirectionally by growing two trees simultaneously—one from qstartq_{start} and one from qgoalq_{goal}—and connecting them when their branches meet, significantly reducing planning time in practice. For optimality, Informed RRT* builds on RRT* (an asymptotically optimal variant of RRT) by focusing sampling within an ellipsoidal heuristic derived from the current best path cost, enabling anytime convergence to optimal solutions while maintaining probabilistic completeness. These variants inherit the asymptotic properties of their base algorithms, succeeding with probability approaching 1 as iterations increase. Despite their strengths, sampling-based methods face challenges in regions of C_free with low volume, such as narrow passages, where uniform sampling rarely places nodes, leading to inefficient exploration or failure to connect components. To mitigate this, specialized local planners are often used, such as for non-holonomic systems (e.g., car-like robots) that respect curvature constraints instead of straight lines. Performance-wise, constructing the PRM graph typically requires O(n log n) time for n samples when using efficient nearest-neighbor data structures like k-d trees, with collision checks dominating in high dimensions. These methods scale well to systems with up to 100 degrees of freedom (DOF), as demonstrated in applications like humanoid robot manipulation.

Optimization and potential field methods

Optimization-based and potential field methods in motion planning generate smooth, collision-free trajectories by formulating the problem as a continuous optimization task or by navigating through artificial force fields, contrasting with discrete graph searches. These approaches are particularly suited for real-time applications where dynamic environments require reactive, gradient-driven motion. They often operate in configuration space, producing paths that can be converted to trajectories with velocity and acceleration profiles. Artificial potential field methods treat the robot's configuration qq as a particle moving under the influence of virtual forces derived from a total potential function U(q)U(q). The potential is composed of an attractive component Uatt(q)=12∥q−qgoal∥2U_{\text{att}}(q) = \frac{1}{2} \| q - q_{\text{goal}} \|^2, which pulls the robot toward the goal configuration qgoalq_{\text{goal}}, and a repulsive component Urep(q)=12η(1d(q,O)−1ρ0)2U_{\text{rep}}(q) = \frac{1}{2} \eta \left( \frac{1}{d(q, O)} - \frac{1}{\rho_0} \right)^2 if d(q,O)<ρ0d(q, O) < \rho_0, where d(q,O)d(q, O) is the distance to the nearest obstacle OO, η\eta is a positive gain, and ρ0\rho_0 is the influence radius of the repulsive field. The total potential is U(q)=Uatt(q)+∑Urep(q)U(q) = U_{\text{att}}(q) + \sum U_{\text{rep}}(q), and the motion is generated by descending the negative gradient −∇U(q)-\nabla U(q) using gradient descent updates of the form q←q+ηFΔtq \leftarrow q + \eta F \Delta t, where the force F=−∇U(q)F = -\nabla U(q) and η\eta is a step size. This method, originally proposed for real-time obstacle avoidance in manipulators and mobile robots, enables reactive planning by continuously recomputing forces based on sensor data. A key advantage is its computational efficiency for real-time reactivity in dynamic settings, but it suffers from local minima traps, such as in U-shaped obstacles where the attractive and repulsive forces balance, halting progress toward the goal. Optimization-based methods frame motion planning as a nonlinear programming problem to minimize a cost functional subject to dynamics and collision constraints, yielding smoother trajectories than potential fields. A prominent example is CHOMP (Covariant Hamiltonian Optimization for Motion Planning), which optimizes a trajectory τ(t)\tau(t) by minimizing the integral cost ∫0Tc(τ(t),τ˙(t)) dt\int_0^T c(\tau(t), \dot{\tau}(t)) \, dt, where cc penalizes acceleration, velocity, and obstacle proximity, while enforcing dynamics and feasibility. CHOMP uses gradient-based optimization invariant to time reparametrization, making it effective for local refinement of initial paths into smooth, low-cost motions. Variants include Model Predictive Control (MPC), which solves receding-horizon optimizations to generate trajectories over a finite time window, replanning at each step for robustness to disturbances in robotic systems like autonomous vehicles. Sequential Quadratic Programming (SQP) approximates the nonlinear problem through iterative quadratic subproblems, enabling efficient handling of constraints in trajectory optimization for manipulators and mobile platforms. These methods excel in producing smooth paths in low-dimensional spaces, such as 2D or 6-DOF manipulation, but scale poorly to high dimensions without approximations.

Modern and Learning-Based Approaches

Reinforcement learning techniques

Reinforcement learning (RL) techniques address motion planning by enabling agents to learn policies through trial-and-error interactions with the environment, particularly in model-free settings where the dynamics are unknown. In these approaches, the state ss typically encompasses the robot's configuration qq, velocity, and obstacle information, while actions aa correspond to control inputs such as joint torques or velocities. Algorithms like Q-learning and Proximal Policy Optimization (PPO) have been adapted for motion tasks, allowing robots to discover collision-free paths without explicit geometric modeling. The core formulation models motion planning as a Markov Decision Process (MDP), where the agent seeks a policy π(a∣s)\pi(a|s) that maximizes the expected cumulative return. Rewards are often designed as r(s,a)=−d(s,g)−c⋅Icollision(s′)r(s,a) = -d(s, g) - c \cdot \mathbb{I}_{\text{collision}}(s'), with d(s,g)d(s, g) denoting the distance to the goal gg, cc a penalty coefficient, and I\mathbb{I} the collision indicator, encouraging progress while penalizing unsafe actions. The value function follows the Bellman equation for Q-learning variants: Q(s,a)=r(s,a)+γmax⁡a′Q(s′,a′)Q(s,a) = r(s,a) + \gamma \max_{a'} Q(s', a') where γ∈[0,1)\gamma \in [0,1) is the discount factor, and s′s' is the next state; this enables value iteration to converge to an optimal policy in discrete spaces, extended to continuous ones via deep approximations. Key algorithms include Deep Deterministic Policy Gradient (DDPG), introduced in 2015 for continuous action spaces in robotics, which combines actor-critic methods to handle high-dimensional control for tasks like robotic arm manipulation. More recently, RL has guided sampling-based planners, such as using learned biases in Rapidly-exploring Random Trees (RRT) to bias exploration toward promising regions, improving efficiency in cluttered environments post-2020. Surveys from 2024-2025 on RL for motion planning (RL-MoP) highlight efforts to mitigate sample inefficiency through hierarchical RL, which decomposes tasks into high-level goal selection and low-level trajectory execution, or model-based pre-training to initialize policies with simulated dynamics. Challenges persist, including the sim-to-real gap, where policies trained in simulation underperform on physical robots due to unmodeled friction and sensor noise, addressed via domain randomization. Safety during exploration is another hurdle, tackled through constrained MDPs that enforce hard limits on risk via Lagrangian penalties or shielding. Integration of RL often positions it for high-level decisions, such as selecting waypoints or modes, while delegating low-level motion to classical planners like potential fields for guaranteed smoothness. This hybrid approach leverages RL's adaptability in uncertain settings alongside deterministic guarantees.

Data-driven and neural network methods

Data-driven and neural network methods in motion planning leverage supervised learning techniques to approximate complex planning problems by training on datasets of expert-generated trajectories. These approaches typically involve collecting high-quality demonstrations from classical planners or human experts, then using neural networks to map input configurations—such as start states qstartq_{\text{start}}, goal states qgoalq_{\text{goal}}, and environmental maps—to feasible paths. For instance, neural motion planners can predict collision-free trajectories directly from sensor data and goal specifications, bypassing exhaustive geometric searches. This paradigm shifts the computational burden from online planning to offline training, enabling rapid inference in real-time applications like robotics and autonomous vehicles. Common architectures include convolutional neural networks (CNNs) for processing occupancy grids or image-based maps to predict free space and trajectory waypoints. Graph neural networks (GNNs) extend this by modeling scenes as graphs, where nodes represent obstacles or configurations and edges capture spatial relationships, allowing the network to propagate information for path prediction in structured environments. Post-2020 developments have incorporated transformers for sequence modeling, treating trajectories as ordered sequences and using self-attention mechanisms to capture long-range dependencies in dynamic scenes. These architectures are trained end-to-end on labeled trajectory data, often achieving sub-second planning times compared to seconds or minutes for traditional methods. A core formulation for these neural planners is a parameterized policy πθ(qstart,qgoal,map)≈\pi_\theta(q_{\text{start}}, q_{\text{goal}}, \text{map}) \approx optimal path, where θ\theta denotes the network weights, and the output is a sequence of waypoints approximating the expert trajectory. The policy πθ\pi_\theta is trained by minimizing the expected loss θ∗=arg⁡min⁡θE[L(πθ(qstart,qgoal,map),τ∗)]\theta^* = \arg\min_\theta \mathbb{E}[\mathcal{L}(\pi_\theta(q_{\text{start}}, q_{\text{goal}}, \text{map}), \tau^*)], where τ\tau is the predicted trajectory, τ∗\tau^* is the ground-truth expert path, and training minimizes a mean squared error (MSE) loss on trajectory points, often augmented with collision penalties. Variants of these methods emphasize imitation learning strategies, such as behavioral cloning (BC), which directly regresses expert actions from states, and dataset aggregation (DAgger), which iteratively collects corrective demonstrations to address distribution shift. In autonomous vehicle contexts, end-to-end planners integrate neural networks with model predictive control (MPC), using learned dynamics models to optimize trajectories while ensuring safety constraints. These approaches have demonstrated success in urban driving scenarios, generating smooth, human-like paths with minimal collisions. Recent advances, as surveyed in 2025, integrate deep neural networks with large language models (LLMs) for high-level planning queries, where LLMs decompose natural language instructions into subgoals that guide neural trajectory generation. Diffusion models have emerged for trajectory synthesis (2023–2025), probabilistically sampling diverse paths from noise conditioned on start-goal pairs and maps, offering improved handling of multi-modal environments over deterministic networks. These methods provide fast inference, often in milliseconds versus seconds for classical algorithms, enabling deployment in time-critical systems. However, they face challenges in generalization to unseen environments, requiring large diverse datasets to mitigate overfitting and covariate shift.

Task and motion planning integration

Task and motion planning (TAMP) integrates high-level symbolic task planning with low-level continuous motion planning to address complex, long-horizon robotic problems that require both discrete decision-making and geometric feasibility. In TAMP, problems are decomposed into a hierarchy where symbolic tasks—such as grasping or navigating—are represented using languages like the Planning Domain Definition Language (PDDL), while geometric motions ensure physical realizability in continuous spaces. This hybrid approach searches over a task-motion hierarchy, interleaving discrete planning to generate action sequences with continuous planning to validate and refine trajectories, enabling robots to handle environments with obstacles and manipulation constraints. Key components of TAMP frameworks include a discrete planner, such as the Fast-Forward (FF) heuristic search algorithm for generating task skeletons from PDDL specifications, interleaved with a continuous planner like Probabilistic Roadmap (PRM) for feasibility checks on motions. The integration often proceeds iteratively: the discrete planner proposes symbolic actions with parameters (e.g., object locations), which the continuous planner evaluates by sampling collision-free paths; failures refine the search by pruning infeasible branches. Optimization in these frameworks typically minimizes a hybrid cost function, defined as the sum of discrete task costs (e.g., action durations) and continuous motion lengths (e.g., path integrals), often represented and solved using AND/OR graphs to decompose the search space into alternative subplans. Prominent algorithms in TAMP include PDDLStream (2019), which extends PDDL with stream-based sampling to integrate symbolic planners and blackbox solvers like motion planners, reducing the need for full discretization by lazily generating continuous solutions during search. Recent advancements, highlighted in 2024 surveys, incorporate large language models (LLMs) for language-guided TAMP, such as LLM3, where pre-trained models like GPT-4 propose and refine action sequences informed by natural language instructions, bridging high-level goals with motion primitives. Challenges in TAMP persist, particularly in scaling to long-horizon tasks due to the exponential growth in search spaces from combining discrete and continuous dimensions, and in grounding symbolic representations to precise geometry amid perceptual uncertainties. Developments in the 2020s have emphasized bimanual and mobile manipulation scenarios, with frameworks like HRL4IN leveraging hierarchical reinforcement learning (RL) to learn reusable task primitives that accelerate motion feasibility checks. Additionally, RL integration has focused on learning heuristics for backjumping in search trees, improving efficiency for contact-rich tasks without sacrificing probabilistic completeness.

Analysis and Properties

Probabilistic completeness and optimality

In motion planning, resolution completeness refers to the property of grid-based algorithms that guarantees finding a solution if one exists, provided the grid resolution is sufficiently fine relative to the problem's clearance requirements. This form of completeness arises from discretizing the configuration space into a lattice, where finer grids approximate continuous spaces more accurately, ensuring that narrow passages are navigable once the cell size falls below a critical threshold determined by obstacle geometry. For instance, algorithms like A* on uniform grids achieve this by exhaustively searching the discrete graph, converging to a valid path as resolution increases, though they may fail at coarse resolutions due to discretization errors. Probabilistic completeness (PC) provides a weaker but more practical guarantee for sampling-based planners in high-dimensional spaces, stating that the probability of failure approaches zero as the computation time or number of samples tends to infinity, assuming a solution exists and the free space has positive measure. Pioneered in the Probabilistic Roadmap Method (PRM), this property holds because random sampling densely covers the configuration space over iterations, with collision checks ensuring valid connections in the roadmap graph. Similarly, the Rapidly-exploring Random Tree (RRT) algorithm exhibits PC by incrementally growing a tree from the start configuration toward the goal, probabilistically exploring the space through biased sampling and steering, though it may require extensions like RRT-Connect for bidirectional search to improve efficiency. In practice, PC implies high success rates in benchmarks, but failure probability decays exponentially with samples only under uniform sampling assumptions. For motion planning under uncertainty, such as partial observability or stochastic dynamics, probabilistic completeness extends to belief space—the space of probability distributions over possible states—where planners sample and propagate beliefs to account for estimation errors. In this setting, PC ensures that the probability of finding a feedback policy that maintains beliefs within safe bounds approaches one as sampling increases, provided the belief space is continuous and the uncertainty model allows measurable coverage. Algorithms like Feedback-based Information Roadmaps (FIRM) achieve this by constructing roadmaps in belief space, discretizing distributions (e.g., via particles or Gaussians) and verifying reachability under maximum likelihood observations, thus handling real-world robotics scenarios with sensor noise. This extension is crucial for tasks like localization-aware navigation, where state-space PC would fail due to unmodeled uncertainties. Optimality in motion planning addresses not just existence but the quality of solutions, with asymptotic optimality (AO) being a key guarantee for advanced sampling-based methods: as computation time approaches infinity, the cost of the returned path converges almost surely to the optimal cost c∗c^*. This is formalized by refining a search graph (e.g., roadmap or tree) until the path cost from start qstartq_\text{start} to goal qgoalq_\text{goal} satisfies cost(qstart,qgoal)≤c∗(1+ϵ)\text{cost}(q_\text{start}, q_\text{goal}) \leq c^* (1 + \epsilon) for any ϵ>0\epsilon > 0, achieved through rewiring to minimize edge costs during expansion. cost(qstart,qgoal)≤c∗(1+ϵ)\text{cost}(q_\text{start}, q_\text{goal}) \leq c^* (1 + \epsilon) Such convergence relies on dense sampling and informed selection, as in RRT*, which extends RRT by adding a cost-optimizing rewiring step after each insertion, or FMT*, which uses a batch-sampling approach with dynamic programming to propagate optimal costs across a grid-like witness set. Anytime optimality builds on AO by allowing interruption at any time, returning progressively better solutions without restarting, making these planners suitable for time-constrained real-time applications. Evaluation of these properties often relies on metrics like success rate (fraction of solved instances within time budgets) and path quality, measured by length, smoothness (e.g., or jerk), or relative to optimal. Benchmarks such as those generated by MotionBenchMaker provide standardized datasets for manipulation tasks, enabling comparisons across planners. These metrics highlight trade-offs, as AO planners like FMT* may require more than PC variants but yield superior trajectories in high-impact applications like autonomous manipulation. Recent advances as of 2025 have extended these properties to learning-based methods, such as neural network-guided sampling and tensor-based , which maintain probabilistic completeness and asymptotic optimality while improving efficiency in high-dimensional and dynamic environments.

Computational complexity

The motion problem is known to be PSPACE-hard, even for in three-dimensional environments with polygonal obstacles. This hardness arises from the need to explore a configuration space that can encode complex computational problems, such as simulating Turing machines through path configurations. Early algorithms for solving the problem exhibited doubly exponential time complexity in the number of (DOF), stemming from the in the arrangement of configuration space obstacles. Optimal motion planning, which seeks the shortest or minimal-cost path, is NP-hard even in relatively simple cases, such as finding the shortest path for a translating amid polyhedral obstacles in 3D. In contrast, sampling-based methods offer more tractable alternatives, with graph construction in probabilistic roadmaps typically requiring O(n \log n) time for n milestones, leveraging efficient nearest-neighbor searches in low dimensions. Grid-based methods, while complete under sufficient resolution, incur of O(r^d), where r is the grid resolution and d is the configuration space dimension, leading to rapid growth that limits their applicability beyond low dimensions. High-dimensional problems, such as planning for robotic arms with 100 DOF, exacerbate these challenges due to the curse of dimensionality, where exhaustive becomes infeasible. Anytime algorithms address this by performing incremental computation, providing initial suboptimal solutions quickly and refining them over time to balance completeness with practicality. Empirical benchmarks demonstrate that sampling-based planners scale effectively to higher dimensions, outperforming exact methods in cluttered environments. To enable real-time performance, trade-offs favor suboptimal planners like greedy variants of rapidly-exploring random trees (RRT), which prioritize speed over global optimality while maintaining probabilistic completeness in expansive spaces.

Problem Variants

Dynamic and differential constraints

Motion planning under dynamic and differential constraints extends classical geometric planning by incorporating the physical limitations of robotic systems, such as velocity bounds, acceleration limits, and non-holonomic behaviors that restrict instantaneous motion directions. Kinematic constraints primarily address velocity limits and directional restrictions, ensuring that planned paths respect the robot's inability to move sideways or instantaneously change orientation. For car-like robots, which model vehicles with a minimum turning radius due to fixed wheelbases, optimal paths under these constraints are well-characterized by Dubins paths for forward-only motion and Reeds-Shepp paths when reversing is allowed. Dubins paths, introduced in 1957, consist of at most three segments—straight lines and circular arcs of fixed radius—connecting initial and final poses while minimizing length. Reeds-Shepp paths, from 1990, extend this to include backward motions, yielding up to 48 possible path types but typically fewer for optimality, enabling maneuvers like parking in tight spaces. A example of non-holonomic kinematic constraints arises in car-like or models, where the robot's is aligned with its heading. The differential equations governing such motion are: x˙=vcos⁡θ,y˙=vsin⁡θ,θ˙=ω,\begin{align*} \dot{x} &= v \cos \theta, \\ \dot{y} &= v \sin \theta, \\ \dot{\theta} &= \omega, \end{align*} with vv as linear and ω\omega as , both bounded by the system's capabilities; feasible paths must satisfy conditions derived from these equations, ensuring despite the constraints. These constraints reduce the controllable compared to holonomic systems, requiring paths that accumulate orientation changes through curvature rather than direct translation. Dynamic constraints introduce full equations of motion, modeled as x˙=f(x,u)\dot{\mathbf{x}} = f(\mathbf{x}, \mathbf{u}) where x\mathbf{x} is the state (position, velocity, etc.) and u\mathbf{u} lies in a compact control set, capturing inertia, forces, and torques. Kinodynamic planning addresses these by synthesizing trajectories that obey both kinematic and dynamic laws, often treating the problem as optimal control under differential constraints. Algorithms for kinodynamic planning include lattice planners, which discretize the state space into a graph of precomputed motion primitives—short, feasible trajectory segments under discrete controls—allowing efficient search via A* or similar methods while approximating continuous dynamics. For instance, lattice planners generate symmetric, repeating control sequences offline, enabling real-time planning in dynamic environments by evaluating swept volumes for collision avoidance. Sampling-based methods like Rapidly-exploring Random Trees (RRT) adapt to dynamics by integrating controls via (ODE) solvers to propagate states forward in time, ensuring collision-free branches that respect the dynamics model. The Kinodynamic RRT* variant, from , extends this to asymptotic optimality by rewiring with optimal local controls, suitable for linear differential constraints. Challenges in these approaches include distinguishing feasible sets (states satisfying constraints) from reachable sets (states attainable from the ), as dynamics may permit theoretically possible but practically inaccessible configurations due to control bounds. Time-optimal control under dynamics often invokes Pontryagin's minimum principle, which provides necessary conditions for optimality by minimizing the Hamiltonian along trajectories, guiding bang-bang control strategies for minimal-time paths. Variants of these constraints appear in underactuated systems, where the number of control inputs is fewer than the , such as quadrotor drones with four rotor thrusts controlling six-dimensional pose (three translational, three ). In such cases, planning must exploit coupling between translation and , often using to generate feasible paths in the reduced control space while avoiding obstacles. These systems highlight the need for holistic state-space exploration, as underactuation limits direct control over all axes, necessitating indirect maneuvers like tilting for lateral motion.

Uncertainty and environmental factors

Motion planning under uncertainty addresses challenges arising from imperfect information, such as noise and partial of the environment, which can lead to unreliable state estimates and potential collisions during execution. In robotic systems, sensor measurements often include , particularly in localization tasks where position estimates are corrupted by , degrading the accuracy of path trajectories in cluttered or dynamic settings. To model such partial observability, Partially Observable Markov Decision Processes (POMDPs) are employed, representing the robot's state as a belief distribution b(q)b(q) over possible configurations qq, which encapsulates epistemic about the true state. In POMDPs for motion planning, the belief state is updated using a Bayes filter upon receiving an zz after action aa, given by the equation: b′(q′)=∑qO(z∣q′)T(q′∣q,a)b(q)b'(q') = \sum_{q} O(z \mid q') T(q' \mid q, a) b(q) where O(z∣q′)O(z \mid q') is the observation likelihood and T(q′∣q,a)T(q' \mid q, a) is the transition probability; this update propagates through the horizon, enabling decisions that hedge against possible worlds. For moving obstacles, which introduce temporal variability and prediction errors, methods like Velocity Obstacles (VO) compute collision-free velocities by mapping relative motions into a velocity space, avoiding sets that lead to intersections within a time horizon. An extension, Optimal Reciprocal Collision Avoidance (ORCA), assumes cooperative agents and selects velocities that reciprocally guarantee safety by taking half the responsibility for evasion, scaling efficiently to multiple dynamic entities. Receding horizon complements these by repeatedly optimizing short-term trajectories while accounting for predicted obstacle motions, re- at each step to adapt to updates. Specific algorithms mitigate these uncertainties: Rapidly-exploring Random Trees (RRBT) extend sampling-based methods like RRT into , growing trees over distributions to find feasible plans under partial , with asymptotic optimality in continuous domains. Chance-constrained optimization formulates safety as probabilistic guarantees, solving for trajectories where the probability of collision P(collision)≤δP(\text{collision}) \leq \delta (e.g., δ=0.01\delta = 0.01) using convex approximations or scenario optimization, ensuring robustness without over-conservatism. Environmental factors like deformable objects and wind further complicate planning by altering geometry or applying stochastic forces mid-execution. For deformable objects, such as in surgical , uncertainty propagates through non-rigid interactions, requiring belief-space planners that sample over possible deformations to maintain margins. Wind disturbances in aerial systems introduce additive perturbations to dynamics, modeled as Gaussian processes, necessitating online replanning to correct deviations; the Dynamic Window Approach (DWA) evaluates admissible velocity windows in real-time, selecting controls that maximize progress while respecting acceleration limits and predicted environmental shifts. Recent advancements integrate (RL) techniques for robust motion planning in uncertain environments, such as learning policies for aerial vehicles in windy conditions.

Multi-agent and hybrid systems

Multi-agent motion planning extends single-agent problems to scenarios involving multiple robots or entities that must coordinate to achieve collision-free paths while satisfying individual goals. In centralized approaches, the joint configuration space is searched holistically, defined as Cjoint=C1×C2×⋯×CnC_{\text{joint}} = C_1 \times C_2 \times \cdots \times C_n, where CiC_i is the configuration space of agent ii, and collision avoidance requires that the distance between any pair of configurations qiq_i and qjq_j exceeds a safety threshold for all i≠ji \neq j. A prominent centralized method is Conflict-Based Search (CBS), which optimally resolves conflicts by building a conflict tree and replanning individual paths iteratively, achieving completeness and optimality in discrete spaces but scaling poorly with agent count due to exponential search complexity. Decoupled methods, such as prioritized , address by sequencing agents according to a priority order, where higher-priority agents plan first without considering others, and lower-priority ones treat predecessors as dynamic obstacles. This approach reduces computational demands but risks suboptimal solutions or deadlocks, where agents block each other indefinitely in constrained environments. Coordination mechanisms enhance planning; for instance, communication protocols allow agents to exchange intentions in real-time, while auction-based task allocation dynamically assigns goals to minimize conflicts in heterogeneous teams. Algorithms like Multi-RRT extend sampling-based methods to multi-agent settings by growing trees in the joint space or coordinating individual RRTs with conflict checks, enabling efficient exploration in continuous high-dimensional environments. Hybrid systems introduce discrete mode switches alongside continuous dynamics, such as a transitioning between walking and driving modes, modeled using hybrid automata that capture guarded transitions between continuous subspaces. These automata represent the system's evolution through discrete events triggering mode changes, ensuring reachability analysis accounts for both and switching constraints. Motion planning in such systems often employs mixed-integer programming (MIP), formulating discrete choices as binary variables within an optimization framework to jointly solve for trajectories and mode sequences, as seen in formulations minimizing subject to collision and dynamics constraints. Challenges include exponential state growth from the product of mode combinations and deadlocks during transitions, exacerbated in multi-agent hybrids where inter-agent coordination must synchronize modes. In the 2020s, developments have emphasized , where decentralized algorithms enable large-scale coordination without central control, drawing on bio-inspired flocking models for emergent collision avoidance. Heterogeneous teams, such as UAV-ground pairings, leverage complementary capabilities—e.g., aerial scouting informing ground —through layered that decouples high-level task allocation from low-level motion, improving efficiency in dynamic scenarios. These advances mitigate earlier issues via distributed computation, though they retain sensitivity to communication delays and partial akin to single-agent .

Applications

Robotics and manipulation

Motion planning is essential in robotics and manipulation, where it enables precise control of robotic arms, mobile platforms, and humanoid systems to perform tasks in cluttered or dynamic environments. For industrial robotic arms, inverse kinematics solvers are integrated with trajectory planning to execute pick-and-place operations while avoiding collisions in shared human-robot workspaces. Sampling-based methods like Probabilistic Roadmaps (PRM) and Rapidly-exploring Random Trees (RRT) generate feasible paths by constructing graphs in configuration space, ensuring obstacle clearance through collision checks. Optimization techniques such as CHOMP further refine these paths for smoothness, with simulations on 6-DOF arms like the ABB IRB 120 demonstrating path lengths of approximately 0.76 m and success rates up to 100% in dynamic obstacle scenarios using methods like CHOMP and RRT-connect. In mobile robotics, motion planning often incorporates (SLAM) for environment modeling, paired with Adaptive Monte Carlo Localization (AMCL) for pose estimation and A* for global to navigate indoor spaces efficiently. For locomotion, planners focus on whole-body coordination, generating footstep sequences and joint trajectories that maintain balance and avoid obstacles, as seen in modular frameworks that decompose complex motions into reusable action primitives. These approaches enable stable traversal over uneven terrain, with computation times under 500 ms for real-time execution on platforms, as demonstrated in frameworks achieving 73-82 ms per step. Manipulation tasks extend motion planning to include grasp synthesis and dual-arm coordination, where algorithms select contact points on objects before computing collision-free trajectories for transport or assembly. Grasp planning uses predefined databases of feasible poses, integrated with randomized inverse kinematics to achieve solutions in 60 ms for single-arm tasks and 278 ms for dual-arm re-grasping of objects like a . Task and Motion Planning (TAMP) bridges high-level sequencing—such as block-stacking to maximize tower height—with low-level optimization, employing mixed-integer linear programming (MILP) to handle discrete actions and continuous dynamics in tabletop scenarios. Seminal demonstrations occurred during the Robotics Challenge (2013–2015), where teams applied PRM variants for manipulation in disaster-response tasks, such as valve turning and debris clearance, highlighting the need for robust in unstructured settings. A 2024 survey on dynamic environment manipulators underscores advancements in learning-based planners like TD3, which adapt to moving obstacles with computation speeds around 0.015 s per trial, while faster methods like APF achieve 6.67 × 10^{-4} s. Challenges persist in contact-rich motions, exemplified by pushing tasks that model frictional interactions via optimization and semidefinite relaxations, yielding near-optimal plans in seconds for simulated push-box scenarios. Real-time integration with vision feedback requires hybrid force-position control to adjust trajectories based on updates, addressing uncertainties in object poses. Sampling methods like PRM facilitate implementation by probabilistically exploring high-dimensional spaces for these contacts. Evaluation metrics emphasize practicality, with cycle times measuring end-to-end task duration and success rates quantifying reliability in benchmarks like the Yale-CMU-Berkeley (YCB) object set. In YCB protocols, pick-and-place of household items achieves success rates often around 80% for rigid objects like mugs but lower for precise tasks like peg insertion under perturbations, providing standardized context for planner performance. As of 2025, learning-based methods have further integrated into applications like surgical for enhanced precision in unstructured anatomies.

Autonomous vehicles and navigation

Motion planning for autonomous vehicles (AVs) often employs a hierarchical approach to balance global route optimization with local reactive adjustments. In this framework, global planning utilizes algorithms like A* to generate efficient, high-level paths that consider overall goals such as reaching a destination while adhering to road networks. Local planning then refines these paths using artificial potential fields (APF), which treat obstacles as repulsive forces and goals as attractive forces to enable real-time collision avoidance in dynamic environments. Behavior planning complements this by incorporating finite state machines (FSMs) to manage discrete maneuvers, such as lane changes, where states represent modes like "maintain lane," "check gap," or "execute merge," transitioning based on sensor data and traffic rules. A key aspect of AV trajectory generation is minimizing jerk—the third of position—to ensure passenger comfort and smooth control inputs. This is typically formulated as an to minimize the of squared jerk, ∫∣∣τ¨(t)∣∣2 dt\int ||\ddot{\tau}(t)||^2 \, dt, subject to constraints like limits, bounds, and traffic regulations. For example, and systems integrate (MPC) for , where MPC predicts future states over a receding horizon and solves constrained optimizations to generate feasible paths that incorporate and environmental interactions. In unmanned aerial vehicles (UAVs) and drone swarms, motion planning extends to three-dimensional spaces, emphasizing that accounts for disturbances and ensures collision-free paths in cluttered . Optimization techniques model as dynamic forces in the cost function, adjusting velocities and headings to maintain stability while minimizing . Recent surveys highlight sampling-based methods for real-time 3D planning, where variants of rapidly-exploring random trees (RRT) generate diverse trajectories that avoid static and moving obstacles in urban or cooperative swarm scenarios. In applications, RRT variants like RRT* provide asymptotically optimal paths by rewiring trees to shorten distances, enabling high-speed navigation through gates under tight timing constraints. Advancements in data-driven methods have transformed AV planning, with 2025 reviews emphasizing the integration of (RL) and neural networks to learn policies from vast datasets of driving scenarios. These approaches enable end-to-end systems that process raw inputs directly into control outputs, bypassing modular pipelines for more adaptive behavior in unstructured environments. RL agents, for instance, optimize long-term rewards for safe merging or by simulating interactions with simulated traffic. Significant challenges persist in achieving high-frequency real-time performance while handling uncertainty from dynamic elements. Motion planners must incorporate probabilistic models to predict trajectories and maintain safety margins, often using sampling for robust path evaluation. Vehicle-to-everything (V2X) communication addresses multi-agent coordination by sharing intent and state data among AVs, reducing collision risks in dense traffic through decentralized .

References

  1. https://msl.cs.illinois.edu/~lavalle/papers/Lav11b.pdf
  2. https://modernrobotics.northwestern.edu/nu-gm-book-resource/10-1-overview-of-motion-planning/
  3. https://ieeexplore.ieee.org/document/10271531
  4. https://www.sciencedirect.com/science/article/pii/S2667379724000652
  5. https://arxiv.org/html/2404.02817v1
  6. https://ietresearch.onlinelibrary.wiley.com/doi/10.1049/iet-csr.2018.0003
  7. https://msl.cs.uiuc.edu/planning/bookbig.pdf
  8. https://www.ri.cmu.edu/publications/principles-of-robot-motion-theory-algorithms-and-implementations/
  9. http://gamma.cs.unc.edu/courses/robotics-f08/PAPERS/latombe99.pdf
  10. https://www.sciencedirect.com/science/article/pii/036083529090034J
  11. https://dl.acm.org/doi/10.1145/359156.359164
  12. https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.3160360305
  13. https://ieeexplore.ieee.org/document/508439
  14. https://msl.cs.illinois.edu/~lavalle/papers/Lav98c.pdf
  15. https://journals.sagepub.com/doi/10.1177/0278364911406761
  16. http://www.ieee-ras.org/algorithms-for-planning-and-control-of-robot-motion
  17. https://wafr2022.github.io/
  18. https://arxiv.org/abs/2006.06469
  19. https://arxiv.org/abs/2510.00182
  20. https://lis.csail.mit.edu/pubs/tlp/spatial-planning.pdf
  21. https://lavalle.pl/planning/node123.html
  22. http://ottelab.com/html_stuff/pdf_files/Bialkowski.Otte.ea.IJRR16.pdf
  23. https://lavalle.pl/planning/node373.html
  24. https://lavalle.pl/planning/book.pdf
  25. https://manipulation.csail.mit.edu/trajectories.html
  26. https://dl.acm.org/doi/10.1145/359104.359110
  27. https://www.sciencedirect.com/science/article/pii/0734189X84901302
  28. https://lavalle.pl/planning/node371.html
  29. https://ieeexplore.ieee.org/document/508439/
  30. https://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/PRM/prmbasic_01.pdf
  31. https://ieeexplore.ieee.org/document/844730/
  32. https://www.ri.cmu.edu/pub_files/2014/9/TR-2013-JDG003.pdf
  33. https://arxiv.org/abs/1105.1186
  34. http://www.neil.dantam.name/papers/li2023sdcl.pdf
  35. https://users.cs.duke.edu/~reif/paper/sunz/bridge/bridge.pub.pdf
  36. https://www.cs.cmu.edu/~motionplanning/lecture/Chap7-Prob-Planning_howie.pdf
  37. https://arxiv.org/pdf/2503.23650
  38. https://onlinelibrary.wiley.com/doi/abs/10.1155/int/1636497
  39. https://arxiv.org/abs/1509.02971
  40. https://ieeexplore.ieee.org/document/11167911/
  41. http://rl.cs.rutgers.edu/publications/LiamICRA2022.pdf
  42. https://arxiv.org/abs/2502.13187
  43. https://arxiv.org/html/2505.17342v1
  44. https://arxiv.org/abs/2303.13986
  45. https://arxiv.org/abs/2006.06248
  46. https://digital-library.theiet.org/doi/full/10.1049/csy2.12020
  47. https://www.researchgate.net/publication/359793852_End-to-End_Learning_of_Autonomous_Vehicle_Lateral_Control_via_MPC_Training
  48. https://www.nature.com/articles/s42256-025-01036-4
  49. https://www.bigai.ai/wp-content/uploads/2024/10/IROS24_LLMPlanning.pdf
  50. https://edplab.org/wp-content/uploads/2014/06/FIRM_ICRA_2012.pdf
  51. https://arxiv.org/abs/1306.3532
  52. https://arxiv.org/abs/2112.06402
  53. https://arxiv.org/abs/2411.19393
  54. https://www.researchgate.net/publication/370684799_Survey_of_optimal_motion_planning
  55. https://users.cs.duke.edu/~reif/paper/movers.pdf
  56. https://users.cs.duke.edu/~reif/paper/canny/NPpath.paper/path.pdf
  57. https://www.cse.lehigh.edu/~trink/Courses/RoboticsII/reading/karaman_sampling-based-optimal-motion-planning.pdf
  58. http://gamma.cs.unc.edu/ITOMP/hierarchical.pdf
  59. https://www.researchgate.net/publication/341899103_Sampling-Based_Motion_Planning_on_Sequenced_Manifolds
  60. https://users.cs.duke.edu/~brd/papers/src-papers/jacm-final.pdf
  61. https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-145/issue-2/Optimal-paths-for-a-car-that-goes-both-forwards-and/pjm/1102645450.full
  62. https://www.jstor.org/stable/2372560
  63. https://www.ri.cmu.edu/pub_files/2009/5/pivtoraiko_kelly_icra09.pdf
  64. https://arxiv.org/pdf/1205.5088
  65. https://robotics.cs.unc.edu/publications/vandenBerg2011_ISRR.pdf
  66. https://homes.cs.washington.edu/~bboots/files/GPMP.pdf
  67. https://www.ri.cmu.edu/pub_files/pub4/roy_nicholas_2003_1/roy_nicholas_2003_1.pdf
  68. https://people.eecs.berkeley.edu/~pabbeel/cs287-fa13/slides/pomdps.pdf
  69. http://www.liralab.it/IIT_school/files/Papers/ijrr95.pdf
  70. https://gamma.cs.unc.edu/ORCA/publications/ORCA.pdf
  71. https://groups.csail.mit.edu/rrg/papers/abry_icra11.pdf
  72. https://web.stanford.edu/~pavone/papers/Ono.Pavone.ea.AURO14.pdf
  73. https://pmc.ncbi.nlm.nih.gov/articles/PMC4096573/
  74. https://www.ri.cmu.edu/pub_files/pub1/fox_dieter_1997_1/fox_dieter_1997_1.pdf
  75. https://www.sciencedirect.com/science/article/pii/S0957417423006486
  76. https://www.sciencedirect.com/science/article/pii/S0004370214001386
  77. https://parasollab.web.illinois.edu/publications/papers/solis-ral-21.pdf
  78. https://www2.cs.sfu.ca/~hangma/pub/aaai19a.pdf
  79. https://www.cs.utexas.edu/~pstone/Papers/bib2html-links/smg.pdf
  80. http://michalcap.net/wp-content/papercite-data/pdf/cap_2013_c.pdf
  81. https://www.kavrakilab.org/publications/bhatia-kavraki2010motion-planning-with.pdf
  82. https://www.sciencedirect.com/science/article/abs/pii/S1367578820300754
  83. https://www.frontiersin.org/journals/robotics-and-ai/articles/10.3389/frobt.2023.1134841/full
  84. https://www.mdpi.com/2075-1702/12/3/200
  85. https://journals.sagepub.com/doi/10.1177/0278364914530482
  86. https://onlinelibrary.wiley.com/doi/10.1155/2024/5969512
  87. https://www.sciencedirect.com/science/article/pii/S095741742300756X
  88. http://crlab.cs.columbia.edu/humanoids_2018_proceedings/media/files/0041.pdf
  89. https://www.interact.kit.edu/downloads/Humanoid_Motion_Planning_for_Dual-Arm_Manipulation_and_Re-Grasping_Tasks.pdf
  90. https://repository.library.northeastern.edu/files/neu:cj82qh18r/fulltext.pdf
  91. https://arxiv.org/abs/2502.02829
  92. https://www.ri.cmu.edu/app/uploads/2019/03/ICRA19Hybrid.pdf
  93. https://arxiv.org/pdf/1502.03143
  94. https://arxiv.org/html/2501.02116v1
  95. https://arxiv.org/abs/2402.04769
  96. https://ieeexplore.ieee.org/document/10103224/
  97. https://link.springer.com/article/10.1007/s43684-021-00015-x
  98. https://arxiv.org/pdf/2112.02133
  99. https://www.sciencedirect.com/science/article/abs/pii/S0968090X2200105X
  100. https://www.mdpi.com/2504-446X/9/3/194
  101. https://www.rairo-ro.org/articles/ro/pdf/2024/04/ro220216.pdf
  102. https://arxiv.org/html/2301.01755v4
  103. https://ieeexplore.ieee.org/iel8/6287639/10820123/10930422.pdf
  104. https://arxiv.org/html/2408.03601v1
  105. https://arxiv.org/html/2406.02916v1
  106. https://www.researchgate.net/profile/Ziran-Wang-6/publication/348430322_Motion_Estimation_of_Connected_and_Automated_Vehicles_under_Communication_Delay_and_Packet_Loss_of_V2X_Communications/links/5ffe9e62299bf140888fa2eb/Motion-Estimation-of-Connected-and-Automated-Vehicles-under-Communication-Delay-and-Packet-Loss-of-V2X-Communications.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.