PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:1802.08705v5cs.AIcs.RO

TL;DR

Continuous robotic planning requires satisfying complex constraints whose values are typically produced by specialized procedures. PDDLStream represents those procedures as black-box streams and provides planners that reduce problems to finite PDDL searches, with Adaptive balancing exploration and exploitation. Across robotic domains and real-world tasks, the framework and Adaptive algorithm support constrained, cost-sensitive planning and low-cost solutions.

  • Problem

    Planning in continuous spaces requires coordinating high-dimensional variables under complex kinematic, collision, visibility, and motion constraints.

  • Method

    PDDLStream extends PDDL with declarative streams for black-box sampling procedures, while its algorithms solve a sequence of finite PDDL problems and Adaptive balances search with sampling.

  • Results

    PDDLStream supports three simulated robotic domains and real-world robot tasks, while Adaptive outperforms existing algorithms particularly on tightly constrained and cost-sensitive problems.

  • Takeaways & Limitations

    Adaptive greedily explores bindings and locally optimizes discovered plans, enabling PDDLStream to produce low-cost solutions for constrained robotic planning.

  • Takeaways & Limitations

    Incremental eagerly evaluates all stream instances, causing overhead when stream evaluations such as inverse kinematics and motion planning are expensive.

Abstract

from arXiv · show

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.

1 Introduction

PDDLStream extends PDDL with a declarative interface for black-box sampling procedures in continuous, constraint-rich planning. Its Adaptive algorithm balances exploring new plans with exploiting existing bindings, outperforming prior algorithms on constrained and cost-sensitive problems and supporting real-world robot planning.

  • Motivation: Continuous robotic planning must coordinate configurations, trajectories, poses, and grasps under kinematic, collision, visibility, and motion constraints.Known specialized procedures include inverse kinematics solvers, collision checkers, and motion planners.
  • PDDLStream: PDDLStream introduces streams that combine conditional generators with declarative facts describing valid inputs and guaranteed output properties.The planner reasons about stream conditions while treating each generator implementation as a black box.
  • Algorithms: Its algorithms construct and solve a sequence of finite PDDL problems, while Adaptive balances searching for optimistic plans against sampling bindings for existing plans.This balance can more aggressively find parameter bindings for existing optimistic plans.
  • Evaluation: Adaptive greatly outperforms two existing algorithms on constrained and cost-sensitive problems, and PDDLStream is also applied to real-world manipulation and kitchen tasks.The experiments use three robotic planning domains and include a robot planning manipulation and kitchen tasks.

2 Related Work

Prior approaches integrate numeric reasoning or black-box procedures with PDDL, but their domain restrictions or specialization limit application to broad continuous robotic planning domains.

  • Numeric planning: Numeric PDDL extensions support variables evolving over time, but most numeric planners handle only linear or polynomial dynamics.Non-polynomial dynamics can sometimes be handled by discretizing time, while analytic encodings of collision constraints may become enormous.
  • Semantic attachments: Semantic attachments connect external modules to PDDL planners, but finite action parameter types restrict them to finite action spaces.This limits their applicability in robotics to domains that are prediscretized.
  • Robotic planning: Existing robotic task-and-motion approaches handle continuous spaces beyond prediscretization but are specialized and require substantial engineering to transfer to new domains.The passage specifically contrasts this limitation with applying the approach to domains such as rovers.

3 PDDLStream

PDDLStream augments PDDL with conditional generators and declarative stream specifications, defining potentially infinite certified facts while retaining compatibility with standard PDDL planning.

  • Language design: PDDLStream is built on PDDL so practitioners can use standard descriptions and off-the-shelf PDDL planners without modifying the planner.The formalism also applies to several ADL features beyond the STRIPS presentation used for exposition.
  • Generators: A conditional generator maps input objects to a finite or infinite enumerable sequence of output tuples.Calling next returns the subsequent tuple when one exists and None otherwise.
  • Streams: A stream adds declarative domain facts for legal inputs and certified predicates that hold for every generated input-output pair.External cost functions declare input domains and return nonnegative costs without producing objects or certifying facts.
  • Problem definition: A PDDLStream problem consists of actions, streams, an initial state, and goals, with streams recursively augmenting the initial state into a potentially infinite fact set.Stream-certified predicates cannot be negated in action preconditions to ensure Turing-recognizability.
  • Solutions: A solution plan is executable when the preimage of its actions and goals is contained in the stream-augmented initial facts.For cost-sensitive planning, the objective is to minimize summed action costs; the planning problem is undecidable, while the algorithms are semi-complete over feasible instances.
  • Representation: PDDLStream keeps declarative actions and predicates in PDDL while expressing generators, initial states, and goals programmatically when first-class objects are needed.This supports real-valued vectors and generator functions operating on non-string entities.

4 Example Domains

The paper demonstrates PDDLStream across manipulation and multi-robot surveying domains whose actions depend on sampled geometric, kinematic, motion, visibility, and collision constraints. The examples also expose cost trade-offs and the stream structure used to encode these tasks.

  • Domain 1: Domain 1 is a mobile-manipulation task in which a PR2 tightly packs blue blocks into a green region.The domain defines move, pick, and place actions and uses derived predicates for containment and safety.
  • Domain 2: In Domain 2, the optimal plan picks the nearer blue block, requiring more actions but less robot travel after moving a red block out of the way.The example illustrates why minimizing travel distance can favor a longer action sequence.
  • Manipulation representation: The manipulation model represents 6 DOF poses and grasps, 11 DOF configurations, waypoint trajectories, and predicates for kinematics, motion, containment, and collision freedom.AtConf, AtPose, Holding, and Empty are fluent predicates, while the remaining listed geometric predicates are static.
  • Manipulation streams: The poses, grasps, inverse-kinematics, motion, and collision-free streams sample placements, grasps, configurations, trajectories, and associated feasibility facts.The inverse-kinematics stream takes pose and grasp inputs to sample configurations on a 4D redundancy manifold.
  • Domain 3: Domain 3 uses two rovers to collect samples, photograph objectives without occlusion, and communicate results to a lander under visibility, distance, reachability, and collision constraints.The domain extends rovers with 3D geometric constraints and is shown with four objectives.

5 PDDLStream Algorithms

PDDLStream algorithms reduce potentially infinite stream-based planning problems to finite PDDL searches of increasing size. They control generated-object width and depth through fact levels while using existing PDDL planners.

  • 5 PDDLStream Algorithms: Four algorithms solve a sequence of finite PDDL problems of increasing size using sound and complete classic-PDDL search procedures.The algorithms can use off-the-shelf PDDL planners and can also run in an anytime fashion.
  • 5 PDDLStream Algorithms: Fact levels limit both infinitely many stream outputs and unbounded compositions of stream instances.A fact’s level reflects the number of stream evaluations required to certify it.
  • 5 PDDLStream Algorithms: Each algorithm records every certified fact’s level and the stream instance that certified it.Stream-instance levels combine domain-fact levels with the number of prior evaluations.
  • 5 PDDLStream Algorithms: External cost-function instances receive the maximum level among their domain facts, ensuring evaluation at the earliest possible level.The level is defined as max over the levels of the cost function’s domain facts.

6 Incremental Algorithm

Incremental planning evaluates stream instances level by level, adds their certified facts to a finite PDDL state, and searches that state for a goal plan. Its exhaustive evaluation can create substantial irrelevant overhead.

  • 6 Incremental Algorithm: Incremental increases the maximum level l, evaluates all legal stream instances through that level, and then searches for a plan.It uses next to query the next output tuple from each stream generator.
  • 6 Incremental Algorithm: INSTANTIATE grounds stream instances whose domain facts are currently certified in U.These legal instances are then considered by APPLY-STREAMS at the active levels.
  • 6 Incremental Algorithm: The certified-fact map U becomes the initial state of a finite PDDL problem, and SEARCH returns a plan when one exists.A returned plan is treated as a solution to the PDDLStream problem.
  • 6 Incremental Algorithm: ADD-CERTIFIED records newly certified facts at the stream instance’s level when OUTPUT produces an output tuple.If the generator returns None, no certified facts are added.
  • 6 Incremental Algorithm: Incremental eagerly evaluates all stream instances, producing many facts irrelevant to the task and potentially incurring substantial computational overhead.The overhead is especially significant when evaluations require expensive inverse-kinematics solvers or motion planners.

7 Optimistic Algorithms

Optimistic algorithms first plan with objects representing possible stream outputs, then identify and evaluate the stream instances supporting those plans. This lazily focuses sampling on candidate plans rather than evaluating every stream indiscriminately.

  • 7 Optimistic Algorithms: Optimistic planning creates candidate objects for stream outputs and searches using optimistic facts before validating those outputs.This separates candidate-plan discovery from stream evaluation.
  • 7 Optimistic Algorithms: Unique optimistic objects are created for individual stream instances rather than shared across all instances of a stream.This differs from directly applying the earlier shared-object approach.
  • 7 Optimistic Algorithms: Each unique optimistic object encodes a partially ordered set of stream-instance evaluations that could produce its value.This representation supports the Binding and Adaptive algorithms.
  • 7 Optimistic Algorithms: Because unique optimistic objects can grow without bound, the algorithms regulate optimistic stream instances by iteratively increasing their maximum level.This controls the number of unique optimistic objects considered at once.
  • 7 Optimistic Algorithms: OPTIMISTIC repeatedly applies optimistic streams, searches for a plan, retraces its supporting stream plan, and processes that plan for a solution.RETRACE recursively collects stream instances supporting the optimistic facts in the plan’s preimage.
  • 7 Optimistic Algorithms: Focused evaluates eligible stream instances from the retraced plan and forces another search iteration after advancing a stream instance’s level.If the optimistic plan uses no optimistic objects, it is returned directly.

8 Binding and Adaptive Algorithms

Binding propagates sampled outputs through a candidate stream plan, while Adaptive repeatedly prioritizes partial bindings to balance new-plan exploration with exploitation. Rebinding fixed generated objects expands the binding space for feasible and low-cost solutions.

  • 8 Binding and Adaptive Algorithms: Focused fails to fully exploit plans returned by SEARCH, motivating Binding and Adaptive procedures that process more of each stream plan.Adaptive can reduce the number of SEARCH calls needed to find a solution.
  • 8 Binding and Adaptive Algorithms: Binding maintains assignments from optimistic objects to sampled objects and substitutes those assignments into later stream inputs and action arguments.Successful stream evaluations update the bindings; complete bindings are applied to the optimistic plan.
  • 8 Binding and Adaptive Algorithms: Unique optimistic objects create a bijection with the corresponding outputs of their stream instances, enabling Binding to propagate values through a plan.This correspondence links each optimistic output to one stream-instance evaluation.
  • 8 Binding and Adaptive Algorithms: Binding terminates when a stream evaluation returns None, and failed stream instances receive increased levels before being reconsidered.In the example, an inverse-kinematics failure raises the affected stream levels and delays certain optimistic sequences.
  • 8 Binding and Adaptive Algorithms: Adaptive retains partial bindings in a persistent queue so previously identified stream plans can be reattempted across invocations.Each queue entry stores a stream plan, optimistic plan, bindings, and the next stream-plan index.
  • 8 Binding and Adaptive Algorithms: Adaptive’s priority queue favors less-evaluated stream instances and plans with fewer unbound optimistic objects.This implements an optimism-in-the-face-of-uncertainty strategy for selecting partial bindings.
  • 8 Binding and Adaptive Algorithms: Rebinding extracts producers of non-optimistic objects, allowing those fixed objects to vary and enabling faster searches for feasible and low-cost solutions.The approach can explore trajectory-distance costs involving objects that were previously fixed.

9 Experiments

The experiments compare four PDDLStream algorithms across three simulated domains and demonstrate application to real-world robotic manipulation and kitchen tasks.

  • Simulated domains: Four algorithms were evaluated on 100 randomly generated problems across three domains using a 2 minute timeout including stream evaluation.Incremental and Focused serve as baselines representing prior work.
  • Simulated domains: Adaptive outperforms Incremental, Focused, and Binding in tightly constrained Domain 1 as the number of blocks increases from 3 to 5.Its advantage is attributed to aggressively searching over many bindings of a single stream plan.
  • Simulated domains: Adaptive converges to a low-cost solution more quickly than Focused and Binding in cost-sensitive Domain 2.Incremental is omitted because it solved only 83% of the problem instances.
  • Simulated domains: Focused, Binding, and Adaptive outperform Incremental and perform about equivalently in the less geometrically constrained Domain 3.Adaptive’s additional stream-binding computation only marginally increases runtime.
  • Real-world tasks: PDDLStream was applied to four real-world task-and-motion-planning problems using a PR2 robot operating with actions such as move, pick, place, pour, and cook.Each manipulation action is supported by streams that sample continuous control parameters and robot trajectories.

10 Conclusion

PDDLStream provides a general-purpose interface for incorporating blackbox sampling procedures into PDDL planning. Its Adaptive algorithm balances search and sampling, improving performance particularly on tightly constrained and cost-sensitive problems while supporting diverse real-world robotic actions.

  • Conclusion: PDDLStream is a general-purpose framework for incorporating sampling procedures in a planning language.Streams connect declarative planning specifications with procedural sampling.
  • Conclusion: Two new algorithms reduce PDDLStream planning to solving a series of finite PDDL problems.This permits use of off-the-shelf PDDL planners as search subroutines.
  • Conclusion: Adaptive balances search and sampling to explore many possible bindings and greedily optimize discovered plans.The conclusion identifies particular benefits on tightly constrained and cost-sensitive problems.
  • Conclusion: PDDLStream was demonstrated on real-world robots operating with a diverse set of actions.

A Theoretical Results

PDDLStream planning is undecidable in general but semi-decidable, so the paper studies semi-complete algorithms for feasible instances under explicit assumptions. Theoretical results establish semi-completeness for incremental, focused, binding, and adaptive algorithms, with modifications needed when stream outputs are not unique.

  • Undecidability: PDDLStream plan existence is undecidable when conditional generators are Turing complete.A reduction from the halting problem uses a stream that simulates one Turing-machine step per evaluation and certifies Reachable exactly when the machine halts.
  • Semi-completeness: The algorithms are analyzed as semi-complete over feasible problem instances because PDDLStream planning is semi-decidable.The framework assumes SEARCH is a sound and complete PDDL planner; cost-sensitive planning instead targets feasibility below a specified threshold C.
  • Semi-completeness: The incremental algorithm is semi-complete because a finite subset of expanded initial facts eventually supports any solution plan.Once those facts enter the constructed state, SEARCH returns a solution by soundness and completeness.
  • Stream output uniqueness: These three algorithms require an additional test stream when output objects are not unique to one stream instance.Without this modification, certifying the same object through multiple streams may require repeatedly evaluating a stream to regenerate it.
  • Stream output uniqueness: The uniqueness assumption is typically plausible for independent samplers over uncountably infinite spaces, where duplicate outputs have probability zero.The paper illustrates this with two streams sampling independently and uniformly from a bounded real interval.
  • Semi-completeness: The focused, binding, and adaptive algorithms are semi-complete after reserving expensive test streams until the level exceeds a sufficiently large constant.This prevents optimistic planning from repeatedly enumerating generators merely to test unlikely memberships.

B.2 Real-World Experiments

The paper evaluates PDDLStream on real-world robotic manipulation and kitchen tasks, including serve, cook, and stack scenarios. The cook task requires an intermediate placement to hand a cabbage from the robot’s right arm to its left arm.

  • Real-World Experiments: The real-world evaluation includes robotic manipulation and kitchen tasks such as serve, cook, and stack.In the cook task, the robot places cabbage on a stove, turns it on, and transfers the cooked cabbage to a tray.
  • Real-World Experiments: The cook task requires an intermediate placement because the robot’s left arm cannot initially reach the cabbage.This placement enables a handoff from the right arm to the left arm before completing the cooking sequence.
Loading 1802.08705v5…