A measurement system expert configurator for the optimum assignment of series-parallel connectable devices

Measurement 11 (1993)97-105 Elsevier

97

A measurement system expert configurator for the optimum assignment of series-parallel connectable devices A. Langella a, G. Betta a and P. Arpaia b aDepartment of Cornputer Science, bDepartment of Electrical Engineering, University of Naples 'Federico II ', Naples, Italy Abstract. In the computer-aided configuration of measurement systems, one encounters the problem of the optimum assignment of series parallel connectable devices. This paper proposes the setting up of an expert system-based solution, applicable to any of these types of device. It also discusses a developed prototype, capable of choosing the optimum configuration for a complex d.c. power supply system. Thus, to attain desired performances, the user is aided in either choosing new devices or configuring an existing supply system. Keywords. Intelligent measurement; Expert system; Optimum configuration

1. Introduction A computer-integrated manufacturing approach has become more and more widespread under current factory management practice, and requires the automation of all activities related to "product genesis" [1,2]. Electrical and electronic measurement are present to a great degree in the production process, and many stimulating projects and prototypes have been developed concerning all aspects of the measurement process [3]. Among these a great deal of attention has been paid to the computer-aided design and engineering of measurement systems [4-6]. In this ambit, C.R.I.A.I. and the University of Naples, relying on previous experience [7,8], have begun to develop an "intelligent" laboratory in which expert system (ES) modules supervise the different phases of a measurement process, thus helping or substituting the measurer in this complex task [9]. Among the different measurer activities [10] surely one of the most troublesome is choosing the most appropriate configuration for a particular application. In fact, in a complex measurement process, remarkable skill is required to perform this activity, since the choice involves knowledge not only of different measurement methods but also of the characteristics of the instruments available on the market 0263-2241/93/$05.00 © 1993 - Elsevier Science Publishers B.V. All rights reserved

98

A. Langella et al. / Measurement system expert configurator

and/or in the laboratory [11,12]. Making the right choice is the first step towards correct final measurement results. A particular configuration problem arises with instruments and components that can be connected to each other (resistances, d.c. and a.c. supplies, etc.). In this case the choice has to be made not only from the available apparatus but also from any combination of the available apparatus. This problem can be very complex if one considers, for example, that with only 10 different resistors, and restricting combinations to no more than 3 of them, 580 possible configurations can be obtained. The high number of possible solutions strongly suggests non-exhaustive searching. In practice, the searching method is often based on empirical experience or common sense, and also accepts solutions that are not absolute optimum ones. The goal is in any case to design a system which is easily implementable, extendable and maintainable. The peculiarities of the solving method of the problem under analysis strongly suggest an ES approach. In fact an ES-based solution is characterized by the following features: (a) the ability to carry out the search by scanning first the solutions with higher probabilities of success (thus allowing a non-exhaustive search); (b) the ability to stop the search as soon as a satisfactory solution has been found (an absolute optimum is not always required); (c) the ease with which the rules on the correct employment of resources as well as on the choice criteria can be formulated, extended and maintained. This paper proposes a knowledge-based solution to the optimum assignment problem for series-parallel connectable devices. The ES design is described in detail with particular reference to the knowledge base structure and the problem solving strategy. Finally the prototype set up to automatically configure a d.c. power supply section is discussed.

2. Expert system design The project was developed according to the following phases: problem definition, informal knowledge base description, problem solving strategy definition, and, finally, choice of the most suitable software tool for implementation. 2.1. P r o b l e m definition

The first step towards correct development of the project as a whole is to identify the problem kernel, mainly in terms of required inputs, ES task and system outputs. Choosing the optimum configuration in an environment, such as a measurement laboratory, is a typical multi-user problem. However, it can be subdivided into the following sub-problems:

A. Langella et al. / Measurement system expert configurator

99

(a)

choice of the optimum configuration for a specified set of requirements from a given data base of series-paralM connectable devices; (b) management of the conflicts between different service requests. Sub-problem (b) was neglected in the first prototype, because it can easily be reduced to a succession of single-user problems by successively applying a suitable priority strategy among the different requests. Thus, the required inputs are the desired configuration parameter values (for example resistor resistance, current, power and accuracy or d.c. power supply voltage, current, power and drift). A meaningful further step is to focus on both the problem class and the ES typology, by analysing those present in the literature [13]. The problem class is "synthesis", that is the search for a solution in a certain space. As regards typology, the ES is designed to substitute the expert, allowing however an interaction in the decision making activity if specifically requested. The problem kernel thus is the following: "Given a data base of series-parallel connectable devices and having specified the desired configuration parameter values (for example, resistor resistance, current, power and accuracy, or d.c. power supply voltage, current, power and drift) the ES has to determine the optimum configuration with few user interactions".

2.2. Informal knowledge-base description To reduce development time, system dimensions, and consultation time, great attention was paid to the knowledge-base design. In particular a KB structure which avoids an exhaustive representation of all possible configurations was built up, based on the definition of both an elementary structure and the criteria for obtaining all possible configurations from it. Every configuration, regardless of complexity, is characterized by the same configuration parameters as an elementary device. Each configuration can thus be called a "generalized device" and is related to two other configurations obtained by adding one more element either in series or in parallel. Relying on such a basic structure, the set of possible solutions can be organized in a tree, the "configuration tree", whose nodes are all generalized devices (see Fig. 1). This organization only requires both the basic structure and the rules to obtain any series and parallel "son" to be represented. To be included in a possible solution, a device must satisfy some constraints -(!>

Fig. 1. Configuration tree.

100

A. Langella et al. / Measurement system expert configurator

which depend on user requirements and on the configuration in which it has to be included. Also in this case, rather than listing and representing all the constraints of each device of each node, some suitable "inheritance" rules were identified allowing such constraints to be easily worked out starting from the root node. In particular three constraint categories can be pointed out on the basis of the inheritance type: (i) "convergent constraint" (A-type): the father constraint is stronger than that of the sons thus allowing more devices to be suitable for the solution (for example voltage constraint for series-connected resistances); (ii) "divergent constraint" (B-type): the father constraint is weaker than that of the sons (typically the accuracy constraint); (iii) "constant constraint" (C-type): the constraint is inherited without any modification (for example voltage constraint for parallel-connected resistances). On this basis, another tree, the "constraint tree", was built up, whose nodes contain the conditions that must be satisfied by the devices in the corresponding configuration tree node.

2.3. Problem solving strategy The criteria chosen to optimize resource exploitation are: (a) minimizing the number of devices employed; (b) using devices working in conditions close to nominal ones. Moreover, it is usually possible to identify a further criterion (c), depending on the particular device under analysis, choosing whether series or parallel connections should be preferred. On the basis of these criteria, a two-phase searching strategy was developed: (i) "superficial navigation" of the configuration tree so as to single out nodes containing potential solutions; (ii) "deep navigation" to locate the best solution for the specific node of the configuration tree.

2.3.1. Superficial navigation Criteria (a) and (c) simply direct the scanning of the configuration tree of Fig. 1: it is navigated breadthwise from left to right (series connection preferred to parallel) or from right to left (parallel connection preferred to series) starting from the root node. In order to single out nodes containing a potential solution, a superficial navigation searches for "instantiable" nodes. A node is said to be instantiable if the elements available in the device data base have nominal characteristics which correspond to the requirements for a particular configuration. To aid this instantiability evaluation, the device data base is divided into different subsets on the basis of the order relations between the requirement characteristics and the corresponding nominal values of each device. These subsets are dynamically updated as soon as a requirement variation occurs during thedeep navigation, as is described in

A. Langella et al. / Measurement system expert configurator

101

the following section. With reference to these subsets, a third tree, the "auxiliary tree", was built up, whose nodes specify the search subset for each element of the corresponding node in the configuration tree. This auxiliary tree is used to establish the condition necessary for a certain node of the configuration tree to be instantiable. A deep navigation is carried out for each instantiable node, in order to choose optimum devices. If a satisfactory solution is found, the consultation ends; otherwise the next possible configuration is searched for by reactivating the superficial navigation. In any case, the consultation ends when all the possible configurations have been investigated.

2.3.2. Deep navigation Whenever the superficial navigation of the configuration tree indicates a configuration which can provide a solution, the best set of devices is chosen on the basis of suitable "coefficients". These were defined according to optimization criterion (b), namely in terms of suitable "distances" between the solution parameters and the requested ones. "Acceptable distances" were fixed for each coefficient on the basis of c o m m o n experience. It can occasionally be useful to identify distance values where acceptance is conditioned by a user decision, thus allowing user/ES interaction. The search for the best solution of a configuration is performed by optimally choosing the last added device (higher identification number in the configuration tree, see Fig. 1) and by iterating this process thus reverting back to the root node. This optimum device is the one that minimizes the "distance" to the target; when selected, it is memorized in a stack. The current configuration is then turned to the father-node, once the problem requirements are updated on the basis of the nominal parameters of the chosen device. It is important to note that this requirement change dynamically affects the previously defined device subsets. The optim u m configuration is completely identified when both the following conditions occur: the actual node is the root one and the search is successful. If the search for the ( N + l ) t h element fails, the Nth one is removed from the stack and, if possible, substituted. If the actual node is the last one added and the search fails, the deep navigation in that node finishes and the superficial navigation is reactivated to point out a new potential solution. The search can fail since the instantiability rules, obtained from comparing both auxiliary tree and data-base contents, provides only the necessary but not the sufficient condition for the existence of a solution. If the search succeeds, the chosen coefficients are determined and the solution, contained in the stack, is shown to the user who can then decide whether or not to continue investigating further configurations. 2.4. Choice of the tool On the basis of an informal description of the knowledge base and the problem solving strategy, it was possible to single out the main features that the shell must have, namely:

102

A. Langella et al. / Measurement system expert configurator

(i) (ii)

rule-based knowledge representation; ability to implement a mixed searching strategy (forward and backward chaining); (iii) ability to describe hierarchical structures; (iv) ease of access to external procedures and data-bases; (v) ability to run on personal computers. Commercially-available shells were surveyed and evaluated, and Knowledge Engineering System, KES 1-14] was found to meet the highlighted needs.

3. Prototype description The developed prototype configures a complex d.c. power supply system. Based on the characteristics of most of the power supplies available on the market, they were supposed to feature continuous regulation of both voltage and current within their nominal ranges. Furthermore, they can be connected in series or in parallel. These features render several solutions feasible, once of course the user has specified his needs, and assuming that several power supplies are available. The following configuration parameters were chosen: output voltage (Vo), output current (Io), and output drift (Do). On this basis the constraint tree of Fig. 2 can be easily built up. It is possible to notice that the drift always represents a B-type constraint, while the requirement of voltage and current are of type A or C on the basis of the relationship between father-node and son-node (series or parallel son). For example, when adding a series device, only the voltage constraints become weaker while the new element has to satisfy the same current limits as the father device.

m>_v° i=1..2~ Int + In2 ~ I° / D.I + Dn2< DO)

V1 + V2_> Vo-~ >I o i=1..2 I nl + Dn2 Io

I

i=l..~ /minlInl'In2l+In3--> I° |

min{V rVn2}+Vn3_>Vo-~ (V a > Vo i= 1..3"~ I'l+I"2>I°; I"3>I° / lln,+In2+I~>I°l Dnl-I-Dn2 + Dn3-~ ~ Do )

Fig. 2. Constraint tree.

~nl+Dn2+Dn3-- Vo AND I. >~Io}; PS2 = {power supplies: V, < Vo AND In/> Io}; PS3 = {power supplies: V. ~> Vo AND I. < Io}; PS4 = {power supplies: V, < Vo AND I. < Io}. The ratio of the total nominal power of the devices in the configuration versus the output power required was chosen as the distance coefficient. The latter, which is representative of the quality of a possible solution, can be expressed: C o = ~ (VniI.i)/(Volo)

(~>1 by definition)

i

Three solution evaluation bounds were defined: Coe[1,2] =~ acceptance; Coe]2,10] =~ conditional acceptance; Co>10 =~ refusal. As far as the drift constraint is concerned, it does not explicitly appear in the optimization process, since it merely causes a dynamic shrinking of the effective data base. The ES obtained consists of 60 rules, 42 attributes, 2 classes and 2 external procedures. Figure 4 shows, as an example, the formal description of the class d.c. power supply and a typical consultation scheme. In order to better clarify how deep navigation operates, a node-2 deep navigation is described in detail with reference to Fig. 4(b). In this case, when the system did not find any device capable of satisfying the task by itself, it proceeded to examine the node-2 configuration (two power supplies connected in series). First a 40 V-10 A device was chosen as the best device in the subset PS2. In this way the new problem requirements became 10 V-10 A; they had to be satisfied by a power supply in the updated PSI subset, for example a 30 V-20 A power supply. The -

104

A. Langella et al. / Measurement system expert configurator

Name : power supply K i n d of entity: Class Definition: attributes: model: str.

(a)

\identifier, different for each power supply \rated v o l t a g e \rated current \rated drift \subset

Vn: real. In: real. Dn: real. IA: PS. Score V: real [defaUlt: Vn/Vo]. Score I: real [default: In/Io]. Score P: real [default: Score_V'Score_I]. busy: truth [default: false]. good: truth [default: true]. optimum: truth [default: true]. stack_pos: int. \current p o s i t i o n solution stack level inibition: int.

in the

% endclass.

r e q u i r e d V O L T A G E [V] 50 r e q u i r e d CURRENT [A] i0 r e q u i r e d DRIFT [%] 0.1 NO S O L U T I O N IN NODE 1 IN NODE 2 P o s s i b l e solution: S(ps40-10,ps30-20) Co=2 Do you want to continue ?: Y IN NODE 3 P o s s i b l e solution: P(ps76-6/l,ps76-6/2) C0=l.8 Do you want to continue ?: Y IN NODE 4 S O L U T I O N WORSE THEN IN NODE 2 Do you want to see it?: N IN NODE 5 Possible solution:P(ps76-6,S(ps25-4/l,ps25-4/2) Do you want to continue ?: N

(b)

Input Input Input

Co=l. 3

Fig. 4. (a) Formal description of the class "power supply". (b) Example of consultation.

configuration coefficient was thus easily computed and shown to the user, who decided whether or not to continue the search.

4. Conclusions An ES-based solution to the problem of the optimum assignment of series-parallel connectable devices was proposed and set up, identifying the most appropriate knowledge structure and problem solving strategy.

A. Langella et al. / Measurement system expert configurator

105

A prototype allowing the automatic optimum configuration of a complex d.c. power supply system was then set up. Its performance, in terms of reliability and consultation speed, confirms the validity of the knowledge base structure as well as the solving method set up. Furthermore, the short time necessary to tailor the prototype, owing to the structured approach and to the essential formalization of an algorithmically complex problem, encourages continuation of the project and its use in an industrial environment. In the latter context, it allows an easy choice of the optimum configuration for existing devices or for ones that are to be purchased. It could also be upgraded to manage the setting-up on-line of the chosen configuration by adding modules for automatic circuit connections. These features can be provided only by adding a highly flexible switch matrix to the measurement station, thereby rendering all the possible configurations feasible. The developed ES will become part of EGEMES, a multi-module expert system for the generation of measurement specifications [9].

References [1] M. Groover, Automation, Production Systems and CIM, Prentice-Hall, Englewood Cliffs, NJ, 1987. [-2] H. Hellwig, The importance of measurement in technology-based competition, IEEE Trans. Instrum. Meas. 39(5) (1990) 685-688. [3] J. Weiler, Industrial measurement of electrical and electronic components, Measurement, 7(1) (1989) 7-12. [4] P.H. Hammond, Computer aided design for control and instrumentation - - A review, Meas. Control 19 (1987) 277-286. [5] P.H. Sydhenam, A. Skinner and R.W. Beijer, Do-it-yourself measurement and control CAE package, Meas. Control 21 (1988) 69-75. [6] M.K. Mirza, F.J.R. Neves and L. Finkelstein, A knowledge-based system for design-concept generation of instruments, Measurement 8(1) (1990) 7 11. [7] G. Betta and A. Pietrosanto, Knowledge base of an expert system for induction motor testing, Proc. lnt. Conf. on Electrical Machines, Pisa, Italy, 1989, pp. 1-6. [8] G. Betta and A. Pietrosanto, An expert system for induction motor testing, Proc. Western Simulation Conf., San Diego, CA, 1990, pp. 89-94. [-9] A. Langella, P. Arpaia and G. Betta, Design of an expert generator of measurement specification, Proc. X I ! IMEKO World Congress, Pekino, China, 1991. [10] G. Zingales, C. Narduzzi and C. Offelli, The role of artificial intelligence in measurement, Proc. lnt. Syrup. on Artificial Intelligence Based Measurement and Control, Kyoto, Japan, 1991. [ l l ] L. Finkelstein and M.S. Leaning, A review of the fundamental concepts of measurement, Measurement 2 (1984) 25-34. [12] P.H. Sydhenam, Structured understanding of the measurement process, Parts 1 and 2, Measurement 3(3) (1985) 115-120; 3(4) (1985) 161-168. [13] F. Hayes-Roth and D. Waterman, Building Expert Systems, Addison-Wesley, Reading, MA, 1983. [14] KES Knowledge base author's manual (PS), A&E Software, 1989.