Knowledge compilation (KC) converts explicitly represented domain knowledge into an efficient algorithm for performing a task. KC technology could have a major impact in fields depending of efficient problem-solving algorithms. For, example, productivity in circuit and mechanical design has grown increasingly dependent on efficient computer-aided design (CAD) tools. KC techniques can accelerate CAD tool development and improve CAD tool reliability. This work will develop knowledge compilation techniques for a variety of CAD applications. Initially the work will focus on spatial configuration problems. Such problems arise in many domains, including VLSI design, mechanical design, and architectural design. It will focus on synthesizing search algorithms composed of such components as generators, testers, and hillclimbing patchers organized into one or more levels of abstraction. The research will develop an investigate a divide- and-conquer approach to KC: A problem specification is partitioned into parts; each part is assigned to be implemented as a particular type of algorithm component. This approach should avoid the control problems that arise in unrestricted transformational models of knowledge compilation. Expected benefits of the research include articulated principles for the synthesis of design algorithms, knowledge compilers implementing such principles, and new CAD algorithms resulting from their application.
