Multiversion model of software control systems for space vehicles with range of decision-making

Introduction. At the stage of designing the appearance of spacecraft control systems, decisions are made on the choice of the composition of the multi-version software of the system using the fuzzy programming method. This allows the designer to set the degree of "attribute preference" and the possible "percentage of attainability" of goals when choosing one or another option for forming the composition of multi-version software [1–3]. The result, as a rule, is a set of non-dominated solutions to the problem of forming the multiversion software of the control system.

The problem of forming a complex of multi-version software for spacecraft control systems is an objective of conditional optimization of a monotonic pseudo-Boolean function.

The most universal of all discrete optimization methods is the exhaustive search method when all feasible solutions are examined to find the best value of the objective function [4].

Algorithms of two main types have been developed in this direction: implicit exhaustive search, where an increase in the speed of finding the optimal solution is realized through narrowing the search area and reducing the total number of calculations in the algorithm and a branch-and-bound method scheme with dividing the search area into smaller sub domains.

Among the exact algorithms of the first type one should single out procedures that use to enhance the computational capabilities of exact algorithms, the idea of narrowing the search area due to the features of the functions-elements of the optimization problem being solved and the fastest traversal of the search area by neighboring points using relations on the space of Boolean variables [5].

The algorithms of the branch-and-bound scheme [6] include algorithms for finding solutions on sub cubes [7–8]. Procedures of this type differ only in the way of organizing the division of the solution search area into sub cubes that is in the way of representing the original optimization problem in the form of a certain number of tasks of lower dimension [9].

A large number of modules of the multi-version software of spacecraft control systems their redundant versions as well as limitations of real needs such as the cost of development, implementation and modification of the system pose the designer the task of making decisions on the choice of the optimal composition of the multi-version software of the system taking into account a number of attributes [10–13].

Due to the existence of a sufficiently large number of alternatives, their assessment is largely influenced by the qualities of the decision-maker himself and his subjective preferences. Therefore when making a choice of the best alternative from a number of proposed ones it is necessary to take into account the subjectivity in the assessments of the decision-maker. [14].

General ranking model when choosing the optimal solution. In new information technologies decision-making is considered to be a set of decisions in conditions of certainty which make it possible to choose unambiguous, consistent, correct decisions based on formalized models of control objects and their environment. The formation of certain probabilistic decisions in conditions of uncertainty should also be considered as decision-making. [11].

The problems of decision support in new information technologies cover all the problems including the class of tasks under the conditions of uncertainty, the final solution of which is carried out outside the used technology. In these cases the information is converted to a form that simplifies and facilitates decisionmaking by other methods. It can be stated that currently various methods and approaches are used to support decision-making, which together complement each other. Decision making involves choosing a sequence of actions and implementing it. Decision support is based on obtaining multivariate decisions using different methods. The decision support methodology includes a variety of schemes and technologies; it can be implemented partially or completely using software and information systems. The simplest decision-making model includes four main cyclically repeating stages:

• -    collection, analysis and transformation of data;

• -    obtaining options for solutions (alternatives);

• -    development of criteria for evaluating decisions;

• -    selection of one of the options based on the selected criteria.

There are different conditions and situations in which you need to make decisions. There are various levels of decision making. The top one is the conceptual level. It allows you to draw up a generalized diagram. Decision making technology generally includes the following stages:

• -    emergence of a problem or task requiring a solution;

• -    formation of the problem at the verbal level;

• -    search for information necessary for making a decision;

• -    formalization of task setting; - analysis and processing of information;

• -    formation of a set of alternatives;

• -    obtaining forecast estimates;

• -    evaluation of the results of decision-making.

A task that requires a solution happens at the first stage. As a rule it is formed at the verbal (nonformalized) level of communication. Thereafter a search and collection of information is carried out in an aspect of the given problem or task. At the same time they collect not only the data necessary for the solution but also information about the methods for solving such problems. After that they formalize or formulate the problem at a formal level. [15].

At the stage of information analysis and processing, complex processing is carried out, including computer methods and expert analysis; direct calculation and heuristic methods; optimization methods.

A possible change in conditions is provided for by obtaining sets of solutions. Mutually exclusive solutions are called alternatives. Therefore, for completeness and taking into account changing conditions as a result of the analysis, the formation of alternatives is carried out, which is presented as an important stage in the decision-making scheme. The presentation of the generalized data is carried out in a form that is convenient for making decisions.

The next stage and one of the most important is the stage of obtaining forecast estimates. At this stage, using the available solutions, information about the conditions and methods of obtaining a forecast, forecast estimates are obtained, and the choice of the forecasting method and the forecast verification method are justified.

After receiving a set of data: alternatives, information about the dynamics of conditions, forecast estimates, assessment of forecast reliability, etc., complex processing is performed using an expert approach. This scheme can work with different technologies and control levels.

The connection between the listed stages should be emphasized. They form a hierarchical sequence. If at one of the stages there is no possibility of its implementation, then the transition to the next is not carried out. Decision support means that the group of these methods is aimed not only at obtaining decisions, but also at providing recommendations for the decision maker. Thus, decision support includes three groups of tasks:

• 1.    Getting a set of solutions but not one.

• 2.    Preparation of criteria for evaluating the solutions obtained.

• 3.    Choosing a solution from the available population.

There is a problem of correct extracting the necessary information when making decisions and evaluating them.

The use of modern technologies and decision-making methods requires the use of formalized data. Therefore the effectiveness of methods for obtaining solutions and decision support depends on the formalization of the problem. So when a complex problem is decomposed to an operational level and the conditions for solving a problem at this level are fully formalized, it is effective to use operations research methods to obtain solutions. If decomposition and complete formalization are impossible, methods of statistical evaluation, the theory of fuzzy sets, etc. are used.

The choice of the best option for the formation of the multi-version software of the system from the entire set of possible implementations can be made using the compensation model of multi-attribute decision making, which allows you to perform a general ranking of alternatives based on the order of their preference for individual attributes and the relationship between them and to determine the best option for the formation of multi-version software.

The developed model of decision-making on the composition of the multiversion software of the system assumes the ranking of possible options for their formation in order of preference. The first ranked option is the best. Using only order of preference as input avoids scaling of quality type attributes [16, 17].

This model is based on the ranking of alternatives for individual attributes. On the basis of this "private" ranking the general order of preference for alternatives is determined taking into account all the attributes and the relationship between them.

There is a linear assignment method that allows performing a general ranking of alternatives. [18]. According to this method the total rank was calculated as the sum of the ranks for individual attributes. In this case information about the relationship between attributes was ignored:

n r , = У Г,, i = 1, m ,                                       (1)

iобщ         ij j=1

where m is a number of alternatives; n is a number of attributes; r ij is a rank of i alternative on j attribute; r is a number of ranks ( r = m ).

However for most decision-making tasks and in particular for choosing the option for forming the multiversion software of the system it is important to take into account this dependence [19]. In this regard on the basis of this method a multi-attribute compensation model was developed for the general ranking of alternatives in order of preference taking into account the dependence of the attributes. The idea of compensation in this case is to take into account the dependence between attributes: a change in the value of one of them leads to a change in the values of any other attributes. Let us define the matrix π as a square nonnegative matrix m x m, whose elements π ik represent the number (or frequency) of the ranking of the alternative A i by the r th rank. The matrix π is formed on the basis of the ranking matrix of alternatives for individual attributes D:

n

• ⁿ ik = E I ⁽ D j ) ■ w ; i = 1, ^m ; j = ^1, r ,

  
  

i = 1

I ( D ji ) =

1,

< 0,

если Djt = i, если Djt * i,

where I (x) is an indicator function; w l is a weight coefficient of the l st attribute.

For different weights, the elements of the matrix n represent the sum of the weights of the attributes of the corresponding rank. It is assumed that the weights are normalized.

Obviously π ik determines the contribution of the alternative A i to the overall ranking . The larger the value of π ik is , the more correct is the assignment of the rth rank to the alternative A i

Let’s define the permutation matrix Q as the square matrix m x m, which elements Q ir = 1, if the alternative A i is assigned a general rank r, and Q ir = 0 otherwise. The objective function can be written as follows:

mr max EEnQ,(4)

Qr = 1 j = 1 under conditions r

E Qr = 1; i = 1, m, j=1

m

EQr=1; i=1,r.

i = 1

Conditions mean that only one rank can be assigned to alternative A i and rank r can only be assigned to one alternative.

Let us denote the optimal permutation matrix representing the solution of the above linear programming problem as Q *. Then the optimal ordering can be achieved by multiplying the matrix A containing the numbers of alternatives by Q *.

Let's consider an example of a model application of the proposed compensatory multi-attributive general ranking model when choosing one of the three alternatives. Let all attributes have increasing preference that is the higher the value of the attribute is the more preferable the alternative is.

Suppose that the ranks of these alternatives for three separate attributes correspond to those given in Table. 1. So the first alternative has the first rank according to the first attribute, the first rank according to the second, and the second according to the third.

Table 1

Ranking alternatives by individual attributes

attribute		1	2	3
	1	A1	A1	A2
	2	A2	A3	A1
	3	A3	A2	A3

Ranking by individual attributes can be represented as a matrix D, the elements of which are the indices of the ranked alternatives:

D = 2

Based on this matrix one can obtain a matrix π, its elements represent the number of assignments to an alternative of each of the ranks. So the first alternative was assigned the first rank twice, the second rank -once, and the third - never, which corresponds to the value in the first row of the matrix:

n =  1  1  1

For weighting factors w1 = 0.2, w2 = 0.4, w3 = 0.4 the elements of the matrix π will change as follows:

	"0.2 + 0.4	0.4	0   "		"0.6	0.4	0 ’
П =	0.4	0.2	0.4		0.4	0.2	0.4	.                               (9)
	.     0	0.4	0.2 + 0.4		. 0	0.4	0.6

The optimal permutation matrix Q * which determines the overall rank of each of the alternatives has the form:

Q* =

It can be seen that the first alternative (the first column corresponds to it) has a general rank equal to one (the first row), the second alternative received the second rank and the third has got the third. Based on the Q * matrix, we get the following order of preferences:

A1 >  A2 >  A3.

The multi-attribute decision making compensation model allows for a general ranking of alternatives in order of preference based on ranking for individual attributes and the relationship between attributes. The merits of this model are its unique advantages in practical application. An expert is required to set the order of preference for alternatives by attributes when collecting data. This approach avoids the difficulties that arise when creating a scale for assessing attributes.

Optimization algorithms.

Implicit brute force algorithms. In the model with sequential organization of software modules, the multi-version software complex is defined as consisting of a set of sequential software modules, for which a set I, card (I) =I is introduced. Many modules are divided into classes that means many classes of software modules (J, card (J) =J) are introduced. By referring a certain software module to a certain class, it is assigned a solution to the corresponding intermediate "typical" problem of control or information processing. Combining "standard" software modules into complexes contributes to the formation of the process of solving the general target problem of the control system. In order to implement modules of one class a software module is assigned which in turn to ensure the reliability of execution is implemented using the multi-version programming methodology. Functionally equivalent versions Sj, (j = 1,J) are developed for each software module in accordance with the original specifications. Thus, a vector S= {Sj}, (j = 1,J), is introduced, its elements are numbers equal to the number of versions of software modules (Sj is the number of versions of a module that solves the problem of class j - that implements a module of class j).

As a result, the set of all software modules К is determined, then K = card (K) characterizes the total number of software modules included in the designed software package.

In addition the set В , card (B) = I of belonging of tasks to classes is determined, the cardinality of which is equal to the number of tasks in the system and each element of this set is equal to the number of the class to which the task belongs. Thus, the element В i of the set В represents the number of a typical module; with its help i-th control problem in the general control complex is solved.

We are introducing Boolean variables:

1, in order to realise i — th (i = 1, I) task

X

= ^ we use s — th (s = 1, SB ) version of module В

0, in opposite case.

The introduced variables unfold into a vector of participation, which formally describes the possible variants of the formation of the composition of the multi-version complex of programs. The task of the optimal formation of multi-version software is to find a set of multi-versions, which determines the greatest reliability of the software package, subject to a certain level of financial costs for creating the system [7; 8; 20]. The problem formulated in this way using the previously introduced notation was formalized as follows:

l maxRNVS 1( X) = П Ri( X),                              (13)

i = 1

SBi where R (X) = 1 — ^П (1 — RB 5)XS is assessment of the reliability of the i-th software module as part of a s =1

multi-version software package, R is an assessment of the reliability of the s-th version of the i-th software module. The limitation on the cost of the designed software package is Cnvs 1( X) < B,

where

I    ^SBi

cw(Xx) = y У Xi • cb s,

NVS1                   S    BiS i=1 s=1

C is the level of financial costs for the implementation of the s-th version of the i-th software module of the designed software package.

Thus in the formal goal setting of this type, the problem of the optimal formation of multi-version software is formulated as finding the values of the components of the vector X so that the reliability function of the software package (13) takes its greatest value if the cost function (14) does not exceed a certain value B.

For a single-valued description of the problems of forming multi-version software complexes as well as for converting two indices of Boolean variables defined in (12) into one number of the participation vector component, it is necessary to determine the procedure for forming the participation vector and accordingly an algorithm for determining the indices of the components of this vector [21 –23].

In the second optimization model, a model with sequential-parallel organization of program modules, a multi-version software package is also considered to consist of a set of control problems of sequential execution (multitude I , card (I)= I ). Like the first model software modules are divided into J types according to the required functions, that is a set of typical control problems is determined or a set of classes of problems – J , card ( J )= J.

But unlike the model with a sequential organization of modules, each task i= 1, I of the software package is implemented not by one module, but by a certain set of software modules which is specified in the vector J i , где J i = { j i ,..., j'j } therefore card ( J i ) = Ji is the number of software modules involved in solving the i-th problem and j^l_k , k = 1, J is the number of the class to which the k-th program module belongs.

Each typical task from the set J is implemented using a fault-tolerant software module developed using the multi-version programming approach, that is, each element of the set J is associated with a set of versions of the module it defines ( V k is a multitude of versions k, k= 1, J , S k = card ( V k ) is a number of module versions k ). Thus for each software module in accordance with the original specifications a S j , ( j= 1, J ) of functionally equivalent versions is developed, that means vector S = { S j }, ( j= 1, J ) is introduced. Its elements are numbers equal to the number of versions of software modules ( S j is a number of module versions realizing j class module).

As in the first model for a formal description of the structure of the designed complex of multi-version software, a vector of participation X is introduced, the components of which are such Boolean variables X _kS as

1, in order to realise i - th (i = 1, I) task

X k = <

weuse s - th (s = 1, S l) version of module k = (k = 1, J[),

Jk

0, in opposite case.

Similarly to the model with sequential organization of software modules the task of optimal formation of multi-version software in this model is to determine the set of multi-versions that characterize the greatest reliability of the software package without exceeding the established budget for creating the system, that is, the optimization problem is formally posed as follows:

l

maxRNy(X X) = П R( X\ i=1

where

J i

R i ( X ) = n R k ( X ), k = 1

and

Sjki

R k ( X ) = 1 - П (1 - R. . J X ks , j_k , s

s = 1

whereas R ( X ) is assessment of the reliability of the i-th set of software modules as part of a multi-version software package, R ⁱ ( X ) is reliability assessment of the k-th software module as part of the i-th set, R _i is assessment of the reliability of the s-th version of the k-th software module as part of the i-th set.

The limitation on the cost of the designed software package is determined by the formula

C nvs 2 ( X ) <  B ,                                      (20)

where

I J i ^Sjkⁱ

C nvs , ( X) = £22 X= ' ] -                     (²»

i = 1 k = 1 s = 1

C is the level of costs for the implementation of the s-th version of the k-th software module as part of jki ,s the i-th set of the designed multi-version software complex. Obviously if among the set of all boundary points we select the two closest to the point Хо all coordinates of which are equal to zero and the boundary point farthest from Хо, and determine the levels Imin and Imax of the point Хо corresponding to these two points then it becomes possible to narrow the region search for solutions since undoubtedly the solution of the obtained optimization problem will belong to the set defined by the following formula

I max

S = U O . ( X o )-                                      (22)

i=I min where X° is a point in the space of Boolean variables such as that X° = 0, i = 1, n .

Thus, to find a solution to the problem it is enough to determine the levels I min and I max of the point Х о and compare the values of the objective function in the elements of the set S , defined by the formula (22).

This property makes it possible to significantly reduce the computational costs of finding an exact solution thereby speeding up the execution of the search procedure. The cardinality of a set S is determined by the following formula

Imax cardS = ^ Ck, k=I .

min where Ck is the number of combinations of n elements by k.

It is also indisputable that due to the additive nature of functions (15) and (19) the boundary point closest to the point Х о will be characterized by the correspondence of its unit coordinates to the largest summands of these expressions. That is in order to reach the boundary point nearest to it from Х о it is necessary to follow the path of the greatest increase of functions (15) and (21).

Algorithm 1. Algorithm for determining the I min level of a point Х о .

• 1.    We take up I =0, X g B n : X = 0, i = 1, n.

• 2.    We form a set of values of versions of software modules of the designed system С , card (С)=n, where n I                         I   M i

is defined as n = ^ S_B or n_{w $2} = ^ ( ^ S i ), depending on the problem being solved.

i = 1       i                         i = 1 k = 1 ^]k

• З.    From the hypothesis C_k = тахС , i = 1, n , X = 0 we determine k.

• 4.    We define X ^ = 1 .

• 5.    If X belongs to the set of feasible solutions, then we set I = I +1 and go to 3step.

The algorithm for determining the boundary point farthest from Хо (the algorithm for determining the level Imax of point Хо) is constructed similarly to algorithm 1, except that in step 3, k should be determined from the condition of the minimum increase in the function that k is determined so that Ck = minC, i = 1, n, Xt = 0.

The search scheme on the set of solutions defined by expression (22) is implemented in the truncated exhaustive search algorithm.

Algorithm 2. Truncated brute force algorithm.

• 1.    We define I min и I max , corresponding to the problem being solved.

• 2.    We take up I = I min .

• 3.    We define such X * vector as R ( X * ) = maxR(X ), X g OO ( X 0 ) .

• 4.    We repeat points 2, 3 for every I = I_m,, I_max.

• 5.    We take vector X as a solution of the task, due to he condition R ( X * ) = maxR(X * ), I = I_m,, I_max.

It is also worth highlighting the following property of pseudo-Boolean functions (15) and (21): if two adjacent to each other points X and Y differ in the value of some i-th component, whereas X i =0, то C(Y)=C(X)+ C i ,where C i is the cost of including the multi-version in the structure corresponding to the i-th component of the participation vector. Thus the form of the constraint in the constructed optimization problems allows one to get rid of the complete calculation of expressions (15) and (21) at each point, if the traversal of the solution search area is organized as moving along neighboring points. The entire value of the constraint function for each of the models is calculated at some starting point of the search. Nevertheless the subsequent values of this function are obtained by adding or subtracting the corresponding value when going through neighboring points.

In order to utilize the above-described property of the constructed optimization problem, a procedure for traversing the graph of Boolean variables by neighboring points was implemented, and each point of the solution domain is viewed by the traversal algorithm only once, which avoids increasing the computational complexity of search procedures. This algorithm for traversing the search area is based on the ability to represent any subcube as a union of its lower base point and a union of disjoint subcubes of lower dimensions. This way of traversing the search area is implemented in an implicit search algorithm with traversing the search area by neighboring points.

Algorithm 3. Algorithm of truncated implicit enumeration with traversal of the search area by neighboring points.

• 1.    We define parameters I min and I max , corresponding to the problem being solved.

• 2.    We take up X g B n : X = 1 V i <  I_mmkk = 0 .

• 3.    Using an implicit enumeration algorithm with traversing the search area by neighboring points, we determine the point X ^* that gives the largest value of the objective function at this stage.

• 4.    We generate the main point X g O ^0 ( I_m)), k = k + 1.

• 5.    We repeat steps C ^Imin times, where C ^k is a number of from n up to k.

• 6.    We take the point X * = maxX * , k = 1, C I mi* . for a task solution

Branch and Bound Scheme Algorithms. In the second group of exact search procedures, the initial problem is divided into several sub problems of smaller dimension by splitting the search area Bⁿ . The partitioning of the solution search area, in turn, is implemented as a partition of the space of Boolean variables into a set of disjoint subcubes that completely cover the entire space. The general scheme of algorithms built using this method is as follows.

Algorithm 4. Branch and bound method diagram (splitting a Boolean hypercube into subcubes).

• 1.    The search area represented (in the general case) by a sub cube in a binary space, is divided into R disjoint sub cubes.

• 2.    The belonging of the boundary points to each of the sub cubes is determined.

• 3.    If at least one boundary point belongs to the sub cube r-th ( r = 1, R )   , then using the methods of

• 4.    The best solution chosen from local ones is taken f ( X ) = min, r = 1,R .

implicit exhaustive search, the sub cube point Х r is found and stored that gives the best value of the objective function that satisfies the constraints.

In the general case, two methods are proposed for dividing a zero hypercube into sub cubes: a partition of B" into 2 ⁿ - " sub sub cubes of the same dimension n_sMb <  n and a method for recursively dividing sub cubes into two sub cubes equal in cardinality, the dimension of which is obviously one less than the dimension of the sub cube being divided. The partition of the space of Boolean variables into sub cubes is based on the corresponding property of the vector-mask.

Conclusion. Optimization tasks, to which the task of forming a complex of multi-version software is reduced, are tasks of the so-called "knapsack" type. However the peculiarities of the objective functions in the optimization models do not allow for their efficient implementation to use the algorithms for solving the knapsack problem developed earlier.

Utilization of the properties of the space of Boolean variables, including the properties and ratios of sub cubes, makes it possible to develop effective regular procedures for the implementation of the constructed optimization models that determine the exact solution of optimization problems.

The choice of the best variant of the formation of the multi-version software of the system is based on the implementation of multivariate decisions when using various methods of multi-attributive decision-making. The multi-attribute decision making compensation model takes into account information about the relationship between attributes. The idea of compensation in this case is to take into account the dependence between attributes: a change in the value of one of them leads to a change in the values of any other attributes. The modified multi-attributive method of ordered preference through similarity to the ideal solution allows finding the best option for the formation of multi-version software by systems in a variety of alternatives of any cardinality.

Experimental data show the advantage in time of searching for a solution to the implicit enumeration algorithm with traversing the search area by neighboring points over the algorithms of the branch-and-bound method.