CONSTRAINTS(ID:892/con034)Constraints using value inference. Related languages
References: The Kernel ThingLab System The kernel ThingLab system consists of a Smalltalk extension, written by the present author, that is used in all ThingLab simulations. Embedded in this program is knowledge about such things as inheritance hierarchies, part-whole relations, and constraint satisfaction techniques. The kernel system doesn?t have any knowledge about specific domains in which ThingLab can be used, such as geometry or electrical circuits. Rather, it provides tools that make it easy to construct objects that contain such knowledge. Another goal in constructing the system, besides the exploration of language design as described above, was to investigate computer-based tools for use in education. For example, a ThingLabstyle system might prove valuable as part of a geometry curriculum, or as an adjunct to a physics laboratory. With this in mind, it is anticipated that there would be two sorts of users of the system. The first sort of user would employ ThingLab to construct a set of building blocks for a given domain. For example, for user in simulating electrical circuits, such a user would construct definitions of basic parts such as resistors, batteries, wires and meters. The second sort of user could then employ these building blocks to construct and explore particular simulations. The knowledge and skills required by these two kinds of users would be different. The first kind of user would need to now about message passing the constraint specification domain (e.g.Ohm?s Law). The second kind of user, on the other hand, could deal with the system using only simple interactive graphics techniques, such as selecting items in a menu or moving pictures around on the screen. Thus, this sort of user wouldn?t need to be familiar with either the details of ThingLab, or with the domain-specific theory behind the simulation (although one of the objectives of a curriculum might be for such a user to acquire this domain-specific knowledge). Extract: Constraint Representation and Satisfaction Constraint Representation and Satisfaction Representation of Constraints The representation of constraints reflects their dual nature as both descriptions and commands. Constraints in ThingLab are represented as a rule and a set of methods that can be invoked to satisfy the constraint. The rule is used by the system to construct a procedural test for checking whether or not the constraint is satisfied, and to construct an error expression that indicates how well the constraint is satisfied. The methods describe alternate ways of satisfying the constraint; if any one of the methods is invoked, the constraint will be satisfied. Merges An important special case of a constraint is a merge. When several parts are merged, they are constrained to be identical. For efficiency, they are usually replaced by a single part rather than being kept as several separate objects. The owner of the parts keeps a symbolic representation of the merge for use in constraint satisfaction, as well as for reconstruction of the original parts if the merge is deleted. One use of merging is to represent connectivity. For example, to connect two sides of the triangle, an endpoint from one side is merged with an endpoint of the other. Another use of merging is to apply pre-defined constraints. Thus, to constrain the base of the triangle to be horizontal, one can simply merge an instance of HorizontalLine with the side to be constrained. Constraint Satisfaction It is up to the user to specify the constraints on an object; but it is up to the system to satisfy them. Satisfying constraints is not always trivial. A basic problem is that constraints are typically multi-directional. For example, the horizontal line constraint is allowed to change either endpoint of the line. Thus, one of the tasks of the system is to choose among several possible ways of locally satisfying each constraint. One constraint may interfere with another; in general the collection of all the constraints on an object may be incomplete, circular, or contradictory. Again it is up to the system to sort this out. The approach taken in ThingLab is first to analyze the constraints on an object and plan how to satisfy them, and then to make the actual changes to satisfy the constraints. In ThingLab, the particular values that an object holds usually change much more rapidly than its structure. For example, if on the display the user moves some part of a constrained geometric object with the cursor, the values held by this object will change every time its picture is refreshed. Each time some value is changed, other values may need to be changed as well to keep the constraints satisfied. However, the object?s structure will change only when the user adds or deletes a part or constraint. The design of the ThingLab constraint satisfaction mechanism is optimized for this environment. A constraint satisfaction plan may depend on the particular structure of an object, but should work for any values that the object might hold. (If not, appropriate tests must be included as part of the plan.) Once a plan for satisfying some constraints has been constructed, Smalltalk code is compiled to carry out this plan. Thus each time the part of the constrained geometric object is moved , it is this pre-compiled method that is invoked, rather than a general interpretive mechanism. Also, the plan is remembered in case it is needed again. Planning is done using symbolic references to the constrained parts, so that the same plan may be used by all instances of a class. If the class structure is changed so that the plan becomes obsolete, it will be automatically forgotten. When an object is asked to make a change to one of its parts or subparts, it gather up all the constraints that might be affected by the change, and plans a method for satisfying them. In planning a constraint satisfaction method, the object will first attempt to find a one-pass ordering for satisfying the constraints. There are two techniques available in ThingLab for doing this: propagation of degrees of freedom, and propagation of known states. In propagating degrees of freedom, the constraint satisfier looks for an object with enough degrees of freedom so that it can be altered to satisfy all its constraints. If such an object is found, that object and all the constraints that apply to it can be removed from further consideration. Once this is done, another object may acquire enough degrees of freedom to satisfy all its constraints. The process continues in this manner until either all constraints have been taken care of, or until no more degrees of freedom can be propagated. In the second technique propagating known states, the constraint satisfier looks for objects whose states are completely known. If such an object is found, the constraint satisfier will look for one-step deductions that allow the states of other objects to be know, and so on recusively. If there are constraints that cannot be handled by either of these techniques the object will invoke a method for dealing with circularity. Currently, the classical relaxation method is the only such method available. As will be described in Chapter 5, relaxation can be used only with certain numerical constraints, and is also slow. In this method, the object changes each of its numerical values in turn so as to minimize the error expressions of its numerical values in turn so as to minimize the error expressions of its constrains. These changes are determined by approximating the constraints on a given value as a set of linear equations by finding the derivative of the error expressions with respect to the value, and solving this set of equations. Relaxation continues until all the constraints are satisfied (all the errors are less than some cutoff), or until the system decides that it cannot satisfy the constraints (the errors fail to decrease after an iteration). If the relaxation method is used, the system issues a warning message to the user. The user can either let things stand, or else supply additional information in the form of redundant constraints that eliminate the need for relaxation. Where are Constraints Useful? Where are constraints useful? In discussing this question, it is important to differentiate what can be expressed using constraints from what sets of constraints can be satisfied. Many more things can be expressed than can be satisfied, For example, it is easy to state the following constraints: xn + yn = zn x, y, z, n integers x, y, z >0 n > 2. However, finding values that satisfy these constraints, or proving that no such values exist, requires either a counterexample or a proof of Fermat?s Last Theorem. What can be expressed using constraints? To express a relation as a constraint, the following information is needed: a rule (from which the system will derive a satisfaction test and an error expression); and one or more methods for satisfying the constraint. For numerical constraints, the methods may be omitted if the user is willing to live with the relaxation method. Any relation that must always hold, and for which this information can be supplied, may be expressed as a constraint. Some relations that cannot be expressed as constraints in a general way using current ThingLab techniques include: any relation involving ordering or time; relations that need hold only under certain conditions; and meta-constraints (constraints on other constraints or on constraint satisfaction strategies). What sets of constraints can be satisfied? If the constraint dependency graph has no circularities, or if the circularities can all be broken using one-step deductions, then the one-pass constraint satisfaction techniques will always succeed, and will provide correct results. Further, the constraints can be satisfied, or determined to be unsatisfiable, in time proportional to that required to execute the local methods provided by the constraints. If the dependency graph does have circularities that cannot be broken by one-step deductions, the constraints for which relaxation can be used. These constraints must either be linear, or else constraints for which linearization is an adequate approximation. An example of a set of circular constraints for which the relaxation method does not work are those that describe a cryptarithmetic problem, e.g. DONALD + GERALD = ROBERT with D=5. [See Newell & Simon 1972 for a description of this domain.] Relaxation is useless here, since the constraints cannot be approximated by linear equations. To solve such kinds of problems, other constraints satisfaction techniques would be needed, such as heuristic search. Relation to Other Work As mentioned previously, the two principal ancestors of ThingLab are Sketchpad an Smalltalk. It is also closely related to work on constraints by Gerald Sussman and his students; other related work includes Simula the Actor languages, KRL, and a number of problem solving systems. Following a discussion of these and other systems, a summary of the novel features of ThingLab is presented. Extract: CONSTRAINTS Works by Gerald Sussman and his Students ThingLab is related to recent work on a constraint language at MIT by Guy Steele and Gerald Sussman [Steele & Sussman 1978], and also to other work by Sussman and his students on the problem of applying artificial intelligence techniques to computer-aided design [Sussman & Stallman 1975, Stallman & Sussman 1977, Doyle 1977, de Kleer & Sussman 1978]. The Thinglab representation of an object in terms of parts and subpart, with explicit representation of shared parts, is nearly isomorphic to the representation independently developed by Steele and Sussman, Their system has a built-in set of primitive constraints, such as adders and multipliers. Using these primitive constraints, compound constraints can be built up. This is much like the method used in the StringLab calculator example described in Chapter 2. These similarities are interesting, given the rather different environments in which the system were written (Lisp and Smalltalk). To handle constraints that cannot be satisfied using a one-pass ordering, they employ multiple redundant views that can cooperate in solving the problem; in their previous work, symbolic algebraic manipulation techniques were employed. They note that powerful algebraic manipulation techniques alone are not enough to solve many interesting problems that can be solved by people; rather, ways are needed of organizing the solution so that the system can use canned theorems, coupled with simple algebra only. Multiple views are one way of encapsulating such theorems. Their use of multiple views has been adopted in ThingLab directly, and the voltage divider example in Chapter 5 is taken from their work. ThingLab does not have any symbolic algebraic capabilities. Their language retains dependency information ? a record of the justifications for each conclusion ? to identify which constraints are responsible in the event of an inconsistency, for use in propagating the effects of an edit, and to allow efficient backtracking when search is needed (dependency-directed backtracking). [since ThingLab has no dependency information, when the structure of an object changes it checks more things, and throws away more constraints satisfaction plans, than it really needs to.] On the other hand, ThingLab has a number of features that are not present in their language. Steele and Sussman have an abstraction mechanism like the one used in ThingLab for building a class given a prototypical example, but do not have a general inheritance hierarchy that allows subclassing. Their system does not have any graphics. In regard to constraints, ThingLab allows constraints on non-numerical objects such as text, as well as on numerical quantities, and can express preferences in addition to absolute requirements. Also, it incrementally compiles the results of constraint satisfaction planning, rather than using an interpreter. in Artificial Intelligence 14(1):1-39 August 1980 view details |