Characterizing Search Spaces

Roy RadaIJCAI 1983

Abstract

This paper introduces the Number of Inversions (NIV), a metric designed to quantify the "ruggedness" of a search space under a specific heuristic. By measuring the degree to which a heuristic misorders states relative to their actual proximity to a goal, the study demonstrates that higher NIV values correlate with increased problem difficulty across graph theory, function optimization, and rule-based planning.

Introduction

In artificial intelligence, heuristics are essential for guiding search algorithms through massive state spaces. While computational complexity (e.g., NP-completeness) provides theoretical limits, it often fails to explain why a specific heuristic performs well on one problem instance but fails on another. This research addresses the lack of a formal measure to characterize heuristic utility by exploring the "similar-state $\rightarrow$ similar-value" hypothesis. In "easy" search spaces, states that are physically close should have similar heuristic values; when this property breaks down, the landscape becomes rugged and difficult to navigate.

The NIV Metric

The core contribution is the NIV (Number of Inversions) measure. The process involves grouping states into equivalence classes ($S_i$) based on their distance from the initial state and using a heuristic-prediction function ($h$) to estimate the best possible heuristic value ($f$) reachable from a current state.

Table showing the relationship between state classes (S), actual heuristic values (f), and predicted values (h).

An inversion occurs when the heuristic's ordering of states contradicts their actual distance to the goal. A high NIV indicates a "noisy" heuristic that frequently misleads the search algorithm. The author also introduces BNIV, a variation for backward-chaining search.

Experimental Setup

The hypothesis was tested across several domains using generated problem instances:

  • Graph Problems: 18 complete graphs with 5 nodes and random edge weights, plus 18 graphs satisfying the triangle inequality ($TS_{Aineq}$).
  • Optimization Functions: Discrete unimodal (1 peak) and multimodal (4 peaks) functions.
  • Planning Problems: Two register assignment "exchange problems" ($E_1$ and $E_2$) modeled after STRIPS-style planning.

Results and Discussion

The primary finding is that NIV effectively characterizes problem difficulty as a relationship between the search space and the heuristic. For example, the Traveling Salesman Problem (TS) consistently yielded higher NIV values than the Minimum Spanning Tree (MST) problem, providing a structural explanation for why TS is more "confusing" for search algorithms.

NIV values plotted against search position, showing higher ruggedness for TS compared to MST.

Key results include:

  • TS vs. MST: Average NIV for TS was significantly and consistently higher than for MST across various search depths.
  • Function Optimization: The multimodal function produced a larger NIV than the unimodal function, confirming that "hill-climbing" is harder when the landscape has false peaks.
  • Planning: NIV successfully flagged problem $E_2$ as having higher complexity than $E_1$ because $E_2$ required a temporary move away from the goal (a heuristic dip).
  • Triangle Inequality: $TS_{Aineq}$ showed lower NIV values than unconstrained TS, though results suggested that node distribution also plays a significant role.

Conclusion

NIV provides a mathematical framework for quantifying search space ruggedness. The study suggests that "difficulty" is not just a property of the problem itself, but of the interaction between the problem space and the heuristic used. While the experiments were conducted on a small scale, they lay the groundwork for a more robust "theory of heuristics" to fundamentally characterize hard versus easy problems.

Summary updated

BibTeX
@inproceedings{rada1983characterizing,
  author = {Roy Rada},
  title = {{Characterizing Search Spaces}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1983},
}
Figure