BACKGROUND OF THE INVENTION

1. Field of the Invention

[0001] This invention relates generally to a diagnostic and prognostic system and method and, more particularly, to a system and method for on-board condition and health monitoring of a vehicle using a multi-dimensional temporal data mining technique.

2. Discussion of the Related Art

[0002] Diagnostic and Prognostic techniques for vehicle state of health monitoring can help forecast the occurrence of a problem in order to take preventive measures before significant damage is done. These techniques become more important for systems where the failure of the system can have critical implications, such as danger to human life. Further, system manufacturers can prevent their customers from being dissatisfied due to the failure of various systems by using diagnostic and prognostic techniques. Previously sold systems by a manufacturer, for example, vehicles produced by an automobile manufacturer, can be monitored through a network, and if any kind of performance degradation is observed, this can be conveyed to the customer before it results in critical damage to the system.

[0003] Efforts have been made in the past to develop diagnostic and prognostic techniques to detect and localize performance degradations in various operating systems. Diagnostic and prognostic techniques are of significant commercial and military interest today, but efforts for their development tend to be ad-hoc, lengthy and expensive. Further, the complexity of the system often restricts realistic physical modeling of the components or interaction between different components or subsystems.

[0004] One existing method based on the principles of diagnosis and prognosis uses temporal data mining. This method has been applied in the telecom industry and in manufacturing facilities. The method, however, only involves mining of data streams that are composed of tokens or logical variables that are uni-dimensional. Since each token represents a single value corresponding to an operating parameter of the system, physical modeling of the interaction between the components becomes difficult and the ability of the method to forecast a failure of a system component is compromised. Further, the application of such a diagnostic and prognostic technique is not known in vehicles.

[0005] As the number of vehicles and their speed increases, there exists a need for better and more efficient safety systems, which will help take failure-preventive measures as soon as any performance degradation in the vehicle is noticed. In addition, the system must be compatible with commercially available, general purpose microprocessors used on vehicles. Further, the system should be provided with enough data points to produce a reliable forecast.

SUMMARY OF THE INVENTION

[0006] In accordance with the teachings of the present invention, a system and method for predicting the occurrence of an event in a vehicle are disclosed. The method includes monitoring a data stream including multi-dimensional tokens having information about one or more vehicle operating parameters. Further, the method includes the identification of a pattern of values of the one or more operating parameters in the data stream by mining the data stream using a temporal data miner, and predicting the occurrence of the event based on the correlation between the detected pattern and a pre-recorded pattern.

[0007] Additional features of the present invention will become apparent from the following description and appended claims, taken in conjunction with the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS

[0008] Figure 1 is a block diagram illustrating a method for predicting the occurrence of an event in a vehicle; and

[0009] Figure 2 is an illustration of an exemplary string of multi-dimensional tokens to be mined by a temporal data miner.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0010] The following discussion of the embodiments of the invention directed to a system and method for on-board condition monitoring of a vehicle using multi-dimensional temporal data mining is merely exemplary in nature, and is in no way intended to limit the invention or its applications or uses.

[0011] The present invention proposes a system and method for exploiting multi-dimensional temporal data mining to detect and localize performance degradations in operating vehicles. Multi-dimensional temporal data mining refers to the capability to detect statistically significant patterns in a serial data stream. It is assumed that the data stream includes tokens or logical values, and could include variables with numeric values or textual values. For purposes of this discussion, it is assumed that any numerical or textual value will be simply represented by a small set of logical values, which characterize the range of the numerical values, for example, low, medium or high pressure, in a context sensitive manner instead of an absolute numeric value with defined units.

[0012] The multi-dimensional aspect refers to the fact that each token can have additional dimensions, or descriptors, recorded with it. For example, one form of added dimensions could be spatial or Cartesian coordinates in the 2-space or 3-space. The spatial coordinates could also refer to electrical connectivity, logical connectivity, or a host of other relevant dimensions of significant to the domain of the application instead of normal geometric relationships. This increases the representational power of the tokens themselves. [0013] A known set of performance degradations could be represented by a set of statistically significant patterns detected by the temporal data miner, which were not present in a reference state of operation.

[0014] Figure 1 is a block diagram 10 illustrating a process for predicting the occurrence of an event in a vehicle. The process begins at box 12 where a data stream or a string composed of multi-dimensional tokens or logical values is monitored. Each multi-dimensional token represents instantaneous values of various operating parameters of a vehicle at a given instance in time. For example, the multi-dimensional tokens can be diagnostic trouble codes (DTC) or events, which are detected on a communication bus of the vehicle. The tokens are said to be multi-dimensional since each token can have values of more than one operating parameter associated with it. The monitored string of multi-dimensional tokens is mined to identify hidden patterns of values at box 14. In an exemplary scenario, a temporal data miner can be used to monitor the string of multi-dimensional tokens and mine it to identify the patterns of values that are hidden. Temporal data mining refers to a technique for discovering hidden patterns in sequences or sub-sequences of events.

[0015] Figure 2 is an illustration of an exemplary string of multi-dimensional tokens to be mined by a data miner. The string 18 is composed of time tagged multidimensional tokens 20, 22, 24, 26 and 28. The multi-dimensional aspect of the tokens is due to the additional information encoded by their various dimensions. For example, token 20 is shown to have dimensions 30, 32 and 34. In an exemplary scenario, the dimensions 30, 32 and 34 can include spatial relations between the values depicted by them. Dimension 30 is shown to capture physical connectivity while the dimensions 32 and 34 capture electrical and logical connectivity, respectively, between the values depicted by the tokens.

[0016] At box 16, the identified pattern of values is correlated or compared with a pre-recorded pattern of values of the same operating parameters. The patterns can be represented as graph structures for efficient processing. The occurrence of an event is forecasted based on the correlation between the two patterns. For example, a pre-recorded pattern can be made of three tokens occurring in the order A followed by B followed by C. If the identified pattern is composed of tokens A followed by B, the occurrence of event C can be predicted with some degree of certainty. Other patterns could be provided, such as A ->• (B and C and D) ->• E, where B, C and D must be detected after the occurrence of A and before the occurrence of E, but the order of occurrence of B, C and D is not important. Further, the time delay between the detection of one token before the occurrence of next token is user selectable. In an exemplary scenario, the identified pattern and the pre-recorded pattern are represented as graphs and are correlated using a fast graph matcher.

[0017] As mentioned above, in an automotive context, the tokens could represent a series of events detected on the vehicle communication bus, such as diagnostic trouble codes, which record that a certain condition is present in the vehicle. The DTCs will be time stamped and captured in the order of occurrence. The string of DTCs would be augmented by other state variables, environmental conditions, performance levels, etc. as determined to be relevant by a subject matter expert. This provides a technique for the subject matter expert to introduce important information into the data mining process in a system that does not require creation of complex models of the systems being monitored. Thus, the process seeks to efficiently utilize the subject matter expert's knowledge in an efficient matter.

[0018] If the forecasted event is indicative of an impending failure of a component, the vehicle driver is warned about the event. In one embodiment, the warning signal is conveyed to the driver through the communication bus of the vehicle. In another embodiment, the performance of the vehicle can be monitored through a centralized network, for example, the OnStar™ network. If any degradation in the performance of a component of the vehicle is observed, the network communicates it and its implications to the driver. However, it will be readily apparent to any person with ordinary skill in the art that the driver of the vehicle can be warned by methods other than those discussed in the embodiments given above.

[0019] The pre-recorded patterns are composed of values of operating parameters obtained when the performance of the vehicle is degraded. These patterns are recorded during a training phase, while the correlation between the identified pattern and the pre-recorded pattern is established during a real time execution phase, that is, on-board a running vehicle. The training phase and the execution phase are explained below.

[0020] During the training phase, a representative string of tokens for every known normal mode of operation is captured. The data recorded during each mode is assumed to be relatively stationary, that is, the patterns of operation would be present throughout the recording. These data-sets are then mined to detect all multidimensional temporal data patterns present in the normal mode of operation. Each of the mined patterns is represented as a graph structure and stored for future use and the patterns together represent the normal mode.

[0021] In the next part of the training, data streams corresponding to a degraded modes of operation of the system are captured. The performance of the system can be considered degraded based on the specifications by a subject matter expert. The data-sets corresponding to each level of performance degradation are captured in a manner similar to the one used for the normal mode. The degradations chosen by a subject matter expert are chosen in such a way that they represent performance reductions of some important and critical type, such as a reduction in the braking ability from the vehicle operational point of view. Each level of performance degradation is accomplished by tapping the subject matter expert's knowledge to determine the components that fail or degrade during actual usage. The end result is a set of data streams that characterizes known levels of performance degradation with a known cause.

[0022] The next step of training involves removal of the normal mode patterns (or graphs) from the patterns corresponding to the degraded mode of operation of the system to capture the new patterns or those which detect the trained degradation. Similarly, patterns that occur in multiple types of failure or degradation, and which, therefore, cannot be used to discriminate between problems, may also be removed.

[0023] For best performance, the subject matter expert filters the final set of patterns manually to eliminate those believed to be inappropriate. For example, a physical interpretation of the logical sequence might suggest something that is already understood and is not deemed relevant by the subject matter expert. Filtering could be manual or algorithmic (semi-automatic) in nature, and based on general rules from the subject matter expert.

[0024] During the real time execution phase, the fast graph matcher can be used to look for the occurrence of patterns associated with some form of failure or degradation, as identified during the training phase. As each node of the pattern is detected, the fast graph matcher continues to monitor the next node until the delay exceeds the allowable limit. Multiple instantiations of the same pattern could be in the process of detection at the same time to ensure that one instantiation did not time out while an identical pattern starting later in time is still being tracked. The run-time detection of patterns corresponding to the degraded mode of operation of the system is taken as a warning that the given degradation may be present in the running vehicle. The driver of the vehicle is warned about it, so that an impending failure or a severe loss of performance is prevented.

[0025] Various embodiments of the present invention offer one or more advantages. The present invention provides a method and system for predicting the occurrence of an event in a system, for example, a vehicle. The present invention serves to monitor the condition of the vehicle while it is in operation, and facilitates taking failure preventive measures as soon as some kind of performance degradation is observed. Further, the invention uses multi-dimensional temporal data mining to forecast the occurrence of an event, which makes the forecast reliable and easy.

[0026] The foregoing discussion discloses and describes merely exemplary embodiments of the present invention. One skilled in the art will readily recognize from such discussion and from the accompanying drawings and claims that various changes, modifications and variations can be made therein without departing from the spirit and scope of the invention as defined in the following claims.