The State of Robot Motion Generation

Motion planning aims to identify a path with minimal cost, such as the shortest path or the fastest trajectory that brings a robot to a desirable goal state, without undesirable collisions, given a fully-observable world model.

Search-based Approaches: Uninformed search methods, such as Uniform Cost Search (UCS) or Dijkstra’s algorithm [1], can compute optimal paths over a discrete representation of the state space in the form of a grid or a graph given a cost function. Informed alternatives, such as A^∗ [2], utilize heuristic cost-to-go estimates from each state to accelerate solution discovery and can still return the optimum solution over the discrete representation for an admissible/consistent heuristic. Due to the comprehensive nature of search and the discrete representation, search methods suffer from the curse of dimensionality, i.e., the possible states to be explored grow exponentially with dimensions, rendering them computationally infeasible for many robotics problems given naïve discretizations. There have been many successful applications of search methods in robotics, however, such as planning for autonomous vehicles [3] and single or dual arm planning [4].

Sampling-based Motion Planners (SBMPs): Sampling provides graph-based representations for searching the collision-free subset of a robot’s state space in a more scalable manner than grids. The Probabilistic Roadmap Method (PRM) [5] samples collision-free configurations as nodes of a roadmap, and collision-free local paths define the edges. The roadmap can then be used to solve multiple queries via search. For specific queries, the Rapidly Exploring Random Tree (RRT) [6] generates a tree data structure rooted in the robot’s start state to quickly explore the free state space until it reaches the goal’s vicinity. RRT does not require a “steering function”, i.e., the ability to perfectly connect two robot states, a primitive required by other methods, allowing it to deal with dynamical systems where “steering functions” are unavailable. PRM and RRT are provably suboptimal, and asymptotically optimal variants (PRM*, RRT*) [7] guarantee that the discovered paths converge to optimal ones as sampling progresses. Recent planners [8] [9] also achieve asymptotic optimality for kinodynamic problems. SBMPs have been applied to autonomous driving [10] and manipulation [11]. The Open Motion Planning Library (OMPL) provides software implementations for most SBMPs [12].

Optimization-based Approaches: The above methods are comprehensive and aim to explore the entire feasible state space, which can lead to increased solution times. Moreover, their basic instances don’t utilize gradient information. The alternative is to locally optimize paths or trajectories for robotic systems given an objective function under physical or operational limits, such as collision avoidance and control bounds. Covariant Hamiltonian Optimization for Motion Planning (CHOMP) [13] demonstrated this principle by iteratively optimizing paths by reducing collision and trajectory costs. TrajOpt [14] utilizes sequential convex optimization and progressively ensures that each iteration produces feasible and collision-free trajectories. k-Order Markov Optimization (KOMO) [15] treats trajectory optimization as a sparse nonlinear program and tries to address high-dim. problems by leveraging sparsity in dynamics and constraints. Factor graphs, a graphical optimization tool rooted in state estimation, and least-squares optimization can be also used for trajectory optimization [16]. A recent approach, the Graph of Convex Sets [17], combines optimization and SBMPs. It builds a graphical structure where nodes are convex regions of the free space, and optimization finds a trajectory over the set of nodes that connects the start with the goal. When optimization techniques work, they tend to find high-quality solutions fast. They can suffer, however, from local minima, which arise from the nonlinear and non-convex nature of robotics problems.

Machine Learning (ML) for Planning: ML can be used to improve the computational efficiency of planning [18]. Some approaches focus on planning components, such as effective sampling [19], avoiding collisions [20], or distance metrics [21]. ML can also determine which combination of methods is best suited for a particular problem [22], or when a solution is not feasible [23]. Neural Motion Planning (NMP) [24] employs neural networks to approximate a planner’s operation typically given data from a simulator. An encoder processes environmental data, like point clouds, to create a compact latent space representation. Then, a planning network predicts the robot’s next configuration based on its current state, the goal state and the encoded environment.

TAMP methods target long-horizon and multi-step robotic tasks, which may include moving through a sequence of goals or manipulating the environment [25]. TAMP methods typically define low-level operators with motion constraints and high-level logical relationships between the operators. Operators can contain hybrid discrete and continuous parameters, motion constraints, preconditions, and effects, which make use of manually defined lifted variables. Planning is then performed via search across these lifted states. Possible state transitions are operators with satisfied preconditions, resulting in a sequence of operators called a plan skeleton. The hybrid parameters in the plan skeleton (e.g., start and goals) must be solved along with the low level operator trajectories. TAMP techniques can be categorized by the order they sequence and satisfy operators [25]: Sequencing first [26] defines a plan skeleton, i.e., a sequence of operators without satisfying their preconditions; this can cause frequent infeasible plans due to the lifted variables not being descriptive enough of underlying constraints. Satisfying first trajectories for operators, then planning with them, can solve this problem, but can spend time creating useless satisfied operators due to not having a plan skeleton to direct search [27]. Interleaved sequencing and satisfying methods can provide a mix of both by checking low-level information for feasibility during task planning [28]. TAMP critically relies on engineering to define preconditions and effects that properly characterize operator behavior and expressive lifted variables. Basic TAMP approaches also struggle under partial observability and uncertainty, which is the focus of recent efforts [29].

The above methods assume a deterministic, perfect world model. Sensing noise and inaccurate execution introduces uncertainty, however, and the need to generate robust motions to such disturbances. If these noise sources can be modeled probabilistically, (Partially Observable) Markov Decision Processes (PO)MDPs provide a formulation to reason about uncertainty. A Markov Decision Process (MDP) consists of a set of states $S$, set of actions $A$, transition probabilities between states $T(s_{t+1}\mid s_{t},a_{t})$, and a reward function $R(s_{t},a_{t},s_{t+1})$. (PO)MDPs employ belief distributions for the problem representation, i.e., probability distribution over states given a set of observations $O$. They can be integrated with Bayesian state estimation (e.g., Kalman or particle filters) that return such beliefs. Solutions to (PO)MDPs are not nominal paths but policies that map beliefs to actions. Due to the consideration of uncertainty, computing an exact solution to a (PO)MDP is often computationally intractable [30], especially given the continuous state and action spaces of robotics.

This has motivated approximate solutions. The Successive Approximations of the Reachable Space under Optimal Policies (SARSOP) [31] applies point-based value iteration and offline sampling to focus on representative beliefs and determine the best action given the sampled set. Determinized Sparse Partially Observable Trees (DESPOT) [32] employ tree search online to compute the optimal action. Online methods can also perform policy search by using a controller in a limited search space, increasing scalability but not bounding solution quality [33]. Heuristic rules or assumptions can reduce complexity by ignoring long-term consequences and focus on immediate gains or most likely outcomes. For instance, Pre-image Back Chaining constructs state-action sequences (pre-images) leading backward from the goal [34]. Generalized Belief Space (GBS) planning dynamically adapts to ongoing sensing updates [35].

Instead of explicitly modeling uncertainty, control tightly integrates state estimation and motion generation in a closed-loop. Thus, it defines policies that are reactive to different possible outcomes that may be observed upon execution.

Low-level Controllers: Proportional Integral Derivative (PID) control and related tools are simple feedback strategies that are robust once tuned. They are ubiquitous for tracking desirable robot controls from higher-level motion generation processes. Path Tracking Controllers dynamically select controls given the latest state estimate to minimize path deviation. These controllers, however, are myopic and typically neither reason about the desired goal or obstacles.

Potential Functions and Operational Space Control: Potential functions [36] define attractive fields towards the goal and repulsive ones that push away from obstacles. Moving along the negative gradient of the sum of these fields provides the motion vector. Some engineering is needed to tune the parameters of the potentials. In complex environments, the corresponding potential may have multiple minima and goal convergence is not guaranteed. Navigation functions [37] are smooth and ensure a single minimum at the goal, but they are more complicated to design and can only be constructed for specific environments (i.e., sphere and star worlds). Such control policies do not have to be defined directly in the robot’s state space. Operational Space Control [38] defines such control laws in lower-dim. task spaces. For instance, if the task involves the robot’s end-effector, a control law is defined to move it towards a desired goal unencumbered by other robot constraints. Additional control laws can be defined so that links avoid collisions. The corresponding motion vectors for the individual links are then mapped and integrated to a state space motion for the robot via the pseudo-inverses of the robot’s Jacobian matrix, which relates robot joint velocities to link velocities through a linear transformation parameterized by the joint states. This allows for multi-level hierarchical control [39], where a hierarchy can be imposed over constraints, operational tasks, and soft objectives. Then, lower priority objectives are solved in the null space of higher priority ones once projected to the state space. These strategies rely on precise robot models and high-quality sensing to provide accurate feedback on robot state.

Linearization and Feedback-based Planning: Principles of linear control can be applied for robot motion generation. The Linear Quadratic Regulator (LQR) provides an optimal solution for linear time-invariant systems given a quadratic cost function as a control law of the form $u(t)=-K\cdot x(t)$, where $x(t)$ and $u(t)$ are respectively the system’s state and the control to be applied at time $t$. Most robots, however, are nonlinear and time-varying, while tasks involve complex, non-quadratic objectives. Feedback linearization locally transforms nonlinear systems into equivalent linear ones so that linear control laws can be applied. It can be used for tracking states $x_{d}$ along a desired trajectory by minimizing the error $e=x(t)-x_{d}(t)$. Given the linearization, these solutions tend to work in the vicinity of the desired goal/trajectory. They can be ineffective when the feedback-linearized system behaves very differently from the original nonlinear system. To expand the set of initial conditions from which the goal can be reached, sequential composition of such feedback policies [40] can give rise to hybrid controllers that sequentially switch between them. LQR-Trees [41] apply sequential composition by combining linear control and SBMPs. They use control verification to evaluate the region of attraction (RoA) of local LQR controllers. They expand a tree backwards from the goal and sample controllers that bring the robot to the RoAs of controllers that lead to the goal. They have been applied on dynamic environments [42] and for systems with dynamics [43].

Model-Predictive Control (MPC) and Replanning: MPC is a simple but powerful feedback strategy that aims to solve fast and repetitively finite horizon optimization problems given the latest state observations [44]. MPC executes the initial portion of the motion and then updates given the latest observation. During each step, MPC uses the system’s model to predict future behavior and makes control decisions that minimize a cost function at the end of the finite horizon, while adhering to constraints, such as collision avoidance. Initial MPC approaches used analytical methods to predict future states, and Linear MPC [45] utilizes linear analytical models or approximations. Various Non-Linear MPC (NMPC) variants have been proposed [46]. Shooting MPC is a common NMPC approach that employs numerical methods, such as guessing an initial set of controls and then locally optimizing to minimize the cost function [47]. It is applicable across robotic systems for bridging the model gap. At the same time, shooting MPC involves numerous parameters that require tuning to achieve good performance [48]. It is also possible to replan using longer horizon planners, where it is important to minimize computational costs so as to achieve tight feedback. For instance, D^∗ Lite [49], a replanning variant of A^∗, updates the path it initially creates to adjust to changes in the workspace. Similarly, replanning versions of SBMPs reuse prior computations to ensure the robot reacts swiftly to changes while maintaining safety [50], including for systems with dynamics [51].

Imitation learning mimics the decision-making process given demonstration data.

Behavior Cloning (BC) trains a model in a supervised manner given a dataset of demonstrations to provide a motion policy. Successful applications of BC have enabled robots to learn complex behaviors [52][53]. The process starts with data collection, which includes capturing sensory inputs and corresponding control actions for a target task. An appropriate ML model architecture (e.g., Convolutional Neural Networks (CNNs) for visual data or Recurrent Neural Networks (RNNs) for sequential data) is trained using supervision to minimize a loss function, such as mean squared error. Gaps between the demonstration and the execution setup, as well as noise and stochasticity, can cause a compounding distributional shift between training and testing [54]. Noise modulates the perception of the true state and can cause erroneous actions from the BC policy. Stochastic state transitions can move the process from an in-distribution state to an out-of-distribution (OOD) one. These effects can compound and make the policy increasingly generate improper actions bringing the robot’s state further OOD. Furthermore, BC is sensitive to engineering decisions, such as observation space, hyperparameters, and recurrent information [55]. These shortcomings motivate more sophisticated approaches.

Incremental Corrections: The DAgger algorithm [56] focuses on decision making in OOD states given the available demonstrations. A dataset of rollouts is collected by executing the BC policy. Then, an expert, such as a human or a planner, is queried to provide the proper actions at the states encountered in this dataset, and the policy is retrained. This process is iterative, as new OOD states will be encountered after each retraining. DAgger heavily relies on an expert to provide the corrections. SafeDAgger provided a more query-efficient extension [57]. It first uses a safety policy to predict the error of the learned policy. This safety policy selects only a small subset of training examples to be collected.

Inverse Reinforcement Learning (IRL) focuses on extracting the problem’s underlying dense reward function given demonstrations to achieve improved generalization relative to BC [58]. This reward function can then be used to extract the policy provided an MDP problem formulation. Initial works [59] modeled the reward as a linear combination of input features, and the weights of this linear combination are obtained by solving an optimization problem. A significant challenge of IRL, however, is the difficulty in scaling to high-dim. systems, which recent approaches attempt to mitigate [60].

Diffusion Policies: Demonstrations commonly include multi-modal behaviors, which multi-layer perceptrons (MLP) may find difficult to express since they are trained via mean squared error (MSE) that averages the demonstrated actions resulting in erroneous choices [61]. In compuater vision, diffusion models have become popular for generating images by expressing multi-modal distributions [62]. This motivates diffusion processes as implicit models for BC, where Diffusion Policy [63] has outperformed alternatives, such as LSTM-GMM [64] in learning from demonstrations. Inference speed of diffusion policies is a challenge for robot motion generations [65] and is an active area of research.

One area of robotics that has garnered interest [66] is Reinforcement Learning (RL), where a machine learning model predicts the Q function of an MDP and the corresponding policy. It has been applied across tasks, e.g., grasping [67], locomotion [68], and assembly [69].

Model-free, On-Policy RL: Standard RL gathers data from interaction with the environment, where Policy Gradient (PG) methods generate a batch of full trajectory data, compute the gradient of each state transition, and scale each gradient by the respective discounted return. PGs update the policy and repeat the process towards maximizing the expected cumulative reward. Proximal Policy Optimization (PPO) [70] is a PG method that leverages a value function, which is the average discounted return from a given state. These are on-policy methods, i.e., they only use data collected from the most recent policy. Exploration can be achieved through the periodic execution of random actions (epsilon greedy), injecting Gaussian noise to policy outputs [71], or using a stochastic policy for entropy maximization [70].

RL faces multiple challenges in robotics: (i) sample inefficiency: Policies need a lot of data to train and take significant training time. Real robot data, however, can be slow, expensive, and unsafe to collect [72]. (ii) instability: Policies can be inconsistent across training sessions due to poorly designed rewards, exploration strategies, learning rate parameters or learning error from neural networks. (iii) reward engineering: Simple rewards are sparse, i.e., they assign a 0 reward everywhere except at the goal. While desirable, sparse rewards often do not find a successful behavior in reasonable time [72]. This motivates dense rewards to guide exploration, which require manual engineering. While dense rewards can improve training time and stability, they can also lead to wrong behaviors, if they do not match the true task objective. (iv) long horizon tasks: The state space to be explored for such tasks is even larger making the propagation of rewards across subproblems difficult.

The above challenges have motivated multiple RL variations in robotics:

Simulation and Domain Randomization: Simulators, which are explicit world models, are useful for addressing sample inefficiency by generating data without real-world experiments. They suffer, however, from the model gap issue. Even so, it may still be possible to create good policies via domain randomization (DR) [73], which can partially compensate for imperfect models during sim-to-real transfer. DR results in behaviors that have the highest expected reward across a variety of underlying dynamics and perception errors.

Off-policy RL Sample inefficiency motivates data reuse. Off-policy RL stores the expected discounted future reward of any in-distribution state-action tuple on a Q function, which is used to train the policy $\pi$. To update the parameters $\theta$ of the Q function for a given state transition $(s,a,r,s^{\prime}$) (state, action, reward, next state), the immediate reward $r$ and future rewards $Q(s^{\prime},\pi_{\phi}(s^{\prime}))$ are used to define the loss function: $L(\theta)=E(Q_{\theta}(s,a)-r+\gamma\cdot Q_{\theta}(s^{\prime},\pi_{\phi}(s^{\prime})))^{2}$. This allows off-policy RL algorithms, such as TD3 [74] and SAC [75], to be more sample efficient than online RL. Off-policy RL, however, is complicated by the instability of neural network learning, especially because errors compound while learning Q functions [76]. A way to mitigate instability is to use target Q functions to query for future rewards [74][75][76]. The target Q functions average their weights slowly with the learned Q function’s weights. Given that the policy is defined as $\pi^{*}(s)=\arg\max_{a}Q(s,a)$, errors in Q function learning, which overvalue actions, are propagated rapidly. This is called an overestimation bias [74]. One way to mitigate overestimation bias to is use a clipped, double Q function, an ensemble of two Q networks coupled with target Q networks, that take the lower value of the two when queried for future rewards to underestimate Q values when uncertain [74][75]. Hindsight Experience Replay (HER) [77] aims for sample-efficiency in multi-goal problems given only sparse rewards. It relabels the end or intermediate states of executed trajectories as the desired goal allowing to train over all available experiences.

Offline RL Offline RL is a subcase of off-policy RL, which doesn’t interact online with the environment to modulate the replay buffer. Instead it uses offline data, focusing on sample efficiency. Offline RL aims to improve the optimality of suboptimal demonstrations by patching together data towards the most optimal solution rather than imitating the data [78]. Additionally, it can handle multi-modal demonstrations as it can solve for the single most optimal action for each state. The policy $\pi$ used for updating the Q function is parameterized via a function approximator. This can cause $\pi$ to choose actions that are out-of-distribution (OOD). The Q function queried with the OOD state-action pair will output an untrained value, which can be an erroneous large reward that can propagate and degrade performance [79]. In online RL, when an OOD state-action pair is overvalued, $\pi$ will favor the action and gather data on the OOD state-action pair, which will remedy the error. IQL [80], which is an offline RL method, mitigates distributional shift by using only state-action pairs from the dataset. Instead, CQL [81] employs a conservative estimate on Q values.

Model-based RL learns a model of the environment, which is then used to roll out the policy to generate training data offline. Relative to a simulator, the learned model can operate over a more compact state representation, run faster, and can be queried for any given state. The major drawback is that RL may exploit errors in the learned model. MOPO [82] aims to mitigate these effects by detecting when the query to the model is out of distribution.

Hierarchical RL (HRL) focuses on long horizon tasks, similar to TAMP (Section 2.2). It temporally abstracts high-level actions that correspond to low-level learned policy. The high-level actions can target exploration to better cover the space and more easily assign rewards [83]. Using random actions to search is not effective in long horizon tasks and guidance for their generation is critical. Long horizon tasks remain rather challenging for RL approaches.

Demonstrations from related or earlier tasks can help bootstrap or guide RL.

Transfer Learning methods exhibit high variability. One approach bootstraps RL by using an adaptively-weighted auxiliary term in the loss function of PPO to increase action similarity for the learned policy against the demonstrated one from a task with similar MDP [84]. It is also possible to pre-train multiple tasks with offline RL given a single task-conditioned policy [85]. Online, the approach fine-tunes both the conditioning parameter and policy to automatically reset tasks for autonomous real-world training. For transferring information across heterogeneous MDPs, researchers have mapped states and actions across MDPs [86] and transfered useful representations across domains [87].

Multi-Task Learning trains many tasks in parallel while sharing information across tasks to accelerate training and improve generalization [88]. Methods focus on how to select parameters to sharing so as to effectively transfer learned representations between tasks [89].

Lifelong Learning emphasizes learning a new task in a sequence by transferring information from previously learned ones without forgetting how to solve them. Retaining previous task information can be done by mixing previous data with new ones during retraining [90]. Functionally composed modular lightweight networks have been proposed to learn a large variety of combinatorially related tasks to solve novel combination tasks in a zero-shot manner [91].

Large Language Models (LLMs) pretrained on internet-scale data have opened new avenues for robot motion generation. LLMs are capable of semantic reasoning and planning, making them candidates for extracting task specifications and creating action models for task planning [92]. LLMs have also been used to improve existing action models to handle failure cases [93]. These methods often do not generate constraints for low level motion in the operators as in TAMP. Furthermore, they have been used in conjunction with evolutionary optimization as code generators for defining rewards, which can be used to acquire complex skills via reinforcement learning [94].

Vision Language Models (VLMs) integrate information from visual input and language. Saycan [95] integrates a visual affordance model, which evaluates possible robot actions, with a language model that interprets the user’s commands and generates high-level action plans. VLMs have also been used for autonomous generation of demonstration data over diverse tasks [96].

This lead to vision-language-action models (VLAs) or Robotics Foundation Models, i.e., large pretrained models that map actions to sensing data and language specifications. They can be fine-tuned for specific tasks to provide improvements in training time and generalization over trainingfrom scratch. OpenVLA [97] is such a model trained on a large robotic manipulation dataset [98] and utilizes large pretrained vision encoders and language models. It has been argued that it performs well on in-distribution tasks and robotic embodiments, while it can be fine-tuned for novel tasks and robotic embodiments.