Qualitative Numeric Planning: Reductions and Complexity
Authors: Blai Bonet, Hector Geffner
JAIR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We illustrate the performance of the QNP translator and solver over some QNPs that capture abstraction of generalized planning problems. ... The translator runs in less than 0.01 seconds and generates a FOND problem P = T(Q) with 54 atoms and 47 actions (50 atoms for encoding the counters and the stack, and 29 actions to manipulate the stack and move the top counter). FOND-SAT finds the solution shown in Figure 7 in 11.25 seconds; it makes 10 calls to the SAT solver that require 3.00 seconds in total. |
| Researcher Affiliation | Academia | Blai Bonet EMAIL Universidad Sim on Bol ıvar Caracas, Venezuela; Hector Geffner EMAIL ICREA & Universitat Pompeu Fabra Barcelona, Spain |
| Pseudocode | Yes | Sieve (Graph G = G(P, π)): repeat Compute the strongly connected components (SCC) of G. Choose an SCC C and a variable X that is decreased in C but is not increased in C; i.e., for some s in C, π( s) is a Dec(X) action, and for no s in C, π( s) is an Inc(X) action. Remove the edges ( s, s ) such that s and s are in C, and π( s) is a Dec(X) action. until G is acyclic (terminating) or there is no SCC C and variable X to choose (non-terminating) Figure 1: Sieve procedure for testing whether policy π for FOND problem P = TD(Q) terminates (Srivastava et al., 2011). |
| Open Source Code | Yes | The reduction from QNPs to FOND problems has been implemented and it can be found in the Github repository https://github.com/bonetblai/qnp2fond. ... The resulting FOND problems T(Q) are solved with FOND-SAT (Geffner & Geffner, 2018), a general SAT-based FOND planner that is available at https://github.com/ tomsons22/FOND-SAT. |
| Open Datasets | No | The paper illustrates its methodology using examples like "Clearing a Block" (Blocksworld), "Placing a Block on Top of Another" (Blocksworld), "Gripper", and "Delivery" problems (Sections 9 and 13). These are descriptions of problem domains or abstractions rather than specific, publicly available datasets with concrete access information (links, DOIs, or formal citations to a dataset repository) used for empirical evaluation. While these are common planning domains, the paper does not specify the particular instances or provide access to the 'datasets' of instances it used for the experiments. |
| Dataset Splits | No | The paper does not use traditional datasets with train/test/validation splits. Instead, it applies its QNP to FOND reduction and solver to different generalized planning problem instances (e.g., Blocksworld, Gripper, Delivery). These are problem specifications, not data that would typically be split for training or testing a machine learning model. Therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., CPU, GPU models, memory, or cloud instance types) used for running the experiments. It only mentions execution times and calls to a SAT solver. |
| Software Dependencies | Yes | The reduction from QNPs to FOND problems has been implemented and it can be found in the Github repository https://github.com/bonetblai/qnp2fond. ... The resulting FOND problems T(Q) are solved with FOND-SAT (Geffner & Geffner, 2018), a general SAT-based FOND planner ... The SAT solver used is Glucose 4.1 (Audemard & Simon, 2009) which builds on Minisat (Een & Sorensson, 2004). |
| Experiment Setup | No | The paper describes the performance of the QNP translator and a FOND planner on various problems, reporting execution times and the number of calls to a SAT solver. However, it does not provide specific experimental setup details such as hyperparameters for model training (as there's no machine learning model being trained in this sense), specific configurations for the FOND-SAT solver beyond its name, or system-level settings for the environment in which these tests were run. |