Technology of a decision-making support system creation in an integrated CAD system

Alexei G. Tchernov, Moscow

Copyright © 1996-2000

1. Introduction

In modern integrated CAD systems one of the important subsystems is a decision-making support system (DSS).

It is possible to highlight the following main functions of DSS:

1. Providing a decision-making person (DMP) with information for decision-making process including information preprocessing.
2. Organizational-methodological support of decision-making process.
3. Simulation of a decision-making effect.
4. Expert functions: recommendations and reasoning.
5. Coordination of group-made decisions.

The specifics of a decision-making problem is that there is no universal solution, and consequently, each problem requires a new DSS to be developed which is implementation of a particular method or a group of methods. As a result, in most cases a DSS is created as a "turn-key" system making impossible its further development without involvement of developers.

Therefore, there becomes actual the problem of apparatus and technology development which would allow to automate the process of DSS creation and decision-making model development. This apparatus, apart from its creating functions, should also provide a task solution and a possibility of studying it, that is to be a technology creating and using the decision-making methods adjusted to the task.

This report addresses problems of creating a technology allowing to quickly and flexibly form a DSS within an integrated CAD system based on a freely extended standard unit set adequate to the problem being solved.

This technology is first of all needed for the tasks where a basis for decision-making is the numerical information because such tasks are the most widely spread (distributed) in engineering practice, and in many cases a non-numerical task may be reduced to a numerical one.

2. Definition of standard units

The proposed technology is based on the fact that for decision-making, as well as any other activity, it is possible to select a number of functions coinciding both semantically and from the formal point of view. Accordingly, such functions may be implemented by means of standard units as structures formed in a special way.

A general scheme of standard unit technologies is shown on fig.1.

It is shown here that use of standard units implies presence of two phases of a problem solution (in our case - DSS creation):

A. Application area analysis in order to form a set of standard units (a standard set) which means selection and description of standard units used for solution of many problems in the given application area;

B. Solution method description for the given problem on the basis of the standard set created.

Therefore, when considering technologies and tools for DSS creation, it is necessary to determine:

1. The way of standard units selection (i.e. what a standard unit is);
1. The form of a standard unit description;
2. The way the standard units joint use is organized;
3. The technology itself for the program system formation on the basis of standard units.

The proposed technology is based on a formal task description treated as a standard unit. The technology operation scheme is shown on fig.2.

The most important for the standard unit technologies is a base definition of a standard unit. The main idea of this paper is to identify standard units and task formal settings. Thus, it is assumed that the transition from the formal task to a particular application requires definition of a data domain model as well as the task solution method - rules for processing the information contained in a model. A standard unit definition does not require such a detailed level. It is only necessary to form the DSS or its components. Finally, the proposed standard units may be represented as shells with predetermined by formal tasks' semantics inputs and outputs and with structure of interrelations between models and methods characteristic of one or another formal task.

It is shown here that a set of standard units can ensure the task solution not only within appropriate formal settings but also solution of the tasks which may be decomposed and reduced to a solution of a logically coordinated combination of these tasks.

Use of a task as a standard unit is caused by two factors. Firstly, the term "task" is adequately perceived by the application experts and is associated, first of all, with mathematical settings of the task:

And secondly, the task, according to said above, has a number "of good properties": on one hand the problem statement (once the problem has been selected) determines the model to be applied which explicitly or implicitly is present in the "Input Data". On the other hand, the task's semantics (determined by the task selection) determines why the task is being solved and a combination of ways to achieve this goal, that is, a set of methods. Here a method means not just a unit of the numerical method software package but also the described above way of the given task solution as a combination of interconnected subtasks.

3. Interrelation between the standard unit components

To solve a problem, its components and their interrelations must be defined. The applied task components are: task description (the task itself), model to solve the task, and task solution method.

According to the said above, the "TASK" standard unit determines three sorts of links:

A task description comprises a shell linking models and methods. Its use to define a way for a more complex task solution specifies only a family of methods and models but not themselves.

When a task (T) arises for a user, for its solution he either selects the existing software (DSS) or creates a new one. Then the existing or created DSS comprises implementation of transformation

R : In —› Out, where
    In - Data set known from the problem statement,
    Out - Data to be found.

As a rule, it is accepted that if the implementation R exists the task is solved on a computer. Thus, to solve a problem T it is necessary to create the software implementing R.

Note that the program is created using units of two types: methods and models. One and the same task may be solved by several methods whereas several tasks may be solved by one and the same method.

This means that a task includes the relation TMet:

TMet : T —› {Method} which puts in correspondence to the task a number of methods for its solution.

On the other hand, if the task is set formally, it may be solved using several models (in various application areas). So, for example, an optimization task in general may be solved on linear or non-linear models, with or without constraints. Thus, there takes place the relation TMod:

TMod : T —› {Model} which puts in correspondence to the task a set of models to solve it.

However within the frames of one formally set problem not all the methods may be used for all possible sorts of models. For example, non-linear models cannot use linear methods. This means that besides TMet and TMod there exists the relation MetMod:

MetMod : Met « Mod which defines a possibility for a joint use of a method and model within the frames of a given problem.

Generalizing, the following triad takes place

where the main role is played by the task. By defining the task, we thus define acceptable methods and models, and also peculiarities of their joint use.

This way, using a standard unit "TASK" to build the relation R, we obtain a flexible apparatus for solving a decision-making problem:

- the model change on the top level (for the source task) automatically varies the model for subtasks;

- when solving each of the subtasks, it is possible to vary the methods within the range of the relations TMet, TMod, MetMod;

- for subtasks the method may be also created on the basis of the "TASK" standard unit. Therefore, it is possible to build hierarchical methods-models for decision-making.

To be able to use the "TASK" standard unit for the technology development, it is necessary to take into account the following factors:

1) Description of the "TASK" standard unit should provide a required level of flexibility and reflect the really existing interrelations "Task - Method - Model";

2) There is required a way of the Method-Model link description within a context of the task.

3) There is required a tool to build a solution method for the task which is a combination of interconnected subtasks.

Before considering the way to take into account the stated problems in the technology proposed, let's give some necessary definitions.

An elementary task is a task described within the frames of considered technology and available for the description of other tasks solutions.

A technique is a task solution method represented as logic of interconnected tasks solutions at a lower layer of hierarchy.

A standard task is an elementary task for which at least one method of solution exists. If this method is a technique, any task included in it should be standard.

A class of the tasks is a task of the top level of hierarchy that requires solution.

As was marked above, a task is a standard unit in technology. For the description of the "TASK" standard unit we shall use a canonical form of task description:

T = { Tn, H : In —› Out } where

In, Out = { E_t } where

E_t = { <Unit Name>, <Identifier>, <Type> } where

We will use the canonical form of the task for description of both elementary tasks and classes of the tasks being solved.

The unit type is specified by its name and can be simple (basic) or complex, formed as a combination of units of basic or complex types.

It is proposed to use the following types as basic unit types for setting a task: NUMBER, LOGICAL, STRING and FUNCTION. The given set is sufficient because on its basis it is possible to present practically any type of data. The rules for the values definition and variables description are clear and correspond to the rules used in the programming languages. The only different one is the FUNCTION type.

The contents of a unit of the given type determines a way of calculation of the right part of the equation:

<Unit Identifier> = <Right Part> depending on a fixed number of arguments.

The ways of the right part calculation are reduced to the three ones:

1. The right part is a FORMULA.

There is specified a formula for the right part calculation. This formula may also be a "correct" sequence of arithmetic expressions the last of which should be an expression of the sort

If the formula contains identifiers different from the function arguments, they are defined as the function parameters. The identifiers used only for storing the intermediate values are not included in the number of function parameters. The function parameters values must be defined as numbers before the function has been actually used.

2. The right part is a TABLE.

The first column of the table contains values of the function for the values of the arguments defined in the following columns. All the values are of the NUMBER type. A way of the table initialization is selected. The function calculation is done on the basis of interpolation and extrapolation of data in the table.

3. The right part is a PROGRAM UNIT.

For the program unit there are specified: the form of its storage (source code, object or library unit), location, programming language, call parameters, way of the function value return (through parameters or through a return code, if return of value is back through the parameter), indication of parameter with the function value.

To convert functions with various internal representation, the following way is proposed.

Let the main (basic) form of the function representation be a program unit as closest to a function implementation on computer.

Because the object-function represented is the same for the three selected forms, there comes a scheme of possible conversions which is implemented in a form of the following relations:

The relations TF, FM, MT define a way of obtaining functions of one sort from functions of another and are a closed system. However, it is reasonable to add to them the relation TM which allows to obtain a program unit from the function-table, and a program unit was selected as a basic form of function representation.

The last unit of the task {A} description represents a number of algorithms for the given task solution which, eventually, represent the methods implemented.

Each of these methods has a specific list of arguments which can be divided into two groups:

1. Target (the known data InM, a set of data defined by the method OutM).
1. Other - carry additional information or are intended for special purposes (OtherM).

Among other method parameters the following subgroups are selected:

a) Working areas of memory;

b) Dimensions (may be referred to as target);

c) Control variables;

d) Information - carry information about the method results;

e) Specific, for example COMMON BLOCK of FORTRAN, external variables, non-standard control variables.

Apart from parameters, a method as a program is characterized by its implementation (L'_m):

1) Implementation in a programming language as a program unit (PU);

2) Implementation as a logic of subtasks solution (L (T)).

Thus, a method as a program is represented as follows (*)

(*) L'_m : InM, OtherM —› OutM, OtherM

L(T)

On the other hand, a task is characterized by its formal statement

Therefore, there is necessary such a description of algorithms {A} which would:

- allow to identify the algorithm;

- make the task input data correspond to the method input variables and data to be found - correspond to the method output variables.

We will distinguish description of the method as programs from its description as a combination of subtasks.

In this case, A must be presented as:

A = { An, Sch, Method' } where

Formal description of the method use will be represented as connecting schemes - special structures of data containing description of two sorts of relations:

Sch = { Sch₁, Sch₂ } where

Such a description allows to close the problem H formal statement with regard to the method:

A = Sch₂ * Method * Sch₁

that is:

H : In —› InM' —› OutM' —› Out, where

Sch₁ L(T) Sch₂

{A}

The possibility of building the relations Sch₁ and Sch₂ is obvious as it is possible to precisely determine rules for definition of In and Out.

The advantage of the connecting scheme mechanism is that for one and the same task there may be used methods with the completely different representation type (executable unit, object module or library unit), programming language or various list of control parameters.

Connecting a method by means of the schemes is done in two phases:

1. Description of the method as a program unit;

2. Creation of the connecting scheme to solve a task.

The second phase is repeated over and over again for different tasks (for example, the non-linear programming methods may be used to solve both an optimization problem and an equation systems).

Possible implementation of a connecting scheme may be a file containing description of features of the method use when solving a particular task. A connecting scheme is divided into sections which may, in turn, be divided into subsections. These sections specify: how the method input data are formed, how the results are interpreted, default values for some variables, how the information variables are interpreted. This description is a construction for the generation which calls programs of the method.

A special case of connecting the method is the case when the method as such did not exist and it is created as a technique. In this case the technique parameters are unambiguously defined by the task statement, and the connecting scheme is not needed.

5. Building a DSS on the basis of standard set units

An object-oriented language is proposed as a description tool for the logic of solving the problem as a combination of interrelated subtasks. Its basic feature is using, as a special sort of operators, tasks from standard sets identified by names. To every indicated task specified there corresponds some detailed mathematical statement. This statement is also formal, to certain extent, as the actual data for the task can only be formed directly while solving the source task by means of the method selected.

Problem statement is formed on the basis of the task canonical form where there are units of abstract types. The abstract types, as accepted, represent the descriptions of the object structure as a combination of objects of basic types and objects of already defined abstract types. Each type has a set of operations defined which allow to use an object of the described type as a single object.

Use of the standard set tasks is possible also through use of the operator "solve the problem as stated" (SOLVE) which renders concrete formal statement of a subtask specifying which objects must be taken as the task units "Input Date" and which objects must be used to place the results of the task (units "To be Found"). The structure of the SOLVE operator and the main constructions of the language are represented on fig.3. The METHOD part in the operator SOLVE is introduced for an "advanced" user which at the algorithm description phase can explicitly specify the task solution method. This structure is similar to the operator-task, with the exception that the operator-task has no such a keyword - SOLVE, and there is no such a part - method.

It is natural for a language to include standard constructions. Such as: cycles, if statements, input-output constructions.

An "underwater stone" of using a method generated in the above described way is the fact that when setting one or several subtasks there are the objects the abstract type of which differs from the attributes of “Input Data” or “To be Found” units for the task canonical form.

However, this conflict may be easily settled down by means of using detailed procedures of abstract types integration in the object-oriented programming languages.

Storing information within the frames of a technology is done by means of a database (DB). The correlation of storage information units is implemented by means of references. The most appropriate for this are databases with a network structure, though it is possible to use relational databases. General structure of the information support is shown on fig.4.

When solving problems in the system with either distributed or centralized DB in multi-user mode conditions, the number of tasks stored in base may be relatively large. This leads to the necessity to limit the number of tasks used for each specialization (application area) of the technology users. Therefore the classes of the tasks solved and standard tasks are grouped by application fields.

 

Task identifier		"Input Data" of the canonical task form				Task name	"To be Found" of the canonical task form
		Id.	Type	Name				Id.	Type	Name
NORMALFUNC		F	Function	Vector of Functions		Normalization of a vector of functions		FN	Function	Vector of normalized functions
WEIGHT	A	Q	Criterion	Vector of Criteria		Determination of criteria weights		W	Number	Vector of criteria weights
	B	Y	Number	Alternatives
IDEAL		Q	Criterion	Vector of Criteria		Definition of the objective (ideal alternative)		I	Number	Ideal alternative
DEVIATION	p;	Q	Criterion	Vector of Criteria		Definition of the maximum acceptable deviation from		DEL	Number	Maximum acceptable deviations from the objective for each
		I	Number	Ideal		the objective				criterion
OPTIMIZATION		Q	Criterion	Criterion of optimization		Search for an extremum of a multi-variable		XOPT	Number	Point of optimum
		X	Number	Variables		function		YOPT	Number	Best value
		C	Constraint	Limitations
CALCULATION		F	Function	The designed function		Calculation of the function in a point		Y	Number	Designed value
		X	Number	Point
WORSTCRIT		Q	Criterion	Vector of Criteria		Definition of criteria with
		Y	Number	Estimations of criteria		unsatisfactory estimates		Y1	Criterion	Vector of unsatisfactory criteria
		P	Number	Matrix of usefulness
USEFULNESS		Q	Criterion	Criteria		Creations of a matrix of usefulness		P	Number	Matrix of usefulness
		C	Constraint	Limitations
SATISALT		Q	Criterion	Vector of Criteria		Definition of a satisfactory alternative		TOL	Logical	Satisfactory
		Y	Number	Alternative
MARGINAL		N	Number	Number of Unsatisfactory Criteria		Definition of marginal coefficients of substitution
		Q	Criterion	Vector of Criteria				SIG	Number	Marginal coefficients
		Y	Number	Rating Matrix
DIRECTION		SIG	Number	Marginal Coefficients		Finding the function improvement direction
		Q	Criterion	Criterion				D	Number	Vector of direction
BEST		P	Number	Matrix of Usefulness		Definition of the best alternative in group		N	Number	Number of the alternative
EQUIVALENT		Q1	Criterion	First Criterion		Definition of equivalent change of a criterion		DQ2	Number	Increments of the second criterion
		Q2	Criterion	Second Criterion
		DQ	Number	First Criterion Increment
PARETO		Q	Criterion	List of Criteria		Construction of a Pareto set		P	Number	Set the Pareto
		WH	Number	High bound weights
		WL	Number	Low bound weights
CONVOLUTION		Q	Criterion	Vector of Criteria		Construction of a convolution of criteria		S	Function	The function of criterion
		W	Number	Weight of Criteria
COMPARISON		Q	Criterion	Vector of Criteria		Comparison of two alternatives		N	Number	Number of the best alternative
		A1	Number	First Alternative
		A2	Number	Second Alternative
LIMITATION		Q	Criterion	Limited Criterion		Overlay of limitation on value of a criterion		C	Constraint	Limitation
		L	Number	Limiting Value
SATISVALUE		Q	Criterion	Criterion		Definition of satisfactory value of a criterion
		Y	Number	Matrix of Usefulness				L	Number	Satisfactory value
		A	Number	Alternative
WORSTVALUE		Q	Criterion	Vector of Criteria		Definition of the worst values of criteria		B	Number	The worst values
SPLITTING		Q	Criterion	Vector of Criteria		Splitting set of criteria		Q1	Number	“Bad” criteria
		Y	Number	Matrix of Usefulness				Q2	Number	"Not Worsing" criteria
								Q3	Number	Worsing criteria

Fig. 5 Standard tasks of a multi-criteria choice

From the point of view of the content of processes proceeding in a technological system, its components interrelations are represented on fig.6.

Let's consider functions of some components present in the scheme.

"SA" - statement analyzer, a unit doing analysis of the particular task statement correctness and preparing the task for being solved. Once a user selected the task to be solved, its statement is formed, the statement analyzer is called up which, in case the statement is correct, selects methods (techniques) allowing to solve the source task. If among these methods for solution of the task a technique is selected, the interpreter is activated. SA will organize the method selection through the dialogue or by using the component called "expert". The way the method is selected depends on installations of the technological system.

"Interpreter" - a unit interpreting the technique type. It is the main unit for a problem solution using techniques. Once the instruction to solve the problem is received from the text, the interpreter, activates the statement analyzer (SA).

"Method Starter" - a unit either activating the interpreter (to solve a task a technique was selected) or loading a method in the main memory and starting its operation once the task input data have been transmitted.

"Expert" - a unit to select a task solution method (technique), provides recommendations on the basis of the user's system of preferences formed by statistical data.

"Technique Editor " - a multi-functional unit ensuring operation with techniques. Its functions: creation of techniques, extension of the standard tasks set, description of classes of the tasks solved, connecting the methods.

"AM" - analyzer of the technique syntactical correctness, prepares a technique for interpretation. In case of an error marks a technique as inaccessible for use.

For use within the frames of a described technology there is proposed a set of multi-criteria selection tasks represented on fig.5. The tasks are shown in the table where each of them is given a number and a name. Techniques generated on the basis of the given standard set represent flexible DSS to solve tasks of the selected class.