PaperlayerView exact revision on arXiv

Source-linked AI summary

Predicate Invention for Bilevel Planning

Tom Silver, Rohan Chitnis, Nishanth Kumar, Willie McClinton, Tomas Lozano-Perez, Leslie Pack Kaelbling, Joshua Tenenbaum

arXiv:2203.09634v3cs.AIcs.LGcs.RO

TL;DR

Manually designed predicates remain a bottleneck for bilevel planning, despite prior learning of operators and samplers when predicates are supplied. The paper learns predicates through grammar-based search guided by a tractable surrogate for planning efficiency. Its learned abstractions solve more held-out tasks within the timeout than baselines and are competitive with hand-designed predicates.

  • Problem

    Bilevel planning depends on symbolic predicates that engineers must design, even though operators and samplers can be learned from demonstrations once predicates are provided.

    Source: §1 · p. 1

  • Method

    The method searches grammar-generated predicate sets by hill climbing, guided by a tractable surrogate intended to preserve the ordering of predicate sets under the real planning objective.

    Source: §5 · p. 4, §5.1 · p. 5

  • Results

    The method solves many more held-out tasks within the timeout than baselines and is on par with, or sometimes better than, hand-designed predicates; on PickPlace1D, its predicates are 7.5x better.

    Source: Results and Discussion · pp. 7–8

  • Takeaways & Limitations

    Predicate variation that appears inconsequential on inspection can substantially affect planning efficiency, supporting a surrogate sensitive to downstream planning performance.

    Source: Results and Discussion · p. 8

    Refinability estimation assumes near-optimal demonstrations, treating abstract plans cheaper than demonstrated plans as suspicious.

    Source: Estimating Refinement Probability · p. 5

Abstract

from arXiv · show

Efficient planning in continuous state and action spaces is fundamentally hard, even when the transition model is deterministic and known. One way to alleviate this challenge is to perform bilevel planning with abstractions, where a high-level search for abstract plans is used to guide planning in the original transition space. Previous work has shown that when state abstractions in the form of symbolic predicates are hand-designed, operators and samplers for bilevel planning can be learned from demonstrations. In this work, we propose an algorithm for learning predicates from demonstrations, eliminating the need for manually specified state abstractions. Our key idea is to learn predicates by optimizing a surrogate objective that is tractable but faithful to our real efficient-planning objective. We use this surrogate objective in a hill-climbing search over predicate sets drawn from a grammar. Experimentally, we show across four robotic planning environments that our learned abstractions are able to quickly solve held-out tasks, outperforming six baselines. Code: https://tinyurl.com/predicators-release

1 Introduction

Bilevel planning can support long-horizon decision-making in continuous spaces, but manually designing its symbolic abstractions is a scaling bottleneck. This work learns predicates from demonstrations using a tractable surrogate for planning efficiency, then uses them to learn operators and samplers for held-out tasks.

1 Introduction

  • Manual design of predicates, operators, and samplers is a bottleneck in scaling bilevel planning, although operators and samplers can be learned from 50–200 demonstrations when predicates are given.The paper targets the missing predicate-learning step.Source: §1 · p. 1
  • The real objective—fast, successful bilevel planning over a task distribution—is too expensive to evaluate directly because each evaluation requires sampler training and planning.The method therefore uses a tractable surrogate connected to the real objective.Source: §1 · p. 1
  • A grammar-based hill-climbing search uses demonstrations and a tractable surrogate objective to learn predicates, which are then used to learn operators and samplers.Together, these learned components support bilevel planning on new tasks.Source: §1 · p. 1
  • The learned abstractions support efficient planning on held-out tasks with more objects, longer horizons, and larger goals than the demonstrations, and outperform objectives based on prediction error, bisimulation, and inverse planning.The framework learns predicates, operators, and samplers from demonstrations across robotic planning environments.Source: §1 · pp. 1–2
  • The framework uses learned predicates to map continuous states into abstract states, then learns operators and samplers to guide planning back in continuous spaces.Figure 1 illustrates this pipeline in a Blocks example.Source: Figure 1 · p. 2

2 Problem Setting

The paper considers deterministic, goal-based planning problems with typed objects, continuous state features, and hybrid actions. Demonstrations provide near-optimal plans for training tasks, and the objective is to solve held-out tasks efficiently.

2 Problem Setting

  • Each task has a typed object set that induces a state space, with each object represented by a real-valued feature vector.The object set can vary between tasks.Source: §2 · p. 2
  • Actions combine typed object arguments with continuous controller parameters, and a known deterministic transition model is shared across tasks.The environment is represented by controllers with discrete typed parameters and continuous parameters.Source: §2 · p. 2
  • A task specifies an initial state and a goal of ground atoms; a solution is an action sequence that reaches a state satisfying every goal atom.The goal predicates are given and sufficient to express goals, but are practically insufficient as state abstractions on their own.Source: §2 · p. 2
  • Training provides one near-optimal demonstration per task, and the objective is to efficiently solve held-out tasks using what is learned from those demonstrations.The transition model makes the state sequence for each demonstration recoverable.Source: §2 · p. 2

3 Predicates, Operators, and Samplers

The planning abstraction has three linked components: predicates define discrete states, operators define abstract actions and transitions, and samplers refine abstract actions into executable actions. These abstractions are learned to support planning despite lost geometric information.

3 Predicates, Operators, and Samplers

  • Predicates map continuous states to discrete abstract states by collecting the ground atoms that hold true.The learned predicate set augments the given goal predicates, which are typically too limited to serve alone as state abstractions.Source: §3 · p. 3
  • Operators encode typed parameters, predicate-based preconditions and effects, and a controller with its object arguments.Ground operators form the abstract action space and induce an abstract transition model by applying their add and delete effects.Source: §3 · p. 3
  • Each operator's sampler proposes a distribution over continuous controller parameters conditioned on the state and objects, refining abstract actions into task actions.The ground sampler is state-conditioned for a specific operator instance.Source: §3 · p. 3
  • The learned abstractions require only weak semantics: each ground operator must have some state and sampled parameters that realize its predicted abstract transition.Unlike downward refinability, this condition need not hold for every state where the operator is abstractly applicable.Source: §3 · p. 3

4 Bilevel Planning

Bilevel planning searches for abstract plans and then attempts to refine each into a task-level solution. Because abstract plans are not guaranteed to be refinable, failed refinements lead the planner to generate another candidate plan.

4 Bilevel Planning

  • The planner searches over abstract plans using predicates and operators, then searches for refinements using predicates and samplers.An abstract plan is a sequence of ground operators that reaches the goal in the abstract transition model.Source: §4 · pp. 3–4
  • Because abstract plans are not guaranteed to refine into task solutions, the planner does not revisit earlier abstract plans and is not probabilistically complete.Extensions to ensure completeness are described as straightforward but outside the paper's focus.Source: §4 · p. 4
  • The outer search uses A* with a domain-independent heuristic to generate abstract plans one at a time, subject to a maximum plan count.The planner uses STRIPS-style predicates and operators to derive the heuristic.Source: §4 · p. 4
  • For each candidate, the inner search samples continuous parameters, checks the resulting state against the expected abstract sequence, and backtracks when a step fails.If refinement succeeds, the task-level plan is returned; if it fails, the planner generates the next abstract plan.Source: §4 · p. 4

5 Learning from Demonstrations

The method learns predicates before operators and samplers, using a surrogate objective to guide search toward abstractions for efficient bilevel planning. It estimates planning time from demonstrations and adds predicates through hill climbing over a complexity-regularized grammar.

5 Learning from Demonstrations

  • The pipeline first invents predicates, then learns the operators and samplers needed for bilevel planning.Operator learning is fast, while sampler learning is slow; both require predicates.Source: §5 · p. 4

5.1 Scoring a Candidate Predicate Set

  • The real objective is efficient planning after learning operators and samplers, but its evaluation is too costly to guide repeated predicate-set searches.Sampler training and repeated refinement searches are the stated bottlenecks.Source: §5.1 · p. 5
  • The surrogate uses demonstrations to estimate planning time without training samplers or running refinement, aiming to preserve the real objective’s ranking of predicate sets.It evaluates abstract plans and estimates whether refinement would succeed.Source: §5.1 · p. 5

Estimating Refinement Probability

  • Refinement probability is estimated from abstract-plan cost relative to the near-optimal demonstration cost: cheaper plans look suspicious, while costlier plans may take longer to reach.The estimate needs only demonstration-plan costs, not their contents.Source: Estimating Refinement Probability · p. 5

Estimating Time

  • Estimated total planning time combines abstract-search nodes with an estimated refinement cost, while a large penalty covers cases where no abstract plan succeeds.The refinement estimate represents the potentially repeated backtracking searches that fail before one succeeds.Source: Estimating Time · p. 6

5.2 Local Search over Candidate Predicate Sets

  • Hill climbing starts from the goal predicates and adds the single predicate that most improves the surrogate until no improvement remains.The grammar balances expressivity against search practicality; complexity costs regularize against neutral predicates, and candidates are enumerated from simpler to more complex.Source: §5.2 · p. 6, Designing a Grammar of Predicates · p. 6

6 Experiments

Across four robotic environments, the proposed method solves more held-out tasks within the timeout than the baselines, and its learned predicates are on par with or sometimes better than manual abstractions. The experiments test harder tasks than training, including different object counts and goals.

Experimental Setup

  • Evaluation uses 50 tasks per seed with more objects and harder goals than training, under a 10-second planning timeout.Results are averaged over 10 random seeds; demonstrations come from bilevel planning with manually defined abstractions.Source: Experimental Setup · p. 6

Environments

  • The four environments span 1D pick-and-place, 3D block stacking, multistep painting, and tool-based assembly, with evaluation plans ranging from 1 to 25 actions.Tools includes physical constraints that the predicate grammar cannot model.Source: Environments · p. 6

Results and Discussion

  • Our method solves many more held-out tasks within the timeout than the baselines across four robotic planning environments.Figure 3 reports the percentage of 50 evaluation tasks solved under a 10-second timeout, averaged over 10 seeds.Source: Figure 3 · p. 7, Results and Discussion · p. 7

Methods

  • The comparison includes six baselines, a manual abstraction, and two ablations; several baselines differ from the proposed method only in predicate learning.The methods also include GNN policies and random controller execution.Source: Methods · p. 7

Results and Discussion

  • Bisimulation often selects useful predicates but too few for effective planning; in Blocks, Clear and HandEmpty help planning despite not being needed for bisimulation on the demonstrations.The authors attribute the gap to prediction accuracy alone not ensuring good planning performance.Source: Results and Discussion · pp. 7–8
  • The learned abstractions are on par with or sometimes better than manual ones, and often achieve very good evaluation performance with just 50 demonstrations.Changing the abstract-search heuristic also revealed that apparently inconsequential predicate differences can substantially affect planning efficiency.Source: Results and Discussion · p. 8

7 Related Work

The paper builds on work learning symbolic abstractions for decision-making and AI planning, but distinguishes itself by optimizing for downstream planning efficiency. It also draws on prior work in multilevel planning for its operator and sampler learning methods.

7 Related Work

  • Earlier symbolic-abstraction objectives often use autoencoding, prediction error, or bisimulation, treating abstractions as replacements for planning in the original transition space.The paper instead treats abstractions as guides for planning.Source: §7 · p. 8
  • Prior research has learned abstractions, action abstractions, or refinement strategies for task and motion planning and hierarchical planning.The authors draw inspiration from these works for operator and sampler learning.Source: §7 · p. 8
  • The distinguishing feature claimed here is explicit optimization of an objective that accounts for downstream planning efficiency.The paper also situates its work among research on learning state abstractions for decision-making.Source: §7 · p. 8

8 Conclusion and Future Work

The paper presents predicate learning explicitly optimized for efficient bilevel planning. Future work includes learning from fewer demonstrations, expanding the predicate grammar, addressing partial observability, and learning controllers.

8 Conclusion and Future Work

  • The paper’s method learns predicates explicitly optimized for efficient bilevel planning.The authors identify active learning, a more expressive grammar, partial observability, and controller learning as future directions.Source: §8 · p. 8
  • Learning controllers would remove the work’s assumption that controllers are given and complete the pipeline for learning predicates, operators, samplers, and controllers.The authors also propose exploring online data gathering, more expressive predicates, and partially observed planning.Source: §8 · p. 8

A.1 Operator Learning

Operator learning groups demonstrated transitions into operator schemas, then learns preconditions by intersecting their abstract states. The procedure is sound over the demonstrations, while its representation restrictions trade expressiveness for efficient learning.

A.1 Operator Learning

  • Two representation restrictions enable operator learning in linear time in the number of demonstrated transitions, but rule out multiple schemas for a controller/effect pair and indirect effects.Predicate invention can compensate for indirect effects by quantifying out objects absent from the controller or effects.Source: §A.1 · p. 11
  • Transitions are abstracted with the learned predicates, grouped when their effects and partially specified controllers unify, and converted into operators with parameters, controllers, and effects.Each equivalence class induces one operator; intersecting its abstract states supplies the preconditions.Source: §A.1 · p. 11
  • The procedure is sound over the demonstrations: each transition has a grounded learned operator whose abstract effects match the demonstrated successor state.Thus, the learned abstractions obey the defined semantics with respect to the training data.Source: §A.1 · p. 11
  • The equivalence classes also provide local datasets and substitutions that are reused during sampler learning.Each transition in a class supplies an example of that operator’s preconditions, controller, and effects.Source: §A.1 · p. 11

A.2 Operator Learning Extended Example

The extended example walks through operator learning on four transitions: transitions are grouped by unifiable effects, and preconditions are obtained by intersecting appropriately grounded abstract states. The resulting operators omit irrelevant color predicates.

A.2 Operator Learning Extended Example

  • Four example transitions are grouped into two equivalence classes by whether their effects can be unified under an object mapping; unchanged predicates and shared objects across classes do not determine membership.The continuous controller parameters are ignored for operator learning and reserved for sampler learning.Source: §A.2 · pp. 11–12
  • The example’s equivalence classes yield one operator for picking up a block and another for stowing one, with parameters and effects drawn from a representative transition.The first class has parameters [?x, ?y] and effects Held(?x) and not On(?x, ?y); the second has [?z] and effects IsStowed(?z) and not Held(?z).Source: §A.2 · p. 12
  • For each transition, atoms involving objects outside its substitution’s image are discarded before precondition learning.For the first transition, this removes On(o2, o3) because o3 is outside the image {o1, o2}.Source: §A.2 · p. 12
  • Intersecting the mapped abstract states gives preconditions On(?x, ?y) for the pickup operator and Held(?z), IsStowable(?z) for the stowing operator.The resulting operator set excludes extraneous atoms about object color.Source: §A.2 · p. 12

A.3 Learning Samplers

Each operator’s sampler predicts continuous controller parameters from the features of its grounded objects. Supervised examples reuse operator-learning substitutions, and a classifier supports rejection sampling to improve the first network’s representational capacity.

A.3 Learning Samplers

  • A sampler is learned per operator to propose continuous controller parameters conditioned on the state and objects grounding that operator.The sampler is a distribution over the controller parameters, with one network regressing a Gaussian’s mean and covariance and a classifier used for rejection sampling.Source: §A.3 · pp. 12–13
  • Sampler training reuses operator-learning substitutions to pair concatenated grounded-object features with the continuous parameter vector from each demonstrated action.The first network’s distributional regression is limited, for example to unimodal distributions; the classifier increases representational capacity through rejection sampling.Source: §A.3 · pp. 12–13

A.4 Predicate Grammar Details

The appendix specifies a shared predicate grammar, reports experiments across four robotic environments, and examines how learned abstractions interact with planner heuristics. In Blocks, learned representations outperform standard encodings on reported hAdd comparisons.

A.4 Predicate Grammar Details

  • The shared grammar combines goal predicates with normalized single-feature inequality classifiers, their negations, and universally quantified forms, assigning costs to candidate complexity.It prunes predicates equivalent on dataset groundings and excludes goal predicates from the candidate grammar because they are always included.Source: §A.4 · p. 13

A.5 Additional Environment Details

  • Evaluation tasks involve more objects in Blocks and Tools; Painting reports 2–3 training widgets and 3–4 evaluation blocks, while Tools tests robustness to physical constraints beyond the predicate grammar.Blocks grows from 3–4 to 5–6 blocks; Tools grows from 2 to 2–3 screws, nails, and bolts.Source: §A.5 · pp. 13–14

A.6 Additional Experimental Details

  • Sampler neural networks are fully connected with two hidden layers of 32 units each; experiments use Pyperplan implementations of AI planning heuristics, with LMCut unless otherwise specified.Source: §A.6 · p. 14

A.8 Varying the Planner Heuristic

  • With hAdd in Blocks, Ours creates over 30x fewer nodes than Manual; learned representations also solve the 36-block IPC 2000 case in 12.5 seconds while standard encoding times out at 2 hours.The separate symbolic-only comparison is specific to Blocks, A*, and hAdd.Source: §A.8 · p. 15, Table 2 · p. 15
  • In analyzed Blocks problems, learned operators do not show the pre-pick hAdd underestimates observed with standard operators, although both require escaping local minima around picks.For a 20-block problem, standard operators had eight such underestimates; none were observed with learned operators in the analyzed problems.Source: §A.8 · p. 15

A.7 Additional Experimental Results

  • The main method’s learning takes longer, but is offline; comparing it with Manual indicates most of that time is spent inventing predicates.Manual specifies predicates but still learns operators and samplers.Source: Table 3 · p. 16
  • Across environments, the surrogate objective decreases monotonically as predicates are added, while plan-cost error and abstract-search nodes do not, supporting the use of both components.Figure 4 reports means over 10 seeds.Source: §A.7 · p. 14, Figure 4 · p. 18
Loading 2203.09634v3…