PaperlayerView exact revision on arXiv

Source-linked AI summary

Motion Planning Networks: Bridging the Gap Between Learning-based and Classical Motion Planners

Ahmed H. Qureshi, Yinglong Miao, Anthony Simeonov, Michael C. Yip

arXiv:1907.06013v3cs.ROcs.AIcs.LG

TL;DR

Motion planning requires collision-free, low-cost paths with strong guarantees and practical efficiency, but classical approaches face computational and environmental challenges. MPNet addresses this gap with neural, bidirectional iterative planning, active continual learning, and hybrid integration with classical planners. Across presented problems, it consistently finds collision-free paths in under a second, while hybrid and sampling-based variants retain formal guarantees.

  • Problem

    Motion planning must find collision-free, low-cost paths while ideally combining completeness, optimality, computational efficiency, and robustness to environmental complexity.

  • Method

    MPNet combines environment encoding and neural bidirectional iterative planning with active continual learning and hybrid integration with classical planners.

  • Results

    MPNet consistently finds collision-free paths in less than a second across the presented problems, while its informed-sampling hybrid retains asymptotic optimality and completeness guarantees.

  • Takeaways & Limitations

    Neural planning can provide computationally efficient near-optimal path generation and informed sampling for sampling-based motion planners across seen and unseen environments.

Abstract

from arXiv · show

This paper describes Motion Planning Networks (MPNet), a computationally efficient, learning-based neural planner for solving motion planning problems. MPNet uses neural networks to learn general near-optimal heuristics for path planning in seen and unseen environments. It takes environment information such as raw point-cloud from depth sensors, as well as a robot's initial and desired goal configurations and recursively calls itself to bidirectionally generate connectable paths. In addition to finding directly connectable and near-optimal paths in a single pass, we show that worst-case theoretical guarantees can be proven if we merge this neural network strategy with classical sample-based planners in a hybrid approach while still retaining significant computational and optimality improvements. To train the MPNet models, we present an active continual learning approach that enables MPNet to learn from streaming data and actively ask for expert demonstrations when needed, drastically reducing data for training. We validate MPNet against gold-standard and state-of-the-art planning methods in a variety of problems from 2D to 7D robot configuration spaces in challenging and cluttered environments, with results showing significant and consistently stronger performance metrics, and motivating neural planning in general as a modern strategy for solving motion planning problems efficiently.

I. INTRODUCTION

Motion planning seeks collision-free, low-cost paths while balancing guarantees, computational efficiency, and robustness to environmental complexity. MPNet combines neural planning, continual learning, and classical planners to address these goals in seen and unseen environments.

  • Motion planning aims to connect start and goal configurations with a collision-free, low-cost path while ideally providing completeness, optimality, efficiency, and robustness to environment complexity.
  • MPNet combines an environment encoder with a planning network that predicts successive robot states from obstacle information, current configuration, and goal configuration.
  • MPNet uses offline batch, continual, and active continual learning, with active learning requesting expert demonstrations only when planning fails.
  • MPNet's continual-learning approach uses episodic memory and constraint optimization to retain prior knowledge while learning from streaming demonstrations.
  • MPNet can generate informed samples for RRT* without additional computational load while preserving asymptotic optimality and completeness guarantees.
  • The hybrid MPNet-classical approach can provide worst-case guarantees by outsourcing difficult path segments to classical planners while retaining computational benefits.
  • MPNet generalizes to similar unseen environments and reports mean computation times below 1 second across presented experiments.
  • Classical complete planners can be computationally intractable, while sampling-based planners trade practical efficiency for probabilistic completeness and remain vulnerable to dimensionality and clutter.

III. MPNET: A NEURAL MOTION PLANNER

MPNet combines an environment encoder with a planning network that incrementally generates motion trajectories from current and goal configurations. The section also describes offline, continual, and active continual learning strategies for training these modules.

  • Architecture: MPNet uses Enet to embed raw point clouds or voxelized environments into a latent representation and Pnet to generate motion-planning outputs.Enet may be fully connected or convolutional, while Pnet conditions on the environment encoding and robot states.
  • Planning: MPNet plans recursively by generating critical states, checking their connectability, and replanning between beacon states when necessary.This divide-and-conquer procedure decomposes a planning problem into subproblems.
  • Training: The training framework includes offline batch learning, continual learning from streams, and active continual learning that requests expert demonstrations when needed.The modules can be trained jointly end-to-end or separately, depending on the available data and training setup.
  • Training: For offline learning, Enet and Pnet may be trained end-to-end or with separate objectives, including contractive autoencoder training for robust environment features.Pnet uses waypoint prediction, while Enet reconstruction uses a regularized encoder-decoder objective.
  • Architecture: Pnet takes the environment encoding, current configuration, and goal configuration to incrementally predict the next waypoint toward the goal.The planning module is trained with one-step look-ahead prediction from expert trajectories.

B. Continual Learning

Continual learning adapts MPNet to streaming expert data while addressing catastrophic forgetting. The method uses episodic-memory constraints and projected gradient updates to prevent new learning from degrading prior performance.

  • Training procedure: Continual learning trains Enet and Pnet end-to-end because both modules must adapt to incoming supervised data.Each input contains the current state, goal state, and obstacle information, with the expert trajectory’s next state as target.
  • Motivation: Streaming neural-network updates can cause catastrophic forgetting when learning from new expert demonstrations.The paper characterizes this issue as negative backward transfer on previously learned tasks.
  • Constraint optimization: MPNet adapts Gradient Episodic Memory to regression by constraining updates so performance on episodic-memory samples does not worsen.The episodic memory stores a finite set of previously seen data.
  • Constraint optimization: If the proposed gradient conflicts with the memory gradient, the method projects it to the nearest feasible gradient using quadratic programming.The constraint requires the projected update g′ to satisfy ⟨g′, gM⟩≥0.
  • Memory: The episodic memory uses global distribution matching so its finite contents approximately represent the unknown global streaming-data distribution.The paper identifies reservoir sampling as a random-sampling implementation of this strategy.

1 Initialize memories: episodic M and replay B∗

The continual-learning procedure initializes MPNet and maintains episodic and replay memories while updating the model with projected gradients. Reservoir sampling preserves an approximate global distribution, and rehearsal further mitigates forgetting.

  • Initialization: The procedure initializes MPNet parameters before processing streaming demonstrations.The algorithm begins with an initialized model and later updates its parameters using projected gradients.
  • Model updates: The algorithm applies quadratic-programming projections to proposed gradients when enforcing continual-learning constraints.Projected updates are used at multiple points in the procedure.
  • Episodic memory: Episodic memory is populated by global-distribution matching, implemented through reservoir sampling over streaming training data.New samples can replace randomly selected old samples according to the reservoir-sampling procedure.
  • Replay memory: A separate replay buffer stores old samples so MPNet can rehearse them during training.Rehearsal is performed periodically according to the replay period r.
  • Replay memory: The paper reports that replay rehearsals further mitigate catastrophic forgetting and improve performance.This rehearsal step supplements the episodic-memory constraint mechanism.

C. Active Continual Learning

Active continual learning selects demonstrations adaptively during streaming planning. It asks an expert planner for failures, further filters demonstrations for episodic memory, and uses recursive replanning to recover feasible paths.

  • Active continual learning: ACL uses two selection levels: it gathers demonstrations from failed problems, then prunes them to populate episodic memory.The second selection stage aims to approximate the global distribution of streaming data.
  • Online procedure: At each time step, the environment supplies initial and goal configurations together with obstacle information before MPNet or an expert planner is used.The algorithm can first train from available demonstrations for up to Nc iterations.
  • Online planning: MPNet’s iterative bidirectional planner produces a coarse path and recursively replans between beacon states that are not directly connectable.This refinement process uses Pnet stochasticity to help recover from failures.
  • Online planning: Lazy states contraction removes redundant states after recursive replanning to produce the final feasible plan.The figure presents this pruning step after the global and local planning stages.

V. MPNET: ONLINE PATH PLANNING

MPNet combines environment encoding and stochastic planning networks in an iterative, recursive, bidirectional planner. It generates coarse paths, checks connections, and replans difficult segments neurally or with a hybrid oracle-assisted strategy.

  • Network components: MPNet uses Enet to encode obstacle information and Pnet to generate stochastic next-state predictions toward the goal.Pnet uses Dropout during execution, producing varied network realizations for planning.
  • Bidirectional planning: The planner runs forward from start to goal and backward from goal to start until the paths meet, using a greedy RRT-Connect-like heuristic.
  • Recursive divide-and-conquer: MPNet recursively decomposes planning into subproblems by replanning between consecutive critical states that are not directly connectable.The initial bidirectional planner produces a coarse path of critical points before recursive replanning.
  • Replanning strategies: Neural replanning makes a fixed number of attempts between beacon states, whereas hybrid replanning invokes an oracle planner after neural attempts fail.The hybrid procedure uses the oracle only when neural replanning does not find a solution after Nr trials.

3) Lazy States Contraction (LSC):

Lazy States Contraction removes redundant states from a path by attempting direct connections between non-consecutive states. This reduces the number of nodes processed during subsequent planning.

  • 3) Lazy States Contraction (LSC): Lazy States Contraction directly connects non-consecutive states when possible and removes redundant intermediate states.It is implemented recursively on a path σ = {c0, c1, · · · , cT}.
  • 3) Lazy States Contraction (LSC): The steerTo function validates a connection by discretizing the straight line between two states and checking each discrete node for collisions.The line is represented as σ(δ) = (1 −δ)c1 + δc2 for δ ∈[0, 1].

5) isFeasible:

MPNetPath encodes the obstacle point cloud, generates a coarse path, contracts redundant states, and checks feasibility. Invalid connections trigger recursive neural replanning and further contraction.

  • 5) isFeasible: MPNetPath encodes raw obstacle point clouds with Enet, then uses BNP to produce a coarse path and LSC to retain critical states.
  • 5) isFeasible: Fig. 4 compares MPNetPath with neural replanning and RRT* across simple and complex 2D, complex 3D, and rigid-body-SE2 environments.The caption reports comparable path lengths to RRT* with much shorter computation times.
  • 5) isFeasible: The planner tests whether consecutive coarse-path states connect through collision-free space before accepting the path.The connection check uses steerTo to determine whether the full path lies in collision-free space.

B. Informed Sampling with MPNet

MPNetSMP uses stochastic predictions from Pnet to generate informed samples for classical sampling-based planners. These samples initially bias exploration toward promising regions before uniform sampling resumes.

  • B. Informed Sampling with MPNet: Dropout stochasticity lets MPNet generate multiple informed samples likely to belong to connectable and near-optimal paths.The samples approximate a subspace containing potential path solutions, including the optimal path.
  • B. Informed Sampling with MPNet: MPNetSMP incrementally generates samples from start toward the goal for Nsmp iterations before the underlying planner switches to uniform random sampling.
  • B. Informed Sampling with MPNet: MPNetSMP-based RRT* is reported as at least 30 times faster than traditional RRT* in the presented environments.
  • B. Informed Sampling with MPNet: The underlying sampling-based planner combines early exploitation of an informed subspace with later exploration through uniform sampling.Once a path is found, it can be returned or further optimized for a cost function.
  • B. Informed Sampling with MPNet: MPNetSMP can generate informed bidirectional samples for bidirectional sampling-based planners, supporting narrow-passage motion planning.

VI. RESULTS

MPNet is evaluated against classical planners across robot configurations and seen or unseen environments, using multiple training strategies and planner variants. The reported results emphasize consistently low computation times, strong path quality, and data-efficient active continual learning.

  • Computation time: MPNetPath and MPNetSMP achieve mean computation times below one second across the presented planning problems.This pattern holds across MPNet variants trained with offline batch, continual, and active continual learning.
  • Evaluation settings: MPNet is evaluated on 2D/3D point-mass, rigid-body-SE2, rigid-body-SE3, and 7DOF Baxter motion-planning problems.The experiments include seen-Xobs and unseen-Xobs datasets, along with cluttered Baxter environments.
  • Training strategies: Active continual learning improves training data efficiency while achieving performance similar to conventional methods under comparable training conditions.Continual and active-continual methods used about ten training epochs, compared with one hundred for offline batch learning; equal-epoch success rates were similar.
  • Comparison with RRT*: MPNetPath is at least 100× faster than RRT* while producing paths within 10% of RRT* path cost.RRT* computation time increases exponentially with planning-problem dimensionality in the reported comparison.
  • Sampling-based planning: MPNetSMP generates near-optimal or optimal paths with computation times below one second and improves on the path quality and time of its RRT* demonstrator.MPNetSMP uses an underlying RRT* planner while restricting sampling to an informed subspace.

C. MPNet Comparison with Advanced Motion Planners

Against advanced classical planners, MPNet variants maintain subsecond computation times across dimensions and datasets while producing competitive or lower-cost paths. The comparisons extend from 2D environments to 7DOF Baxter and SE(3) rigid-body planning.

  • Simple 2D: In simple 2D environments, MPNetPath:NP is at least 80× faster than BIT* and 30× faster than Informed-RRT*.MPNetSMP provides about 8× and 5× speed improvements over BIT* and Informed-RRT*, respectively, in the same setting.
  • Cross-dataset comparison: MPNetPath and MPNetSMP remain below one second on both seen-Xobs and unseen-Xobs datasets, whereas Informed-RRT* and BIT* take longer as dimensionality increases.The comparison covers offline batch, continual, and active continual training for MPNet.
  • Training efficiency: Continual and active-continual learning use about ten training epochs versus one hundred for offline batch learning, while equal-epoch success rates are similar.Offline batch learning has higher success rates when compared after the differing training schedules used in the experiments.
  • 7DOF Baxter: MPNetPath:NP plans the 7DOF Baxter multi-target trajectory in less than a second, while BIT* takes about 3.01 minutes to find a path within 10% of its cost.The task involves reaching, picking up, and transferring an object to another target; MPNet was not trained on trajectories connecting table-top configurations.
  • SE(3) rigid body: In cluttered SE(3) environments, MPNet achieves about 85% success, with mean computation times of 0.96 and 1.61 seconds for batch and continual models versus 2.84 seconds for BIT*.Mean path costs are 457.80, 512.73, and 836.85 for MPNet batch, MPNet continual, and BIT*, respectively.
  • Neural replanning: Neural replanning addresses failures caused when straight-line connections between collision-free beacon states are themselves not collision-free.Without replanning, MPNet exhibits a success rate of about 60−70%; stochastic replanning helps recover from subproblem failures.

B. Sample Selection Strategies

The paper studies episodic-memory sample selection for continual learning and analyzes MPNet’s completeness guarantees. It reports that global distribution matching performs slightly better than other tested selection metrics and that completeness relies on the underlying sample-based planner.

  • Episodic memory: Continual learning stores a subset of past demonstrations in episodic memory to mitigate catastrophic forgetting as new demonstrations arrive.The memory-selection problem is framed as choosing examples that support a generalizable model from streaming data.
  • Selection strategies: Global distribution matching performs slightly better than reward and coverage maximization on the evaluated seen-Xobs and unseen-Xobs simple 2D datasets.The study compares four sample-selection strategies using mean success rates.
  • Training strategy choice: Active continual learning is preferred when demonstrations are expensive because it requests expert data only when MPNet fails to find a path.Batch offline learning is preferred when abundant offline data can be generated by existing planners.
  • Completeness guarantees: MPNet is stated to eventually find a feasible path whenever one exists, with its worst-case completeness guarantee relying on the underlying sample-based motion planner.The analysis uses RRT* as the oracle sample-based planner because RRT* is probabilistically complete.

1) Probabilistic completeness of MPNetPath:

MPNetPath achieves probabilistic completeness when start and goal states are feasible and a collision-free solution exists, using oracle replanning for non-connectable states. The broader MPNetSMP hybrid retains asymptotic optimality and practical computational advantages through informed sampling and classical planners.

  • Assumptions and guarantee: Under the stated assumptions, MPNetPath finds a path whenever one exists with probability one as the underlying RRT* oracle runs indefinitely.The assumptions require obstacle-free start and goal states and at least one feasible connecting path.
  • Assumptions and guarantee: MPNetPath first generates a coarse neural path, then uses replanning to connect consecutive beacon states that are not directly connectable.The proof sketch attributes the guarantee to applying the assumptions during replanning of these beacon states.
  • MPNetSMP extension: MPNetSMP combines informed sampling with later uniform exploration, allowing its tree to remain connected while eventually covering the configuration space like RRT*.This exploitation-to-exploration schedule supports the underlying sampling-based planner’s completeness behavior.
  • MPNetSMP extension: MPNetSMP retains asymptotic optimality because it changes only the sampling strategy while leaving RRT*’s internal rewiring machinery unchanged.The proposition states that the probability of finding an optimal path approaches one as the graph’s sample count approaches infinity.
  • Computational implications: MPNetSMP has the same O(n log n) complexity as RRT*, while MPNetPath empirically avoids oracle calls in up to 90% of challenging cases.When MPNetPath does need the oracle, it replans only a small segment, reducing the practical workload despite the O(n log n) worst case.
Loading 1907.06013v3…