image001.gif

 

Contents

 

Granichin O.N. (SPbSU) What is the actual structure of complex information-control systems? 3

Kuchumov R. I. (PetrSU) Implementation and analysis of work-stealing task scheduler20

Malkovsky N. V. (SPbSU) Stochastic network flow processes

40

Senin I. (SPbSU) A randomized algorithm for processing ultrasound diagnostics data 87

Khlebnikov M. V. (ICS RAS) Extertnal estimation of reachability sets for linear dynamical systems 112

Bykov A. V., Scherbakov P. S. (ICS RAS) A nonconvex matrix sparsity detector with applications to optimal control of linear systems 123

 

Abstracts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

 

 

 


ABSTRACTS

What is the Actual Structure of Complex Information-Control Systems?

O. N. Granichin

Saint Petersburg State University

o.granichin@spbu.ru

 

Key words: clustering, self-organizing, adaptive systems, multi-agent systems, time-varying state space structure, airplane with “feathers”.

 

The paper describes the main underlying features of the author’s new RNF project which is aimed at the development of model predictive adaptive control with time-varying state space structure.

 

In the recent years, control of multi-agent robotic systems has received a great deal of attention in science and technology. The miniaturization and increased computing power of sensors and actuators can further extend the range of applicability of the results of modern control, identification, and estimation theories. In particular, theoretical issues of adaptive control in changeable environment and under time-varying structure of the state space have been only marginally considered so far due to the limited ability of practical realization, and require more attention.

 

Use of traditional mathematical models of motion of systems with a large number of transducers / sensors and actuators often leads to very complex problems involving extremely high-dimensional state spaces. The multi-agent technology can eectively solve many of the problems arising in this context by replacing the general model of interaction with a complex system having multiple local models and their aggregation (clustering). In this paper, for the case of time-varying structure of the wind disturbances, we extend our previous results on synchronization and consensus in the network control theory toward the flight control when a vast array of sensors and actuators (“feathers”) is distributed over the surface of an airplane. We study the possibilities of using Local Voting Protocol for the adaptations of airplane’s feathers in a turbulence flow.

 

Bibliogr.: 14 refs.


 

 

 

 

 

 

Implementation and Analysis of Work-stealing Task Scheduler

R. I. Kuchumov

Petrozavodsk State University

kuchumovri@gmail.com

 

Key words: Task schedulers, work-stealing, deques, concurrent computing, multithreading.

 

Concurrent work-stealing task schedulers yield near-optimal task distribution and also have low execution times, memory, and synchronization overhead. The essence of this strategy is that when a processor runs out

 

of tasks to execute, it starts to steal tasks from other processors. One of the drawbacks of this strategy is a large number of steals when dealing with relatively small tasks. This paper presents an implementation of a work-stealing task scheduler that allows to take more than one task per single steal operation. With this modification, the total number of steals can be significantly reduced.

 

Bibliogr.: 14 refs.

 

Stochastic Network Flow Processes

N. V. Malkovsky

Saint Petersburg State University malkovskynv@gmail.com

 

Key words: network flow, stochastic systems, optimal control, capacity constraints.

 

Network flow processes are being intensively analyzed for many decades. Such processes emerge naturally when the dynamics of a system is subject to so-called capacity constrained. These type of constrains may represent a variety of situations from the width of the road to the speed of communication channels in information networks. In this paper, one class of such flow problems is discussed. A general description of the problem is as follows: How can we transit the system from one state to another in a minimum possible time by applying a flow process? Methods for both deterministic and stochastic cases are presented and analysed in detail.

 

Bibliogr.: 51 refs.

 

 

 

 

A Randomized Algorithm for Processing Ultrasound Diagnostics Data

I. Senin

 

Saint Petersburg State University i.senin@2012.spbu.ru

 

Key words: compressive sensing, ultrasound tomography, travel time tomography, randomized measurements.

 

Ultrasound tomography has been successfully applied in medical diagnostics, in particular, in breast cancer diagnostics. The progress in technologies allows for a significant increase in the amount of sensors used within imaging devices; this leads to a rapid growth of data to be processed. On the other hand, tomography images are known to have has sparse representation. According to the recently developed theory of Compressive Sensing (CS), it is possible to recover such kind of images from undersampled data. In this paper, an improved reconstruction algorithm for travel time tomography is proposed, which utilizes image sparsity for CS. Numerous experiments show that the developed algorithm exposes the same performance (quality of images) while using considerably less amount of data.

 

Bibliogr.: 31 refs.

 

Extertnal Estimation of Reachability Sets for Linear Dynamical Systems

M. V. Khlebnikov

 

Institute of Control Sciences RAS mkhlebnikov2008@yandex.ru

 

Key words: Linear dynamical system, reachability set, invariant ellispoid, linear matrix inequalities.

 

Simple extertnal estimates of reachability sets for linear dynamical systems are proposed. They are represented as the intersection of inva-riant ellispoids, whose number is less then the dimension of the system. The explicit relations for the determination of such ellipoids is given. A numerical exapmle is analyzed.

 

Bibliogr.: 12 refs.

 

 

 

A Nonconvex Matrix Sparsity Detector with Applications to Optimal Control of Linear Systems

A. V. Bykov

 

P. S. Shcherbakov

 

Institute of Control Science

 

alexey.bykov.mipt@gmail.com

 

cavour118@mail.ru

 

Key words: linear systems, sparse feedback, H-optimization, LMIs, DC-functions, CCCP.

 

In [8], an approach to sparse feedback design in linear control systems was proposed, leading to row/column sparse controller gain matrices, i.e., those containing zero rows/columns. To solve this problem, a special matrix norm was considered such that it was used as a convex surrogate for the inherently nonconvex original problem. The contribution of this current paper is twofold. First, we propose a dierent surrogate which shows itself more ecient, though also being nonconvex. Second, we extend the original approach toward the classical H-optimization problem. A heuristic in support of the eciency of the new surrogate is given and numerical examples are presented that testify to a better performance of the new method.

 

Bibliogr.: 19 refs.