Research map / Learning theory and algorithms / Combinatorial and search optimization
Computing Plan-Length Bounds Using Lengths of Longest Paths
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace traversal diameter with recurrence diameter as the compositional base case | Compositional planning bounds · Planning benchmark domains | bound size: 4e5 -> 3e3 (logistics); 4e7 -> 8e3 (TPP); 1e8 -> 8e0 (blocksworld) | Helped |
| Use recurrence diameter only when traversal diameter is greater than 2 (ablation) | Compositional planning bounds · Planning benchmark domains | bound computation time | Helped |
| Use recurrence diameter only when traversal diameter is greater than 2 (ablation) | Compositional planning bounds · Problems where recurrence-diameter computation terminates | bound size | No clear effect |
| Use b1 only when expbound is greater than 50; otherwise use traversal diameter (ablation) | Compositional planning bounds · Planning benchmark domains | bound computation time | Helped |
| Use b1 only when expbound is greater than 50; otherwise use traversal diameter (ablation) | Compositional planning bounds · TPP | average bound: 8e3 -> 4e7 | Hurt |
| Use the factored compact SMT encoding instead of the explicit-state recurrence-diameter encoding (ablation) | Recurrence-diameter computation · Planning benchmark abstractions | number of problems bounded within timeout | Helped |
| Use recurrence-diameter-based bounds as horizons instead of traversal-diameter-based bounds | Mp · Planning benchmarks | problem coverage | Helped |
| Use recurrence-diameter-based horizons instead of traversal-diameter-based horizons | Mp · Zeno | problem coverage | Mixed |
| Use tighter recurrence-diameter-based bounds as planning horizons | Mp · Problems requiring more than 5 seconds to solve | planning time including bound computation: more than 5 seconds | Helped |
Closest papers by meaning
- Novelty vs. Potential Heuristics: A Comparison of Hardness Measures for Satisficing Planning (AAAI 2024 · similarity 0.87)
- On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence (AAAI 2024 · similarity 0.86)
- Symbolic Numeric Planning with Patterns (AAAI 2024 · similarity 0.86)
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.85)
- PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning (AAAI 2025 · similarity 0.84)
- Temporal Numeric Planning with Patterns (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.