PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning How to Search for Plans with Exponentially Less Space

Dominik Drexler, Simon Ståhlberg, Markus Fritzsche, Blai Bonet

arXiv:2610.10954v1cs.AI

TL;DR

Heuristic search can require exponentially much space even with an almost perfect heuristic. The paper learns indexical policies with choose rules that mark where backtracking is needed, then uses structural termination to bound executions and guide depth-first search. The learned policies outperform LAMA, BFWS, and Levitron across the reported test benchmarks, with most tasks solved within one second and 100 MiB.

  • Problem

    Heuristic planning search can store exponentially many states, even when the heuristic is almost perfect.

    Source: §1 · p. 1

  • Method

    The paper learns indexical policies with choose rules for backtracking and uses a depth-first scout to search their AND/OR execution graphs.

    Source: §1 · p. 1, §9 · p. 8

  • Results

    1,709 of 1,890 test tasks are solved, more than LAMA, BFWS, and Levitron; most are solved within one second and 100 MiB.

    Source: §8.2 · p. 8, §9 · p. 8

  • Takeaways & Limitations

    Structural termination bounds policy executions polynomially in task objects, enabling polynomial-space search without visited-state storage, with time exponential only in choice depth.

    Source: §1 · p. 1, §9 · p. 8

    Policies are proven to solve their training tasks but may fail outside them, and their polynomial-space bound limits the plan lengths they can produce.

    Source: §9 · pp. 8–9

Abstract

from arXiv · show

Heuristic search for a plan can store exponentially many states, even when its heuristic is almost perfect. We instead learn search control, one specification per domain, written as an indexical policy: a generalized policy with registers that hold objects and modes that sequence its rules. We add the choose rule, which loads an object into a register and marks a backtracking point, where one candidate suffices; every other rule must work for all of its outcomes and needs no search. Our main result is that structural termination, which rules out infinite executions, also bounds every execution by a polynomial in the number of objects. A depth-first procedure then finds a plan in polynomial space, however large the state space, with no list of visited states. The cost is time, exponential only in the choice depth, the number of real choices along an execution. Any class that such a policy solves therefore lies in NP, and in P at constant choice depth. We learn these policies with a language model in a counterexample-guided loop that certifies termination, verifies the training tasks, and keeps the choice depth small. With the learned policies, the procedure solves 1,709 of 1,890 test tasks of the IPC 2023 Learning Track and the Autoscale Agile suite, more than LAMA, BFWS, and Levitron, and most of them within one second and 100 MiB.

1 Introduction

The paper recasts generalized policies as search control: they guide a planner’s search rather than decide a plan without search. Choose rules mark where backtracking is needed, while structural termination bounds executions and enables polynomial-space search.

1 Introduction

  • The search control is a generalized policy for a fixed domain and its tasks, but it guides a search rather than deciding a plan action by action.Indexical policies use registers to hold objects and modes to sequence rules.Source: §1 · p. 1
  • A choose rule marks a backtracking point where one candidate need succeed; ordinary rules require every outcome to work, keeping search localized.The policy and task define an AND/OR graph: ordinary rules are AND vertices and choose rules are OR vertices; the scout searches it depth-first.Source: §1 · p. 1
  • Structural termination bounds every execution by a polynomial in the number of task objects, so depth-first search finds plans in polynomial space without storing visited states.Its time can grow exponentially with choice depth, the number of choices with multiple candidates along an execution.Source: §1 · p. 1
  • Classes solved by such policies lie in NP, and in P at constant choice depth.The plan-length bound excludes Towers of Hanoi and excludes Sokoban unless NP = PSPACE.Source: §1 · p. 2
  • 1,709 of 1,890 test tasks are solved, more than LAMA, BFWS, and Levitron, with most solved within one second and 100 MiB.The evaluation covers the IPC 2023 Learning Track test set and Autoscale Agile suite.Source: §1 · p. 2

2 Related Work

Earlier approaches prune or restrict planning search, but retain a standard search procedure and its potentially exponential open and closed lists. This paper instead defines the search space through policies whose depth is bounded by a property checked before tasks are seen.

Search control

  • Earlier search-control methods prune paths with temporal-logic formulas, restrict search to task decompositions, or use domain-specific knowledge, while retaining standard search and its open and closed lists.Those lists can grow exponentially in size.Source: §2 · p. 2

Choice and AND/OR search

  • The paper’s AND/OR search resembles strong solutions in nondeterministic planning, but its AND vertices come from policy rules rather than environmental outcomes.An ordinary rule must work for every transition it admits, leaving the rest of the policy search-free.Source: §2 · p. 2

Language models for planning

  • Prior language-model planning work includes synthesis with feedback or soundness checks and pairing models with planners or validators; this paper follows a generator–adversary learning loop.Unlike a domain-specific heuristic that leaves decisions to best-first search, its policies mark which decisions require search.Source: §2 · p. 2

3 Background

The background defines classical planning tasks and the policy framework used to control executions. Indexical policies add registers and modes, while structural termination supplies an acyclicity guarantee.

3 Background

  • A classical task specifies a domain, objects, initial state, and goal; a plan is a sequence of ground actions that reaches a goal state.A task class consists of tasks sharing a domain while varying in objects, initial state, and goal.Source: §3 · p. 2
  • Description-logic features denote object sets or pairs, with emptiness and cardinality yielding Boolean and numerical features; these features refer only to unary and binary predicates.Goal predicates let features compare the current state with the goal, and numerical features are non-negative integers bounded in each task.Source: §3 · p. 2

3.1 Policies and Structural Termination

  • A policy solves a task when every maximal execution from its initial state is finite and ends at a goal; this strong condition allows any permitted transition.Standard rules specify conditions and effects, including changes that may be arbitrary for features marked as such.Source: §3.1 · pp. 2–3
  • Indexical policies add modes for sequencing and contexts and registers for focusing rules on objects or object pairs; their rules can transition, load objects, or apply actions.Executions begin with empty registers, and modules and call rules are left for future work.Source: §3.1 · p. 3
  • Structural termination rules out infinite trajectories based on feature-change patterns and establishes acyclicity; the verifier abstracts away register contents and accepted policies are acyclic on every task.A load into a register may change every feature that depends on it arbitrarily in the verifier’s abstraction.Source: §3.1 · p. 3

4 Query and Arithmetic Features

The feature language is extended with relational-algebra queries and arithmetic. Queries allow features to relate objects across predicates of any arity, while arithmetic enables additional numerical measures relevant to termination.

4 Query and Arithmetic Features

  • Relational-algebra queries extend features to predicates of any arity, including higher-arity predicates that prior work compiled away.Queries use joins, projection, renaming, selection, union, and difference; fixed queries take polynomial time to evaluate.Source: §4 · p. 3
  • Queries can express properties relating more than two objects, beyond what description-logic features can express directly.The example query denotes box–destination pairs for a push when the player can stand behind the box.Source: §4 · p. 3
  • Arithmetic features include constants and basic operations, allowing sums to measure progress that no single count captures.The Spanner example combines loose nuts with reachable locations; subtraction is truncated at zero and division rounds down to preserve non-negative integer values.Source: §4 · p. 3

5 Search Spaces and Choose Rules

The paper defines an AND/OR search space for indexical policies in which ordinary rules and states impose universal obligations, while choose rules introduce backtracking over candidates. A depth-first scout searches only at choose rules, with choice depth and width capturing how much search may be needed.

5.1 Search Spaces

  • Augmented states and rule vertices form a directed bipartite search graph; states and ordinary rules are AND vertices, while choose rules are OR vertices.Thus choices among rules and ordinary-rule outcomes are universal obligations; only a choose rule's candidate is existential.Source: §5.1 · p. 4
  • A graph vertex is solved from the goal backward: an OR vertex needs one solved child, while every other non-goal vertex needs at least one child and all its children solved.An applicable choose rule with no candidates is unsolved.Source: §5.1 · p. 4

5.2 Backtracking and Search

  • The scout explores depth-first, following one child at state and ordinary-rule vertices and trying candidates with backtracking only at choose-rule vertices.Structural termination makes the search finite; a policy that solves the task guarantees the scout returns a plan, though a scout run can find a plan even when the policy does not solve the task.Source: §5.2 · pp. 4–5
  • In Peg Solitaire, two choose rules select each jump because a legal jump can leave the remaining pegs unsolvable; each jump therefore makes two choices.A numerical feature decreases on the jump, certifying structural termination.Source: §5.2 · p. 5

5.3 Choice Depth and Choice Width

  • Choice depth counts OR vertices with at least two children, and choice width is the largest OR branching factor; these, rather than the number of choose rules, determine the scout's search burden.With depth at most k and width at most B, the scout explores at most the sum of B^i for i from 0 to k choice sequences.Source: §5.3 · p. 5

6 Bounded Search Depth

Structural termination bounds every policy trajectory polynomially in the number of task objects, yielding a depth-first scout that uses polynomial space. The bound also limits which task classes policies can solve, while whether polynomial plan length is sufficient remains open.

6 Bounded Search Depth

  • Every trajectory of a fixed structurally terminating policy has polynomial length in the number of task objects, so a depth-first scout can find a plan in polynomial space.The scout stores only its current path and the candidate index at each OR vertex, rather than a set of visited states.Source: §6 · p. 5
  • The trajectory bound depends on the policy's modes and features, and its polynomial degree is not uniform across policies.The degree is D|ΨN|.Source: §6 · p. 5

6.1 Completeness

  • Solving a class places plan existence in NP, and in P when choice depth is constant; this excludes Towers of Hanoi and, unless NP = PSPACE, Sokoban.Unless P = NP, constant-choice-depth policies also cannot solve classes with NP-hard plan existence.Source: §6.1 · p. 6
  • The converse remains open: polynomial-length plans for every solvable task do not yet establish that a structurally terminating policy can solve the class.Bounded action search alone is insufficient because structural termination requires progress on features.Source: §6.1 · p. 6

7 Learning Policies with Choose Rules

A language-model generator proposes and revises policies while an adversary searches for solvable tasks on which they fail. Candidates are checked for structural termination and task solving, with learning objectives favoring general policies that require little search.

7 Learning Policies with Choose Rules

  • The generator constructs policy features and rules on demand, while the adversary proposes task-generator settings intended to expose policy failures.The task generator's source identifies which initial states and goals can occur, including invariants not implied by the domain description alone.Source: §7 · p. 6
  • Accepted policies must terminate structurally and solve every training task; among qualifying policies, the learning objective favors small choice depth.Replacing a choose rule with a load rule does not necessarily reduce search: a load rule requires every candidate to work.Source: §7 · p. 6
  • Validation checks structural termination first, then task execution, then universal verification; verification is skipped when execution fails.A resource limit during a task check is inconclusive.Source: §7 · p. 6, Figure 1 · p. 6
  • The adversary retains a task only when an independent planner finds it solvable and the candidate policy fails or reaches a resource limit; earlier tasks are rechecked after revisions.A returned policy need not have every retained task verified when checks remain inconclusive.Source: §7 · p. 6

8 Experiments

The experiments evaluate learned policies on IPC-learning and Autoscale test tasks, examining policy learning, generalization, planner comparisons, and the search-space trade-offs of storing explored states.

8.2 Results

  • IP solves 850/900 IPC-learning and 859/990 Autoscale tasks, versus Levitron’s 630 and 768; most IP solves occur within one second and 100 MiB.IP+Ch solves 1 and 16 more tasks than IP on the respective benchmarks; IP+All solves one more per benchmark than IP+Ch, but uses up to 1,819 MiB more than IP.Source: Table 2 · p. 7, §8.2 · p. 8, Figure 2 · p. 8

8.1 Setup

  • IPC-learning has 900 test tasks (30 each at easy, medium, and hard); Autoscale has 990 tasks across 33 domains, with training tasks outside Sokoban and Nomystery capped at 65 objects and test tasks up to 19,615 objects.Peg Solitaire is the exception, where every task has 33 objects.Source: §8.1 · p. 8
  • IP stores only its current path, while IP+Ch stores explored choice points and IP+All stores all explored augmented states, giving up the polynomial-space bound.IP+Ch’s peak memory is within 2% of IP on 90% of tasks and at most 291 MiB higher.Source: §8.1 · p. 8, §8.2 · p. 8

8.2 Results

  • Learned policies avoid choose rules in P domains and use them in NP-complete or PSPACE-complete domains; every retained policy is structurally terminating and proven to solve its training tasks.Most policies without choose rules need one generator proposal, while Freecell, Mprime, Snake, and Sokoban need 11–20.Source: §8.2 · p. 8
  • Relational queries expose predicates of arity greater than two and avoid unnecessary search from limited feature expressivity in several tractable domains.The ablation introduced choose rules in Tidybot, Rovers, Data-network, and TPP when queries were removed.Source: §8.2 · p. 8

9 Conclusions

The paper uses choose rules to mark decisions that require search, while structural termination bounds execution length and lets a depth-first scout find plans in polynomial space. Learned policies solve more test tasks than LAMA, BFWS, and Levitron on both benchmarks, but their guarantees do not extend to every task or plan length.

9 Conclusions

  • Choose rules mark decisions that need search, and structural termination bounds every trajectory by a polynomial in task size, yielding polynomial-space plan finding.The scout’s time cost is exponential only in choice depth.Source: §9 · p. 8
  • With learned policies, the scout solves more test tasks than LAMA, BFWS, and Levitron on both benchmarks, most within one second and 100 MiB.Storing explored choice points solves a few more tasks at little extra memory, but gives up the space bound.Source: §9 · p. 8
  • The learning approach extends a counterexample-guided loop with choose rules and relational-algebra queries.The paper identifies learning policies with modules and calls, and extending the depth bound to them, as future work.Source: §9 · pp. 8–9
  • Structural termination does not guarantee success on unseen tasks, and the plan-length bound limits which classes these policies can solve.The resulting class lies in NP, excluding Towers of Hanoi and Sokoban unless NP = PSPACE.Source: §9 · pp. 8–9

A Supplement to Section 5 (Search Spaces and Choose Rules)

The proof establishes that the scout returns a plan whenever a structurally terminating indexical policy solves the task. It uses a solved choice function and induction over finite trajectories to show that the scout eventually finds a successful path.

A Supplement to Section 5 (Search Spaces and Choose Rules)

  • A structurally terminating policy that solves a task guarantees that the scout returns a plan for it.Structural termination makes the policy graph acyclic; with finitely many augmented states, trajectories are finite.Source: A Supplement to Section 5 (Search… · p. 11
  • Induction on the longest trajectory shows the scout finds a plan from each reachable augmented state.It stops at a goal; otherwise, ordinary transitions lead to solved states with shorter trajectories.Source: A Supplement to Section 5 (Search… · p. 11
  • At choose rules, the scout tries candidates one by one and eventually reaches a successful candidate unless an earlier one succeeds.Failed candidates are abandoned after finitely many steps because the graph is acyclic and each vertex has finitely many children.Source: A Supplement to Section 5 (Search… · p. 11

B Supplement to Section 6 (Bounded Search Depth)

Structural termination bounds policy trajectories polynomially in the number of task objects. This bound supports a depth-first search procedure using polynomial space, and constrains the complexity of the task classes these policies can solve.

B Supplement to Section 6 (Bounded Search Depth)

  • Finite numerical feature values have a polynomial bound because the policy’s fixed arithmetic expressions are bounded by a(n + 1)^D + b.Each numerical feature therefore has at most p(n) values, including infinity.Source: B Supplement to Section 6 (Bounded… · p. 11
  • Every trajectory of a structurally terminating indexical policy with choose rules has at most polynomially many transitions in the number of objects.The bound applies to every task, not only tasks that the policy solves.Source: B Supplement to Section 6 (Bounded… · p. 11
  • The tuple count is finite because Boolean features have at most two values and numerical features at most p(n) values.The tuple records numerical feature values, not merely whether they are zero or positive.Source: B Supplement to Section 6 (Bounded… · p. 11
  • Structural termination’s verifier removes progress-making edges until its abstract graph is acyclic, ruling out repeated mode-and-feature tuples along a trajectory.The proof uses this absence of repeated tuples to bound trajectory length by the number of possible tuples.Source: B Supplement to Section 6 (Bounded… · p. 11
  • A depth-first scout stores only its current path and candidate indices at OR vertices, returning a plan in polynomial space.It builds the graph on demand rather than storing visited states.Source: B Supplement to Section 6 (Bounded… · p. 12
  • A solved task class has polynomial-length plans and lies in NP; if choice depth is bounded by a constant, plan existence is in P.The polynomial-length plans provide certificates for membership in NP.Source: B Supplement to Section 6 (Bounded… · p. 12

C Supplement to Section 8 (Experiments)

The supplement reports the no-query ablation’s learning and testing setup and describes its policy behavior. Without queries, the learned policies use choose rules in four additional domains, which the text attributes to insufficient feature expressivity.

C Supplement to Section 8 (Experiments)

  • Without queries, policies use choose rules in four additional domains; the text says these rules introduce unnecessary search and indicate insufficient feature expressivity.Policies learned with queries avoid choose rules in each of those domains.Source: C Supplement to Section 8 (Experiments) · p. 12
  • Table 3 compares object counts for training and test tasks, reporting median and maximum objects per task.Training tasks are those retained by the adversary during learning.Source: Table 3 · p. 13
  • Table 4 reports no-query learning effort and policy sizes for IPC-learning and Autoscale; finalized policies were all proven structurally terminating.Mprime learning reached the iteration limit, and Autoscale Sokoban was cancelled after roughly 24 hours; the last available policies were tested.Source: C Supplement to Section 8 (Experiments) · p. 12, Table 4 · p. 13
  • Table 5 compares test coverage for main and no-query ablation policies on IPC-learning and Autoscale, alongside LAMA, BFWS, and Levitron.It distinguishes IP, IP+Ch, and IP+All by how much explored search information they store.Source: C Supplement to Section 8 (Experiments) · p. 12, Table 5 · p. 14
Loading 2610.10954v1…