Title: Cooperate processing units using stored cooperation problem solving knowledge and receive information to perform problem solving
Abstract: A mobile agent mediates cooperation among schedulers by executing a cooperation protocol. For heuristics such as strategies and the order in which variables are decided, which are used as criteria of selecting the value of a variable from candidates, when the heuristics are to be built into a solving method of a constraint satisfaction problem, processes with regard to these heuristics are so substantially localized as to be capable of parallel execution. These processes capable of parallel execution, as autonomous operations of different mobile agents, can be under modeling in natural form, resulting in easy installation. This facilitates software construction for reflecting the heuristics in a solving method of a constraint satisfaction problem, as well as improves the maintainability and extendibility of software.
Patent Number: 7,016,934 Issued on 03/21/2006 to Kawamura, et al.
| Inventors:
|
Kawamura; Takahiro (Ohta-ku, JP);
Tahara; Yasuyuki (Yokohama, JP);
Kase; Naoki (Yokohama, JP);
Hasegawa; Tetsuo (Shibuya-ku, JP);
Ohsuga; Akihiko (Kawasaki, JP)
|
| Assignee:
|
Kabushiki Kaisha Toshiba (Kawasaki, JP)
|
| Appl. No.:
|
340619 |
| Filed:
|
January 13, 2003 |
Foreign Application Priority Data
| May 06, 1998[JP] | 10-123382 |
| Sep 30, 1998[JP] | 10-278527 |
| Current U.S. Class: |
709/202; 718/100; 718/102 |
| Current Intern'l Class: |
G06F 15/16 (20060101) |
| Field of Search: |
718/100,102
709/202
|
References Cited [Referenced By]
U.S. Patent Documents
| 5872972 | Feb., 1999 | Boland et al.
| |
| 5944783 | Aug., 1999 | Nieten.
| |
| 6012152 | Jan., 2000 | Douik et al.
| |
| 6065039 | May., 2000 | Paciorek.
| |
| 6092099 | Jul., 2000 | Irie et al.
| |
| 6134580 | Oct., 2000 | Tahara et al.
| |
| 6148327 | Nov., 2000 | Whitebread et al.
| |
| 6226666 | May., 2001 | Chang et al.
| |
| Foreign Patent Documents |
| 05-238455 | Sep., 1993 | JP.
| |
| 07-242940 | Sep., 1995 | JP.
| |
Other References
"The DARPA Knowledge Sharing Effort : Progress Report" by ¥bibitem{DARPA}
Paaatil, P.S., Fikes, R.E., Patel-Schneider, R.E., Macay, D., Finin, T., Gruber,
T.R. and Neches, R., Proceedings of the Third International Conference on Principles
of Knowledge Representation and Reasoning, 1992.
"Mobile Agent Technology Implementing Network Society" by Shiniti Motoida, Takashi
Moriyasu, Takahiro Kawamura, Toshiba review, vol. 53, No. 8, pp. 2-6, Aug. 1998.
"JAFMAS : A JAVA-based Agent Framework for Multiagent Systems Development and
Implementation" by Chauhan, D., phD thesis, ECECS Department, University of Cincinnati, 1997.
Sycara, K.P, Sadeh, N. and Fox, M.S., "Distributed constrained heuristics search",
IEEE Transactions on Systems, Man And Cybernetics, vol. 21, No. 6, pp. 1446-1461, 1991.
Sycara, K.P, Roth, S.F., Sadeh, N. and Fox, M.S., "Resource Allocation in Distributed
Factory Scheduling", IEEE Expert, vol. 6, No. 1, pp. 29-40, 1991.
Barbuceanu, M. and Fox, M.S., "Cool : A language for describing coordination
in multi agent systems," Proceedings of the First International Conference on Multi-Agent
Systems, pp. 17-24, 1995.
Genesereth, M., et al., "Software Agents," Special issue on Intelligent Agents,
Communication of the ACM, vol. 37, No. 7, pp. 48-53, Jul. 1994.
"Knowledge Sharing and Reuse by Cooperative Architecture," Nishida, Toyoaki,
Jan. 1994.
Shinichi Honiden, "Mobile Agents Technology—Software Technology for Network
Computing," Sep. 15, 1998, pp. 228-233 (English Abstract only).
Takahiro Kawamura et al., "An Approach to Distributed Constraint Satisfaction
Problems by Using Mobile Agents—Development of Distributed Cooperative Power
Outage Scheduling System," IEICE Technical Report, vol. 98, No. 58, May 21, 1998,
pp. 15-22 (English Abstract only).
|
Primary Examiner: An; Meng-Al T.
Assistant Examiner: Vo; Lilian
Attorney, Agent or Firm: Banner & Witcoff, Ltd.
Parent Case Text
CROSS REFERENCE TO RELATED APPLICATIONS
This application is a continuation of prior U.S. application Ser. No. 09/305,753,
filed May 6, 1999, now U.S. Pat. No. 6,529,934, which is based upon and claims
the benefit of priority from the prior Japanese Patent Application Nos. 10-123382,
filed May 6, 1998 and 10-278527, filed Sep. 30, 1998, the entire contents of which
are incorporated herein by reference.
Claims
What is claimed is:
1. A processing unit among a plurality of processing units that form a distributed
system, comprising:
storage means for storing target knowledge with regard to a given target and
problem solving knowledge representing how problem solving with regard to said
target is to be performed;
communication means for communicating with a mediation agent to transmit information
of the processing unit and receive information from the mediation agent; and
processing means for performing a part of said problem solving by making use
of said target knowledge and said problem solving knowledge fundamentally and making
use of said information from said mediation agent optionally,
wherein said mediation agent is generated when the processing unit is required
to cooperate with another processing unit, wherein the mediation agent migrates
among said processing units and has cooperation problem solving knowledge that
represents how said processing units cooperate with each other to perform said
problem solving, and wherein the mediation agent mediates cooperation among said
units by making use of said cooperation problem solving knowledge to cause said
each unit to perform said problem solving.
2. The processing unit according to claim 1, wherein the processing unit is a
scheduler that has a plurality of variables and performs a constraint satisfaction
problem solving by assigning for each variable a value that is not contrary to
a constraint among the variables.
3. The processing unit according to claim 1, wherein said communication means
communicates with said mediation agent in a predetermined format.
4. The processing unit according to claim 3, wherein said medication agent comprises:
communication means for communicating with said each processing unit in said
format; and
coordination means for performing coordination among said processing units.
5. The processing unit according to claim 3, wherein said each processing unit
exists on a plurality of nodes, respectively, and wherein said mediation agent
has the mobility to migrate among said nodes.
6. The processing unit according to claim 4, wherein the processing unit comprises
coordination means for performing coordination of the processing unit.
7. The processing unit according to claim 4, wherein said coordination means
of said mediation agent comprises:
protocol management means for managing an interaction protocol that performs
coordination among said processing unit; and
status management means for performing said coordination by managing status of
information processing based on said interaction protocol.
8. The processing unit according to claim 1, wherein said mediation agent comprises
means for diminishing the mediation agent when the mediation agent completes cooperation
among said processing units.
9. A mobile agent which migrates among a plurality of processing units that form
a distributed system, comprising;
storage means for storing cooperation problem solving knowledge that represents
how said plurality of processing units cooperate with each other to perform said
problem solving;
communication means for communicating with said plurality of processing units
to receive information from each processing unit and transmit information generated
from either or both of said cooperation problem solving knowledge and the received
information to each processing unit; and
processing means for generating the information to be transmitted to each processing
unit by making use of said cooperation problem solving knowledge when said plurality
of processing units are required to cooperate with each other, and for mediating
cooperation among said processing units by causing said communication means to
transmit the generated information to each processing unit, whereby causing each
processing unit to perform said problem solving,
wherein said each processing unit comprises communication means for communicating
with said mobile agent in a predetermined format; and
wherein the mobile agent comprises means for diminishing the mobile agent when
the mobile agent completes cooperation among said processing units.
10. The mobile agent according to claim 9, wherein said each processing unit
is a scheduler that has a plurality of variables and performs a constraint satisfaction
problem solving by assigning for each variable a value that is not contrary to
a constraint among the variables, wherein said mobile agent comprises generation
means for generating an agent in correspondence to each alternative when there
exists a plurality of alternatives with regard to the assignment of values for
the variables, and wherein said each agent corresponding to each alternative executes
said cooperation protocol among said schedulers independently of the other agents
and according to the alternative.
11. The mobile agent according to claim 9, wherein said each processing unit
is a scheduler that has a plurality of variables and performs a constraint satisfaction
problem solving by assigning for each variable a value that is not contrary to
a constraint among the variables, wherein said mobile agent comprises generation
means for generating an agent in correspondence to each strategy if there exists
a plurality of strategies of what criterion is used for selection of a value to
be assigned, and wherein said each agent corresponding to each strategy performs
search of said solution by assigning values for the valuables independently of
the other agents, at the same time, and according to the strategy.
12. The mobile agent according to claim 9, wherein said each processing unit
is a scheduler that has a plurality of variables and performs a constraint satisfaction
problem solving by assigning for each variable a value that is not contrary to
a constraint among the variables, wherein said mobile agent comprises generation
means for generating an agent in correspondence to each variable when there are
a plurality of schedulers that have variables being approximately equal in priority
with regard to the order in which values are decided, wherein said each agent corresponding
to each variable performs search of said solution by assigning values for the valuables
independently of the other agents and at the same time, and wherein said mobile
agent comprises means for merging each agent by changing each variable so as to
minimize the change of each variable according to said constraint among the variables.
13. The mobile agent according to claim 9, wherein the mobile agent comprises:
communication means for communicating with said each processing unit in said
format; and
coordination means for performing coordination among said processing units.
14. The mobile agent according to claim 9, wherein said each processing unit
exists on a plurality of nodes, respectively, and wherein the mobile agent has
the mobility to migrate among said nodes.
15. The mobile agent according to claim 13, wherein at least one of said processing
units comprises coordination means for performing coordination of the processing unit.
16. The mobile agent according to claim 13, wherein said coordination means of
the mobile agent comprises:
protocol management means for managing an interaction protocol that performs
coordination among said processing units; and
status management means for performing said coordination by managing status of
information processing based on said interaction protocol.
Description
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 technique 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 fund 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. 'Ib "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 World" by Akitomo Otubo, Toshio
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 partial 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 search", IEEE
Transactions on Systems, Man And Cybernetics, Vol. 21, No.6, pp. 1446-1461, 1991.
Sycara, K. P, Roth, S. F., Sadeh, N. and Fox, M. S., "Resource Allocation in Distributed
Factory Scheduling", IEEE Expert, Vol. 6, No.1, pp. 29-40, 1991).
Unlike the backtrack algorithm described above, the asynchronous backtrack
algorithm allows the agents to determine their own values asynchronously and concurrently
based on the local information. And, the agents exchange the new constraint (nognod)
with each other to find a combination of variable values satisfying the system-wide constraints.
The distributed constraint satisfaction technology like this include CORBA (Common
Object Request Broker Architecture), an ORB (Object Request Broker) proposed by
OMG (Object Management Group). The ORB is a mechanism responsible for execution,
communication, and management of functionally-divided applications, each composed
of objects, in a distributed system. This architecture not only provides the applications
with the basic operation of the objects but also allows the applications to use
sophisticated common and generic functions, such as printing and data exchange.
It also provides business applications with the services common to all applications
as well as the services specific to each application.
FIG. 23 is a diagram showing the concept of the architecture like CORBA described
above. As shown in the figure, each object has both problem solving knowledge and
target knowledge. lb perform processing necessary for the target knowledge owned
by an object, the object sends a message to some other object to use the method
owned by that object.
Another distributed constraint satisfaction architecture is disclosed in
Japanese Patent Laid-Open No. Hei 7-6157 and Japanese Patent Laid-Open No. Hei
9-91431. In this architecture, the agents resident in some nodes (called stationary
agents) are used as schedulers each of which performs direct negotiation with other
schedulers (hereinafter called "direct negotiation model").
FIG. 24 is a diagram showing how a plurality of stationary agents SA perform
direct negotiation with each other. Note that, in the direct negotiation model,
agents, not the objects, are used and that they are autonomous. Therefore, as shown
in the conceptual diagram in FIG. 25, each agent autonomously decides which method
to use according to the condition under which the agent processes its own target knowledge.
Another method of sharing knowledge is also known, such as a facilitator
model implemented through DARPA knowledge sharing activity (The DARPA Knowledge
Sharing Effort). In this model, a plurality of agents use the coordination facilitator
to exchange knowledge via the common language for exchanging common knowledge ("Knowledge
Sharing and Reuse through Coordination Architecture" by Toyoaki Nishida, Artificial
Intelligence Society Magazine, Vol. 9, No. 1, January 1994, pp. 23-28). That is,
in the facilitator model, the agents exchange knowledge via one facilitator.
However, the prior art of distributed constraint satisfaction described
above has the following problems. First, for an ORB such as CORBA and the direct
negotiation model described above, the communication functions such as the highly-sophisticated
message routing function or communication protocol must be included in advance.
This makes it difficult to develop a distributed scheduling system and to utilize
the existing scheduling system.
In addition, including these communication functions into individual schedulers
results in the already-included protocol being always used as the scheduler coordination
protocol, making it difficult to add or change the protocol. Thus, it is difficult
to efficiently implement or use the constraint satisfaction algorithm, best suited
for the constraint type, for use as the coordination protocol. The coordination
protocol, a protocol defining a sequence of information exchange actions among
a plurality of subjects to achieve an object, may be represented, in general, as
a state transition diagram.
In addition, including complex processing, such as scheduler communication or
branch search, into the individual schedulers constituting the direct negotiation
model results in the frequent data exchange among schedulers especially when the
variables of the schedulers must be coordinated step by step. This increases both
the processing load of the individual schedulers and the communication amount over
the network connecting the schedulers.
When a branch search fails due to a network error and the search of a part is
terminated abnormally in the ORB or the direct negotiation model described above,
the whole processing is influenced.
In the facilitator model described above, communication processing centralization
in one facilitator causes a system bottleneck. In addition, the facilitator performs
only simple message routing but does not virtually perform coordination processing.
That is, the facilitator is not responsible for the progress of the whole processing,
nor does it tell the individual schedulers what to do next.
Another problem with the constraint satisfaction method in the above-described
distributed coordination mode is that heuristics is not reflected on the solution.
Heuristics, also called an exploratory method, is thought of as a rule-of-thumb
equation in which solutions are discovered by evaluation of the progress made toward
the final result.
It is pointed out that, in general, solution search efficiency depends largely
on the heuristics factors such as a strategy for the decision of individual agent
variables or the variable decision priority order among agents (Reference: "Constraint
Based Search and Its Application" by Kazuo Miyashita, Artificial Intelligence Magazine,
Vol. 12, No. 3, pp. 374-380, May 1997). For a constraint satisfaction problem having
a plurality of solutions, heuristics has a strong impact on the quality of the
final solution.
Typical heuristics includes the ability to switch the strategy or the priority
described above depending upon the situation. However, since the strategy and the
priority are determined by the system configuration according to the conventional
algorithm for distributed constraint satisfaction, heuristics cannot be reflected
well on the processing and, as a result, it is difficult to increase the quality
of search efficiency and quality.
Consider the power cut plan for work of electric power system facilities
described above as an example. The coordination among stations is not fixed but
varies according to the period of the year (busy season and off-season), the relation
among stations, or the processing power of maintenance companies. And, the selection
and the weighting of objects depend dynamically on such changeable factors as the
priority of schedule coordination, min;mi˜.˜tion of movement during
the work period, averaging of work load, and reduction in the number of suspensions.
Thus, coordination should be made more flexible depending upon the situation
by using the coordination method or strategy In addition, it is expected that Japanese
electric power companies will have power generation departments and power transmission
departments in the near future like European and American power companies and that
medium and small-sized electric generation companies will enter the electric power
industry. If such is the case, it is desirable that a flexible coordination method
be used, instead of the conventional fixed coordination method, to satisfy the
need from the requesting stations and requesting departments directly and easily.
However, the method according to the prior art uses a fixed strategy and
priority. Even if the strategy may be changed, the whole processing must be reexecuted
each time the strategy is changed. Re-executing the whole processing for each strategy
change requires a long time; in addition, it does not satisfy the need to find
a solution more speedily.
Conventionally, even when there are a plurality of agents with equal
priority, the method according to the prior art selects one of the agents sequentially.
This method does not always give a solution satisfying individual agents and, therefore,
there has been a need to increase the quality of a solution.
On the other hand, as computer networks have become popular rapidly, interconnection
among applications over the network becomes more important.
In particular, in conjunction with the setup of the network infrastructure and
the trend toward the openness of application software, the need arises to interconnect
applications via the network. (Reference: "Software agents" by Genesereth, M. R.
and Ketchpel, S. P, Special Issue on Intelligent Agents, Communications of the
ACM, Vol. 37, No. 7, pp. 48-53, July. 1994/"Mobile Agent Technology Implementing
Network Society" by Shiniti Motoida, Takashi Moriyasu, Takahiro Kawamura, Toshiba
review, Vol. 53, No. 8, pp. 2-6, August 1998).
More specifically, it is desirable that the existing dedicated program, called
the legacy system, and existing databases be used as much as possible and that,
by working them together, efficient distributed systems be built and managed.
Representative applications include an experiment, called CALS (Commerce
At Light Speed), which digitizes information relating to the whole life cycle of
a product, EC (Electronic Commerce) such as online shopping, and inter enterprise
EC aiming at the electronic commerce among enterprises. lb implement those applications,
interconnection among applications over networks is a key to success.
Nowadays, a variety of technologies and standards are proposed to implement
inter-system data exchange over networks. Some of the examples include SGML which
is a document processing description system, XML which is a network version of
SGML, and STEP which is used for representation and exchange of product technology data.
However, consistent operation of a distributed system requires knowledge
sharing based on data exchange as well as the coordination among constituent elements
that composes the distributed system. Lack of such a coordination function impairs
the merit of the distributed system. However, in the conventional environment to
develop such distributed system has never supported the coordination function sufficiently.
Recently, efforts have been made to develop a distributed object system
using distributed system constituent elements as objects and a multi-agent system
composed of a plurality of coordinating agents. However, most of development support
tools for use on these systems have communication functions among constituent elements
but not coordination functions among them. Therefore, a framework providing not
only communication functions but also coordination functions is required. This
framework is a partially completed software product used to create specific parts
for use in building an actual distributed system.
That is, recently, the distributed architecture is shifting from the conventional
client-server model (FIG. 26) to the distributed object model (FIG. 27) which may
be built more flexibly. This type of distributed object model generally requires
that the connected systems understand each other and that modeling and interface
specifications be defined rigidly. For example, knowledge about the object (IDL
interface and so on) of a remote partner must be known in advance. In addition,
because the logic of coordination among a plurality of objects is not supported
in the conventional object-oriented programming system, the object designer must
include the logic into individual objects.
On the other hand, for the multi-agent model which is now under study, the constituent
elements of a distributed system are regarded as agents. Several models are proposed
for executing coordination among a plurality of agents.
Those models include KQML facilitators (Reference: "Actors: A model of Concurrent
Computation in Distributed Systems" by Agha, G., The MIT Press, 1986/"An Overview
of KQML: A knowledge Query and Manipulation Language" by Finin, T. and Wiederhold,
G., Department of Computer Science, Stanford University, 1993./"The DARPA Knowledge
Sharing Effort: Progress report" by ¥bibitem{DARPA} Paaatil, P. S., Fikes,
R. E., Patel-Schneider, R. E., Macay, D., Finin, T., Gruber, T. R. and Neches,
R., Proceedings of the Third International Conference on Principles of Knowledge
Representation and Reasoning, 1992.) and a model called a federation model.
However, these models place emphasis on speedy routing of each message in
a system where connected agents interact with each other based on the exchange
of KQML messages. This means that the models do not support the higher-level coordination
function deciding how to solve the problem based on the messages received by a
plurality of agent or issued from the user.
Agent development tools for the higher-level coordination function include
COOL (Reference: "Cool: A language for describing coordination in multi agent systems"
by Barbuceanu, M. and Fox, M. S., Proceedings of the First International Conference
on Multi-Agent Systems, 1995.) and JAFMAS (Reference: "JAFMAS: A JAVA-based Agent
Framework for Multiagent Systems Development and Implementation" by Chauhan, D.,
phD thesis, ECECS Department, University of Cincinnati, 1997).
These tools propose the general methodology for developing a multi-agent system
based on Speech-Act (Reference: "How to do Things With Words" by Austin, J. L.(ed),
Oxford University Press, 1962). At the same time, the tools support an interaction
protocol (hereinafter called IP) for explicitly representing inter-dependency among
KQML messages. This IP, primarily composed of the communication element and the
coordination element, is a procedure allowing constituent elements, such as applications,
to communicate with each other and to coordinate the constituent elements to solve
a given problem.
However, creating the IP with the use of these tools is very complex. This
is because each agent must have its own dedicated IP and that the IPs of all agents
must be compatible. Therefore, when the user wants to add or modify some part of
a problem solving procedure at initial time or during a production run, the complex
interaction flow among agents must be broken down into the IP of each individual
agents compatibly and repeatedly.
In particular, this task is impractical when there are many related agents or
when the problem solving procedure is very complex. At the same tune, verifying
whether or not the IPs of the agents are compatible becomes more difficult.
That is, the prior art attempted to achieve two objects at the same time: to
process the difference in the interface formats which vary each constituent element
just as dialects vary from district to district and to coordinate the interaction
among individual constituent elements. This makes it difficult to develop the IP efficiently.
SUMMARY OF THE INVENTION
The present invention has been proposed in order to solving the problems of the
related art described above. The first object of the present invention is to achieve
an improved technique for distributed processing with regard to a constraint satisfaction
problem. In other words, it is an object of the invention to cause an agent to
mediate cooperation among a plurality of applications such as schedulers, thereby
proceeding the whole processing smoothly, facilitating utilization of the existing
applications and addition and change of cooperation protocols, avoiding concentration
of processes and communications and reducing the range that is affected when a
partial fault has occurred, and realizing flexible processing and improving search
efficiency and quality of the solution.
The second object of the present invention is to provide a technique that can
enhance flexible bonding of a plurality of the existing systems such as legacy
systems and package software, by making use of a mediation agent.
The above-described problems in the prior art are solved by an improvement in
information processing technology according to the present invention. In order
to perform problem solving with regard to a given target, there are provided information
processing systems and methods that mediate coordination among processing units
by making use of at least one agent. In one aspect of the present invention, there
is provided an information processing system comprising a plurality of processing
units that form a distributed system and a means for generating at least one agent.
Each processing unit has a first storage area storing target knowledge with regard
to the target and problem solving knowledge representing how the problem solving
is to be performed, and performs a part of the problem solving by making use of
the target knowledge and the problem solving knowledge. Each generated agent has
a second storage area storing cooperation problem solving knowledge that represents
how the plurality of units cooperate with each other to perform the problem solving,
and mediates cooperation among the units by making use of the cooperation problem
solving knowledge to cause each unit to perform the problem solving.
According to this information processing system, by causing the agent to
mediate cooperation among the plurality of processing units, an exchange among
processing units and management of the whole processing are realized, resulting
in that it is unnecessary to give a high degree of autonomy such as a complicated
cooperation protocol for each processing unit. Therefore, a plurality of processing
units such as existing schedulers that are used individually, can be used as bases
to be combined with each other, resulting in easy construction of systems such
as distributed and cooperative type of scheduling systems.
Since a cooperation protocol is encapsulated in an agent, it is easy to add
and change protocols. Concretely, it is supposed that constraint satisfaction algorithms
and the like, which are most suitable to dissolve various type of constraints,
are installed as cooperation protocols, and selectively used according to purposes
and situations.
By building various cooperation protocols into each of the mobile agents respectively,
and selectively using them according to situations, it is possible to dynamically
add a new cooperation function to the individual schedulers. This means that it
is possible to hide a cooperation protocol among schedulers, facilitating the use
of a new protocol without restriction by an existing protocol.
Further, in this information processing system, desirably, each processing
unit performs a process for problem solving and, when it is necessary to cooperate
with another processing unit, generates an agent to execute a cooperation protocol
among said processing units. In this case, since the application generates an agent
as the need arises to allow a desired protocol to be used, an improvement inflexibility
of operation is achieved.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a conceptual view that shows the first embodiment of the present invention.
FIG. 2 is a conceptual view that shows a state of causing a mobile agent to
mediate cooperation among schedulers S in the first embodiment of the present invention.
FIG. 3 is a functional block diagram that shows the configuration of the first
configuration of the present invention.
FIG. 4 is a functional block diagram that shows concretely the configuration
of the mobile agent in the first configuration of the present invention.
FIG. 5 is a flowchart that shows a general processing procedure in the first
configuration of the present invention.
FIG. 6 is a flowchart that shows a cooperation protocol in the first embodiment
of the present invention.
FIG. 7 is a graph that shows a result of an experiment 1 in an example,
to which the first embodiment of the present invention is applied.
FIG. 8 is a graph that shows a result of an experiment 2 in an example,
to which the first embodiment of the present invention is applied.
FIG. 9 is a conceptual view that shows an example of the configuration of the
second embodiment of the present invention.
FIG. 10 is a block diagram that shows the configuration of the second embodiment
of the present invention.
FIG. 11 is a conceptual view that shows an example of IP, which is under modeling
as a type of state transition diagram.
FIG. 12 is a conceptual view that shows an example of with regard to IPs associated
with problem solving procedure, how they are unified.
FIG. 13 is a explanatory drawing that illustrates exemplarily a form of message
which is exchanged between a mediation agent and a wrapper.
FIG. 14 is a flowchart that shows an example of a processing procedure in the
second embodiment of the present invention.
FIG. 15 is a conceptual view that shows a state of concentrating conversations
among constituent elements included in a distributed system in the second embodiment
of the present invention.
FIG. 16 is a conceptual view that shows a structure of architecture levels in
an example of the present invention.
FIG. 17 is a conceptual view that shows an example of the present invention.
FIG. 18 is a conceptual view that shows IPs added to each other, which are distributed
to every constituent element in the prior art (before change of algorithm).
FIG. 19 is a conceptual view that shows IPs added to each other, which are distributed
to every constituent element in the prior art (after change of algorithm).
FIG. 20 is a conceptual view that shows IPs unified with regard to problem solving
procedure in an example of the present invention (before change of algorithm).
FIG. 21 is a conceptual view that shows IPs unified with regard to problem solving
procedure in an example of the present invention (after change of algorithm).
FIG. 22 is a conceptual view that shows an example that a single problem solver
performs intensively processing as an example of the prior art.
FIG. 23 is a conceptual view that shows an example that objects exchange directly
each other.
FIG. 24 is a conceptual view that shows, as an example of the prior art, a direct
negotiation model.
FIG. 25 is a conceptual view that shows, as an example of the prior art, an
example that an agent negotiates directly.
FIG. 26 is a conceptual view that shows a client server model being an architecture
of the prior distributed system.
FIG. 27 is a distributed object model being an architecture of the prior distributed system.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
Embodiments of the present invention are described below, with references
made to relevant accompanying drawings. The present invention is generally implemented
by a computer that has peripheral devices and software that controls the computer,
in which case the software is a combination of instructions that follow the description
of the present invention in this document, parts of the invention that are from
the prior art making use of prior art methods that were described in the foregoing
section on background art. This software is not limited to program code, and includes
data that is prepared for use at the time the program code is executed.
The software implements the technique of the present invention by using physical
resources which may include a processing unit such as a CPU, a coprocessor, or
a chip set, an input device such as a keyboard or a mouse, a storage device such
as a memory or a hard disk drive, and output devices such as a display or a printer.
It should be noted that various configurations of specific software and hardware
can be used to implement the present invention. For example, the software can be
in various forms, such as a compiler, an interpreter, or an assembler and, it is
possible to perform communication externally by means of a removable storage medium
such as a floppy disk, or a network connection unit. A storage medium such as a
CD-ROM onto which is stored a program or software for implementing the present
invention alone forms one aspect of the present invention. Additionally, part of
the functions of the present invention can be implemented in a physical electronic
circuit, such as an LSI device.
As described above, because there are various methods that can be envisioned
for
implementing this present invention using a computer, virtual circuit blocks that
implement the individual functions of the present invention and the embodiments
thereof will be used to describe the present invention and embodiments thereof below.
101. First Embodiment
(1. Configuration)
(1-1. General Configuration)
First, FIG. 1 is a conceptual view which shows a support system for planning
of power cut for work of electric power system facilities, this support system
providing support for the generation of a power cut plan for work of electric power
system facilities, and this support system being an embodiment of distributed processing
technology related to constraint satisfaction problem. Specifically, this embodiment
has a plurality of schedulers S (corresponding to the above-noted applications)
which correspond to various stations in the electric power system, and mobile agents
MA, which mediate cooperation between the various schedulers.
In the above configuration, each of the schedulers S is formed by the addition
of a wrapper for the purpose of connection to a mobile agent, added to an existing
scheduling system that is used alone, and it is possible for the existing applications
to be selected freely from package software and the like. In this embodiment the
user, if required with respect to the individual schedulers, performs input of
various scheduling data that is used in scheduling, such as the details of the
facilities for each individual station in the electric power system.
In this embodiment, various facilities (such as main lines, transmission lines,
generators, and transformers) that exist within the electrical power system, which
is distributed among the various stations, serve as the "targets" as noted above,
the above-noted "problem solving" being the generation of a power cut plan as a
time schedule for suspending the transmission of power for the purpose of performing
maintenance, replacement, and additions with regard to the facilities.
Further, in this embodiment, as shown in the conceptual view presented in
FIG. 2, when any of the each of the schedulers S is required to cooperate by, for
example, using target knowledge and methods held by another scheduler, it does
not perform direct negotiation with or sending of a message to the other schedulers,
but rather makes use of mediation of a mobile agent, the other scheduler S with
which cooperation is to be performed, based on this mediation, responding by establishing,
in accordance with the generation of its own power cut plan, what type of method
is to be used, and what type of target knowledge is to have the values of its variables changed.
(1-2. Configuration of the Scheduler and the Mobile Agent)
The general configuration of the schedulers S that are connected to the computer
network N and the mobile agents MA that migrate about the network N will be described
below, with reference being made to FIG. 3. In this embodiment, if a scheduler
S is required to cooperate with another scheduler S, a request such as a system
call is output to software for implementing this embodiment, a mobile agent that
performs mediation of cooperation being generated in response to this type of request.
Each of the schedulers S, as shown in FIG. 3, has a communication section S
1
for the purpose of performing communication with a mobile agent via the network
N, a target knowledge storage section S
2, a target knowledge management
section S
3, a problem-solving knowledge storage section S
4, and a
problem solving knowledge management section S
6.
Of the above elements of the scheduler S, the communication section S
1
is a simple driver that has the minimal required configuration for making connection
to a mobile agent MA that has migrated thereto and for performing data transfer
with the mobile agent. The communication section SI has no particular complex message
routing function or cooperation protocol for the purpose of transfer of messages
with another scheduler. The target knowledge storage section S
2 stores knowledge
with regard to the configuration of electrical power system facilities, which are
the target, this being the target knowledge. The target knowledge management section
S
3 performs access management of reading and updating with respect to the
above-noted target knowledge.
The problem-solving knowledge storage section S
4 stores problem-solving
knowledge which represents what problem solving is to be done, this problem solving
knowledge being chiefly processing procedures for the purpose of generating a partial
power cut plan for individual stations. The problem-solving knowledge management
section S
6 manages access, for example, reading of the problem-solving knowledge
which, in this case, also serves to perform processing for problem solving, that
is, which also serves to use target knowledge and problem-solving knowledge to
generate a partial power cut plan as described above.
The mobile agent MA serves to mediate cooperation between each application, by
executing a cooperation protocol, this mobile agent MA having a communication section
M
1, a cooperation problem-solving knowledge storage section M
2, a
cooperation problem-solving knowledge management section M
3,and a network
migration section M
6.
Of the above-noted elements, the communication section M
1 communicates
with each of the schedulers S. The cooperation problem-solving knowledge storage
section M
2 stores cooperation problem-solving knowledge that represents
what kind of cooperation is to be performed in order to generate an overall electrical
system power cut plan. The cooperation problem-solving knowledge management section
M
3 manages access, for example, reading of solving-solving knowledge described
above which, in this case, also serves to mediate cooperation between a plurality
of schedulers S, by executing a cooperation protocol in accordance with the problem-solving knowledge.
That is, in a mobile agent MA, the above-noted cooperation problem solving knowledge
storage section M
2, cooperation problem-solving knowledge management section
M
3, and network migration section M
6 implement a cooperation protocol,
and in doing so cooperation is performed between schedulers. FIG. 4 shows a specific
configuration of a mobile agent MA, viewed as a virtual circuit block for implementing
this type of cooperation.
(1-3. Specific Mobile Agent Configuration)
A power cut plan for work of electric power system facilities, which is a constraint
satisfaction problem in this embodiment of the present invention, is described
below, with the premise that the configuration is that shown in FIG. 4. Specifically,
the power cut plan for work of electric power system facilities describes what
facilities at what station are to be suspended and during which periods, and is
generated by assigning values to variables that represent, for example, the facilities
or power cut periods, these values representing, for example, the facilities ID,
and power cut dates and time. Each of the schedulers S that are in charge of the
stations has a plurality of such variables, some of these variables being subject
to constraints with respect to variables of other schedulers S, and some of these
variables having no constraints with respect to variables of other schedulers S.
The generation of a power cut plan for work of electric power system facilities
is directed to ultimate obtainment of the solution of the problem by the assignment
of values to these variable that do not violate the constraints that are established
between variables. For this reason, each of the schedulers S is minimally configured
so as to assign values to variables that are not subject to constraints between
variables of other schedulers S. With regard to variables that are subject to constraints
with respect to the variables of other schedulers, if necessary, mobile agent MA
mediation is done to assign values by performing cooperation so as to adjust the
values of variables with respect to other schedulers.
In order to mediate such cooperation, a mobile agent MA has a migration section
3, an end judgement section
4, a constraint acquisition section
5,
a constraint dissolution section
6, a backtracking control section
8,
a clone processing section
9, a merge processing section
10, and
a generation/disappearance section
11. Of these elements, the migration
section
3 causes migration of a mobile agent MA on the network N as shown
in FIG. 3, thereby causing cycling around the network N, and how a mobile agent
MA is to be cycled around the network is stored as a cyclic list
2, this
cyclic list
2 being updated in response to the progress situation of the
cooperation protocol.
The end judgement section
4 makes a judgment about the end condition of
the cooperation protocol. For example, in the case in which a mobile agent MA is
generated by a request from a scheduler S and this mobile agent completes execution
of the required cooperation protocol, this mobile agent independently disappears
or is brought into disappearance by notification to the system from the scheduler
S that issued the request.
The constraint acquisition section
5 receives a constraint that straddles
a variable of a plurality of schedulers S or a variable of each individual schedulers
S, a constraint
1 that is received in this manner being stored within the
mobile agent MA.
The constraint dissolution section
6 generates a partial solution by assigning
values to variables so that constraints are satisfied, after which it further assigns
values to variables to extend the partial solution, in a manner that does not violate
the partial solution that had been generated up until that point.
(1-4. Configuration Related to Backtracking Control)
In this manner, by the constraint dissolution section
6 assigning values
sequentially to variables as the mobile agent cycles around the schedulers S, overall
power cut plan for work of electric power system facilities approaches completion.
Each time a partial solution is extended by assigning a new variable value, the
immediately previous partial solution is stored within the mobile agent MA as the
original state
7. The original state
7 can also, for example, be
stored in a stationary agent.
In the case in which search space for a solution to a constraint satisfaction
problem is of a tree structure, the new assignment of a value to a variable is
equivalent to proceeding to the next branch in the tree. In correspondence with
this, this original state
7 is stored in a stack, so that each time a variable
value is stored, the old partial solution is pushed onto the stack, and when it
is not possible to assign a value to a variable, the original state
7 is
popped from the stack, this representing a return to the previous branch point
in the tree, which represents a back-track.
That is, when there is a plurality of options for assigning a value to a variable,
the backtracking control section
11 serves to generate a mobile agent that
corresponds to each of the options. The judgment as to what type of agents MA
2
are to be generated in the case of what type of options, and in what cases what
type of agent MA is to disappear and how it is to disappear, this representing
the algorithm for a search of the solution, is performed by the done processing
section
9 and the merge processing section
10.
(1-5. Clone Processing Section)
Specifically, when there are a plurality of values that can be assigned
to a variable, so that there is a plurality of strategies for selecting values
to be assigned to a variable in accordance with some criterion, the clone processing
section
9 issues an instruction to the generation/disappearance section
11, so as to generate a mobile agent MA that corresponds to each of the
strategies. In this case, each of the mobile agents MA that correspond to the strategies
search for a solution by assigning values to variables in a mutually independent
manner, in accordance with its strategy.
In this embodiment, when one solution is obtained of the mobile agents MA the
clone processing section
9 and the sequence determining section
11,
in response to the state, either bring each of the other mobile agents into disappearance
corresponding to other strategies, or keep the series of mobile agents without
disappearance until a solution is found by all mobile agents MA, these also serving
to select the best of the mobile agents MA that correspond to each of the strategies,
based on a pre-established criterion.
(1-6. Merge Processing Section)
The merge processing section
10, when there is a plurality of schedulers
S that have approximately the same priority with regard to the sequence of establishing
values, issues an instruction to the generation/disappearance section
11,
thereby causing the generation of other mobile agents MA that correspond to each
of the variables. In this case, each of the mobile agents that correspond to v
