Knowledge-based circuit design
Christopher Tong · 1988
Design involves creating artifact descriptions that satisfy the requirements imposed by the designer, the artifact domain, the domain, logic, and experience. A design system that must produce solutions for a broad class of design problems potentially faces a search of a large space with a low solution density. In this dissertation, we present an approach for dealing with scale-up in the size and complexity of the design problem. We enhance the power of the design planner by conceiving it as alternating between hierarchically reformulating the design space and committing to choices in the reformulated space. Backtracking in the new space is reduced because the reformulation process is geared toward creating a space whose decisions do not interact. We use the circuit design domain to study how to control the design process when both choice consistency and optimality matter. We present a model of the design process that integrates constraint propagation, branch-and-bound, patching and optimization. Without the guidance of a global perspective, however, these techniques can lose effectiveness. Constraint propagation or patching can be wasted effort if used while searching sub-optimal design subspaces. Branch-and-bound may be misled by bounds that are wildly optimistic or pessimistic, if unidentified optimizations or interactions among choices exist. Applied locally, optimization may only achieve a local maximum. This dissertation describes an approach to controlling the design process called goal-directed planning (GDP). GDP focuses early attention on gathering information for constructing an appropriate search space. It uses constraint-based reasoning to form macro-decisions, groups of decisions whose choices interact functionally; it uses rough design--generation and execution of abstract design plans and arguments that can be sharpened over time, to rank and prune choices for these decisions. We have implemented a computer program called DONTE (Design process ONTology Experiment) which applies GDP to the task of circuit design. In specific, we show how DONTE accepts software-like specifications (e.g., for a stack) subject to a single resource limitation goal (e.g., a parts count goal) and produces a TTL circuit implementation in a reasonable amount of time.