Automated Configuration Problem Solving by Charles J. Petrie

Author:Charles J. Petrie
Language: eng
Format: epub
Publisher: Springer New York, New York, NY

3.3 Generate and Test

The simplest type of configuration problem solving is to “generate and test”. If all of the configuration conditions are expressed as constraints, then either the solving algorithm consists of some sort of CPS that tries values until consistency is achieved, or a specialized solver that somehow distinguishes among the constraints and assigns values to some variables first and then checks for consistency because it is known that this is efficient for the problem domain.

A more general type of algorithm distinguishes the constraints as goals and restrictions, as described in Sect. 2.4, and tries to satisfy some goal or subgoal (requirement-type constraint) and then test to see whether any restriction-type constraint is violated. The simplest systems select both a goal and a way to achieve it at random. A more sophisticated system allows the use of special knowledge both to select a goal and the first or next method to try in achieving it [50]. Using such knowledge to select methods allows at least local preferences to be easily considered. For instance, in building a boat, one may always prefer to start with wood as a building material, and try concrete last.

An immediate benefit of such reasoning is that goals may be used to explain component assignments. Such explanations may involve subgoaling. The choice of a propeller is a means of pushing the water, which is a subgoal of the goal of configuring a propulsion system, which is itself a subgoal of the general boat design. Further, most configuration solving techniques, including constraint satisfaction, may assign parts to a configuration at an intermediate stage in problem solving that are not needed in the final configuration. With goals, parts may be filtered out of the configuration if they have no valid goal associated with them.

Goals also allow for problem decomposition in that any method may decompose the goal into subgoals that are more easily solved. For instance, given the goal of building an automobile, a method may decompose it into the subgoals of building a drive train and a chassis, which can be pursued separately, but with their individual solutions connected by compatibility and aggregate constraints that restrict the candidate solutions.

Once a goal and a method of achieving it is determined, then the consequences of this design decision must be examined. Some systems consider all consequences to be new constraints and some [50, 71] distinguish between new subgoals that have to be achieved (new requirements) and constraint restrictions that may be violated because of the decision (new constraint violations). In [50], constraint violations can only be fixed by retracting some previous design decision: i.e., backtracking, or by relaxing a constraint.

One advantage of such a system is that irrelevant constraints do not have to be considered: once a decision has been made, a search, by proof for example, can be made to determine which, if any, constraints (restrictions) might be violated. There may be many constraints that are simply irrelevant for a particular search path that leads to a solution.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.