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].
Optimal Partial-Order Plan Relaxation via MaxSAT
Authors: Christian Muise, J. Christopher Beck, Sheila A. McIlraith
JAIR 2016 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We empirically compare our approach to an existing polynomial-time heuristic for relaxing a sequential plan due to Kambhampati and Kedar (1994) and find that the latter is extremely proficient at computing a minimum deordering, matching the optimal solution in every problem tested. We find, however, that a minimum reordering can be substantially more flexible than a minimum deordering, having fewer ordering constraints and far more linearizations. We also compare the efficiency of our technique with a related approach that uses a Mixed Integer Linear Programming encoding to compute the minimum reordering (Do & Kambhampati, 2003) and find that our approach consistently performs better on problems of non-trivial size. Our results show that while an existing heuristic approach consistently produces the optimal deordering of a sequential plan, our approach has greater flexibility when we consider reordering the actions in the plan while also providing a guarantee of optimality. |
| Researcher Affiliation | Academia | Christian Muise EMAIL Department of Computer Science, Toronto, Ontario, Canada. M5S 3G4 J. Christopher Beck EMAIL Department of Mechanical & Industrial Engineering Toronto, Ontario, Canada. M5S 3G8 Sheila A. Mc Ilraith EMAIL Department of Computer Science, Toronto, Ontario, Canada. M5S 3G4 |
| Pseudocode | Yes | Algorithm 1: Relaxer Algorithm Input: Sequential plan, a, including a I and a G Output: Relaxed Partial-order plan, A, O |
| Open Source Code | No | The paper does not contain an unambiguous statement that the authors' code for the methodology described in this paper is publicly available, nor does it provide a direct link to a code repository. |
| Open Datasets | Yes | For our analysis, we considered every STRIPS domain from the previous International Planning Competitions (IPC, Hoffmann, 2016). Hoffmann, J. (2016). ICAPS competition page. http://ipc.icaps-conference.org/. Accessed: 2016-09-06. |
| Dataset Splits | No | The paper refers to problems from the International Planning Competitions (IPC) and lists benchmark sizes for each domain (e.g., "airport (50)", "depot (22)"), but it does not specify any explicit training/test/validation splits for these problems. |
| Hardware Specification | Yes | We conducted all experiments on a Linux desktop with a 3.4GHz processor, and each run of Sat4j was limited to 30 minutes and 4GB of memory. |
| Software Dependencies | Yes | We evaluate the ability and effectiveness of the state-of-the-art partial weighted Max SAT solver, Sat4j (Le Berre & Parrain, 2010), to optimally relax a plan using our proposed encodings. We implemented the MILP model using the state-of-the-art MILP solver Gurobi (version 5.6.2) (Gurobi Optimization, Inc., 2015). |
| Experiment Setup | Yes | We conducted all experiments on a Linux desktop with a 3.4GHz processor, and each run of Sat4j was limited to 30 minutes and 4GB of memory. |