Expected Solution Quality

John L. Bresina, Mark Drummond, Keith Swanson

In the domain of constrained optimization—such as scheduling complex telescope observations—the "optimal" solution is often a theoretical construct. The search space is frequently so vast that finding the absolute best solution is computationally impossible, leaving researchers with a difficult question: How do we evaluate the quality of a scheduler when we don't know what the best possible score is?

Researchers from NASA Ames Research Center address this by introducing the Expected Solution Quality (ESQ) method. Rather than chasing an unreachable optimum, ESQ uses statistical sampling to map the search space, providing a baseline to determine where a scheduler’s performance sits relative to the "average" feasible solution.

The ESQ Methodology

The ESQ method relies on three primary components to characterize an unknown search space:

  1. Iterative Sampling: A Monte Carlo approach that generates random feasible schedules by traversing the search tree and making random choices at each branch.
  2. Quality Density Function (QDF): By generating a large set of random samples (e.g., 1,000), researchers estimate the probability distribution of scores for a specific problem instance. This distribution provides the mean and standard deviation necessary to contextualize any single scheduler's result.
  3. The Quality/Time Measure: This metric calculates the probability $p$ of a random sample matching a scheduler's performance. The "expected sampling time" ($1/p$ multiplied by the time per sample) creates a unitless "common currency" to compare schedulers across different computational costs and solution rarities.

Characterizing the Search Space

To understand the difficulty of a problem, ESQ analyzes the structure of the search tree. In the telescope scheduling domain, the authors estimated a search space of approximately $10^{61}$ possible schedules. By tracking the branching factor at various depths, they can visualize how constraints narrow the possibilities as a schedule is built.

Figure 1: The average branching factor decreases as the search depth increases, illustrating the narrowing of the search space.

Performance and Heuristic Analysis

The power of ESQ lies in its ability to reveal the statistical significance of performance gaps. In one test case, a greedy look-ahead scheduler achieved a score of -11.56, while a standard heuristic dispatch method scored +0.14. In this objective function, lower scores represent higher quality.

Figure 3: The Quality Density Function (QDF) shows the distribution of random samples centered around zero. The greedy look-ahead scheduler (at -12) is statistically rare, while the dispatch method (at 0) performs no better than a random guess.

While the raw scores might appear close, the ESQ analysis revealed that the greedy look-ahead scheduler was 8.89 standard deviations better than the mean. When accounting for the statistical rarity of such a solution, the look-ahead method was found to be 16 orders of magnitude more effective than the dispatch method.

Furthermore, the method highlighted a "bias discrepancy" in common heuristics. For instance, "airmass" (atmospheric quality) served as an excellent local predictor for high-quality schedules. Conversely, "fairness" proved to be a global attribute that is difficult to optimize with simple greedy approaches because its early-stage prefixes often yield poor scores, even if they lead to better final results.

Conclusion

Expected Solution Quality provides a robust framework for evaluating algorithms in domains where the ground truth is missing. By transforming arbitrary scores into statistical probabilities, researchers can objectively measure progress and identify when existing heuristics fail to align with the true goals of the objective function. Future applications include self-evaluating systems that can dynamically adjust scheduling strategies based on the evolving "shape" of the search space.

Summary updated

BibTeX
@inproceedings{bresina1995expected,
  author = {John L. Bresina and Mark Drummond and Keith Swanson},
  title = {{Expected Solution Quality}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure