Improving Search through Diversity

Peter Shell, Juan Antonio Hernandez Rubio, Gonzalo Quiroga BarroAAAI 1994

Introduction

In complex search spaces where the number of possible states is astronomical (e.g., $10^{200}$), traditional symbolic AI search methods like beam search must prune the majority of paths to remain computationally feasible. Typically, these algorithms retain only the $K$ "best" states based on a heuristic evaluation function. However, this often leads to a "similarity trap" or premature convergence: the $K$ best states become nearly identical, differing by only a single operator. If the true global optimum requires a path that appears sub-optimal in the short term, standard searchers will prune it early.

This paper, originally presented at AAAI 1994, introduces "diversity search." By borrowing concepts from Genetic Algorithms and applying them to symbolic search, the authors demonstrate how maintaining a diverse "pool" of candidate solutions prevents algorithms from getting stuck in local optima, leading to significantly better global outcomes in complex, real-world domains.

The authors propose a Diversity Beam Search algorithm. Instead of exclusively keeping the $K$ highest-scoring states, the algorithm retains an additional $K'$ states chosen specifically for their difference from the current best set.

Key Technical Contributions

  • Domain-Independent Diversity Metric: Diversity is measured based on the sequence of operators used to reach a state. If two states were reached using mostly different actions, they are considered diverse, regardless of domain-specific features.
  • The "Band" Search Strategy: To avoid wandering into "diverse but useless" territory, the "banded" approach groups states into multiple bands based on diversity scores. Within each band, the states with the lowest costs are retained. This allows high-diversity states to eventually "jump" into the primary cost-evaluation set if they lead to a breakthrough.
  • State-Match Function: A formal logic calculates the "closeness" of two states by comparing their constituent operators, independent of their application order.

Empirical Evidence: The Crowding Effect

A core motivation for diversity search is the observation that standard beam searchers often "put all their eggs in one basket." The authors provide empirical evidence of this "crowding effect" in their analysis of operator overlap across the search beam.

Analysis of operator diversity in standard beam search, showing high overlap between candidate states.

As shown in the table above, in a standard beam search, over 97% of operators are common across all states in the beam on average. This lack of diversity confirms that standard searchers are prone to premature convergence.

Results and Discussion

The algorithm was evaluated using real-world treasury data from Union Fenosa, a large electric utility in Spain. The task involved daily cash management—a high-complexity search space with roughly 100 possible operators per state and solutions requiring sequences of approximately 100 operators.

The researchers compared a standard beam searcher (width 10) against several diversity-based variants (width 5 for cost + 5 for diversity).

Relative cost performance of diversity search variants compared to the standard beam search baseline across four test weeks.

As summarized in the results table, diversity-based searchers consistently outperformed the baseline. The most effective strategy, the Band(4,1) variant, achieved average costs that were only 71% of the standard beam searcher. The performance was particularly striking in "hard" cases like Week 1, where the diversity searcher reduced costs to just 28% of the baseline by avoiding a state where funds were trapped in unusable accounts. While "simple" diversity search occasionally underperformed in simpler search spaces (e.g., Week 4), the Banded variants proved robust across all scenarios.

Conclusion and Future Work

Diversity search treats "covering ground" as a formal evaluation criterion alongside cost. While highly effective in complex spaces, the authors note that in search spaces without many local maxima, diversity slots might be "wasted." Future work could explore dynamic diversity parameters, such as a "simulated annealing" schedule where the requirement for diversity decreases as the search nears its conclusion. Additionally, while the operator-based metric is domain-independent, further testing in domains like game-playing or theorem-proving would validate its generalizability.

This summary is based on the 1994 AAAI paper "Improving Search through Diversity."

Summary updated

BibTeX
@inproceedings{shell1994improving,
  author = {Peter Shell and Juan Antonio Hernandez Rubio and Gonzalo Quiroga Barro},
  title = {{Improving Search through Diversity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure