Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
General Policies, Subgoal Structure, and Planning Width
Authors: Blai Bonet, Hector Geffner
JAIR 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we address this question by relating bounded width with the existence of general optimal policies that in each planning instance are represented by tuples of atoms of bounded size. We also define the notions of (explicit) serializations and serialized width that have a broader scope, as many domains have a bounded serialized width but no bounded width. Such problems are solved nonoptimally in polynomial time by a variant of the Serialized IW algorithm. Finally, the language of general policies and the semantics of serializations are combined to yield a simple, meaningful, and expressive language for specifying serializations in compact form in the form of sketches, which can be used for encoding domain control knowledge by hand or for learning it from examples. Sketches express general problem decompositions in terms of subgoals, and terminating sketches of bounded width express problem decompositions that can be solved in polynomial time. The paper includes multiple theorems and proofs, such as "Theorem 4 (Completeness of IW(T)). If T is an admissible set of atom tuples in problem P, IW(T) finds an optimal plan for P." and discusses complexity in O-notation without presenting empirical results from experiments. |
| Researcher Affiliation | Academia | Blai Bonet EMAIL Universitat Pompeu Fabra, Spain. Hector Geffner EMAIL RWTH Aachen University, Germany Link oping University, Sweden. |
| Pseudocode | Yes | Figure 1: IW(T) Search. Algorithm 1: IW(T) Search. Figure 2: IW Search. Algorithm 2: IW Search. Figure 3: An IWΦ search is like an IW(T) search but instead of tracking the tuples in T, it tracks feature valuations, and prune nodes whose valuation have been already seen. Guarantees for completeness and optimality are given in Theorem 29. Algorithm 3: IWΦ Search. Figure 4: SIW solves a problem P by using the serialization to decompose P into subproblems, each one that is solved with an IW search. Testable serialization means that there is an algorithm for testing s s for any pair of states. The completeness of SIW is given in Theorem 35. Algorithm 4: SIW Search. Figure 5: SIWR is SIW with the serialization R induced by the sketch R. The completeness and complexity of SIWR is given in Theorem 40. Algorithm 5: SIWR Search. Figure 6: The Sieve algorithm takes as input a directed edge-labeled graph G that is either accepted or rejected. The graph G is the graph G(R) constructed using the feature-based rules in a set R. If G is accepted, the binary relation on feature valuations induced by R is deemed as terminating, and thus R is feature-acyclic (cf. Theorem 41). Algorithm 6: Sieve. |
| Open Source Code | No | The paper does not contain any explicit statement about releasing open-source code for the described methodology, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper discusses established planning domains (e.g., Blocksworld, Grid, Delivery, Marbles, Towers of Hanoi) as examples for theoretical analysis, but does not refer to specific dataset instances with access information for empirical experimentation. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments involving dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments, thus no specific software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, thus no specific experimental setup details or hyperparameter values are provided. |