Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
1998-03-30
2002-01-01
Davis, George B. (Department: 2122)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S045000, C706S051000, C706S019000
Reexamination Certificate
active
06336110
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to an improvement in the technology for calculating a solution of a so-called constraint-satisfaction problem so that a large problem may be solved speedily.
2. Description of the Related Art
A constraint-satisfaction problem is known as a problem for assigning a set of consistent values to a set of variables. A set of consistent values means that these values satisfy combinational constraints defined of the set of variables. Hereafter, each variable is corresponded to a part of a thing e.g., a system, a product, etc., and each value is corresponded to an alternative to implement the part. Each part may be provided with multiple choices (alternatives) and constraints, such as permissible and impermissible combinations, exist on a combination of alternatives selected respectively for different parts. A solution for the constraint-satisfaction problem is a combination of alternatives that may be applied to all parts so that all constraints are satisfied.
An example of the constraint-satisfaction problem is shown below. Assume that machine X consists of four parts, A, B, C, and D, and that three implementation methods are provided for each of the four parts. That is, implementation methods a1, a2, and a3 (hereafter represented as {a1, a2, a3}) are provided for part A, {b1, b2, b3} for part B, {c1, c2, c3} for part C, and {d1, d2, d3} for part D. Each choice (for example, implementation method a1) for a part is called an alternative.
In addition, assume that there is a constraint that the same implementation number cannot be used between each two parts: that is, between, A and B, A and C, A and D, B and C, B and D, and C and D. For example, if the implementation method of part A is aj (j=1, 2, 3), then the implementation methods of parts B, C, and D must be bk, ck, and dk (k≠j), respectively. Similarly, if the implementation method of part B is bj (j=1, 2, 3), then the implementation methods of parts C and D must be ck and dk (k≠j), respectively. If the implementation method of part C is cj (j=1, 2, 3), then the implementation method of part D must be dk (k≠j).
Under the constraint described above, consider selecting implementation methods A, B, C, and D to design machine X so that all the conditions required for a combination(combination conditions) are satisfied. In this example, since there is not any combination of implementation methods, or any solution, which satisfies all the combination conditions, machine X cannot be designed. However, making of this judgment on the constraint-satisfaction problem requires that all the combinations of the implementation methods for each part are checked, as shown below, to see whether they satisfy the combination conditions:
{a1, b1, c1, d1}
{a1, b1, c1, d2}
{a1, b1, c1, d3}
{a1, b1, c2, d1}
{a1, b1, c2, d2}
As understood from the combinations above, it is difficult for a designer to make such a judgment even if combinations for only four parts are checked as this example. If combinations for a more large number of parts are checked, it becomes more difficult to make such a judgment. For example, if there are as many as 30 parts and four implementation methods are provided for each of the four parts, a huge number of combinations of alternatives must be checked. It is virtually impossible to check each combination as described above. For this reason, a solution for a constraint-satisfaction problem has been found, in most cases, using a trial-and-error method based on experience.
The constraint-satisfaction problem is not limited to a field where an alternative must be selected for each of the parts that make up a machine such as the one described above. The problem may be applied to many other fields too; for example, it may be applied to how parameters should be specified for each part of a software product or how a plurality of objects should be arranged in a limited area. Therefore, the constraint-satisfaction problem occupies a very important position, for example, in building an expert system.
In general, the constraint-satisfaction problem is defined as follows. That is, when a system (problem) includes a plurality of parts each having a finite number of alternatives used for implementation of each part or its function and when there is a constraint on the combination of two alternatives of each pair of parts in said plurality of parts, the constraint-satisfaction problem is a problem that finds an alternative satisfying the constraint for each part.
However, except a special case, the constraint-satisfaction problem is an NP complete problem. Here, let y-th power of x be represented as “x{circumflex over ( )}y”. Then, the NP complete problem refers to a problem whose amount of calculation for solving the problem may be represented as described below. That is, let the number of parts be N, and the maximum number of alternatives allowed for each part be d. In this case, finding of a combination of alternatives consistent with all parts may require d{circumflex over ( )}N calculation at the maximum. For example, if N is 100 and the maximum number of alternatives is 2, 2{circumflex over ( )}100 calculations may be necessary at the maximum. It is impossible to carry out such calculations within a time expendable in practical applications.
As a method for solving for the constraint-satisfaction problem, there is a method which reduces the amount of calculation by localizing the range affected by a constraint. (Reference: Rina Dechter, Judea Pearl: “Network-Based Heuristics for Constraint-Satisfaction Problems”, Artificial Intelligence 34 (1988)). However, during calculation, this method introduces constraint relations which do not exist at first and therefore requires about d{circumflex over ( )}N calculations in many cases.
A polynomial calculation method is also available for solving a problem where a constraint graph representing a constraint relation between parts is represented as a tree structure or as a K-tree structure which is an extension of a tree structure (Reference: Eugene Freuder, “Complexity of K-Tree Structured Constraint Satisfaction Problems”). However, this method requires conditions that are rarely satisfied in a practical application.
For the reason described above, a conventional method for solving the constraint-satisfaction problem, which is very important in building an expert system, has been capable of handling very small-scaled problems only, except special cases such as when problems are represented as tree-structured graphs representing the constraint relation between parts.
Consequently, it is desired to provide a system and a method which are useful for solving a large constraint-satisfaction problem at a high speed. Also, it is desired to provide a system and a method which are useful for building a machine or a computer program system, including a plurality of parts for each of which a plurality of alternatives are provided when constraints exist on combinations of alternatives for different parts, in such a manner that the constraint is satisfied more easily than the related art.
SUMMARY OF THE INVENTION
In an aspect, the present invention is a system for calculating a solution of a constraint-satisfaction problem including a plurality of parts for each of which a plurality of alternatives are provided when a constraint exists on a combination of alternatives selected respectively for different parts in said plurality of parts. The system divides a set of alternatives provided for a plurality of parts of a given problem to be solved into a plurality of subsets such that each subset has not more than two alternatives for each part, and analyzes a combination of alternatives for each subset to check whether the combination of alternatives satisfies said constraint, whereby allowing a solution of the problem to be calculated from the analyzed combination. Calculation of a solution for a subset in which each pa
Hasegawa Tetsuo
Tamura Shinsuke
LandOfFree
System for solving of a constraint-satisfaction problem and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for solving of a constraint-satisfaction problem and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for solving of a constraint-satisfaction problem and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2844630