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
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
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
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.
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.