Research map / Learning theory and algorithms / Combinatorial and search optimization
Novelty vs. Potential Heuristics: A Comparison of Hardness Measures for Satisficing Planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Compares novelty width, correlation complexity, and a new river measure (based on potential heuristics over wet states) as hardness measures for satisficing planning, and shows a plan-preserving conversion that reduces the river measure to 2.
Problem
Measuring the hardness of classical planning tasks for satisficing search; existing measures (novelty width, correlation complexity) look at different parts of the state space and their relationship is unclear.
Approach
Introduces the river measure, the smallest dimension of a potential heuristic that is descending and dead-end avoiding only over wet states (states reachable by descending walks from the initial state), relaxing correlation complexity; proves RM ≤ CC and RM ≤ oNW+1, and shows an E-conversion (step counter) reduces RM to 2.
Key results
- River measure satisfies RM(Π) ≤ CC(Π) and RM(Π) ≤ oNW(Π)+1 ≤ NW(Π)+1 (theoretical bounds).
- E-conversion of any planning task admits a plan-enforcing potential heuristic of dimension 2 (oNW of converted task is 1).
- On a binary counter example, CC is at least 2 while a little/big endian task admits WDDA heuristics of dimension 1 from each state, showing the maximal per-state RM differs from task-level RM.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply E-conversion by adding a step-counter variable | Any solvable planning task · E-converted task | river measure: 2 | Helped |
| Apply E-conversion by adding a step-counter variable | Any planning task · E-converted task | optimistic novelty width: 1 | Helped |
| Use novelty-width search with input width k when it finds a plan | Planning task Π · General planning tasks | potential-heuristic dimension: k + 1 | Helped |
| Use a WDDA potential heuristic instead of requiring DDA over all alive states | Planning task Π · General planning tasks | heuristic dimension: RM(Π) ≤ CC(Π) | Helped |
| Use a potential heuristic to guide the initial-state search | Planning task Π · General planning tasks | river measure: RM(Π) ≤ oNW(Π) + 1 | Helped |
| Remove the location-x-y-is-visited variables (ablation) | Visit-All 3×3 grid task · Visit-All | river measure: 1 to 2 | Hurt |
| Retain the location-x-y-is-visited variables (ablation) | Visit-All 3×3 grid task · Visit-All | river measure: 2 to 1 | Helped |
| Use a dimension-1 potential heuristic based on visited-location facts | Visit-All 3×3 grid task · Visit-All | river measure: 1 | Helped |
Surprising findings
- Adding a step-counter state variable (E-conversion) can drastically reduce the hardness measures, contradicting the intuition that larger tasks are harder.
- Removing goal-irrelevant variables in Visit-All raises the RM from 1 to 2, showing the measure depends on task representation.
Limitations
- Results are purely theoretical with no empirical evaluation on benchmark domains.
- Measures are highly dependent on task representation, so comparisons may be sensitive to modeling choices.
- Synthesis of WDDA heuristics is in Σp2 per the authors' inference, which is hard in general.
Experimental setup
Baselines: novelty width correlation complexity
Builds on: potential heuristics novelty width search correlation complexity
Closest papers by meaning
- Fat- and Heavy-Tailed Behavior in Satisficing Planning (AAAI 2018 · similarity 0.89)
- Higher-Dimensional Potential Heuristics for Optimal Classical Planning (AAAI 2017 · similarity 0.87)
- Computing Plan-Length Bounds Using Lengths of Longest Paths (AAAI 2021 · similarity 0.87)
- Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning (AAAI 2017 · similarity 0.86)
- Thought of Search: Planning with Language Models Through The Lens of Efficiency (NeurIPS 2024 · similarity 0.84)
- PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning (AAAI 2025 · similarity 0.84)
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.