PaperlayerView exact revision on arXiv

Source-linked AI summary

Memory of Motion for Warm-starting Trajectory Optimization

Teguh Santoso Lembono, Antonio Paolillo, Emmanuel Pignat, Sylvain Calinon

arXiv:1907.01474v4cs.RO

TL;DR

Trajectory optimizers can be sensitive to their initial guesses, motivating a way to reuse previously solved motions. The paper learns task-to-path mappings from a motion database and uses function approximators to provide warm-starts. It reports improved solver performance, including benefits from memory-based goal selection and an ensemble.

  • Problem

    Trajectory optimization can be sensitive to its initial guess, and a poor guess can lead to a poor local optimum.

    Source: §I · p. 1

  • Method

    The paper learns task-to-path mappings from a database of robot paths using function approximators and dimensionality reduction, and uses the memory for warm-starting and goal selection.

    Source: §I · p. 1, 4) Dimensionality reduction · p. 3

  • Results

    The experiments report improved solver performance, with ensemble warm-starts boosting success rate and memory-based goal selection significantly improving performance.

    Source: §I · p. 2, §VI · p. 8

  • Takeaways & Limitations

    The memory can serve both as a source of warm-start trajectories and as a metric for choosing among alternative goals.

    Source: §VI · p. 8

    With an RBF covariance function, GPR assumes a smooth, continuous task-to-path mapping and can perform poorly on discontinuities or multimodal outputs.

    Source: 3) Bayesian Gaussian Mixture… · p. 3

Abstract

from arXiv · show

Trajectory optimization for motion planning requires good initial guesses to obtain good performance. In our proposed approach, we build a memory of motion based on a database of robot paths to provide good initial guesses. The memory of motion relies on function approximators and dimensionality reduction techniques to learn the mapping between the tasks and the robot paths. Three function approximators are compared: $k$-Nearest Neighbor, Gaussian Process Regression, and Bayesian Gaussian Mixture Regression. In addition, we show that the memory can be used as a metric to choose between several possible goals, and using an ensemble method to combine different function approximators results in a significantly improved warm-starting performance. We demonstrate the proposed approach with motion planning examples on the dual-arm robot PR2 and the humanoid robot Atlas.

I. INTRODUCTION

Trajectory optimization addresses high-dimensional, constrained robot planning, but its non-convexity makes solver outcomes sensitive to the initial guess. The paper proposes a memory of motion that learns task-to-path mappings to warm-start the solver and compares function approximators, goal selection, and an ensemble.

I. INTRODUCTION

  • Trajectory optimization for high-DoF robots faces constraints such as collision avoidance and joint limits, and its non-convexity makes global optimization difficult.The paper notes that collision constraints are a particular source of non-convexity.Source: §I · p. 1
  • A poor initial guess can trap an iterative optimizer at a poor local optimum, making convergence and solution quality sensitive to initialization.Source: §I · p. 1
  • The memory of motion learns a potentially nonlinear, multimodal mapping from task descriptors to robot paths using a motion database, function approximation, and dimensionality reduction.The term includes both the motion database and the algorithms used to query warm-starts.Source: §I · p. 1
  • Memory queries take milliseconds rather than the seconds required by sampling-based warm-starting methods, and close initial guesses reduce solver convergence time.The cited comparison describes sampling-based computation as comparable to solver convergence time.Source: §I · pp. 1–2
  • The paper compares k-NN, GPR, and BGMR, highlights BGMR for multimodal outputs, and reports improved success rates from an ensemble and improved performance from memory-based goal selection.Source: §I · p. 2

II. RELATED WORK

Prior work uses trajectory libraries, learned mappings, and sampling-based planners to reuse motion experience. The paper distinguishes its approach by addressing multimodal outputs, selecting among goals with the memory, and combining approximators for warm-starts.

II. RELATED WORK

  • Prior approaches use trajectory libraries and learned policies or mappings, including k-NN, neural networks, and GPR to predict actions, trajectories, or movement-primitive parameters.Source: §II · p. 2
  • PRM, RRT-based methods, Experience Graphs, Lightning, and related approaches reuse precomputed paths or experience to bias planning or reduce online search.Other cited work learns trajectories for cyclic walking or real-time catching.Source: §II · p. 2
  • The authors distinguish their approach by handling multimodal outputs with BGMR, using memory to choose among goals, and using an ensemble that outperforms individual methods for warm-starting.Source: §II · p. 2

III. METHOD

The method learns task-to-path mappings from optimized examples and uses function approximators to query warm-starts. It also describes goal selection and ensemble use; the supplied detailed method passages focus on database construction and k-NN.

III. METHOD

  • The method includes building a memory from function approximation and dimensionality reduction, using it to choose among goals, and combining approximators in an ensemble.Source: §III · p. 2

A. Building a Memory of Motion

  • The database is built by sampling task descriptors, optimizing paths for those tasks until N task-path pairs are collected, and training k-NN, GPR, or BGMR on the pairs.Source: A. Building a Memory of Motion · p. 2

1) k-Nearest Neighbor (k-NN):

  • k-NN finds K database tasks nearest to the query under a chosen metric and averages their associated paths; it works well with sufficiently dense data but faces exponential storage growth as task dimension increases.The paper uses Euclidean distance and treats k-NN mainly as a baseline against the other methods.Source: 1) k-Nearest Neighbor (k-NN) · p. 2

2) Gaussian Process Regressor (GPR):

GPR predicts paths from task inputs using a posterior mean, but its accuracy depends on the mapping being smooth and it does not scale well to very large datasets. BGMR uses a Bayesian mixture model and a component-based prediction to address multimodal outputs.

2) Gaussian Process Regressor (GPR):

3) Bayesian Gaussian Mixture Regression (BGMR):

  • BGMR estimates a posterior over mixture parameters, automatically determines the number of components, and uses priors to reduce overfitting in high-dimensional problems.Its predictive distribution is a mixture of t-distributions.Source: 3) Bayesian Gaussian Mixture… · p. 3
  • For multimodal outputs, BGMR predicts with the mean of the highest-probability component rather than averaging across modes.It can alternatively return each component mean as a separate prediction.Source: 3) Bayesian Gaussian Mixture… · p. 3

4) Dimensionality reduction:

The method reduces the high-dimensional path output before learning its mapping from tasks. PCA is used in this work to compress the path representation, while the memory-building and goal-selection procedures use the resulting learned approximator.

4) Dimensionality reduction:

  • PCA projects paths into a lower-dimensional representation, reducing memory requirements while maintaining or potentially improving approximation performance.The paper uses PCA because the number of time steps is not large; RBF bases, ICA, factor analysis, and variational autoencoders are also mentioned as possible techniques.Source: 4) Dimensionality reduction · p. 3
  • The memory-building procedure samples tasks, solves each with TrajOpt, retains valid paths, and optionally applies PCA before training the function approximator.The initial guess for each sampled task is a straight-line motion.Source: 4) Dimensionality reduction · p. 4
  • For multiple goals, the method predicts an initial path for each and selects the goal whose predicted path has the lowest cost before running TrajOpt.The procedure uses the total discrete velocity as the cost.Source: 4) Dimensionality reduction · p. 4

B. Using the Memory as a Metric

The memory of motion can rank alternative goals by the cost of their predicted initial paths, avoiding the expense of planning fully to every goal. An ensemble runs optimizations from different approximators in parallel and stops when one finds a valid path.

B. Using the Memory as a Metric

  • Selecting the goal with the lowest predicted-path cost can improve optimizer performance because the cost is quick to compute relative to optimization.The memory predicts an initial path for each candidate task, and the lowest-cost task is sent to the trajectory optimizer.Source: B. Using the Memory as a Metric · p. 4

C. Using Ensemble Method to Provide Warm-Start

  • The ensemble runs trajectory optimizations in parallel, each warm-started by a different function approximator, and terminates the others when one finds a valid path.The memory-as-metric method can also serve as an ensemble component.Source: C. Using Ensemble Method to Provide… · p. 4
  • Combining function approximators with different learning characteristics can significantly improve motion-planning performance over choosing a single method.Source: C. Using Ensemble Method to Provide… · p. 4

IV. EXPERIMENTS

The experiments test memory-based warm-starts for TrajOpt across motion-planning tasks on PR2 and Atlas. They compare solutions by convergence time, feasibility-based success rate, and cost.

IV. EXPERIMENTS

  • The evaluation covers robot paths for PR2 and Atlas, with TrajOpt as the optimizer being warm-started.The method is evaluated on paths, though it can also be applied to robot trajectories.Source: §IV · p. 4
  • Five motion-planning cases use sampled task-path datasets to train function approximators, with 30 time steps except 15 for Atlas.PCA uses 50 components, and k-NN uses K = 1.Source: §IV · p. 4
  • Methods are compared by convergence time, feasibility-based success rate, and cost over random test tasks.Reported convergence times and costs include standard deviations.Source: §IV · p. 4
  • Warm-start query times are under 5 ms for most methods, except BGMR without PCA at around 20 ms.These times are omitted from the comparison because they are negligible relative to convergence time.Source: §IV · p. 4

A. Base motion planning

Base-motion experiments compare learned warm-starts for tasks with one or two waypoint-derived routes. With two possible routes, GPR averages the modes, whereas k-NN and BGMR preserve viable alternatives.

A. Base motion planning

  • Straight-line initialization through the kitchen fails to find a feasible solution, so database paths are generated using manually selected waypoints around the kitchen.The two database settings use the right waypoint alone or both left and right waypoints.Source: A. Base motion planning · p. 5
  • The one-waypoint database represents a unimodal mapping, and k-NN, GPR, and BGMR perform similarly.The database contains routes that go through the right waypoint.Source: A. Base motion planning · p. 5, Table III · p. 5
  • With two route modes, GPR averages them into a path through the kitchen, while k-NN and BGMR are not affected.k-NN uses K = 1; BGMR automatically builds local models for each mode.Source: A. Base motion planning · p. 5
  • Figure 2 contrasts the straight-line waypoint warm-start with k-NN, GPR, and BGMR; GPR's multimodal warm-start goes through the kitchen, yielding 0 success rate.Retrieving BGMR's two highest-probability components produces both possible solutions.Source: A. Base motion planning · p. 5

B. Planning from a fixed initial configuration to a random goal configuration

Across fixed-start, random-start, and Cartesian-goal planning, the relative performance of the approximators depends on task structure. The experiments also report that goal selection by the memory and a parallel ensemble improve warm-start performance.

B. Planning from a fixed initial configuration to a random goal configuration

  • With a fixed PR2 start and random goal, GPR and BGMR perform similarly; PCA cuts each path from 30 × 14 variables to 50 components, more than an 8× reduction while maintaining performance.PCA does not significantly improve performance, but reduces data size.Source: B. Planning from a fixed initial… · p. 5

D. Planning to Cartesian goals from a fixed initial configuration

  • For Cartesian goals, METRIC GPRPCA outperforms the direct Cartesian-goal approaches on all three criteria, and the ensemble further raises success to 98%.Finding five IK solutions and their warm-starts takes around 0.1 s, described as negligible relative to convergence time.Source: Table V · p. 6, D. Planning to Cartesian goals from a… · p. 6

C. Planning from a random initial configuration to a random goal configuration

D. Planning to Cartesian goals from a fixed initial configuration

  • For Cartesian goals, BGMR performs better than GPR among direct-goal methods because the mapping to paths is more multimodal than for joint-configuration goals.This result is reported as further evidence that BGMR handles multimodal output better than GPR.Source: D. Planning to Cartesian goals from a… · p. 6

E. Planning whole-body motion for an Atlas robot

The Atlas experiment applies the memory of motion to whole-body planning from a fixed configuration to random right-hand positions, with fixed feet and a ZMP constraint. The ensemble improves success and speeds computation, though randomly sampled tasks are not guaranteed feasible.

E. Planning whole-body motion for an Atlas robot

  • The 34-DoF Atlas experiment predicts trajectories from right-hand Cartesian targets, using 1,000 training tasks and 250 test tasks.The hand orientation is unconstrained, and the feet remain fixed while the ZMP stays between them.Source: E. Planning whole-body motion for an… · pp. 6–7
  • The ensemble increases the success rate by more than 10%, while GPR and BGMR perform similarly with the more uniform zero-initialized database solutions.Unlike the PR2 dual-arm experiment, Atlas database construction uses zero initialization, yielding more uniform solutions.Source: E. Planning whole-body motion for an… · p. 7
  • k-NN performs well in this task, where the hand position is constrained to lie inside the shelf.The paper attributes this to the small input size.Source: E. Planning whole-body motion for an… · p. 7
  • Memory-based warm-starting makes this constrained Atlas task more than four times faster than planning without a warm-start; the ensemble reaches only about 70% success because sampled tasks may be infeasible.Without a warm-start, planning averages about 6.3 seconds.Source: E. Planning whole-body motion for an… · p. 7

A. Choice of function approximators

The paper compares when different function approximators work well, then motivates combining them when a task’s output modality is unclear. It reports that the ensemble improves success, while the static-environment assumption limits reuse when environments change.

A. Choice of function approximators

  • k-NN tends to work well with dense data or small input spaces, GPR with unimodal outputs, and BGMR better than GPR with multimodal outputs.These observed characteristics can guide method selection across tasks.Source: A. Choice of function approximators · p. 7
  • Because a task’s output modality may be unclear, the authors propose combining function approximators with an ensemble.The paper notes that tasks can differ in modality, including the comparison between Sections IV-D and IV-E.Source: A. Choice of function approximators · p. 7

B. Data requirement

  • With small training sets, GPR performs well while k-NN and BGMR trail STD; the ensemble remains stable with high success, and its convergence time falls as training data grows.The comparison uses the task with the largest input space among the evaluated tasks.Source: B. Data requirement · p. 7, Figure 3 · p. 8

C. Ensemble method

  • Unlike an ensemble of motion planners, the approach combines function approximators around one configured planner; its components provide likely near-optimal starts that reduce average computation time.The paper compares this benefit with multiple-waypoint initialization in Table IV.Source: C. Ensemble method · p. 7

D. Dynamic environment

  • The method assumes a static environment, so changed environments require rebuilding the memory; construction ranges from about 3 minutes for a simple example to about 3 hours for a complex one.The authors suggest updating affected parts or adding moving-obstacle locations as future directions.Source: D. Dynamic environment · p. 7

VI. CONCLUSION

  • Across PR2 and Atlas experiments, warm-starts improve solver performance; PCA modestly improves solutions while reducing storage, goal selection improves Cartesian-goal planning, and the ensemble boosts success.The conclusion presents these as results of the memory-of-motion approach.Source: §VI · p. 8
Loading 1907.01474v4…