Semantic error diagnostic process for multi-agent systems

• US 6,550,024 B1
• Filed: 02/03/2000
• Issued: 04/15/2003
• Est. Priority Date: 02/03/2000
• Status: Expired due to Term

• Current Assignee: Mitel Cloud Services, Inc. (MLN TopCo Ltd.)
• Original Assignee: Zarlink Semiconductor Inc. (Microchip Technology Incorporated)
• Inventors: Choi, Daniel, Gray, Tom, Manvoksi, Serge, Pagurek, Bernard
• Primary Examiner(s): Beausoliel, Robert
• Assistant Examiner(s): CHU, GABRIEL L
• Application Number:
  US09/497,305
• Time in Patent Office: 1,167 Days
• Field of Search: 714/2, 714/3, 714/4, 714/25, 714/31, 714/37, 714/38, 714/47
• US Class Current: 714/47.2
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards

Abstract

A method and apparatus for automatically locating sources of semantic error in a multi-agent system based on setup connection tree information, and informing the appropriate agents so that they can avoid using the faulty resources in the future. The setup connection tree model is established based on patterns of agent actions for expressing the logical relationship between available resources in the disjunctive normal form (d.n.f.). A table is used to record different sets of resources for use in the resource selection process. Thus, faulty resources can be located by means of induction. A global database is also maintained for updating information on semantic errors in the system.

Claims

1. Apparatus for automatically locating sources of semantic error in a multi-agent system having an application agent with a head portion and a body portion for initiating an application in response to a service request and one or more underlying agents and resources for implementing said application, comprising:

a temporary database in the head portion of said application agent for storing diagnostic information; and

a plurality of rule-based expert system scripts in the head portion of said application agent for receiving said service request and in response assigning an identity value to said application, retrieving diagnostic information from said temporary database for indicating whether said application as identified by said identity value has previously encountered a semantic error, and

I) in the event said diagnostic information indicates that said application has not previously encountered any said semantic error, then

a) issuing a job request via the body portion of said application agent to said underlying agents and resources along with said identity value and diagnostic information indicating that said application has not previously encountered any said semantic error, whereupon said underlying agents and resources return simplified setup connection tree information for said application as identified by said identity value, and

b) initiating performance tests via the body portion of said application agent on said underlying agents and resources for detecting any said semantic error, and

i) in the absence of detection of any said semantic error then updating said temporary database to indicate that said application as identified by said identity value has resulted in said absence of detection of said semantic error, and

ii) in the event of detection of said semantic error then analyzing said simplified setup connection tree information and said performance tests to identify a predetermined one of said underlying agents and resources responsible for said semantic error and updating said diagnostic information in said temporary database in response thereto, and

II) in the event said diagnostic information indicates that said application has previously encountered said semantic error then issuing said job request to said underlying agents and resources along with said diagnostic information via the body of said application agent whereby selection of said predetermined one or more of said underlying agents and resources responsible for said semantic error is avoided.

2. The apparatus of claim 1, wherein said simplified setup connection tree information further comprises a plurality of expert system facts expressed using only AND and XOR actions and wherein multiple calls to any single agent are indexed by means of a call list for identifying said multiple calls.

3. The apparatus of claim 2, wherein said plurality of rule-based expert system scripts further comprise:

at least one watcher script;

at least one analyzer script; and

at least one modified script;

said watcher script being adapted to receive and parse said service request to verify beliefs of said watcher script and in the event said beliefs of said watcher script are false taking no further action and in the event said watcher script beliefs are true generating said identity value, retrieving said diagnostic information from said temporary database, and generating a request message including said identity value and said diagnostic information to said at least one modified script;

said modified script being adapted to receive and parse said request message to verify beliefs of said modified script and in the event said beliefs of said modified script are false then generating a failure message and in the event said beliefs of said modified script are true then issuing an order including said diagnostic information to the body portion of said application agent, whereupon said body portion either accepts said order or rejects said order;

said watcher script being further adapted to send a further failure message to said modified script in the event that said body portion rejects said order and to initiate said performance tests in the event that said body portion accepts said order whereupon said body portion returns results of said performance tests to said watcher script, and in the event said test results are successful then sending a success notification to said analyzer script and in the event said test results are not successful sending a failure notification to said analyzer script;

said analyzer script being adapted to receive from said underlying agents and resources said simplified setup connection tree information relating to said application as identified by said identity value and for receiving from said watcher script one of either said success notification or said failure notification and in the event of receipt of said success notification then updating said temporary database to indicate that said application as identified by said identity value has resulted in said absence of detection of said semantic error, and in the event of receipt of said failure notification executing an analysis process for analyzing said simplified setup connection tree information and said performance tests to identify said predetermined one of said underlying agents and resources responsible for said semantic error, updating a badlist of faulty agents and resources to include said predetermined one of said underlying agents and resources and then clearing said diagnostic information for said application in said temporary database.

4. The apparatus of claim 3, wherein said analyzer further comprises:

an analysis script for reducing said simplified setup connection tree information to a reduced tree in the form of a logical expression of relationship between said application agent and said resources;

a transformation function for transforming said reduced tree into a transformed list in disjunctive normal form; and

a table generation function for generating a table of sets of selectable ones of said resources arranged in rows, wherein said rows are arranged in an order such that only one different resource appears between two neighboring rows of said table, and storing said table as diagnostic information in said temporary database.

5. The apparatus of claim 4, wherein said diagnostic information is stored in said temporary database in key-value pairs each comprising said identity value as a key and a record object as a value, said record object containing fields for storing said identity value, said simplified setup connection tree information, said table and a table pointer.

6. The apparatus of claim 5, wherein said performance tests each comprise a keyword for identifying test type, a conditional symbol and a threshold numerical value.

7. The apparatus of claim 6, further including a global information database maintained by said analyzer script for storing detailed information concerning semantic errors encountered in said multi-agent system.

8. The apparatus of claim 7, wherein said detailed information is stored in said global information database in key-value pairs each comprising details of each said application, said simplified setup connection tree information, said table, a list of said resources suspected of causing semantic errors and a list of failed ones of said performance tests.

9. The apparatus of claim 8, wherein said diagnostic information includes said badlist, said call list and an information list in the form of one of either a null string value in the event said application has not previously encountered any said semantic error, and a set of said resources selected from said table in the event said application has previously encountered said semantic error.

10. The apparatus of claim 9, wherein said set of said resources is arranged as a plurality of caller-callee pairs wherein each caller comprises said identity value of said application and said callee comprises a further identity value of one of said underlying agents.

11. The apparatus of claim 10, wherein the body portion of said application agent further comprises a tester object for testing quality of service of said underlying agents and resources upon initiation of said performance tests by said watcher script and in response returning said results of said performance tests to said watcher script.

12. The apparatus of claim 11, wherein said body portion further includes a modified broker object for receiving said order including said diagnostic information from said modified script and, in the event said information list contains said null string value, sends said simplified setup connection tree information to said analyzer script, creates said tester object and after said tested object has returned said results of said performance tests to said watcher script destroys said tester object, and in the event said information list does not contain said null string value then selects a healthy one of said resources based on information contained in said information list and said badlist.

13. The system of claim 1, wherein said rule-based expert system scripts are written in Java Expert System Shell.

14. A method for automatically locating sources of semantic error in a multi-agent system having an application agent with a head portion and a body portion for initiating an application in response to a service request and one or more underlying agents and resources for implementing said application, comprising the steps of:

receiving said service request;

assigning an identity value to said application;

retrieving diagnostic information from a temporary database for indicating whether said application as identified by said identity value has previously encountered a semantic error;

I) in the event said diagnostic information indicates that said application has not previously encountered any said semantic error, then

a) issuing a job request via the body portion of said application agent to said underlying agents and resources along with said identity value and diagnostic information indicating that said application has not previously encountered any said semantic error, whereupon said underlying agents and resources return simplified setup connection tree information for said application as identified by said identity value, and

b) initiating performance tests via the body portion of said application agent on said underlying agents and resources for detecting any said semantic error, and

i) in the absence of detection of any said semantic error then updating said temporary database to indicate that said application as identified by said identity value has resulted in said absence of detection of said semantic error, and

ii) in the event of detection of said semantic error then analyzing said simplified setup connection tree information and said performance tests to identify a predetermined one of said underlying agents and resources responsible for said semantic error and updating said diagnostic information in said temporary database in response thereto, and

II) in the event said diagnostic information indicates that said application has previously encountered said semantic error then issuing said job request to said underlying agents and resources along with said diagnostic information via the body of said application agent whereby selection of said predetermined one or more of said underlying agents and resources responsible for said semantic error is avoided.