Randomized Algorithms

Amelin K.S., Granichin O.N. (SPbSU) New randomized algorithms in control and data processing

Morozkov M.A. (SPbSU) Fast algorithm for finding true number of clusters in a large data set

Smirnov S.I. (SPbSU) A quasirandomized method for solving systems of linear equations


Amelin K.S. (SPbSU) Software engineering of unmanned aerial vehicle for mobile autonomous group

Krivokon D.S., Vakhitov A.T. (SPbSU) Non-stationary optimization with prediction step for object tracking with two cameras

Ponyatskiy V.M. (KBP, Tula) Identification of non-stationary dynamic plants by a method of invariant embedding over a fixed interval

Ponyatskiy V.M. (KBP, Tula) The minimax approach to the design ofmthe interval Kalman filter

Multi-Agent Systems

Amelina N.O. (SPbSU) Multi-agent technology, adaptation, self-organization, consensus

Parsegov S.E. (ICS R.AS, Moscow) Generalized linear algorithms for formation control

Discrete Stochastic Systems

Trubnikov V.N., Tchirkov M.K. (SPbSU) Representability conditions of generalized regular languages by stochastic automata

Krivulin N.K., Nev O.A. (SPbSU) Asymptotic properties of state vector in a generalized linear stochastic dynamical system with symmetric matrix

Information Systems

Pavlenko D.V. (SPbSU) Syntax element matching in version control systems

Shats V.N. (SPb) A stochastic method for classification and training





Randomized Algorithms

New Randomized Algorithms in Control and Data Processing

K. S Amelin, O. N. Granichin

Saint Petersburg State University,

Key words: randomized algorithms, optimization and estimation, control.

Randomization allows one to enrich the observation data and design speedy algorithms significantly reducing the number of operations and annihilating systematic errors (the bias effect of an arbitrary noise). Their accuracy usually weakly depends on the data dimension.

A randomized algorithm is nothing but a procedure where one or more steps are based on a random rule, that is, when using a randomized algorithm, at some stage instead of making a decision ourselves we call on fate to choose for us. But then, a question arises naturally: why should resorting to fate be any wise? Fate is not an expert of anything, all it does is choosing by chance. So, why should randomized be any good? A conscious use of randomized methods demands to question ourselves about this issue, and this paper contains some answers on this question. An exposition of randomized algorithms and their application are given.

Bibliogr.: 86 refs.



Fast Algorithm for Finding True Number of Clusters in a Large Data Set

M. A. Morozkov

Saint Petersburg State University

Key words: clustering, randomized algorithms, adaptive control, optimization, machine learning.

One of the most difficult problems in cluster analysis is the identification of the number of groups in a given data set. In this paper we propose a randomized approach in the rate distortion framework and devise the corresponding randomized algorithm. The fundamental ideas of novel scenario approach are used in order to significantly reduce the computational cost. Having the ability to determine the true number of groups in a data set and perform clustering online, we outline several applications to control systems and decision-making problems that can essentially benefit from the considered algorithm. Simulation results show considerable improvement of the rate of convergence under the guaranteed level of probability.

Bibliogr.: 25 refs.



Quasirandomized Method for Solving of Linear Equation Systems

S. I. Smirnov

Saint Petersburg State University

Key words: system of linear algebraic equations, Monte Carlo method, Quasi-Monte Carlo method, stochastic approximation.

As it is known, finding a root of the equation F (x) = 0 or extrema of the function G (x) from the measurements of F and G corrupted by random noise can be implemented via use of stochastic approximation methods.

Of the great applied interest is the case where the above-mentioned values are calculated by the Monte-Carlo method. In particular, if it is required to solve a large system of the linear algebraic equations, it is possible to reduce computational burden by using randomization or designing unbiased estimates for the sum of squares of the adjustments (we choose random equations from n, where < n). Specifically, Quasi-Monte Carlo (QMC) methods might be very useful in simulations.

In this paper we present stochastic approximation algorithms for solving large systems of linear algebraic equations and discuss the advantages of using QMC for these problems.

Bibliogr.: 8 refs.




Software Engineering of Unmanned Aerial Vehicle for Mobil Autonomous Group

K. S Amelin

Saint Petersburg State University

Key words: unmanned aerial vehicles, UAV, navigation system, autopilot, actuators, autonomous group of UAV, software engineering.

The control system architecture for an unmanned aerial vehicle (UAV) is considered which guarantees its proper functioning in an autonomous UAV group. The prototype of this newly created UAV is described. Flight optimization approaches are described.

Bibliogr.: 31 refs.



Non-stationary Optimization with Prediction Step for Object Tracking with Two Cameras

D. S. Krivokon, A. T Vakhitov

Saint Petersburg State University,

Key words: non-stationary optimization, object tracking, stereo-camera.

The paper presents an application of a non-stationary randomized optimization method with prediction step to the problem of tracking an object from noisy readings of the two calibrated perspective cameras. Over the examples, the algorithm outperforms previously proposed non-stationary randomized optimization. The paper contains both theoretical justification and simulation.

Bibliogr.: 19 refs.



Identification of Non-stationary Dynamic Plant by a Method of Invariant Immersing on the Fixed Interval

V. M. Ponyatskiy

KBP, Tula,

Key words: identification, dynamic plant, parameters, discrepancy, signal, noise, model, reverse time.

A nonlinear method of invariant embedding is used in this paper for identification of non-stationary dynamic plants. With the proposed approach, the initial conditions for the estimated parameters can be refined via use of identification algorithms in reverse time. An inverse time estimation algorithm for the non-stationary parameters of a dynamic plant is designed and analyzed.

Bibliogr.: 5 refs.


Synthesis of the Interval Kalman Filter on the Basis of the Minimax Approach

V. M. Ponyatskiy

KBP, Tula,

Key words: dynamic plant, filtering, signal, noise, estimation.

An approach is proposed to interval Kalman filter both in continuous and discrete time. The interval Kalman filter is designed and compared to the conventional Kalman filter. The analysis of the results shows that the minimax filter provides a better accuracy of estimation while retaining the properties of the cojventional Kalman filter.

Bibliogr.: 3 refs.



Multi-Agent Systems

Multi-agent Technology, Adaptation, Self-organization, Consensus

N. O. Amelina

Saint Petersburg State University

Key words: multi-agent systems, multi-agent control, self-organization, adaptation, consensus, workload balancing network.

The paper presents a brief introduction to the multi-agent technology which focuses on the two important fields, namely, multi-agent systems in computer science and multi-agent control in a new control theory. Multi-agent technology is also deeply connected with decentralized and parallel computation, network communications and other related areas. The considerations are supplied by examples of self-organization and adaptation in a logistic problem and network workload balancing algorithm.

Bibliogr.: 42 refs.



Generalized Linear Algorithms for Formation Control

S. E. Parsegov

Institute of Control Sciences of RAS, Moscow

Key words: multi-agent systems, formation control.

In recent years, a new framework for systems to be handled appeared which is based on decentralized cooperative control using simple, identical, cooperating subsystems named agents. Such systems are referred to as multi-agent systems. In this paper, some linear algorithms that extend and generalize the known results for formation control are proposed. As the first step, the algorithms of allocation of a group of agents on a segment are considered, stability criteria and convergence analysis results are presented.

Bibliogr.: 8 refs.


Discrete Stochastic Systems

Representing Conditions

of Generalized Regular Languages

by Stochastic Automata

V. N. Trubnikov,

M. K. Tchirkov

Saint Petersburg State University

Key words: stochastic finite automata, generalized regular languages, representation of generalized languages by automata, synthesis of automata in accordance with a regular expression of language.

The paper presents analysis and substantiation of necessary and sufficient conditions for the representation of generalized regular languages defined over the field of real numbers by stochastic finite automata. A stochastic automaton satisfying these conditions is designed from a regular expression of the generalized language. An example is given.

Bibliogr.: 7 refs.



Asymptotic Properties of State Vector

in a Generalized Linear Stochastic Dynamical

System with Symmetric Matrix

N. K. Krivulin, O. A. Nev

Saint Petersburg State University,

Key words: stochastic dynamical system, Lyapunov exponent, idempotent semiring, convergence in distributions.

The paper examines stochastic dynamical systems described by a linear vector equation with second-order symmetric matrix in an idempotent semi-ring with operations of maximum and addition. It is assumed that the diagonal of the matrix consists of a nonnegative random variable and zero, whereas both off-diagonal elements are equal to a nonnegative constant. A problem of calculating the mean asymptotic growth rate of system state vector (the Lyapunov exponent) is considered. The solution includes change of variables resulting in new random variables that appear to be more suitable for analysis than the random coordinates of the state vector. Furthermore, for the new random variables, corresponding sequences of one-dimensional probability distributions are constructed and their convergence is examined. The Lyapunov exponent is calculated as the mean value of the limiting distribution for one of the sequences.

Bibliogr.: 10 refs.


Information Systems

Syntax Elements Matching in Version Control Systems

D. V. Pavlenko

Saint Petersburg State University


The paper presents a formulation of the matching problem for file syntax elements. Solution of this problem facilitates better description of the modifications performed over the stored file contents and efficient solution of the conflict problem.

Bibliogr.: 9 refs.


Stochastic Method of Solving Problems of Classification and Training

V. N. Shats

St. Petersburg

Key words: information environment, classification problem, expansion of initial information, stochastic algorithm.

A stochastic method is proposed for the solution of classification and training problems. A continuous mapping of the set of points represented by objects with noisy data is considered, which generates a matrix that, under certain conditions, retains the properties of the objects in the original matrix. This mapping is implemented as a continuous multivariable function obtained in the information environment theory developed by the author. By varying random parameters of this function, an ensemble of matrices can be obtained. These enrich the initial information and reduce the corresponding problem to statistical evaluation of the deterministic solutions for individual matrices computed through a uniform algorithm.

Bibliogr.: 10 refs.