OPTIMIZING THE PARAMETER POLLING ORDER USING DYNAMIC PROGRAMMING

Yu. M. Ageev, V. I. Konovalov, S. P. Revina

(Presented by the Scientific and Technical Seminar of the Department of Automation
and Telemechanics)

A single device polls \(n\) parameters that have pairwise distinct static characteristics. The polling order remains unchanged from cycle to cycle. It is required to determine an optimal, in the sense of the selected criterion, order for polling the parameters under the condition of limited switching speed of the commutator.

Let us introduce some notation:

\(x_i\) — the monitored parameters, \(i=(1,n)\);

\(h_{i0},\ h_{i()}\) — the admissible numbers of quantization intervals of the \(i\)-th parameter;

\[ \varepsilon_{ij}=\frac{\Delta x_j}{\Delta h_{i0}} \]

— the relative instability of the quantization interval.

The remaining notation is given in [1].

The method for finding the parameter polling order proposed in [1] is sufficiently simple and can be used in preliminary calculations. However, the polling order determined in this way will not be optimal.

Various indicators may be chosen as the optimality criterion. In the present work, the quantity

\[ C=\sum_i^n \sum_j^{\gamma i} \varepsilon_{ij}^{2} \]

is adopted as such a criterion.

Consequently, the problem of finding the optimal polling order is the problem of finding values of \(x_i\) that minimize the objective function \(C\).

The difficulty of solving it as a quadratic programming problem lies in the fact that it is multiextremal. Without dwelling on an analysis of the possibilities of applying nonlinear programming methods, let us consider an iterative method for solving the problem.

Suppose that some arbitrary polling order of the parameters is known. For this order the value of the criterion is computed as

\[ C_1=\sum_i^n \sum_j^{\gamma i} \varepsilon_{ij}^{2}. \]

By rearranging some parameters, another polling order is found, for which \(C_2 < C_1\). Then a third parameter polling order and the corresponding index \(C_3 < C_2\) are considered, and so on. The procedure is repeated until the minimum value of the criterion \(C\) is obtained. The trivial way of obtaining a new polling order—simple enumeration of all possible variants—is completely unacceptable, since already for \(N_0 \geqslant 10\) the problem becomes practically unsolvable.

Let us define some concepts used below. A shift operation consists in the fact that some parameter previously connected to the \(p\)-th position of the commutator is connected to the \(q\)-th position. If \(p > q\), then all parameters connected to the positions lying between \(p\) and \(q\) are shifted by one position in the direction of increase. If \(p < q\), then these parameters are shifted by one position in the direction of decrease.

A transposition operation consists in the fact that two different parameters connected to different positions of the commutator exchange places. The admissible numbers \(h_{i0}\) and \(h'_{i0}\) express the number of commutator positions between two positions of one and the same parameter and are determined by the formula

\[ h_{i0}=\left[\frac{N_i}{\gamma_i}\right]; \qquad h'_{i0}=h_{i0}+1, \]

where the square brackets denote rounding to the nearest integer. The admissible numbers characterize the uniformity of the quantization interval. If \(h_{ij}=h_{i0}\) or \(h_{ij}=h'_{i0}\) for all parameters, then \(C=\min\), and the polling order is optimal.

The essence of the proposed method is as follows:

1. By the method described in [1], the initial polling order is found.

2. For each parameter, \(h_{ij}\), \(h_{i0}\), \(h'_{i0}\) are determined.

3. Priority is established in placing the parameters by the positions of the commutator. Higher priority is assigned to parameters with larger \(\gamma\), since the same instability of the quantization interval, expressed by the number of commutator positions, for parameters with larger \(\gamma\) leads to an increase in \(C\).

4. Using the shift operation, we obtain such an arrangement of parameter \(i=n\) with \(\gamma=\gamma_{\max}\) over the commutator positions that the condition

\[ \Delta h_{nj}=h_{n0}\quad \text{or}\quad \Delta h_{nj}=h'_{n0} \]

is satisfied.

1. For parameters with \(\gamma=\gamma_k\), where \(k=n-1;\ n-2;\ \ldots,\ 1\), applying the transposition operation, equality is obtained:

\[ \Delta h_{kj}=h_{k0}\quad \text{or}\quad \Delta h_{kj}=h'_{k0}. \]

Since, when comparing any two polling orders, the values of the index \(C\) are computed and subsequently only the order with the smaller \(C\) is considered, the described process is convergent.

The method is convenient for implementation on a digital computer. The algorithm for determining the optimal parameter polling order is shown in Fig. 1. The algorithm is divided into 7 blocks. Blocks 1–4 require no additional explanation. In block 5, the largest deviations of the intervals \(\Delta h_{ij}\) are found. The \(\Delta h_{ij}\) \((i=n,\ j=\overline{1,\gamma_{\max}})\) are compared with \(h_{i0}\). If \(\Delta h_{ij}-h_{i0}=0\), then \(\Delta h_{ij}\) is an admissible number; proceed to the next \(\Delta h_{ij}\). If \(\Delta h_{ij}-h_{i0}<0\), and consequently also \(\Delta h_{ij}-\Delta h_{i0}<0\), then the smaller, modulo, of these differences is stored: \(\Delta=\Delta h_{ij}-h_{i0}\). Proceed to the next comparison of \(\Delta h_{ij}\). If \(\Delta h_{ij}-h_{i0}>0\), then \(\Delta_1=\Delta h_{ij}-h_{i0}=0\) is checked.

If equality holds, it is obvious that \(\Delta h_{ij}\) is an admissible number; proceed to the next comparison. If \(\Delta_1>0\), the smaller (modulo) difference is stored. Next, the maximal \(\Delta\) and \(\Delta_1\) are found and stored. Block 6 performs the shift operation. Three cases are possible:

1. \(\max |\Delta|=0;\ \max |\Delta_1|\ne 0\).

One parameter from the critical interval \(\Delta h_{ij}\) is taken in turn, placed to the left of the parameter \(i=n\) with the maximum deviation \(\Delta_1\), \(C\) is computed and compared with the previous value of \(C\).

Fig. 1

For further consideration, the polling order corresponding to the smaller value of \(C\) is adopted. If a smaller \(C\) has not been obtained, proceed to block 7.

1. \(\max |\Delta|\ne 0;\ \max |\Delta_1|=0\).

Parameters are included one by one in the critical interval, starting with the one of lower priority, with \(|\Delta| \ne 0\), thereby increasing it, i.e., bringing it closer to the required one. Each time, \(C\) is computed until the smallest value is obtained; the corresponding polling order is recorded, after which one proceeds to block 5; otherwise, to block 7.

\[ \text{3. } \max |\Delta| \ne 0; \quad \max |\Delta_1| \ne 0 \]

In this case it is advisable, while decreasing \(\Delta_1\), simultaneously to increase \(\Delta\). Parameters are selected in turn from the larger interval and placed into the smaller one; each time the indicator \(C\) is computed and compared with the previous one. Subsequently, the polling order corresponding to the smaller criterion \(C\) is considered, and one proceeds to block 5. If there is no smaller \(C\), one proceeds to block 7.

Block 7 performs the transposition operation. The parameter corresponding to the largest deviation of the quantization interval is selected and placed successively in the positions of those parameters that have lower priority, starting with the lowest of them. The indicator \(C\), computed each time, is compared with the preceding value. If the new value of \(C\) is smaller, the corresponding polling order is accepted and one proceeds to block 5. Otherwise, the transposition operation continues until all parameters have been enumerated. The last value of \(C\) obtained will be minimal, and the polling order optimal. By this algorithm, parameter-polling programs were found for all cases in which \(\gamma_{\max} \le 10\).

REFERENCES

1. Yu. M. Ageev, V. I. Konovalov. On the polling order of parameters in centralized-control systems. Present collection.