Back to AI Research

AI Research

Efficient Lookahead Encoding and Abstracted Width f... | AI Research

Key Takeaways

  • Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning This research addresses the challenge of creating "gene...
  • Generalized planning aims to learn policies that generalize across collections of instances within a classical planning domain.
  • Recent Graph Neural Network (GNN) approaches have learned nearly perfect policies for several domains.
  • This work improves on the recently published idea of Iterated Width (IW) policies.
  • Therein, the policy broadens its successor scope through an IW-lookahead search that can "jump" over multiple transitions, simplifying the problem structure.
Paper AbstractExpand

Generalized planning aims to learn policies that generalize across collections of instances within a classical planning domain. Recent Graph Neural Network (GNN) approaches have learned nearly perfect policies for several domains. This work improves on the recently published idea of Iterated Width (IW) policies. Therein, the policy broadens its successor scope through an IW-lookahead search that can "jump" over multiple transitions, simplifying the problem structure. Yet, each transition is evaluated individually, leading to unscalable compute costs and expressivity limitations. Furthermore, although IW(1) is attractive because it scales linearly with the number of atoms, it becomes inefficient once thousands of objects are considered, as in the International Planning Competition (IPC) 2023 benchmark. We address both limitations. First, we introduce a vastly more efficient holistic encoding of the entire search tree. It jointly represents IW(1)-reachable states only by their relational differences to the current state, enabling Relational GNNs (R-GNNs) to score all transitions in a single forward pass. Second, we define Abstracted IW(1) to improve scaling through relational abstraction during novelty checks. Rather than testing fully instantiated atoms, it abstracts each atom by replacing all but one argument with its type. The original atom is novel if any of its abstracted forms is novel. This structural compression shifts novelty search scaling from atoms to objects, while preserving meaningful subgoal structure. We evaluate our contributions on the hyperscaling IPC 2023 benchmark and across diverse domains, including domains requiring features beyond the $C_2$ logic fragment. Our policies achieve new state-of-the-art performance, significantly surpassing prior work, including the classical planner LAMA.

Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning
This research addresses the challenge of creating "generalized policies" in classical planning—systems that can solve a wide variety of problems within a domain without needing to perform a full, time-consuming search for every new instance. While recent approaches using Graph Neural Networks (GNNs) have shown promise, they often struggle with computational costs and limited expressivity when faced with large-scale problems containing thousands of objects. This paper introduces two primary innovations to improve the efficiency and scalability of these policies, allowing them to handle complex benchmarks like those found in the International Planning Competition (IPC) 2023.

Holistic Search Tree Encoding

Previous methods for generalized planning often evaluated potential future states (successors) individually, leading to redundant calculations and high memory usage. The authors introduce a "holistic" encoding that represents an entire search tree of possible future states at once. Instead of re-encoding the entire state for every potential move, the system only encodes the relational differences—the specific atoms that change—between the current state and its successors. By processing these differences within a Relational GNN in a single forward pass, the model significantly reduces memory consumption and computational overhead, allowing it to evaluate many more possibilities efficiently.

Abstracted Width for Scalable Search

To further improve performance, the researchers developed "Abstracted IW(1)," a more efficient version of the Iterated Width (IW) search algorithm. Standard IW(1) novelty checks, which determine if a state is worth exploring, can become slow as the number of objects in a problem grows. The new abstracted approach simplifies these checks by replacing specific object arguments in atoms with their general types. This structural compression shifts the complexity of the search from being dependent on the number of atoms to being linear in the number of objects. This allows the system to identify meaningful subgoals and navigate large state spaces much faster while still maintaining the ability to decompose complex tasks.

Performance and Results

The authors evaluated their new approach on the hyperscaling IPC 2023 benchmark, which includes massive instances such as a 488-block Blocksworld. The results demonstrate that the combination of holistic encoding and abstracted novelty checks allows the system to outperform existing state-of-the-art methods, including the classical planner LAMA. Furthermore, the lookahead mechanism proved effective in domains that require complex logical reasoning beyond the standard $C_2$ logic fragment, showing that the model can generalize effectively even in challenging, large-scale environments.

Comments (0)

No comments yet

Be the first to share your thoughts!