|
Krivokon D.S. (SPbSU) Randomization-based position estimation
system for moving objects using camera motion.
. . . . . . . . . .3 Prodanov T.P. (SPbSU) Adaptive Randomized Algorithms for Community Detection in Graphs.
. . . . . . . . . . . . . 29 Kaliteevskiy V. N. (SPbSU) Communication method for decentralized network of autonomous group of
mobile robots. . . . . . . . . . . . . . 77 Senov A. A.
(SPbSU) Improving distributed
stochastic gradient descent estimate via loss function approximation.
. . . . . . . . . . . . . 103 Abstracts
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 |
ABSTRACTS
Randomization-based position estimation system for moving
objects using camera motion
D.
S. Krivokon
Key
words: randomization, depth estimation, dynamical systems.
We propose a system for reconstructing the position of
moving objects based on use of
video camera. Randomized algorithms are at the core of this system; they are based on arbitrary camera motion
and allow for the estimation of the position
of the object under general conditions. The paper presents a description of the
system, results of real-time experiments, and formal proof of convergence of
the estimation algorithm.
Bibliogr.: 22 refs.
Use of randomized algorithms for
processing information signals in aircraft control
V.
M. Ponyatskiy
KBP,
kbkedr@tula.net, pwmru@rambler.ru
Key words: Kalman filter, system, automatic tracking.
We consider aircraft
control systems where the formation of the control actions are implemented on
the basis of the measured data signals. Kalman filtering algorithms are widely
used to filter out the Gaussian noise. In the works of O. Granichin, use of
randomized algorithms is considered for filtering random processes with
measuring offset. The paper presents both continuous and discrete algorithms
and extrapolation of the measured coordinates obtained in the framework of Kalman filtering methods; these are intended to
be used in closed-loop control. Experiment performed in Matlab and the analysis
of the results show that the system designed with a randomized algorithm
processes the input signal and is insensitive to noises, as opposed to systems
with Kalman filter, wherein the output coordinate monitors not only the input
signal, but also a low frequency component of the noise measurement.
Bibliogr.: 7 refs.
Adaptive
Randomized Algorithms for Community Detection in Graphs
T.P.
Prodanov
Key words: community detection, complex
networks, stochastic approximation.
During the
last seventeen years, the study of complex networks has grown rapidly, and
search of tightly connected groups of nodes, or community detection, proved
to be powerful tool for analyzing real systems.
Randomized algorithms
for community detection are effective but there
is no “universal” parameters that make these algorithms perform good partitions
for every input complex network. In
article, we propose to apply a simultaneously perturbed stochastic approximation to randomized algorithms and
propose two new adaptive modifications that adjust the parameters to the input
data and provide good partitions for a wider range of input networks.
Bibliogr.: 26 refs.
Mathematical Models
and Methods of Optimal Control of Work-stealing Deques in Shared Memory
E.
A. Barkovsky
Karellian
Scientific Center RAS
Key words: work-stealing, deques, data
structures, Markov chains, random walks.
In this paper
we propose mathematical models and solve the problems of optimal partitioning of shared memory
for work-stealing deques and finding the optimal number of elements to “steal”.
Operations have probabilistic characterization and, along with sequential
execution, it is possible to execute
operations on deques in parallel.
Bibliogr.: 14 refs.
Edges of Finite Automata as a Tool for the Description
of Algorithms for Constructing Waterloo-like Automata
V. N.
Dolgov
Togliatti
State University
N. V.
Sofonova
Key words: nondeterministic finite automata,
minimization algorithms, universal automaton, basis automaton, full automaton.
As
it is well known, algorithms of minimization of nondeterministic finite
automata may be complicated by the constructions for certain automata as in the
example by Kameda and Weiner; these were referred to as Waterloo automata.
Where possible, such a construction should be built automatically on the basis
of the Waterloo automaton by using the so-called full automaton for the
corresponding language before applying the said algorithms to the state
minimization of nondeterministic finite automata. This paper considers a
pre-requisite for such a construction, the comparison of the edges of full
automaton with those of the universal automaton as well as those of the basis
automaton.
Bibliogr.: 14 refs.
Communication
Method for Decentralized Network of Autonomous Group of
V.
N. Kaliteevskiy
Key words: multi-agent systems, group interaction, load balancing, checksum calculation, communication, architecture
of mobile robots.
A method of communication
and maintenance of integrity of a decentralized
network of autonomous mobile robots is explored in this paper, as well as the software and hardware
feasibility of such a method. For collective data storage in a group of mobile
robots, it is proposed to use checksum algorithms, which balance the load of
computing nodes. For the programming implementation of the communication
of data, multi-agent technology is used. An
ultra light unmanned aerial vehicle (UAV) is used as the mobile robot.
Bibliogr.: 21 refs.
Improving
Distributed Stochastic Gradient Descent Estimate via Loss Function
Approximation
A.
A. Senov
Key words: large scale optimization, stochastic
optimization, parameter estimation, parallel algorithms, distributed
algorithms, stochastic gradient descent, least-squares estimation.
At present, the problems of learning and optimization in the context
of huge amounts of data has became very
important. Unfortunately, even online and parallel optimization methods may
fail to handle such amounts of data and fit the time limits. In this case,
distributed optimization methods may be the only tool to provide a solution to the
problem. In this paper we present a review of the state-of-the-art of the
distributed optimization methods and consider
a particular case of the optimization problem with separable
stochastic quadratic loss function.
We propose two algorithms which are substantially based on the method
mentioned. Finally we experimentally demonstrate the superiority of the proposed algorithms over the
known ones.
Bibliogr.: 20 refs.