Systems and methods for distributed fault diagnosis using precompiled finite state automata

• US 6,778,943 B2
• Filed: 08/13/2002
• Issued: 08/17/2004
• Est. Priority Date: 08/13/2002
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Su, Rong, Koutsoukos, Xenofon, Kurien, James A.
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Charioui, Mohamed
• Application Number:
  US10/217,028
• Publication Number:
  US 20040034506A1
• Time in Patent Office: 735 Days
• Field of Search: 702/181-185, 702/187-189, 709/106-108, 709/220, 709/224, 710/15, 710/67, 717/154-159
• US Class Current: 702/183
• CPC Class Codes: G05B 23/0248 Causal models, e.g. fault tree; digraphs; qualitative physics

Abstract

Most model-based diagnostic approaches are at least partially centralized. Routing information to or through a centralized processing unit is vulnerable to failure of the central processing unit and/or of the communication system connecting the central processing unit to the sensor or the local diagnostic subsystems. Centralized schemes also limit the amount of processing to that provided by the single centralized processing unit. The systems and methods according to this invention use local diagnostic subsystems that include finite state automata to model the possible states of local components given local sensor readings and potential inputs from other local diagnostic subsystems. Potential states are found during diagnosis of a local component, give one or more observations of that component. This state information is then distributed to other local diagnostic subsystems. Potential states are then found diagnosis of the local component, given state information provided concerning the states of other components.

Claims

1. A method for determining a global diagnosis of a system that has a plurality of components, each component having an associated local diagnostic subsystem that includes a finite-state automaton that represents that component, the method comprising:

initializing the finite state automata representing the components;

inputting at least one of the local diagnostic subsystems, at least one of a new observation from a sensor associated with the component associated with that local diagnostic subsystem or at least one information constraint received by that local diagnostic subsystem from another local diagnostic subsystem;

determining a set of evolutions of the finite state automaton that are consistent with the received at least one of the new observation or the received at least one information constraint;

outputting the set of evolutions to at least one other one of the plurality of local diagnostic subsystems; and

outputting the set of evolutions from at least one of the plurality of local diagnostic subsystems as the global diagnosis.

2. The method of claim 1, wherein:

inputting at least one of the local diagnostic subsystems, at least one of a new observation from a sensor associated with the component associated with that local diagnostic subsystem or at least one information constraint received by that local diagnostic subsystem from another local diagnostic subsystem comprises determining if a new observation from a sensor associated with the component associated with that local diagnostic subsystem was input;

if a new observation was input, determining a set of evolutions comprising determining the set of evolutions of the finite state automaton that are consistent with the new observation.

3. The method of claim 2, further comprising generating a new sub-language based on the determined observation consistent evolutions.

4. The method of claim 3, wherein outputting the set of evolutions to at least one other one of the plurality of local diagnostic subsystems comprises outputting the new sub language to the at least one other one of the plurality of local diagnostic subsystems.

5. The method of claim 1, wherein:

inputting at least one of the local diagnostic subsystems, at least one of a new observation from a sensor associated with the component associated with that local diagnostic subsystem or at least one information constraint received by that local diagnostic subsystem from another local diagnostic subsystem comprises determining if at least one information constraint received by that local diagnostic subsystem from another local diagnostic subsystem was input;

if at least one information constraint received by that local diagnostic subsystem from another local diagnostic subsystem was input, determining a set of evolutions comprising determining the set of evolutions of the finite state automaton that are consistent with the at least one information constraint received by that local diagnostic subsystem from another local diagnostic subsystem.

6. The method of claim 5, further comprising generating a new sub-language based on the determined information constraint consistent evolutions.

7. The method of claim 6, wherein outputting the set of evolutions to at least one other one of the plurality of local diagnostic subsystems comprises outputting the new sub language to the at least one other one of the plurality of local diagnostic subsystems.

8. The method of claim 1, further comprising waiting a predetermined period of time after one of the plurality of local diagnostic subsystems receives at least one information constraint from at least one other local diagnostic subsystem before outputting the global diagnosis.

9. The method of claim 8, further comprising:

determining, for at least one of the plurality of local diagnostic subsystems, whether that local diagnostic subsystem has received at least one information constraint from at least one other local diagnostic subsystem within the predetermined time; and

if that local diagnostic subsystem has received at least one information constraint from at least one other local diagnostic subsystem within the predetermined time, resetting the predetermined time to be measured from about the time that that local diagnostic subsystem received at least one information constraint from at least one other local diagnostic subsystem.

10. A method for using a local diagnostic subsystem to determine a local diagnosis of a component of a system, the local diagnostic subsystem including a finite state automaton representing the component, the method comprising:

initializing the finite state automaton representing the component;

inputting at least one of a new observation from a sensor associated with the component or at least one information constraint received from another local diagnostic subsystem;

determining a set of evolutions of the finite state automaton that are consistent with the received at least one of the new observation or the received at least one information constraint; and

determining a local diagnosis of the component based on the set of evolutions.

11. The method of claim 10, further comprising outputting the set of evolutions to at least one other local diagnostic subsystem, each other local diagnostic subsystem including a finite state automaton representing an other component of the system.

12. The method of claim 11, further comprising determining a set of the at least one other local diagnostic subsystem to which the set of evolutions is to be output.