Integrated Task and Motion Planning

Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, Tomás Lozano-Pérez

★ Must read October 2020

TL;DR A review that frames task and motion planning (TAMP) as a search over discrete plan skeletons plus the continuous constraints each skeleton induces. It sorts 33 lines of prior work by whether they sequence actions first, satisfy constraints first or interleave the two, and by whether they use pre-discretized values, sampling or optimization.

What they do

A manipulating robot must choose actions, their continuous parameters (which grasp, where to place an object) and collision-free motions. This review treats all three as one problem, task and motion planning (TAMP), and gives one framework for comparing the algorithms that solve it.

How it works

Modes. Picking or placing an object changes which degrees of freedom can move. Mode switches happen only where two modes’ feasible sets intersect, usually a lower-dimensional set.
Plan skeletons. Task-planning action templates get continuous parameters and constraints such as kinematics, stable placement, grasp, motion and collision-free. Fixing the action sequence leaves a hybrid constraint satisfaction problem (H-CSP) over the free parameters.
Solving H-CSPs. Joint satisfaction optimizes all parameters at once. Individual satisfaction chains conditional samplers, for example a stable pose followed by IK for that pose.
Combining the searches. Methods sequence first, satisfy first or interleave the two. They can also reuse solved constraints or small unsatisfiable sub-problems across skeletons.

Results

Table 1 places 33 lines of work (8 multi-modal motion planning, 25 TAMP) in a 3x3 grid. No listed method combines satisfaction-first with optimization.
Sequencing first pays off when action sequencing is cheap and H-CSPs are expensive. Satisfying first pays off when sampling does not blow up combinatorially, each discrete search has real overhead, and sampled values rarely meet critical constraints.
Joint satisfaction needs one solution per skeleton and lets constraints steer each other, but needs differentiable constraints, which collisions rarely provide. Samplers need only black-box checks but must cover the whole solution space.

Limitations

Scope is limited to deterministic actions, fully known state, rigid objects of known shape and holonomic robots. There is no new algorithm or experiment, and the table is not exhaustive. Sampling and optimization solvers cannot prove a problem infeasible. Dynamics, deformables, uncertainty and learning are left as open directions.

Figures

From Figure 1: The goal is to pour the blue cup into the white bowl. The green block blocks reachable grasps of the c... — From Figure 1: The goal is to pour the blue cup into the white bowl. The green block blocks reachable grasps of the cup, so the planner moves the block first, then picks up the cup and pours.

From Figure 4: Feasible configurations of a 1D robot and one movable object in two transit modes (robot free) and two... — From Figure 4: Feasible configurations of a 1D robot and one movable object in two transit modes (robot free) and two transfer modes (robot holding the object). The robot can switch modes only at the single points where these lines cross; right, the graph of legal mode switches.

From Figure 8: A plan skeleton (move, pick, move while holding, place on the stove, cook) drawn as a factor graph. Ro... — From Figure 8: A plan skeleton (move, pick, move while holding, place on the stove, cook) drawn as a factor graph. Round nodes are state variables, boxes are constraints, grey values are constants and thick black lines are values held fixed over time.

From Figure 11: Two representative TAMP algorithms. Top: search for a plan skeleton, then solve all its constraints j... — From Figure 11: Two representative TAMP algorithms. Top: search for a plan skeleton, then solve all its constraints jointly. Bottom: sample values for individual constraints, then search for a plan that uses them, sampling more on failure.

Abstract

The problem of planning for a robot that operates in environments containing a large number of objects, taking actions to move itself through the world as well as to change the state of the objects, is known as task and motion planning (TAMP). TAMP problems contain elements of discrete task planning, discrete-continuous mathematical programming, and continuous motion planning, and thus cannot be effectively addressed by any of these fields directly. In this paper, we define a class of TAMP problems and survey algorithms for solving them, characterizing the solution methods in terms of their strategies for solving the continuous-space subproblems and their techniques for integrating the discrete and continuous components of the search.

Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.

Matt Strong