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

Abstract

This paper describes a partial reimplementation of Doug Smith's CYPRESS algorithm design system within the Soar problem-solving architecture. The system, CYPRESS-SOAR, reproduces most of CYPRESS' behavior in the synthesis of three divide-and-conquer sorting algorithms from formal specifications. CYPRESS-Soar is based on heuristic search of problem spaces, and uses search to compensate for missing knowledge in some instances. CYPRESS-Soar also learns as it designs algorithms, exhibiting significant transfer of learned knowledge, both within a single design run, and across designs of several different algorithms. These results were produced by reimplementing 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.