Learning When to Quit: Meta-Reasoning for Motion Planning

Authors: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

Licences

Open Access
Paper: CC BY 4.0

Everything below draws on the full paper under its CC BY 4.0 licence; its figure is credited to the authors.

TL;DR

Learns from past planner runs when to stop an anytime motion planner (RRT, PRM, Lazy PRM*) so the trade-off between path quality and planning time is maximised.

Why it matters

Any robot that plans with RRT or PRM has to pick a planning time budget, and a fixed time or fixed quality threshold wastes either time or path quality. The method wraps an unmodified anytime planner, so it can be added on top of existing OMPL-style planners as long as training problems from the target environment distribution are available.

Problem

Anytime motion planners keep shortening a path the longer they run, but there is no well-characterised relation between solution quality and computation time, so it is unclear when to stop planning and start moving. Their performance profiles are highly non-smooth because shorter paths appear in sudden jumps when the planner finds a new homotopy class, which rules out simple online extrapolation of future quality.

Proposed solution

The authors learn a stopping policy from performance profiles of past planning problems drawn from the same distribution, maximising a user-weighted utility U(q, t) = wq − (1 − w)t. A model-based variant learns a Markov decision process over discretised quality and time and solves it with value iteration; two model-free variants (a feed-forward classifier on hand-designed features and an RNN sequence-to-sequence model) imitate oracle stop decisions computed post hoc. A CNN predicts the optimal path length from a 2D workspace image so that profiles from problems of different difficulty can be normalised and compared.

Key insights

Optimal stopping times can be computed post hoc for each training run, which turns the policy-learning problem into supervised imitation learning instead of reinforcement learning.
Normalising path quality needs the unknown optimal path length; a CNN that predicts it from a 2D workspace image makes profiles comparable across problems, and a poor normaliser (a straight start-to-goal line) cuts utility sharply.
Richer history features (slope, flatness) make the model-based transition model far more accurate but its estimation cost grows from seconds to more than a day, a direct case of the curse of dimensionality.
The RNN learns its own temporal features from the raw utility sequence and gave the most reliably good results across planners and utility weights.

Main results

CNN optimal-path-length predictor accuracy on 200 held-out workspaces: 88.21%, 96.23% and 94.25% in three environment distributions.
Using the CNN normaliser gave utilities of 0.58, 0.65 and 0.66 in those three environments, against 0.63, 0.70 and 0.67 with ground-truth optimal lengths and 0.39, 0.40 and 0.60 with a straight-line normaliser.
Transition-model held-out loss fell from 1.84 (no features) to 0.22 with (t, q) and 0.10 with (t, q, slope), while estimation time rose from 0.41 s to 10.64 s and 11,933.72 s.
RRT* at w = 0.8: oracle utility 0.677, RNN 0.670, model-based 0.663, classifier 0.658, against 0.634 for the fixed-quality and 0.575 for the fixed-time baseline.
PRM* at w = 0.8: oracle 0.718, model-based 0.702, RNN 0.698, classifier 0.697, fixed quality 0.674, fixed time 0.662.
At w = 0.2 the fixed-quality baseline turned negative (−0.283 for RRT, −0.344 for PRM, −0.367 for Lazy PRM*), while the learned methods stayed positive.

Limitations

The CNN optimal-solution predictor takes a 2D workspace image, which limits the methods to problems with planar workspaces; extension to 3D via voxel grids or point clouds is suggested but not done.
A new problem is assumed to come from the same distribution as the training problems, and training needs many long planner runs on representative problems.
Adding history features to the model-based method was computationally infeasible for the larger experiments, so it used only (q, q_prev, t).
All evaluation is in simulation with a three-degree-of-freedom rigid robot in 2D workspaces; no physical robot was tested.
Only a linear utility U(q, t) = wq − (1 − w)t was studied.

Field impact

The paper was a finalist for the IROS 2021 Best Paper Award on Cognitive Robotics and has 14 citations. It does not state a code or data release.

Abstract

Anytime motion planners are widely used in robotics. However, the relationship between their solution quality and computation time is not well understood, and thus, determining when to quit planning and start execution is unclear. In this paper, we address the problem of deciding when to stop deliberation under bounded computational capacity, so called meta-reasoning, for anytime motion planning. We propose data-driven learning methods, model-based and model-free meta-reasoning, that are applicable to different environment distributions and agnostic to the choice of anytime motion planners. As a part of the framework, we design a convolutional neural network-based optimal solution predictor that predicts the optimal path length from a given 2D workspace image. We empirically evaluate the performance of the proposed methods in simulation in comparison with baselines.

Open Source Robotics