Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-05-06
2003-03-04
Follansbee, John A. (Department: 2127)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S202000
Reexamination Certificate
active
06529934
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an improved technique for processing information using a computer network, and more particularly to an improved techniques for distributed processing with regard to constraint satisfaction problem and an improvement in technology for readily realizing flexible bonding of a plurality of the existing systems.
2. Description of the Related Art
Recently, a practical approach using the framework of a constraint satisfaction problem (CSP) has been made to various problems including production scheduling problems and facilities and parts layout problems. The constraint satisfaction problem refers to a problem of finding a combination of values satisfying a constraint for a plurality of variables.
In a constraint satisfaction problem, individual elements such as facilities or parts constituting an actual problem are represented by variables. In this case, there are many constraints that may include one requiring that the facilities and the parts be placed at least a predetermined distance apart between each two of them. These constraints are represented as constraints among variables. An actual thing, such as which one of several alternatives is to used or where in a plane or on a time-axis each element is to be placed, is represented by a specific value of each variable. After that, finding the values of the individual variables that satisfy the above-described constraint gives a solution of the problem.
That is, to find a solution is to find a combination of variable values that satisfy the constraint. A combination of such variable values represents, for instance, a working schedule or a semiconductor device layout. A part of a solution, for example, a combination of some of the variables, is called a partial solution. The processing of such a constraint satisfaction problem is based on the branch search that performs a search, for example, when there are several branches that are capable of acquiring several alternative variable values, with regard to what kind of alternatives exist as the next branches according to which one is selected from the current several branches.
Knowledge about problem solving, such as a processing procedure for solving a constraint satisfaction problem, is called problem solving knowledge. Knowledge about the elements, or variables, of a target, such as a schedule or a layout, to be solved as a constraint satisfaction problem and about a constraint among the elements or variables is called target knowledge.
One known solving method for this constraint satisfaction problem is a method in which a single problem solver provides knowledge about the problem and, at the same time, dissolves all the constraints. To “dissolve” a constraint is to assign specific values not conflicting with the constraint.
FIG. 22
is a diagram showing the concept of a single problem solver which has both problem solving knowledge and target knowledge. The problem solver calls a method corresponding to individual target knowledge for problem solving.
However, for a large constraint satisfaction problem such as an actual scheduling problem, a target for which problem solving is performed is physically distributed and, in most cases, the decision making actions at several levels are performed concurrently. In addition, assigning all tasks to the single problem solver requires the unified management of a large amount of data and results in the disclosure of information associated with the local aspect of the problem at one particular point, thus making it difficult to ensure security.
In particular, it is difficult to apply the single, centralized system described above to an actual large problem. The constraint satisfaction problem is, for example, a power cut plan for work of electric power system facilities. The power cut plan for work of electric power system facilities sets up dates on which power transmission will be temporarily suspended to maintain, replace, or add various types of facilities (bus bar, power transmission line, power generator, transformer, etc.).
Most conventional systems for supporting the power cut plan for work of electric power system facilities collect the schedules of all stations in one location (Reference: “Development of Support System of Power Cut Plan for Work” by Akitomo Otubo, Thoshio Takahasi, Datashi Saito, Kazue Simada, Masaya Ono, Hirotaka Nakano, Yosiaki Osako, pp.138-139, 1997 Power System Convention, 1997). However, the system according to the prior art such as described above must perform a huge amount of centralized calculation and therefore requires a long processing time because the scale is very large. In addition, when the result of centralized calculation is not accepted by stations, the centralized calculation must be repeated. This sometimes causes a communication bottleneck.
Another problem is that the centralization of processing or communication loads decreases the applicability to the dynamic environment in the real world. For this reason, a method for modeling an actual large constraint satisfaction problem and for solving the problem efficiently with a plurality of solvers in the distributed coordination mode is now being studied.
This problem solving method, which works in the distributed coordination mode through a plurality of problem solvers, allows individual stations in the electric power system to work together to solve constraints coordinatable locally among themselves, except when the constraints require system-wide information as in a current calculation. This method gives us many advantages; that is, it reduces the centralized calculation load, reduces the coordination time, and results in fewer modification requests from the schedule made by each station.
Recently, many actual problems are modeled as large constraint satisfaction problems. And, as the means for solving such modeled problems efficiently, more emphasis is placed now on the constraint satisfaction problem solving method which works in the distributed coordination mode described above.
The method for satisfying constraints in the distributed coordination mode is called a distributed constraint satisfaction or a distributed constraint satisfaction problem. The method sometimes uses a plurality of equal agents (problem solvers). Standard algorithms used for this method include the synchronous backtrack algorithm and the asynchronous backtrack algorithm (Reference: “Tutorial Distributed Search and Its Surroundings” by Makoto Yokoo, Computer Software Vol. 12, No. 1, pp. 31-86, January 1995/“New Development of CSP: Distributed/Dynamic/Incomplete CSP” by Makoto Tokoo, Katsutosi Hirayama, Artificial Intelligence, Vol. 12, No. 3., pp. 381-389, May. 1997).
The synchronous backtrack algorithm executes the backtrack type search algorithm using a plurality of agents. In this algorithm, the order in which agents determine their variables is fixed. More specifically, the first agent temporarily determines the values of its own variables and sends the values (partial solution) to the next agent. The next agent determines the values of its own variables so that the values satisfy both the partial solution and the constraint and adds the values to the partal solution; it then sends the resulting partial solution to the next agent.
When some agent tries to determine the values of its own variables but finds that there is no value satisfying the partial solution and the constraint, the agent sends a value-change request (backtrack) message to the previous agent. In this synchronous backtrack algorithm, agents send the partial solution serially, allowing the knowledge owned by individual agents to be integrated and thereby giving a solution satisfying the constraints.
Sycara and his group proposed the back jumping algorithm developed by improving the search efficiency of the above-described backtrack algorithm. They are studying the application of that algorithm to the scheduling problem. (Reference: Sycara, K. P., Sadeh, N. and Fox, M. S., “Distributed constrained heuristics searc
Hasegawa Tetsuo
Kase Naoki
Kawamura Takahiro
Ohsuga Akihiko
Tahara Yasuyuki
Banner & Witcoff, LTD.
Follansbee John A.
Kabushiki Kaisha Toshiba
LandOfFree
Information processing system and method for same does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information processing system and method for same, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information processing system and method for same will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3027430