Accession Number:

ADA339333

Title:

Exploiting Stochasticity in Systematic Search: Results on a Highly Structured Domain

Descriptive Note:

Final technical rept. Jan 96-Jan 97

Corporate Author:

CALSPAN UB RESEARCH CENTER BUFFALO NY

Personal Author(s):

Report Date:

1997-10-01

Pagination or Media Count:

56.0

Abstract:

We introduce a new benchmark domain for hard computational problems that bridges the gap between purely random instances and highly structured problems. We show how to obtain interesting search problems by introducing random perturbations into a structured domain, and how such problems can be used to study the robustness of search control mechanisms. Our experiments demonstrate that the performance of search strategies designed to mimic direct constructive methods degrade surprisingly quickly in the presence of even minor perturbations. On the other hand, our experiments show that by adding a random element to a complete search procedure we can dramatically improve the performance of deterministic methods. These results apply both for the case of finding consistent models as well as for the case of proving inconsistency, complementing the well known success of using randomness in incomplete model find procedures. We pushed the idea of exploiting stochasticity one step further by combining algorithms that exhibit competing behavior into portfolios. Our results show that a portfolio approach can have a dramatic impact in terms of the overall performance, in comparison to the performance of each of its component algorithms. An interesting special case is when the best strategy consists of combining copies of the same algorithm. This portfolio is analogous to the practice of restarts for stochastic procedures, where the same algorithm is run repeatedly with different seeds, a common practice in the theorem proving community. Combining copies of the same algorithm into a portfolio might be a good strategy, especially in the cases that one algorithm dominates for a given class of problems.

Subject Categories:

  • Operations Research
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE