Systems and methods for distributed algorithm for optimization-based diagnosis

• US 6,687,653 B1
• Filed: 08/13/2002
• Issued: 02/03/2004
• Est. Priority Date: 08/13/2002
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Zhao, Feng, Koutsoukos, Xenofon, Kurien, James A.
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Charioui, Mohamed
• Application Number:
  US10/217,026
• Time in Patent Office: 539 Days
• Field of Search: 702/113-115, 702/122, 702/179, 702/181-188, 702/FOR.103, 702/FOR.104, 702/FOR.111, 702/FOR.123, 702/FOR.124, 702/FOR.133, 702/FOR.134, 702/FOR.135, 702/FOR.139, 702/FOR.170, 702/FOR.171, 700/26-28, 700/213-244, 340/540, 340/531, 340/539.14, 375/224, 375/227, 375/260, 714/25-31
• US Class Current: 702/183
• CPC Class Codes: G05B 23/0213 Modular or universal configuration of the monitoring system, e.g. monitoring system having modules that may be combined to build monitoring program; monitoring system that can be applied to legacy systems; adaptable monitoring system; using different communication protocols
• CPC Class Codes: G05B 23/0251 Abstraction hierarchy, e.g. "complex systems", i.e. system is divided in subsystems, subsystems are monitored and results are combined to decide on status of whole system
• CPC Class Codes: G05B 23/0294 Optimizing process, e.g. process efficiency, product quality
• 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

Abstract

A system for the distributed diagnosis of a physical system includes serveral local diagnostic subsystems that generate local diagnoses based on observations of a component of the physical system. An interface is defined by which the local diagnostic subsystems communicate. Further, an algorithm for assembling a global diagnosis from the local diagnoses is fined.

Claims

1. A local diagnostic subsystem usable to diagnose a component of a physical system, comprising:

at least one observation variable, each observation variable storing a physical value received from a sensor monitoring a first component that describes a state of the first component;

at least one assumption variable, each assumption variable storing a value representing an assumption about the state of the first component;

at least one dependent variable, each dependent variable storing a value representing a quantity relating one of the at least one observation variable to one of the at least one assumption variable;

a plurality of constraints, each constraint relating two of the at least one observation variable, the at least one assumption variable and the at least one dependent variable to describe a behavior of the component; and

at least one diagnosis variable relating a local diagnosis of the local diagnostic subsystem to a second local diagnosis of a second local diagnostic subsystem.

2. The local diagnostic subsystem of claim 1, wherein the one or more variables comprise at least one of at least one local pseudo-assumption variable that corresponds to a pseudo-assumption variable of the second local diagnostic subsystem, and at least one local pseudo-observation variable that corresponds to a pseudo-assumption variable of the second local diagnostic subsystem.

3. A diagnostic system usable to diagnose a component of a physical system, comprising:

an initialization circuit, routine or application that initializes the diagnosis system to an initial diagnosis;

a local diagnosis circuit, routine or application that generates one or more candidate local diagnoses based on a physical value received from a sensor monitoring the component, the physical value describing a state of the component;

a diagnosis management circuit, routine or application that selects a local diagnosis from among the one or more candidate local diagnoses; and

a remote diagnosis management circuit, routine or application that communicates with a second diagnostic system, wherein zero, one or more of the candidate local diagnoses are based in part on a second local diagnosis generated by the second diagnostic system.

4. A method for diagnosing a physical system, the system comprising a plurality of physical components being diagnosed by a plurality of local diagnostic subsystems, the method comprising:

initializing a first local diagnostic subsystem to an initial diagnosis;

assigning an observation value to an observation variable of the first local diagnostic subsystem, wherein the observation value corresponds to a physical value received from a sensor monitoring a first component and describing a state of the first component;

performing a first local diagnosis in the first local diagnostic subsystem to determine a minimal cost diagnosis explaining the observation value;

determining whether the lowest cost diagnosis requires a change in the value of a pseudo-assumption variable of the first local diagnostic subsystem to a desired value;

performing a second local diagnosis in the first local diagnostic subsystem in which the value of the pseudo-assumption variable is held constant to determine a maximum cost;

supplying a desired value and the determined maximum cost to a second local diagnostic subsystem where the second local diagnostic subsystem contains a pseudo-observation variable corresponding to the pseudo-assumption variable of the first local diagnostic subsystem;

performing a third local diagnosis in the second local diagnostic subsystem to determine whether a diagnosis in which the pseudo-observation variable is set to the desired value can be performed for a cost less than the maximum cost;

adopting the first local diagnosis in the first local diagnostic subsystem when the third local diagnosis can not be performed for a cost less than the maximum cost; and

adopting the second local diagnosis in the first local diagnostic subsystem when the third local diagnosis can be performed for a cost less than the maximum cost.