Information processing system and method for same

• US 6,529,934 B1
• Filed: 05/06/1999
• Issued: 03/04/2003
• Est. Priority Date: 05/06/1998
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Kawamura, Takahiro, Ohsuga, Akihiko, Hasegawa, Tetsuo, Tahara, Yasuyuki, Kase, Naoki
• Primary Examiner(s): Follansbee, John A.
• Application Number:
  US09/305,753
• Time in Patent Office: 1,398 Days
• Field of Search: 709/100, 709/202, 709/102
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4875 with migration policy, e.g. auction, contract negotiation
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

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.

Claims

1. An information processing system which performs problem solving with regard to a given target, comprising:

a plurality of processing units that form a distributed system, each processing unit having a first storage area storing target knowledge with regard to said target and problem solving knowledge representing how said problem solving is to be performed, wherein said each processing unit performs a part of said problem solving by making use of said target knowledge and said problem solving knowledge;

at least one mobile agent that migrates among said plurality of processing units, said mobile agent having a second storage area storing cooperation problem solving knowledge that represents how said plurality of processing units cooperate with each other to perform said problem solving, said mobile agent mediating cooperation among said processing units by making use of said cooperation problem solving knowledge to cause said each processing unit to perform said problem solving; and

means for diminishing said mobile agent when said mobile agent completes cooperation among said processing units.

2. The information processing system according to claim 1, wherein said each processing unit comprises first communication means for communicating with said mobile agent in a predetermined format.

3. The information processing system according to claim 2, wherein said mobile agent comprises:

second communication means for communicating with said each processing unit in said format;

coordination means for performing coordination among said processing units.

4. The information processing system according to claim 3, wherein at least one of said processing units comprises second coordination means for performing coordination of each processing unit.

5. The information processing system according to claim 3, wherein said coordination means comprises:

protocol management means for managing an interaction protocol that performs coordination among each processing unit;

status management means for performing said coordination by managing status of said information processing based on said interaction protocol.

6. The information processing system according to claim 2, wherein said each processing unit exists on a plurality of nodes, respectively, and wherein said mobile agent has the among said nodes.

7. An information processing system which performs problem solving with regard to a given target, comprising:

a plurality of processing units that form a distributed system, each processing unit having a first storage area storing target knowledge with regard to said target and problem solving knowledge representing how said problem solving is to be performed, wherein said each processing unit performs a part of said problem solving by making use of said target knowledge and said problem solving knowledge; and

at least one agent having a second storage area storing cooperation problem solving knowledge that represents how said plurality of processing units cooperate with each other to perform said problem solving, said agent mediating cooperation among said processing units by making use of said cooperation problem solving knowledge to cause said each processing unit to perform said problem solving,

wherein 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 each agent corresponds to a respective one of a plurality of alternatives with regard to the assignment of values for the variables, and wherein said each agent corresponding to the respective alternative executes a cooperation protocol among said each scheduler independently of the other agents and according to the respective alternative.

8. An information processing system which performs problem solving with regard to a given target, comprising:

a plurality of processing units that form a distributed system, each processing unit having a first storage area storing target knowledge with regard to said target and problem solving knowledge representing how said problem solving is to be performed, wherein said each processing unit performs a part of said problem solving by making use of said target knowledge and said problem solving knowledge; and

at least one agent having a second storage area storing cooperation problem solving knowledge that represents how said plurality of processing units cooperate with each other to perform said problem solving, said agent mediating cooperation among said processing units by making use of said cooperation problem solving knowledge to cause said each processing unit to perform said problem solving,

wherein 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 each agent corresponds to a respective one of a plurality of strategies if they exist as a plurality of strategies of what criterion is used for selection of a value to be assigned, and wherein said each agent corresponding to the respective strategy performs a search of a solution by assigning values for the valuables independently of the other agents, at the same time, and according to the respective strategy.

9. An information processing system which performs problem solving with regard to a given target, comprising:

a plurality of processing units that form a distributed system, each processing unit having a first storage area storing target knowledge with regard to said target and problem solving knowledge representing how said problem solving is to be performed, wherein said each processing unit performs a part of said problem solving by making use of said target knowledge and said problem solving knowledge; and

at least one agent having a second storage area storing cooperation problem solving knowledge that represents how said plurality of processing units cooperate with each other to perform said problem solving, said agent mediating cooperation among said processing units by making use of said cooperation problem solving knowledge to cause said each processing unit to perform said problem solving,

wherein 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 each agent corresponds 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 deeded, wherein said each agent corresponding to each variable performs a search of a solution by assigning values for the valuables independently of the other agents and at the same time, and wherein said system 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.

10. An information processing method for performing problem solving with regard to a given target by mating use of a plurality of processing units that form a distributed system and at least one mobile agent that migrates among said plurality of processing units, comprising the steps of:

causing said each processing unit to perform a part of said problem solving by making use of target knowledge with regard to said target and problem solving knowledge that represents how said problem solving is to be performed;

causing said each processing unit to perform said problem solving by causing said mobile agent to mediate cooperation among said processing units by making use of cooperation problem solving knowledge that represents how said plurality of processing units cooperate with each other to perform said problem solving; and

causing said mobile agent to be diminished when said mobile agent completes cooperation among said processing units.

11. The information processing method according to claim 10, further comprising the steps of:

causing said each processing unit to perform a process for said problem solving;

causing said each processing unit to generate a mobile agent when it is necessary to cooperate with another processing unit; and

causing said mobile agent to execute a cooperation protocol among said processing units.

12. The information processing method according to claim 10, further comprising the step of causing said each processing unit to communicate with said mobile agent in a predetermined format.

13. The information processing method according to claim 12, further comprising the steps of:

causing said mobile agent to communicate with said each processing unit in said predetermined format; and

causing said mobile agent to perform coordination among said processing units.

14. A computer-readable storage medium storing a program for performing problem solving by making use of a plurality of processing units that forms a distributed system and at least one mobile agent that migrates among said plurality of processing units, said program comprising:

means for causing a computer to cause each processing unit to perform a process for said problem solving;

means for causing a computer to cause said each processing unit to generate a mobile agent when it is necessary to cooperate with another processing unit; and

means for causing a computer to cause said mobile agent to execute a cooperation protocol among said processing units; and

means for causing a computer to cause said mobile agent to be diminished when said mobile agent completes cooperation among said processing units.

15. A computer-readable storage medium storing a program for performing information processing by making use of a plurality of processing units that forms a distributed system and at least one mobile agent that migrates among said plurality of processing units, said program comprising:

means for causing a computer to set a mobile agent that performs coordination among said processing units;

means for causing a computer to cause each processing unit to communicate with said mobile agent in a predetermined format; and

means for causing a computer to cause said mobile agent to diminish when said mobile agent completes coordination among said processing units.

16. The computer-readable storage medium according to claim 15, said program comprising:

means for causing a computer to cause said mobile agent to communicate with said each processing unit in said format;

means for causing a computer to cause said mobile agent to perform coordination among said processing units.

17. A distributed cooperation system for a plurality of application systems in a network system, wherein each application system comprises:

a first storage which stores a first knowledge representing an object being processed by the application system;

a second storage which stores a second knowledge representing methods for processing by the application system;

a mobile agent having a third storage which stores third knowledge representing cooperation methods with said plurality of application systems, mediation means for mediating cooperation among said application systems using the third knowledge, and migration means for migrating among said application systems; and

means for diminishing said mobile agent when said mobile agent completes cooperation among said application systems.

18. An information processing system which performs problem solving with regard to a given target, comprising:

a plurality of processing units, each processing unit existing logically and physically independent from each other and having a first storage area storing target knowledge with regard to said target and problem solving knowledge that represents how said problem solving is to be performed, wherein said each processing unit performs said problem solving separately and locally by making use of said target knowledge and said problem solving knowledge and processing said target knowledge and said problem solving knowledge independently, said plurality of processing units being connected to each other through a network; and

at least one mobile agent that migrates among said plurality of processing units, said mobile agent existing in the network logically and having a second storage area storing cooperation problem solving knowledge that represents how said plurality of processing units cooperate with each other to perform said problem solving, wherein when it becomes difficult for a first processing unit to perform a specific problem solving separately and locally, said mobile agent mediating cooperation between the first processing unit and a second processing unit necessary for the specific problem solving in said plurality of processing units by making use of said cooperation problem solving knowledge; and

means for diminishing said mobile agent when said mobile agent completes cooperation among said processing units.

19. The method of claim 18, wherein mediating cooperation includes coordinating schedules of the first and second processing units.

20. A method of performing problem solving with regard to a given target by making use of a plurality of processing units and at least one mobile agent in an information processing system, wherein each processing unit exists logically and physically independent from each other and said plurality of processing units are connected to each other through a network, and the mobile agent exists in the network logically and migrates among said plurality of processing units, comprising:

causing said each processing unit to perform said problem solving separately and locally by making use of target knowledge with regard to said target and problem solving knowledge that represents how said problem solving is to be performed;

causing said mobile agent, when it becomes difficult for a first processing unit to perform a specific problem solving separately and locally, to mediate cooperation between the first processing unit and a second processing unit necessary for the specific problem solving in said plurality of processing units by making use of cooperation problem solving knowledge that represents how said plurality of processing units cooperate with each other to perform said problem solving; and

causing said mobile, agent to be diminished when said mobile agent completes cooperation among said processing units.

21. The method of claim 20, wherein mediating cooperation includes coordinating schedules of the first and second processing units.

22. A computer-readable storage medium storing a program for performing problem solving with regard to a given target by making use of a plurality of processing units and at least one mobile agent, wherein each processing unit exists logically and physically independent from each other and said plurality of processing units are connected to each other through a network, and the agent exists in the network logically and migrates among said plurality of processing units, said program comprising:

means for causing a computer to cause said each processing unit to perform said problem solving separately and locally by making use of target knowledge with regard to said target and problem solving knowledge that represents how said problem solving is to be performed;

means for causing a computer to cause a first processing unit of said plurality of processing units to generate a mobile agent when it becomes difficult for the first processing unit to perform a specific problem solving separately;

means for causing a computer to cause the generated mobile agent to mediate cooperation between the first processing unit and a second processing unit necessary for the specific problem solving in said plurality of processing units by making use of cooperation problem solving knowledge that represents how said plurality of processing units cooperate with each other to perform said problem solving; and

means for causing a computer to cause said mobile agent to be diminished when said mobile agent completes cooperation among said processing units.

23. The method of claim 22, wherein mediating cooperation includes coordinating schedules of the first and second processing units.

24. A computer-readable storage medium storing a program for performing problem solving with regard to a given target by making use of a plurality of processing units and at least one mobile agent, wherein each processing unit exists logically and physically independent from each other and said plurality of processing units are connected to each other through a network, and the agent exists in the network logically and migrates among said plurality of processing units, said program comprising:

means for causing a computer to set a mobile agent that performs coordination among said plurality of processing units;

means for causing a computer to cause said each processing unit to communicate with said mobile agent in a predetermined format; and

means for causing a computer to cause said mobile agent to be diminished when said mobile agent completes cooperation among said processing units.

25. The method of claim 24, wherein performing coordination includes coordinating schedules of the first and second processing units.