ABSTRACTS
Randomized
Algorithms
New Randomized Algorithms in Control and Data
Processing
K. S Amelin, O. N.
Saint Petersburg
Oleg_granichin@mail.ru, konstantinamelin@mail.ru
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
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
Key words: system of linear algebraic equations,
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.
Filtering
Software Engineering of Unmanned Aerial Vehicle for
Mobil Autonomous Group
K. S Amelin
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
dmitry00@gmail.com, alexander.vakhitov@gmail.com
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,
kbkedr@tula.net, pwmru@rambler.ru
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,
kbkedr@tula.net, pwmru@rambler.ru
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
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
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
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
nkk@math.spbu.ru, nevolga@gmail.com
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
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
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.