Introduction
In automated planning, characterizing the difficulty of a task is crucial for selecting appropriate search algorithms. Traditionally, two distinct frameworks have dominated this landscape: Novelty Width (NW), which measures the "newness" of states during search, and Correlation Complexity (CC), which assesses the complexity of potential heuristics needed to guide a search. While NW is often viewed as an optimistic measure focused on the path from the initial state, CC is seen as a pessimistic one, requiring a solution path from every possible state. This paper bridges these two paradigms by introducing the River Measure (RM).
Bridging the Gap: The River Measure
The authors propose the River Measure as a unifying theoretical tool. RM focuses on "Wet States"—those reachable from the initial state that can lead to a goal without encountering dead ends. By calculating the minimum dimension of a potential heuristic required to guide search through these states, RM provides a middle ground between the local focus of novelty and the global requirements of correlation complexity.
The paper establishes a clear hierarchy of these measures, proving that $RM(\Pi) \le CC(\Pi)$ and $RM(\Pi) \le oNW(\Pi) + 1 \le eNW(\Pi) + 1 \le NW(\Pi) + 1$. This formal link demonstrates that novelty-based search logic and potential heuristics are more mathematically intertwined than previously understood.
The Hardness Paradox and E-Conversion
A significant contribution of this work is the discovery of a "Hardness Paradox." The authors introduce E-Conversion, a transformation where a simple step counter is added to a planning task. Surprisingly, this addition—which provides no new functional information for solving the task—can artificially collapse the River Measure of any solvable task to a value of 2.
This finding highlights a critical sensitivity to representation. It suggests that current hardness measures may be capturing the complexity of the encoding rather than the intrinsic difficulty of the problem. For instance, removing seemingly "irrelevant" variables can actually increase the River Measure, making a task appear harder to the heuristic despite having a smaller state space.
Complexity and Practical Implications
The research also delves into the computational complexity of synthesizing these heuristics. The authors find that finding a heuristic that satisfies RM requirements is situated at the second level of the polynomial hierarchy ($\Sigma^p_2$), indicating that while simple heuristics may exist (especially after E-conversion), finding them is computationally intensive.
Furthermore, while E-conversion theoretically allows for backtrack-free search with low-dimensional heuristics, it presents practical challenges. By preventing the pruning of "duplicate" states, it can lead to inefficient search behavior in real-world planners, despite the lower theoretical hardness score.
Conclusion
By unifying novelty and potential heuristics under the River Measure, this paper provides a more comprehensive understanding of planning hardness. However, the sensitivity of these measures to representational changes like E-conversion poses a challenge for the field. Future work must focus on developing "robust" hardness measures that are invariant to such representational "tricks," ensuring that our metrics truly reflect the underlying difficulty of reaching a goal.
Summary updated