Материалы подготовлены лаб. 13
Зарубежная периодика по тематике ИПИ РАН
Выпуск № 1, апрель 2006 г.
Материалы подготовлены лаб. 13
Журнал Systems & Control Letters, Elsevier B. V
Volume 54, Issue 1, Pages 1-94 (January 2005)
Том 54, вып. 1 (Январь 2005 г.)
СТАТЬИ
1. Смешанное управление: вариант дискретного времени
Mixed control: the discrete-time case
рages 1-13, Riccardo Muradore and Giorgio Picci
Abstract : A stochastic and a mixed stochastic control problem for discrete-time systems are considered and solved. Conditions for existence of a solution are derived, based on the solvability of an equivalent minimax problem. In this framework, it is possible to consider at the same time both stochastic and deterministic disturbances highlighting their mutual effects. The controller can be designed by solving a system of three coupled Riccati equations. Such equations display how the - type minimization problem and the -type constraint influence each other.
Author Keywords: Discrete-time systems; Robust control; Stochastic control; Mixed control; Uncertain stochastic system
2. Дистанционное управление LTI системами посредством сетей с пошагово - изменяемым состоянием
Remote control of LTI systems over networks with state quantization
рages 15-31, Hideaki Ishii and Tamer Baar
Abstract We consider a remote control system, where the plant and the controller are connected by a network cable, and study the problem of designing quantizers for its stabilization. It is assumed that the computation available on the plant side in the sensor/actuator is limited and also that broadcast of messages is allowed over the channel.
Author Keywords: Asymptotic stability; Stability radius; Singular perturbation; Implicit systems; Index of matrix pencil
3. Встроенно-системный подход к определению робастной стабильности для класса сингулярно - возмущенных линейных систем
Implicit-system approach to the robust stability for a class of singularly perturbed linear systems
рages 33-41, Nguyen Huu Du and Vu Hoang Linh
Abstract Asymptotic stability and the complex stability radius of a class of singularly perturbed systems of linear differential-algebraic equations (DAEs) are studied. The asymptotic behavior of the stability radius for a singularly perturbed implicit system is characterized as the parameter in the leading term tends to zero. The main results are obtained in direct and short ways which involve some basic results in linear algebra and classical analysis, only. Our results can be extended to other singular perturbation problems for DAEs of more general form.
Author Keywords: Asymptotic stability; Stability radius; Singular perturbation; Implicit systems; Index of matrix pencil
4. Механизм отображения неизвестного параметра в системе плавного и адаптивного управления
A novel parameter projection mechanism for smooth and stable adaptive control
рages 43-51, Maruthi R. Akella and Kamesh Subbarao
Abstract A novel parameter projection technique for handling uncertain parameters with a priori available upper and lower bounds is the subject of this paper. It is a wellknown fact that the conventional parameter projection method employed in certainty equivalence adaptive control is able to guarantee global asymptotic stability only after compromising control smoothness. In contrast, the technique presented in this paper preserves both stability and smoothness guarantees for the closed-loop adaptive system. The novelty of the proposed adaptive control formulation comes through our deliberate introduction of a nonlinear re-parameterization of uncertainty, thereby amounting to a significant shift from the classical certainty equivalence methodology. The proposed controller is non-overparameterized and has the potential to significantly improve transient performance because of full and proper utilization of all the available prior information on the unknown parameters. The technical descriptions are further elaborated via the Duffing nonlinear oscillator example to highlight the advantages of this new approach.
Author Keywords: Nonlinear adaptive control; Smooth parameter projection; Nonlinear parametrization; Duffing oscillator
5. Сверточные коды с максимумом по профилю расстояния
Convolutional codes with maximum distance profile
pages 53-63, Ryan Hutchinson, Joachim Rosenthal and Roxana Smarandache
Abstract Maximum distance profile codes are characterized by the property that two trajectories which start at the same state and proceed to a different state will have the maximum possible minimum distance from each other relative to any other convolutional code of the same rate and degree.
In this paper we use methods from systems theory to characterize maximum distance profile codes algebraically. The main result shows that maximum distance profile codes form a generic set inside the variety which parametrizes the set of convolutional codes of a fixed rate and a fixed degree.
Keywords: MDS codes; Convolutional codes; Column distances; Feedback decoding; Superregular matrices
6. Некоторые результаты по регулируемости планарных вариационных неравенств
Some results on the controllability of planar variational inequalities
pages 65-71, Bernard Brogliato
Abstract This note deals with the controllability of a class of planar complementarity dynamical systems, which can also be viewed as planar evolution variational inequalities. It is shown that the complementarity conditions influence the controllability of the system a lot.
Keywords: Variational inequalities; Complementarity systems; Projected dynamics; Unilateral dynamics; Controllability
7. Условия существования непрерывных запоминающих функций для нелинейных диссипативных систем
Conditions for the existence of continuous storage functions for nonlinear dissipative systems
pages 73-81, I. G. Polushin and H. J. Marquez
Abstract The problem of existence of continuous storage functions for dissipative nonlinear systems is considered. It is shown that, if a nonlinear system is dissipative in the state x*, then, under certain assumptions, a continuous storage function can be constructed on a set of points accessible from x* by concatenation of a finite number of forward and backward motions of the system. Most of these assumptions are weaker than certain controllability-type properties and can be checked using similar tests.
Keywords: Dissipative systems; Storage functions; Nonlinear systems; Local w-uniform reachability; Weak accessibility
8. Лемма для негладких вещественных границ
A nonsmooth strict bounded real lemma
pages 83-94 M. R. James and I. R. Petersen
Abstract In the theory of linear H∞ control, the strict bounded real lemma plays a critical role because it provides a connection between the stabilizing solutions to the H∞ Riccati equations and the stability and disturbance attenuation of the closed-loop system. Nonlinear versions of the strict bounded real lemma are also important in nonlinear H∞ control theory. In this paper, we investigate the extension of the linear strict bounded real lemma and its smooth nonlinear generalization to cases where the solutions of the associated nonlinear PDE are not necessarily differentiable.
Keywords: Strict bounded real lemma; Nonlinear systems; Nonlinear H∞ control; Nonlinear robustness
Volume 54, Issue 2, (February 2005)
Том 54, вып. 2, Февраль 2005
СТАТЬИ
1. Итеративный подход к решению методом наименьших квадратов системы матричных уравнений Сильвестра
Iterative least-squares solutions of coupled Sylvester matrix equations
Ding, Feng; Chen, Tongwen, p95-107
Abstract: In this paper, we present a general family of iterative methods to solve linear equations, which includes the well-known Jacobi and Gauss–Seidel iterations as its special cases. The methods are extended to solve coupled Sylvester matrix equations. In our approach, we regard the unknown matrices to be solved as the system parameters to be identified, and propose a least-squares iterative algorithm by applying a hierarchical identification principle and by introducing the block-matrix inner product (the star product for short). We prove that the iterative solution consistently converges to the exact solution for any initial value. The algorithms proposed require less storage capacity than the existing numerical ones. Finally, the algorithms are tested on computer and the results verify the theoretical findings
2. О решении уравнения Сильвестра, появляющегося в теории дескрипторного управления системами
On the solution of a Sylvester equation appearing in descriptor systems control theory
Castelan, Eugênio B.; da Silva, Vilemar Gomes, p109-117
Abstract: The solution of a generalized Sylvester equation associated to a linear descriptor system and subject to some rank and regional pole-placement constraints, is studied in this paper. Under the hypothesis of strong-detectability of the descriptor system, a sequence of coordinate transformations is proposed such that the considered problem can be solved through a Sylvester equation associated to a detectable reduced-order normal system. Thus, solutions to this equation can be found either by eigenstructure assignment or by regional pole-placement in LMI-type regions of the complex plane. The proposed results are motivated from its use for designing minimal-order observers and for computing output feedback control laws by a particular technique. Some numerical results are reported and possible extensions for the proposed approach are commented.
3. О стохастических уравнениях Рикатти для решений в системе линейных и квадратичных уравнений Рикатти
On stochastic Riccati equations for the stochastic LQR problem
Zhu, Jinghao, p119-124
Abstract: This paper studies an approximation of stochastic Riccati equations for stochastic LQR problems some of which may be even with indefinite control weight costs.
4. Об алгебраической идентифицируемости отклика каналов для конечного импульса, порождаемого линейными предварительно кодированными сигналами
On the algebraic identifiability of finite impulse response channels driven by linearly precoded signals
Manton, Jonathan H.; Neumann, Walter D.; Norbury, Paul T., p125-134
Abstract: It is common in wireless communications to perform some form of linear precoding operation on the source signal prior to transmission over a channel. Although the traditional reason for precoding is to improve the performance of the communication system, this paper draws attention to the fact that the receiver can identify the impulse response of the channel without any prior knowledge of the transmitted signal simply by solving a system of polynomial equations. Since different precoders lead to different systems of equations, this paper addresses the fundamental issue of determining which classes of linear precoders lead to a system of equations having a unique solution. In doing so, basic properties of polynomial equations which are useful for studying other identifiability issues commonly encountered in engineering and the applied sciences are presented.
5. Сингулярная функция полезности Ханкеля для Шмитовских пар систем входа-выхода
Hankel singular value functions from Schmidt pairs for nonlinear input–output systems.
Gray, W. Steven; Scherpen, Jacquelien M. A., p135-144
Abstract: This paper presents three results in singular value analysis of Hankel operators for nonlinear input–output systems. First, the notion of a Schmidt pair is defined for a nonlinear Hankel operator. This makes it possible to define a Hankel singular value function from a purely input–output point of view and without introducing a state space setting. However, if a state space realization is known to exist then a set of sufficient conditions is given for the existence of a Schmidt pair, and the state space provides a convenient representation of the corresponding singular value function. Finally, it is shown that in a specific coordinate frame it is possible to relate this new singular value function definition to the original state space notion used to describe nonlinear balanced realizations.
6. Идентификация нелинейных систем, использующих кусочно-линейную модель Хаммерштейна
Identification of nonlinear systems using a piecewise-linear Hammerstein model
Dolanc, Gregor; Strmčnik, Stanko, p145-158
Abstract: In the paper a method for nonlinear system identification is proposed. It is based on a piecewise-linear Hammerstein model, which is linear in the parameters. The model and the identification algorithm are adapted to allow the parameter identification in the presence of a special form of the excitation signal. The identification method is derived from a recursive least-squares algorithm, which is properly adapted to take into account the proposed model structure and the properties of the identification signal. The applicability of the approach is illustrated by an example in which a discontinuous nonlinear static function is connected to a dynamic block.
7. Монотонные системы, охваченные положительной обратной связью: теорема мультистабильности и приведения
Monotone systems under positive feedback: multistability and a reduction : Enciso, German; Sontag, Eduardo D.. Systems & Control Letters, Feb2005, Vol. 54 Issue 2, p159-168
Abstract: For feedback loops involving single input, single output monotone systems with well-defined I/O characteristics, a recent paper by Angeli and Sontag provided an approach to determining the location and stability of steady states. A result on global convergence for multistable systems followed as a consequence of the technique. The present paper extends the approach to multiple inputs and outputs. A key idea is the introduction of a reduced system which preserves local stability properties.
8. Множественно-ориентированный подход к выбору оптимальной обратной связи стабилизации
A set oriented approach to optimal feedback stabilization.
Grüne, Lars; Junge, Oliver, p169-180
Abstract: We present a numerical construction of an optimal control based feedback law for the stabilization of discrete time nonlinear control systems. The feedback is based on a recently developed numerical solution method for optimal control problems using set oriented and graph theoretic algorithms. We show how this method can be used to construct approximately optimal and stabilizing feedback laws and present an a posteriori error estimation technique for the adaptive generation of the underlying set oriented space discretization.
Журнал IEEE Transactions on Computers
January 2005 (Vol. 54, No. 1) Январь 2005 (вып. 54, №1)
ISSN:
СТАТЬИ
1. Коды обнаружения ошибок: алгоритмы и быстрое исполнение
Error-Detection Codes: Algorithms and Fast Implementation
Gam D. Nguyen pp. 1-11
Abstract Binary CRCs are very effective for error detection, but their software implementation is not very efficient. Thus, many binary non-CRC codes (which are not as strong as CRCs, but can be more efficiently implemented in software) are proposed as alternatives to CRCs. The non-CRC codes include WSC, CXOR, one's-complement checksum, Fletcher checksum, and block-parity code. In this paper, we present a general algorithm for constructing a family of binary error-detection codes. This family is large because it contains all these non-CRC codes, CRCs, perfect codes, as well as other linear and nonlinear codes. In addition to unifying these apparently disparate codes, our algorithm also generates some non-CRC codes that have minimum distance 4 (like CRCs) and efficient software implementation.
Index Terms- Fast error-detection code, Hamming code, CRC, checksum
2. Алгоритм работы интегральных схем для модульного умножения\деления
A Hardware Algorithm for Modular Multiplication/Division
Marcelo E. Kaihara, Naofumi Takagi, IEEE, pp. 12-21
Abstract A mixed radix-4/2 algorithm for modular multiplication/division suitable for VLSI implementation is proposed. The algorithm is based on Montgomery method for modular multiplication and on the extended Binary GCD algorithm for modular division. Both algorithms are modified and combined into the proposed algorithm so that almost all the hardware components are shared. The new algorithm carries out both calculations using simple operations such as shifts, additions, and subtractions. The radix-2 signed-digit representation is used to avoid carry propagation in all additions and subtractions. A modular multiplier/divider based on the algorithm performs an n{\hbox{-}}{\rm bit} modular multiplication/division in O(n) clock cycles where the length of the clock cycle is constant and independent of n. The modular multiplier/divider has a linear array structure with a bit-slice feature and can be implemented with much smaller hardware than that necessary to implement both multiplier and divider separately.
Index Terms- Computer arithmetic, hardware algorithm, modular multiplication, modular division, redundant representation, cryptography.
3. Програмный кэш с отслеживанием
Software Trace Cache
Alex Ramirez, Josep L. Larriba-Pey, IEEE, Mateo Valero, IEEE, pp. 22-35
Abstract This paper explores the use of compiler optimizations which optimize the layout of instructions in memory. The target is to enable the code to make better use of the underlying hardware resources regardless of the specific details of the processor/architecture in order to increase fetch performance. The Software Trace Cache (STC) is a code layout algorithm with a broader target than previous layout optimizations. We target not only an improvement in the instruction cache hit rate, but also an increase in the effective fetch width of the fetch engine. The STC algorithm organizes basic blocks into chains trying to make sequentially executed basic blocks reside in consecutive memory positions, then maps the basic block chains in memory to minimize conflict misses in the important sections of the program. We evaluate and analyze in detail the impact of the STC, and code layout optimizations in general, on the three main aspects of fetch performance: the instruction cache hit rate, the effective fetch width, and the branch prediction accuracy. Our results show that layout optimized codes have some special characteristics that make them more amenable for high-performance instruction fetch: They have a very high rate of not-taken branches and execute long chains of sequential instructions; also, they make very effective use of instruction cache lines, mapping only useful instructions which will execute close in time, increasing both spatial and temporal locality.
Index Terms- Pipeline processors, instruction fetch, compiler optimizations, branch prediction, trace cache.
4. Локальная поддержка организации потока: энергосберегающий протокол распространения информации для беспроводных сенсорных сетей
Location-Aided Flooding: An Energy-Efficient Data Dissemination Protocol for Wireless Sensor Networks
Harshavardhan Sabbineni, IEEE, Krishnendu Chakrabarty, IEEE, pp. 36-46
Abstract We present a new information dissemination protocol for wireless sensor networks. This protocol uses location information to reduce redundant transmissions, thereby saving energy. The sensor network is divided into virtual grids and each sensor node associates itself with a virtual grid based on its location. Sensor nodes within a virtual grid are classified as either gateway nodes or internal nodes. While gateway nodes are responsible for forwarding the data across virtual grids, internal nodes forward the data within a virtual grid. The proposed approach, termed location-aided flooding (LAF), achieves energy savings by reducing the redundant transmissions of the same packet by a node. We study the performance of LAF for different grid sizes and different node densities and compare it to other well-known methods. We show that LAF can save a significant amount of energy compared to prior methods.
Index Terms- Communication protocol, location, energy management, information dissemination, flooding.
5. Расписание ориентации радара в режиме реального времени для фазированной антенной решетки с ориентированными элементами
Real-Time Dwell Scheduling of Component-Oriented Phased Array Radars
Tei-Wei Kuo, IEEE, Yung-Sheng Chao, Chin-Fu Kuo, Cheng Chang, pp. 47-60
Abstract A multifunction phased array radar must search and track suspicious targets in its surveillance space in a real-time fashion. With inefficient scheduling implementations in many traditional systems, much radar resource is wasted with a very limited performance gain. This paper targets one of the most important issues in the design of modern phased array radars: real-time dwell scheduling. We formalize the typical workload of a modern phased array radar and propose a rate-based approach to schedule radar dwells in a real-time fashion. We show how to reserve radar resources to guarantee the minimum radar operation without sacrificing the stability of the system. The strength of our approach is verified by a series of simulation experiments based on a real phased array radar for air defense frigates [9]. A significant improvement in the performance of phased array radars was shown.
Index Terms- Phased array radar, real-time dwell scheduling, rate-based scheduling, radar control computer.
6. Построение оптимальной детерминированной схемы разбиения (партишингс) в сканирующем встроенном блоке тестирования ошибок: математические принципы и реализация, отвечающие критерию «стоимость – эффективность»
The Construction of Optimal Deterministic Partitionings in Scan-Based BIST Fault Diagnosis: Mathematical Foundations and Cost-Effective Implementations
Ismet Bayraktaroglu, Alex Orailoglu, IEEE, pp. 61-75
Abstract Partitioning techniques enable identification of fault-embedding scan cells in scan-based BIST. We introduce, in this paper, deterministic partitioning techniques capable of resolving the location of the fault-embedding scan cells. We outline a complete mathematical analysis that identifies the class of deterministic partitioning structures and complement this rigorous mathematical analysis with an exposition of the appropriate cost-effective implementation techniques. We validate the superiority of the deterministic techniques both in an average-case sense by conducting simulation experiments and in a worst-case sense through a thorough mathematical analysis.
Index Terms- Fault diagnosis, scan-based BIST, finite field arithmetic.
Журнал Artificial Intelligence, Elsevier B. V
Feb2005, Vol. 162 Issue 1-2 Том 162 Выпуск 1-2 Февраль 2005
СТАТЬИ
1. Специальный выпуск по проблеме переформулирования, посвященный памяти Сола Амареля
Special Volume on Reformulation, dedicated to the memory of Saul Amarel
1928–: Ellman, T.. A
2. Предисловие к специальному выпуску по проблеме переформулирования
Introduction to the Special Volume on Reformulation
By: Ellman, Thomas.
3. Аппроксимации первого порядка наибольшей верхней границы: характеристика и алгоритмы
First order LUB approximations: characterization and algorithms
By: del Val, Alvaro.
Abstract: One of the major approaches to approximation of logical theories is the upper and lower bounds approach introduced by Selman and Kautz (1991, 1996). In this paper, we address the problem of lowest upper bound (LUB) approximation in a general setting. We characterize LUB approximations for arbitrary target languages, both propositional and first order, and describe algorithms of varying generality and efficiency for all target languages, proving their correctness. We also examine some aspects of the computational complexity of the algorithms, both propositional and first order; show that they can be used to characterize properties of whole families of resolution procedures; discuss the quality of approximations; and relate LUB approximations to other approaches existing in the literature which are not typically seen in the approximation framework, and which go beyond the “knowledge compilation” perspective that led to the introduction of LUBs
4. Логическое доказательство, основанное на разбиении, для первого порядка и теории высказываний
Partition-based logical reasoning for first-order and propositional theories
By: Amir, Eyal; McIlraith, Sheila.
Abstract: In this paper we show how tree decomposition can be applied to reasoning with first-order and propositional logic theories. Our motivation is two-fold. First, we are concerned with how to reason effectively with multiple knowledge bases that have overlap in content. Second, we are concerned with improving the efficiency of reasoning over a set of logical axioms by partitioning the set with respect to some detectable structure, and reasoning over individual partitions either locally or in a distributed fashion. To this end, we provide algorithms for partitioning and reasoning with related logical axioms in propositional and first-order logic. Many of the reasoning algorithms we present are based on the idea of passing messages between partitions. We present algorithms for both forward (data-driven) and backward (query-driven) message passing. Different partitions may have different associated reasoning procedures. We characterize a class of reasoning procedures that ensures completeness and soundness of our message-passing algorithms. We further provide a specialized algorithm for propositional satisfiability checking with partitions. Craig's interpolation theorem serves as a key to proving soundness and completeness of all of these algorithms. An analysis of these algorithms emphasizes parameters of the partitionings that influence the efficiency of computation. We provide a greedy algorithm that automatically decomposes a set of logical axioms into partitions, following this analysis.
5. Технические условия проблемы компиляции для теста пропозиционной выполнимости
Compiling problem specifications into SAT
By: Cadoli, Marco; Schaerf, Andrea.
Abstract: We present a compiler that translates a problem specification into a propositional satisfiability test (SAT). Problems are specified in a logic-based language, called np-spec, which allows the definition of complex problems in a highly declarative way, and whose expressive power is such as to capture all problems which belong to the complexity class NP. The target SAT instance is solved using any of the various state-of-the-art solvers available from the community. The system obtained is an executable specification language for all NP problems which shows interesting computational properties. The performance of the system has been tested on a few classical problems, namely graph coloring, Hamiltonian cycle, job-shop scheduling, and on a real-world scheduling application, namely the tournament scheduling problem.
6. Проблемно-зависимое качественное абстрактное представление доменов разбиений
Task-dependent qualitative domain abstraction
By: Sachenbacher, M.; Struss, P.
Abstract: Automated problem-solving for engineered devices is based on models that capture the essential aspects of the behavior. In this paper, we deal with the problem of automatically abstracting behavior models such that their level of granularity is as coarse as possible, but still sufficiently detailed to carry out a given behavioral prediction or diagnostic task. A task is described by a behavior model, as composed from a library, a specified granularity of the possible observations, and a specified granularity of the desired results. The goal of task-dependent qualitative domain abstraction is to determine maximal partitions for the variables' domains (termed qualitative values) that retain all the necessary distinctions. We present a formalization of this problem within a relational (constraint-based) framework, and devise solutions to automatically determine qualitative values for a device model. The results enhance the ability to use a behavior model of a device as a common basis to support different tasks along its life cycle.
7. К построению практической теории переформулирования для доказательств в отношении физических систем
Towards a practical theory of reformulation for reasoning about physical systems
By: Choueiry, Berthe Y.; Iwasaki, Yumi; McIlraith, Sheila.
Abstract: Reformulation is ubiquitous in problem solving and is especially common in modeling physical systems. In this paper we examine reformulation techniques in the context of reasoning about physical systems. This paper does not present a general theory of reformulation, but it studies a number of known reformulation techniques to achieve a broad understanding of the space of available reformulations. In doing so, we present a practical framework for specifying, classifying, and evaluating various reformulation techniques applicable to this class of problems. Our framework provides the terminology to specify the conditions under which a particular reformulation technique is applicable, the cost associated with performing the reformulation, and the effects of the reformulation with respect to the problem encoding.
