Vol 21, No 1 (2022)
Digital information telecommunication technologies
Mathematical Model and Algorithm of Branch and Boundary Method for Optimizing Solutions for Package Compositions in Multi-Stage Systems
Abstract
Modern methods for solving problems of planning of task packages execution in multi-stage systems are characterized by the presence of restrictions on their dimension, the impossibility of obtaining guaranteed best results in comparison with fixed packages for different values of the input parameters of tasks. The problem of optimizing the composition of task packages executed in multi-stage systems using the method of branches and borders is solved in the paper. Studies of various ways of forming the order of execution of task packages in multi-stage systems (heuristic rules for ordering task packages in the sequences of their execution on MS devices) have been carried out. The method of ordering packets in the sequence of their execution (a heuristic rule), which minimizes the total time for implementing actions with them on the devices, is defined. The method of ordering the types of tasks, according to which their packages are considered in the procedure of the method of branches and borders, is formulated on the basis of the obtained rule. A mathematical model of the process of implementing actions with packages on the system devices, which provides the calculation of its parameters, has been built. The construction of a method for forming all possible solutions for the composition of task packages for a given number of them has been completed. Decisions on the composition of task packages of different types are interpreted in the procedure of the method of branches and borders in order to build the optimal combination of them. To implement the method of branches and borders, a branching (splitting) procedure is formulated, which assumes the formation of subsets of solutions that include packages of different compositions of tasks of the same type. Expressions for calculating the lower and upper estimates of the values of the optimization criterion for the composition of packages for subsets formed in the branching procedure are constructed. The dropout procedure involves the exclusion of subsets whose lower estimate is not less than the record. To find optimal solutions, a breadth-first search strategy is applied, which provides for the study of all subsets of solutions that include various packages of tasks of the same type obtained as a result of the procedure for splitting subsets of tasks that are not excluded from consideration after the implementation of the dropout procedure. The developed algorithms are implemented programmatically, which allowed to obtain the results of planning the execution of task packages in a multi-stage system, which are on average 30 % better than fixed packages.
Informatics and Automation. 2022;21(1):5-40
5-40
On the Expediency and Possibilities of Approximating a Pure Delay Link
Abstract
When solving problems of controlling an object with delay, it is often necessary to approximate a pure delay link with a minimum phase link in order to ensure the possibility of using analytical methods for regulator design. There are many approximation methods based on the Taylor series expansion, as well as modified methods. The most famous one is the Padé approximation method. The known approximation methods have significant drawbacks, which this paper reveals. However, there are other methods of forming other types of filters that can serve as a better approximation in determining the delay relationship, although they are not used for these purposes. In particular, methods of forming the desired differential equation of a locked-loop system of a given order by the method of numerical optimization are known. In this case, the locked-loop system behaves like a filter of the corresponding order, the numerator of which is equal to one, and the specified polynomial is in the denominator. Modeling has shown that such a filter is an effective alternative approximation of the delay link and can be used for the same purposes for which it was supposed to use the Padé approximation. The polynomial coefficients in the literature were calculated only up to the 12th order. The higher the polynomial order is, the more accurate the approximation is.
Informatics and Automation. 2022;21(1):41-67
41-67
Theoretical Aspects in Forming Complex Structure Signal
Abstract
Receiving and transmitting paths of modern radio communication systems are built on the basis of an open structure that provides hierarchical differentiation of access to the provided telecommunication services. However, this approach does not exclude the possibility of access to the transmitted content by unauthorized users. Hiding information by methods of cryptographic protection in such a situation only activates additional interest in transmission, therefore the most pragmatic solution is to use signals of a complex structure, which significantly complicate or even exclude the extraction of information from them by third-party users. The problem of regulating access selection in the development and design radio system elements is rather multifaceted and has a high degree of complexity. One of the directions for solving problems in this subject area is based on the well-known approaches to expanding the signal base, however, algorithms for their practical implementation were obtained without taking into account the limitations on the allocated resource and the very fact of using these algorithms. Based on the theory of systems and the general theory of communication, an approach to the formation of signal structures of a complex structure has been developed, which ensures an increase in the properties of their structural secrecy in relation to unauthorized users. At the same time, the known solutions at the physical level of signal spaces were refined, which made it possible to formalize the procedures for the formation of radio signals with specified properties. The method of formalizing the function of displaying the signal space based on the allocation of stochastic properties of pseudo-random sequences has been substantiated, which made it possible to ensure the uncertainty of their structure in case of unauthorized processing. The approbation of the proposed approach is given on the example of the formation of quadrature modulation signals, taking into account the subsequent analysis of their properties from various positions of legitimate and illegitimate users. The results obtained confirm the uncertainty during illegitimate processing with a slight deterioration in the noise immunity properties of radio communication systems. In general, this allows to conclude the adequacy of theoretical solutions. As an example, constellation diagrams of signals at the output of a quadrature receiver are presented. The set of proposed technical solutions presented in the work determines the novelty of this approach. The scientific problem to be solved belongs to the class of problems of synthesis of signals of complex structures.
Informatics and Automation. 2022;21(1):68-94
68-94
Properties of Harmonic and Composite Half-Waves, Determination of the Uniform Time Sampling Interval of Digital Signal Processors
Abstract
When building autonomous real-time systems (RTS), it is necessary to solve the problem of optimal multitasking loading of a number of parallel functioning digital signal processors. One of the reserves for achieving the desired result is the implementation of samples from the sensor signals of information about the magnitude of the signal most rarely in time. In this case, it is necessary to provide a linear or stepwise approximation of the signal by samples with an acceptable reconstruction error. One of the system tasks of these processors is filtering signals or limiting the spectrum to the cutoff frequency. A distinctive feature of the approach proposed in the article is the fulfillment of the condition: if the measurement of this frequency is difficult (for example, in the electromechanical means of the RTS), then for such signals it is proposed to match the maximum values of the harmonic half-wave parameters: approximation error, speed and acceleration. The study opens up the prospect of applying new approaches to sampling the time of signals in the amplitude-time domain and determining the equivalent cutoff frequency of the signal spectrum for such signals. In this article, the dependences of the value of the unit of system time for input-output of data on the degree of agreement between the maximum values of the signal parameters are obtained. A mathematical model of the extreme behavior of a signal between two adjacent samples is given in the form of a harmonic half-wave. The study is also extended to convex composite harmonic functions, according to which the signal can deviate from the results of a linear or stepwise approximation of the signal for these samples. The comparison of the models by the value of the relative time sampling intervals, depending on the degree of matching of the maximum parameters of the harmonic half-wave, is carried out. When comparing, in addition to these maximum parameters, the relationship of the maximum signal speed with the error of approximating the samples by steps and the relationship of the maximum acceleration of the signal with the maximum error of the linear approximation was taken into account. The results make it possible to determine the duration of the intervals of uniform sampling of the signal time based on the results of the inspection of the control object, substantiate a significant increase in the sampling interval of time or a similar increase in the number of tasks to be solved per unit of system time.
Informatics and Automation. 2022;21(1):95-125
95-125
Artificial intelligence, knowledge and data engineering
Hybrid Network Structures and Their Use in Diagnosing Complex Technical Systems
Abstract
An approach to the technical diagnostics of complex technical systems based on the results of telemetry information processing by an external monitoring and diagnostics system using hybrid network structures is proposed. The principle of constructing diagnostic complexes of complex technical systems is considered, which ensures the automation of the technical diagnostics process and is based on the use of models in the form of hybrid network structures for processing telemetric information, including multilayer neural networks and discrete Bayesian networks with stochastic learning. A model of changes in the parameters of complex technical systems technical state based on multilayer neural networks has been developed, which makes it possible to form a probabilistic assessment of attributing the current situation of complex technical system functioning to the set of functions considered situations according to individual telemetry parameters, and multilevel hierarchical model of complex technical systems technical diagnostics based on a discrete Bayesian network with stochastic learning, which allows aggregating the information received from neural network models and recognizing the current situation of complex technical system functioning. In the conditions of functioning emergencies of the complex technical system, according to the results of processing telemetric information, faulty functional units are localized and an explanation of the cause of the emergency is formed. The stages of complex technical systems technical diagnostics implementation using the proposed hybrid network structures in the processing of telemetric information are detailed. An example of using the developed approach to solving problems of spacecraft onboard system technical diagnostics is presented. The advantages of the proposed approach to the technical diagnostics of complex technical systems in comparison with the traditional approach based on analysis of telemetry parameters values belonging to the given tolerances are shown.
Informatics and Automation. 2022;21(1):126-160
126-160
Polynomial Approximations for Several Neural Network Activation Functions
Abstract
Active deployment of machine learning systems sets a task of their protection against different types of attacks that threaten confidentiality, integrity and accessibility of both processed data and trained models. One of the promising ways for such protection is the development of privacy-preserving machine learning systems, that use homomorphic encryption schemes to protect data and models. However, such schemes can only process polynomial functions, which means that we need to construct polynomial approximations for nonlinear functions used in neural models. The goal of this paper is the construction of precise approximations of several widely used neural network activation functions while limiting the degree of approximation polynomials as well as the evaluation of the impact of the approximation precision on the resulting value of the whole neural network. In contrast to the previous publications, in the current paper we study and compare different ways for polynomial approximation construction, introduce precision metrics, present exact formulas for approximation polynomials as well as exact values of corresponding precisions. We compare our results with the previously published ones. Finally, for a simple convolutional network we experimentally evaluate the impact of the approximation precision on the bias of the output neuron values of the network from the original ones. Our results show that the best approximation for ReLU could be obtained with the numeric method, and for the sigmoid and hyperbolic tangent – with Chebyshev polynomials. At the same time, the best approximation among the three functions could be obtained for ReLU. The results could be used for the construction of polynomial approximations of activation functions in privacy-preserving machine learning systems.
Informatics and Automation. 2022;21(1):161-180
161-180
A SLAM system based on Hidden Markov Models
Abstract
Methods of simultaneous localization and mapping (SLAM) are a solution for the navigation problem of service robots. We present a graph SLAM system based on Hidden Markov Models (HMM) where the sensor readings are represented with different symbols using a number of clustering techniques; then, the symbols are fused as a single prediction, to improve the accuracy rate, using a Dual HMM. Our system’s versatility allows to work with different types of sensors or fusion of sensors, and to implement, either active or passive, graph SLAM. A graph-SLAM approach proposed by the International’s Karto Robotics in Cartographer, the nodes represent the pose of the robot and the edges the constraints between them. Nodes are usually defined according to contiguous nodes except when loop closures are detected where constraints for non-contiguous nodes are introduced, which corrects the whole graph. Detecting loop closure is not trivial; in the ROS implementation, scan matching is performed by Sparse Pose Adjustment (SPA). Cartographer uses an occupancy map in order to estimate the position where the map representation is done via Gmapping. The Toyota HSR (Human Support Robot) robot was used to generate the data set in both real and simulated competition environments. In our SLAM representation, we have wheel odometry estimate according to initial position of the robot, a Hokuyo 2D Lidar scan for observations, and a signal control and a world representation is estimated. We tested our system in the kidnapped robot problem by training a representation, improving it online, and, finally, solving the SLAM problem.
Informatics and Automation. 2022;21(1):181-212
181-212