Sanjay Mittal

AAAI Conference 1990 Conference Paper

Dynamic Constraint Satisfaction Problems

• Sanjay Mittal

Constraint satisfaction (CSP) is a powerful and extensively used framework for describing search problems. A CSP is typically defined as the problem of finding consistent assignment of values to a fixed set of variables given some constraints over these variables. However, for many synthesis tasks such as configuration and model composition, the set of variables that are relevant to a solution and must be assigned values changes dynamically in response to decisions made during the course of problem solving. In this paper, we formalize this notion as a dynamic constraint satisfaction problem that uses two types of constraints. Compatibility constraints correspond to those traditionally found in CSPs, namely, constraints over the values of variables. Activity constraints describe conditions under which a variable may or may not be actively considered as a part of a final solution. We present a language for expressing four types of activity constraints in terms of variable values and variables being considered. We then describe an implemented algorithm that enables tight interaction between constraints about variable activity and constraints about variable values. The utility of this approach is demonstrated for configuration and model composition tasks.

IJCAI Conference 1989 Conference Paper

Towards a Generic Model of Configuraton Tasks

• Sanjay Mittal
• Felix Frayman

A precise definition is provided for general configuration tasks. Two important assumptions are identified: (i) functional architecture and (ii) key component per function. A domainindependent model is presented based on these assumptions. These assumptions are shown to be both useful and tenable in real domains. They are useful because they limit the complexity of the general configuration task, determine the basic knowledge needed for solving a configuration task, and enable more efficient problem solving methods. Ideas are presented both for representing the knowledge and controlling the search. Some of these ideas were originally implemented in the Cossack expert system.

IJCAI Conference 1987 Conference Paper

Compiling Design Plans from Descriptions of Artifacts and Problem Solving Heuristics

• Agustin A. Araya
• Sanjay Mittal

An analysis of the design plans in the Pride expert system shows that they integrate knowledge about structure and functionality of artifacts as well as problem-solving heuristics A method is presented by which such plans can be automatically generated by compiling knowledge about artifacts, problem solving heuristics, and characteristics of specific problems. Knowledge compilation allows the creation of plans tailored to particular problems and offers potential benefits in maintaining a knowledge base, in reusing the same knowledge for different purposes, and in providing a framework for more systematic knowledge acquisition

AAAI Conference 1987 Conference Paper

Making Partial Choices in Constraint Reasoning Problems

• Sanjay Mittal

Constraint problems derived from design and configurations tasks often use components (structured values) as domains of constrained variables. Most existing methods are forced into unnecessary search because they assign complete components to variables. A notion of partial choice is introduced as a way to assign a part of a component. The basic idea is to work with descriptions of classes of solutions as opposed to the actual solutions. It is shown how this idea can reduce search and in the best case eliminate search. A distinction is made between a partial commitment (a partial choice that would not be retracted) and a partial guess. A particular way to implement partial choice problem solvers is discussed. This method organizes choices in a taxonomic classification. Use of taxonomies not only helps in pruning the search space but also provides a compact language for describing solutions, no-goods, and representing constraints. It is also shown how multiple hierarchies can be used to avoid some of the problems associated with using a single hierarchy.

AAAI Conference 1986 Conference Paper

A Knowledge-Based Framework for Design

• Sanjay Mittal

Many design problems can be formulated as a process of searching a "well-defined" space of artifacts with similar functionality. The dimensions of such spaces are largely known and are constrained by relations obtained from the implicit functionality of the designed artifact. After identifying the kinds of knowledge that mediate the search for acceptable designs, a computational framework is presented that organizes the required knowledge as design plans. A problem solver is described that executes these plans. The problem solver extends the notion of dependency-directed backtracking with an advice mechanism. This mechanism allows information from a constraint failure to be used as advice in modifying a partial design. An expert system for designing paper transports inside copiers has been successfully built based on this framework.

IJCAI Conference 1983 Conference Paper

CSRL: A Language for Expert Systems for Diagnosis

• Tom Bylander
• Sanjay Mittal
• B. Chandrasekaran