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].
Deterministic Oversubscription Planning as Heuristic Search: Abstractions and Reformulations
Authors: Carmel Domshlak, Vitaly Mirkis
JAIR 2015 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical evaluation on a large set of OSP tasks conļ¬rms the eļ¬ectiveness of the proposed techniques, and opens a wide gate for further developments in oversubscription planning. This work is a revision and extension of the formulations and results presented by the authors at ICAPS-2013 and ECAI-2014 (Mirkis & Domshlak, 2013, 2014). [...] Our empirical evaluation on a large set of OSP tasks conļ¬rms the eļ¬ectiveness of the proposed techniques. Moreover, to the best of our knowledge, our implementation constitutes the ļ¬rst domain-independent solver for optimal OSP, and we hope that more advances in this important computational problem will follow. |
| Researcher Affiliation | Academia | Carmel Domshlak EMAIL Vitaly Mirkis EMAIL Faculty of Industrial Engineering & Management, Technion Israel Institute of Technology, Haifa, Israel |
| Pseudocode | Yes | Figure 3: Best-ļ¬rst branch-and-bound (BFBB) search for OSP [...] Figure 9: A polynomial-time algorithm for computing Īŗ(u) for a strong 0-binary value partition u Up (Theorem 7) [...] Figure 10: A pseudo-polynomial algorithm for approximating Īŗ(u) for general 0-binary value partitions u Up (Theorem 10) [...] Figure 11: (a) A modiļ¬cation of the algorithm from Figure 10 to arbitrary value partitions u Up (Theorem 12), and (b) a pseudo-polynomial time separation oracle for the corresponding linear programs Lv 3 in Eq. 13 [...] Figure 13: BFBB search with landmark-based budget reduction [...] Figure 14: Iterative BFBB with landmark enhancement |
| Open Source Code | No | To test and illustrate the value that additive abstractions can bring to heuristic-search OSP, we implemented a prototype heuristic-search OSP solver8 on top of the Fast Downward planner (Helmert, 2006). Since, unlike classical and net-beneļ¬t planning, OSP still lacks a standard suite of benchmarks for comparative evaluation, we have cast in this role the STRIPS classical planning tasks from the International Planning Competitions (IPC) 1998-2006. |
| Open Datasets | Yes | In our evaluation, we compared BFBB node expansions with three heuristic functions, tagged blind, basic, and h M. With all three heuristics, the h-value of a node n is set to 0 if the cost budget at n is over-consumed. If the cost budget is not over-consumed, then: ... The evaluation contained all the planning tasks for which we could determine oļ¬ine the minimal cost budget needed to achieve all the goals. Each such task was approached under four diļ¬erent budgets, corresponding to 25%, 50%, 75%, and 100% of the minimal cost needed to achieve all the goals in the task, and each run was restricted to 10 minutes. Table 1 shows the number of tasks solved within each domain for each level of cost budget.9 Figure 8 depicts the results in terms of expanded nodes across the four levels of cost budget. (Figures 18-21 in Appendix B provide a more detailed view of the results in Figure 8 by breaking them down into diļ¬erent levels of cost budget.) |
| Dataset Splits | No | The evaluation contained all the planning tasks for which we could determine oļ¬ine the minimal cost budget needed to achieve all the goals. Each such task was approached under four diļ¬erent budgets, corresponding to 25%, 50%, 75%, and 100% of the minimal cost needed to achieve all the goals in the task, and each run was restricted to 10 minutes. Table 1 shows the number of tasks solved within each domain for each level of cost budget. |
| Hardware Specification | No | The paper does not explicitly describe the hardware used for its experiments. It only mentions the software environment and time limits. |
| Software Dependencies | No | To test and illustrate the value that additive abstractions can bring to heuristic-search OSP, we implemented a prototype heuristic-search OSP solver8 on top of the Fast Downward planner (Helmert, 2006). [...] generation of disjunctive action landmarks for (Īµ, Sref)-compilations using the LM-Cut procedure (Helmert & Domshlak, 2009) of Fast Downward; and |
| Experiment Setup | Yes | The size of each projection was limited to 1000 abstract states, and the ancestors of the goal variable v were added to the corresponding projection (initialized to contain v) in a breadth-ļ¬rst manner, from v back along the arcs of the causal graph, until the abstraction could not be expanded within the aforementioned size limit. [...] The evaluation contained all the planning tasks for which we could determine oļ¬ine the minimal cost budget needed to achieve all the goals. Each such task was approached under four diļ¬erent budgets, corresponding to 25%, 50%, 75%, and 100% of the minimal cost needed to achieve all the goals in the task, and each run was restricted to 10 minutes. [...] we ļ¬rst devised the projections with respect to the original OSP problem Ī , and the open list was ordered as if the search is done on the original problem, that is, by s n V , b g(n) + X v L s n lcost(L) where s V is the projection of the Ī L s state s on the variables of the original OSP task Ī . [...] Second, when a new node n is generated, we check whether L: v L/0 s n lcost(L) g(n ) + X L: v L/0 s n lcost(L), for some previously generated node n that corresponds to the same state of the original problem Ī , that is, s n V = s n V . If so, then n is pruned right away. |