CYPRESS-Soar: A Case Study in Search and Learning in Algorithm Design

Abstract

This paper describes a partial reimplementation of Doug Smith's CYPRESS algonthm design system within the Soar problem-solving architecture. The system, CYPRESS-SOAR, reproduces most of CYPRESS' behavior in the synthesis of three divide-and-<:anquer sorting algorithms from formal specifications. CYPRESS-Soar is based on heuristic search of problem $Jl&ceS, and uses search to compensate for missing knowledge m some instances. CYPRESS-Soar also learns as it designs algorithms, exhibiting significant transfer of learned knowledge, both within a single design run, arid across designs of several different algorithms. These results were produced by re1mplementing just the high-level synthesis control of CYPRESS, simulating the results of calls to CYPRESS' deduction engine. Thus after only two months of effort. we had a surprisingly effective research vehicle for investigating the roles of search, knowledge, and learning in this domain.