Automated Synthesis of Constrained Generators

Abstract

Knowledge compilation is an emerging research area that focuses on "compiling" a problem solver's inefficient, explicit knowledge representation into more efficient, implicit forms. This paper presents a technique that transforms a declarative problem description (specifying the problem but not how to solve it) into a reasonably efficient, generate-and-test problem solver. Our technique performs constraint incorporation, modifying the parameter generators so they only generate values that satisfy the problem constraints. Successful constraint incorporation depends upon choosing the right solution representation (i.e., the set of parameters). Having expressed a constraint in terms of a particular set of parameters, incorporation fails if the constraint is not factorable into constraints on the individual parameter generators . RICK, a Refinement-based constraint Incorporator for Compiling Knowledge, is a prototype program that compiles a problem specification into a problem solver using least commitment, topdown refinement to achieve constraint incorporation. RICK refines an abstract solution representation to avoid premature commitment to representations that hinder constraint incorporation. RICK is able to incorporate local constraints that constrain relatively small portions of the entire solution. We have tested these ideas by having RICK automatically construct a house floor planning problem solver.