METHOD OF QUALITY ANOMALIES DETECTION IN INTERACTIVE ELECTRONIC TECHNICAL MANUALS FOR AIRCRAFT MAINTENANCE AND REPAIR

Full Text

Introduction. The purpose of quality assessment of IETM for aviation technology is to come to a general conclusion on the obtained degree of meeting the de- mands for interactive electronic technical manuals within the context of unclear initial expert data used for evalua- tion [1-5]. Assessment of quality of IETM for aircraft maintenance and repair means stating their compliance with the requirements of the already existing database of that quality indications. The proposed method of detecting quality anomalies of the IETM in question is a combination of corresponding logical-mathematical model of such anomalies, developed for application to the subject content logic circuits (SCLC) [6; 7] and the algorithm of its performance in the technological process of designing interactive electronic manuals. Anomaly representation by a graph isomorphically nested in SCLC configuration of IETM. The scientific and methodological concept of quality management of IETM for aircraft maintenance and repair implies that quality improvement of software technology for the spe- cific electronic manuals is achieved by applying available qualimetric toolkits for software and information products [8; 9]. Particular attention is paid to quality improvement of IETM content, the factual material describing the sub- ject area of maintenance and repair of specific aircraft models [10-12]. In turn, the SCLC method that provides the sufficient quality level for IETM design offers the developers a means specially focused on IETM for air- craft maintenance and repair content quality [13]. How- ever, designing electronic content for IETM with the use of SCLC does not guarantee the absence of its quality anomalies. If the method of multi-level quality assessment of IETM for aircraft shows a low level of quality achieved in the design process, it will be necessary to improve this quality. Thus, there appears the problem of anomalies detection in the electronic content of the evaluated IETM. It is for solving this problem that the method of quality anomalies detection of IETM for aircraft maintenance and repair is aimed at. These IETM were originally developed on the basis of the corresponding SCLC. The model of quality anomalies of IETM provides the analysis of the SCLC configuration as some basic graph and regards the anomaly as a more specific graph [13]. The specific graph is a graphical description of various partial distortions of the logic presented in the form of SCLC. There is quite a number of typical logic distortions in the design of IETM electronic content, in the sequence of frame appearance, etc. The most common examples are logical ring, transitive closure, non-specified fact (condi- tion execution failure). In other words, the SCLS structure is regarded as a basic graph, within which a subgraph isomorphic to the given one is determined. Here graph isomorphism is understood as equivalence ratio for a set of graphs [14; 15]. The graph, to which the subgraph within the basic graph that displays SCLC configuration relates as isomorphic, graphically specifies the corre- sponding type of content logical anomaly in IETM for aircraft maintenance and repair (anomalies of the logic of subject content representation as regards the SCLC). The process of representation of the anomaly in the form of a graph isomorphically nested in the configura- tion of SCLC of IETM (when the description of the speci- fied anomaly model is formalized by applying mathe- matical methods of the graph theory technique) takes the form shown in fig. 1. Strictly speaking, the algorithm for detection of an anomaly graph isomorphically embedded in SCLC of IETM, as related to the general method of detecting quality anomalies in IETM for aircraft mainte- nance and repair, will not undergo significant logical and structural changes. The algorithm initially specifies SCLC decomposition procedures and methods detecting embed- ded anomalous structures (based on the graph theory technique). The complexity of this approach is due to the fact that the task of quality anomalies detection in SCLC of IETM is regarded here as a problem of graph isomor- phic nesting detection (or isomorphism to a subgraph); the existing algorithms of solving the problem reflect expo- nential time complexity of software implementation [15]. The problem of graph isomorphism detection has a correct interpretation in the subject area of designing IETM for aircraft maintenance and repair. In particular, there exists a set of effective algorithms for detection within a complex graph, such as SCLC configuration in a real, operational IETM for aircraft maintenance and re- pair, a subgraph isomorphic to the specified one (sub- graph-quality anomaly) [15]. There are 2 classes of algo- rithms for such detection. Class 1 is the implementation of hierarchy principle for the so-called non-exhaustive algo- rithms that recursively improve their performance in the way of scope and precision of the parameter analysis of vertices and / or edges invariant to graph isomorphism, and, accordingly, called invariants. Class 2 of the algo- rithms relates to implementation of the same algorithm hierarchy principle, but in the way of exhaustion at one of the search steps of the so-called isomorphic permutation. The worst parameters are demonstrated by algorithms implementing the so-called total direct exhaustion. They can be applied only to SCLC of limited scale. At the same time, the solution of the problem of isomorphic nesting of subgraph into SCLC graph of IETM for aircraft mainte- nance and repair is trivial in regard to software tools and is described in [14; 15]. Thus, the representation of IETM for aircraft mainte- nance and repair quality anomaly by a graph isomorphi- cally nested in the configuration of its SCLC allows to reduce detection of the specified anomalies to the mathe- matico-algorithmic problem of detecting the specified isomorphic subgraph in the corresponding logic scheme. Then it becomes possible to detect typical structural em- beddings that characterize logic errors in the feeding of electronic content to IETM for aircraft maintenance and repair from the list / database of predetermined anomalous logic substructures. Concretization of the graph model of IETM quality anomaly developed on the basis of logic schemes of the subject content. Analysis of presentation of IETM con- tent quality anomalies as an isomorphic embedding of a graph reflecting the corresponding SCLC configuration showed that the graphs defining these anomalies may have a diverse and complex form. The classification of mathematical methods for detect- ing graph isomorphism, i.e. methods for solving the prob- lem of detection of a graph isomorphic to a specified one, is shown in fig. 2 [15]. As the choice of graph fragments of the same type is varied, the invariants are divided into three classes: local, quasi-global and global. The solution of the subtask of invariant detection is carried out on the basis of the statement proved by the graph theory - graph G is isomorphically embedded into graph G’if and only if φ (G <> G’) ≥ | G | [14]. Concretization of IETM quality anomaly graph model developed on the basis of SCLC involves determining the best mathematical method for solving the problem of isomorphic graph nesting that conforms to constraints of the subject area of IETM for aircraft maintenance and repair quality management. Algorithm for detecting isomorphic nesting of a quality anomaly graph in SCLC configuration of IETM. The algorithm for solving the problem of detec- tion of isomorphic graph nesting that conforms to con- straints of the subject area of IETM for aircraft mainte- nance and repair quality management, as stated in the classification of methods given above, is implemented on the basis of compound method of directed exhaustion. It combines the main advantages offered by directed ex- haustion methods that employ local, quasi-global and global invariants. The suggested algorithm makes use of the following invariants: - number of vertices n(L); - number of edges m(L); - power vector S(L) = (s1, s2, …, sn), which, in par- ticular, yields numerical invariants s(L) = min S(L, x) and s’(L) = max S(L, x); - outdegree S-(x); - indegree S+(x); - adjacency matrix A(L). In the design of the algorithm the following assump- tions and limitations were adopted: - it is assumed that the vertices (edges) of the graphs have the same properties, i. e. in the algorithm weighting factors of the vertices (edges) are neglected. The reason is that for different types of graphs there will be different requirements for weighting factors; - all vertices should be numbered; - only directed graphs are considered: when analyzing undirected graphs, it is necessary to specify one edge as two, i. e. as connecting vertices in both directions; - “unconnected” vertices are not considered, i. e. each object must have at least one link with another object. Fig. 1. Key steps of anomaly representation by a graph isomorphically nested in SCLC configuration of IETМ Рис. 1. Основные этапы представления аномалии графом, изоморфно вложенным в структуру ЛСПК ИЭТР Fig. 2. Classification of graph isomorphism detection methods Рис. 2. Классификации методов установления изоморфизма графов The methodological basis of the proposed algorithm for solving the problem of isomorphic graph nesting is the thesis that logic circuits S1 = {A1, R1} and S2 = {A2, R2} in combination outline a constraints system that affects a set of hypothetically possible solutions and significantly reduces it. Here it is not an exhaustion of solution vari- ants, which would lead to N-factorial searches, but appli- cation of a constraints system by a specific algorithm onto a specially devised field; inside this field, as a result of a sequence of actions aimed at meeting the require- ments of the constraints system, a ready-made solution is formed. This variant may look like a permutation matrix for graphs of the same dimension. What can be assumed is as follows: a field with a set of hypothetically possible permutations can be presented in the form of n × m ma- trix; for n and m - the number of graph vertices, respec- tively. Such a matrix should be correctly called further as graphs as shown in fig. 4. Adjacency matrices and possi- ble permutations matrices for this pair of graphs are shown in fig. 5. In the matrix of possible permutations С, in the first column, there is an enumeration of all graph B vertices, and in the first string - of all graph A vertices. The number of possible permutations is entered in N+1 column. The initial completion of a matrix of possible permu- tations is carried out by analyzing indegrees and outde- grees of the original graphs according to the rule: vertex can Bi correspond to vertex Aj only if indegrees and out- degrees of this vertex are greater than or equal to those of vertex Aj. Thus, the initial filtering of solution variants is performed. Mathematically, this is formalized and writ- ten as: if C = ì1, if s(B, bi ) £ s( A, ai ) and s(B, bj ) £ s( A, a j ), possible permutations matrix. So, as an illustrative exam- ple, in fig. 3 there are two graphs - G1 and G2, and ij í î 0, in other variants. the corresponding adjacency matrices. The subgraph of G1 isomorphic to G2 is highlighted in gray. Permutation matrix for G2 graph and the subgraph of G1 isomorphic to G2 is shown in fig. 4. Still, the invariant of isomorphic permutation remains the same: æ1 2 3 4 5 6 7 8 9 Аö è ø j= ç1 7 8 4 5 А 2 3 6 9 ÷ . The essence of the algorithm suggested for detection of isomorphic nesting of a quality anomaly graph in SCLC configuration of IETM can be adequately pre- sented by solving a problem of an isomorphic nesting of Further adjustment of the matrix is performed by im- posing the following system of constraints: 1. Graphs cannot be isomorphic if there is at least one null string in “Number of possible permutations” column. 2. In case of one-to-one correspondence of vertices Bi and Aj (Bi↔Aj), there can be no other symbols ‘1’ in col- umn j of possible permutations matrix (C). To meet this restrictive condition, it is necessary to eliminate from col- umn j of the matrix the so-called “extra” characters ‘1’. As the stated correspondence may turn out false for a cer- tain vortex, the elimination of characters ‘1’ from the matrix must be performed so that a possibility to restore the matrix at a certain step still remained. The Mirage vari- able is introduced for this purpose: its value changes after each cycle of imposing a constraints system on the possi- ble permutations matrix. Consequently, the operations to be made can mathematically be represented as follows: if C[N+1, i] = 1 and C[j, i] = ’1’ , the element C[k, i] of value ’1’ (for k = 1…m; k ≠ i) is assigned the current value of Mirage variable. If all the values of the matrix column ”number of possible permutations” are greater than 1, to find a quick solution, it is necessary to start work at the lowest value string. G1 1 2 3 4 5 6 7 8 9 A B C D 1 2 3 4 5 6 7 8 9 A B C D 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 8 4 5 A 2 3 6 9 1 7 8 4 5 A 2 3 6 9 Fig. 3. An illustrative example of an isomorphic graph nesting Рис. 3. Частный пример изоморфного вложения графов Fig. 4. Example of detection of a quality anomaly graph isomorphic nesting in SCLC configuration of IETМ Рис. 4. Пример распознания изоморфного вложения графа - аномалии качества на структуре ЛСПК ИЭТР Adjacency matrix of graph A: 1 2 3 4 5 6 7 8 S-(x) 1 0 1 0 0 0 0 1 0 2 2 0 0 1 0 0 1 0 1 3 3 0 0 0 1 1 0 1 0 3 4 0 0 0 0 0 1 0 0 1 5 0 0 0 1 0 1 0 0 2 6 0 0 0 0 0 0 1 0 1 7 0 0 0 0 0 0 0 1 1 8 0 0 0 0 0 0 0 0 0 S+(x) 0 1 1 2 1 3 3 2 Adjacency matrix of graph В: 1 2 3 4 5 6 S-(x) 1 0 0 1 1 0 1 3 2 0 0 0 0 0 1 1 3 0 1 0 0 0 0 1 4 0 1 1 0 0 0 2 5 1 1 0 0 0 0 2 6 0 0 0 0 0 0 0 S+(x) 1 3 2 1 0 2 Possible permutations matrix (matrix C): А1 А2 А3 А4 А5 А6 А7 А8 Number of permutations В1 0 1 1 0 0 0 0 0 2 В2 0 0 0 0 0 1 1 0 2 В3 0 0 0 1 0 1 1 0 3 В4 0 1 1 0 1 0 0 0 3 В5 1 1 1 0 1 0 0 0 4 В6 0 0 0 1 0 1 1 1 4 Fig. 5. Adjacency matrices of graphs and of possible permutations Рис. 5. Матрицы смежности графов и возможных подстановок And the first of the previously unused cells of the cor- responding string is assigned the so-called “focus”, i. e. an active cell is set (the coordinates of permutation vertices C [FocB, FocA] are determined). The remaining ‘1’ char- acters must be “covered” by Mirage variable. When Bi↔Aj, to the vertices Bk (k = 1...m) adjacent to Bj, there can correspond only those Al (l = 1...n) verti- ces that are adjacent to Ai vertex. To meet this condition, the so-called “extra” ’1’ characters in the possible permu- tations matrix must be “covered” by Mirage variable. Mathematically, this can be written as follows: a) if C[j, i] = ’1’ and B[j, FocB] = ’1’ and A[j, FocA] ¹ ¹ ’1’ then C[j, i] = Mirage; b) if C[j, i] = ’1’ and B[FocB, i] = ’1’ and A[FocA, i] ¹ ¹ ’1’ then C[j, i] = Mirage, where А, В are initial adjacency matrices, and C is possi- ble permutations matrix. 3. Other special constraints taking account of the spe- cifics of detection of a quality anomaly graph isomorphi- cally nested in a specified SCLC configuration within the IETM in operation. The presented list of constraints is not complete and closed. In this case, the constraints perform the function of a logic filter. In accordance with the specifics of the problem of detection of a quality anomaly graph isomor- phically nested in a specified SCLC configuration within the IETM in operation, additional filters - constraints may be introduced. The proposed algorithm for detection of a quality anomaly graph isomorphically nested in SCLC configura- tion allows to specify the structure of quality anomaly detection method applied to IETM for aircraft mainte- nance and repair. The final version of the method struc- ture is presented in fig. 6 Fig. 6. Logic structure of method of detecting quality anomalies in IETM for aircraft maintenance and repair Рис. 6. Логическая структура метода выявления аномалий качества ИЭТР по эксплуатации и ремонту авиационной техники Анализ результатов Анализ результатов Анализ результатов Generally, the method of quality anomalies detection of IETM for aircraft maintenance and repair comprises the following succession of key stages: 1) formalize and configurate SCLC for IETM in the form of directed graph; 2) select the configuration of the quality anomaly graph (logic error) from the database of quality anomaly configurations based both on the analysis of previously detected logic errors of content representation in IETM, and on relevant database provided by experts; 3) using a filter system based on the selected pair of configuration models of SCLS proper and of the anomaly, complete the matrix of possible permutations; 4) solve the mathematico-logical problem of the graph isomorphic nesting detection; 5) analyze the detection outcome, if necessary, select for analysis the next version of configuration models of SCLS proper and of the anomaly. Conclusion. The method of quality anomalies detec- tion of IETM for aircraft maintenance and repair allows to detect logic-configuration anomalies of SCLC for IETR from the list (database) of pre-detected quality anomaly configurations (logic errors of electronic content presenta- tion); the method can be applied to interpret the results of quality assessment of IETM for aircraft maintenance and repair, i.e. detection and elimination of the stated quality anomalies, the configuration of which is known in ad- vance.

About the authors

E. A. Frolova

Saint Petersburg State University of Aerospace Instrumentation

Email: frolovaelena@mail.ru
67, Bolshaya Morskaya Str., Saint Petersburg, 190000, Russian Federation

Ya. A. Ivakin

Saint Petersburg State University of Aerospace Instrumentation

67, Bolshaya Morskaya Str., Saint Petersburg, 190000, Russian Federation

A. O. Smirnov

Saint Petersburg State University of Aerospace Instrumentation

67, Bolshaya Morskaya Str., Saint Petersburg, 190000, Russian Federation

References

Supplementary files