Matt Strong

Matt Strong

CS PhD at Stanford University

← Paper Digest

PDDLStream: Integrating Symbolic Planners and Blackbox Samplers via Optimistic Adaptive Planning

Caelan Reed Garrett, Tomás Lozano-Pérez, Leslie Pack Kaelbling

Seminal February 2018

TL;DR PDDLStream extends the PDDL planning language with streams, blackbox samplers such as IK solvers and motion planners, and solves the result as a sequence of finite PDDL problems. Its new Adaptive algorithm solves about 98% of 5-block packing problems, where the earlier algorithms solve about 10%.

What they do

Task and motion planning needs continuous values (poses, grasps, trajectories) that only procedures such as IK solvers and motion planners can produce. PDDLStream adds streams to PDDL: blackbox conditional generators plus a declarative statement of the facts their outputs satisfy. Domain-independent algorithms reduce a PDDLStream problem to a sequence of finite PDDL problems, each solved by an unmodified planner (FastDownward). The appendix proves the algorithms semi-complete, i.e. complete over feasible problems.

How it works

  • Streams. A stream.pddl file declares each stream’s inputs, domain facts, outputs and certified facts; its generator is ordinary Python code (sample stable poses, call IK, plan a motion, check collisions).
  • Optimistic planning. Rather than evaluating every stream eagerly (Incremental), the planner first plans with placeholder objects, one per stream instance, then evaluates only the streams that plan needs (Focused). A level per fact bounds evaluations and grows when no plan is found.
  • Binding. Each stream’s outputs feed the later streams of the same plan, so a whole stream plan is checked at once.
  • Adaptive. Keeps a queue of partially bound stream plans and keeps sampling bindings for them, splitting time equally between search and sampling. Rebinding also resamples objects already fixed in a plan, to lower its cost.

Results

100 random problems per domain, 2-minute timeout:

  • Domain 1 (PR2 packing blocks into a small region): with 5 blocks Adaptive solves about 98% of problems, Focused and Binding about 10%, Incremental none (Figure 3).
  • Domain 2 (place one of two blocks while minimizing base travel): after 120 s Adaptive’s mean plan cost is about 19, versus about 41-43 for Focused and Binding (Figure 4). Incremental solved only 83% of instances.
  • Domain 3 (two rovers): the three optimistic algorithms beat Incremental and perform about equally.
  • A real PR2 planned and executed serve, cook, stack and coffee tasks.

Limitations

Adaptive’s advantage shrinks in less geometrically constrained domains (Domain 3). The completeness proof for the optimistic algorithms assumes each stream output is unique to one stream instance; otherwise extra, expensive test streams are needed. Real-robot plans run open-loop.

Figures

From Figure 1: A real PR2 planning to serve a meal, a cup and a cooked cabbage (green block), on the brown tray.
From Figure 1: A real PR2 planning to serve a meal, a cup and a cooked cabbage (green block), on the brown tray.
From Figure 1: Domain 1 with 5 blocks; the PR2 must pack every blue block into the small green region.
From Figure 1: Domain 1 with 5 blocks; the PR2 must pack every blue block into the small green region.
From Figure 2: Domain 3 with 4 objectives; two rovers photograph the blue objectives and report to the lander by line...
From Figure 2: Domain 3 with 4 objectives; two rovers photograph the blue objectives and report to the lander by line of sight.
From Figure 3: Fraction of Domain 1 problems solved by each algorithm with 3 to 5 blocks.
From Figure 3: Fraction of Domain 1 problems solved by each algorithm with 3 to 5 blocks.
Abstract

Many planning applications involve complex relationships defined on high-dimensional, continuous variables. For example, robotic manipulation requires planning with kinematic, collision, visibility, and motion constraints involving robot configurations, object poses, and robot trajectories. These constraints typically require specialized procedures to sample satisfying values. We extend PDDL to support a generic, declarative specification for these procedures that treats their implementation as black boxes. We provide domain-independent algorithms that reduce PDDLStream problems to a sequence of finite PDDL problems. We also introduce an algorithm that dynamically balances exploring new candidate plans and exploiting existing ones. This enables the algorithm to greedily search the space of parameter bindings to more quickly solve tightly-constrained problems as well as locally optimize to produce low-cost solutions. We evaluate our algorithms on three simulated robotic planning domains as well as several real-world robotic tasks.

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.