The balance problem of min–max systems is co-NP hard

Min–max systems are timed discrete event dynamic systems containing min, max and plus operations. A min–max system is balanced if it admits a global cycle time (generalized eigenvalue) for every possible assignment of parameters. This paper proves that the testing of the balance property for min–max systems is co-NP hard by showing that the test of inseparability is co-NP hard. The latter result is established on a new complexity result, namely, that the testing of existence of non-trivial fixed points for monotone Boolean functions is NP-complete.     

The stochastic interdependence of dynamic risk-sensitive decision rules

Certainty-equivalent decisions are risk neutral with respect to the uncertainty about outcomes. This paper examines risk-sensitive decisions which optimize a combination of the first two moments of a stochastic objective. These decisions are shown to be stochastically inseparable with respect to time, and cannot be fully optimized by recursive techniques such as dynamic programming. An example in economic planning shows that this inseparability property can have considerable significance in practice     

两类模糊系统具有插值性的充要条件

当模糊系统具有插值性时,它必具有泛逼近性.因此,由插值性可以分析模糊系统的逼近能力.本文讨论了由“交”和“并”的方式聚合推理规则所生成的两类模糊系统的插值性问题.首先,通过分析由“单点”模糊化方法、CRI(com positional ru le of inference)算法以及“重心法”构造的模糊系统,指出模糊系统是否具有插值性关键取决于模糊蕴含算子的第二个变量为0和1时的表达式或取值.在此基础上,得到两类模糊系统具有插值性的充要条件.最后给出了满足这两个充要条件的一些常用的蕴涵算子.     

Nonlinear state affine identification methods: Applications to electrical power plants

A nonlinear identification method by simple state-space models is proposed in the discrete-time case. This approach is suggested by theoretical results similar to the approximation property known for a long time for Volterra series. The proposed technique uses extensions with polynomial inputs of bilinear systems called state-affine systems. This modelling requires a small computing time and enables us to obtain nonlinear models which can be easily implemented on microprocessors and remain valid over a wide range of operating conditions. Several physical examples concerning electric power plants are also reported.     

基于分布式神经动态优化的综合能源系统多目标优化调度EI北大核心CSCD

研究了基于神经动态优化的综合能源系统(Integrated energy systems,IES)分布式多目标优化调度问题.首先,将IES元件单元(包含负荷)作为独立的决策主体,联合考量其运行成本和排放成本,并计及多能源设备间的传输损耗,提出了IES多目标优化调度模型,该模型可描述为一类非凸多目标优化问题.其次,针对此类问题的求解,提出了一种基于神经动力学系统的分布式多目标优化算法,该算法基于动态权重的神经网络模型,可以解决不可分离的不等式约束问题.该算法计算负担小,收敛速度快,并且易于硬件实现.仿真结果表明,所提算法能同时协调综合能源系统的经济性和环境性这两个冲突的目标,且获得了整个帕累托前沿,有效降低了综合能源系统的污染物排放量和综合运行成本.     

Spatiotemporal inseparability in early vision: centre-surround models and velocity selectivity

Several computational theories of early visual processing, such as Marr's zero-crossing theory, are biologically motivated and based largely on the well-known difference of Gaussians (DOG) receptive-field model of retinal processing. We examine the physiological relevance of the DOG, particularly in the light of evidence indicating significant spatiotemporal inseparability in the behaviour of retinal cell types. From the form of the inseparability we find that commonly accepted functional interpretations of retinal processing based on the DOG, such as the Laplacian of a Gaussian and zero crossings, are not valid for time-varying images. In contrast to current machine-vision approaches, which attempt to separate form and motion information at an early stage, it appears that this is not the case in biological systems. It is further shown that the qualitative form of this inseparability provides a convenient precursor to the extraction of both form and motion information. We show the construction of efficient mechanisms for the extraction of orientation and two-dimensional normal velocity through the use of a hierarchical computational framework. The resultant mechanisms are well localized in space-time and can be easily tuned to various degrees of orientation and speed specificity.     

Diagnosability of delay-deadline failures in fair real time discrete event models

In this article a method for failure diagnosis of real time discrete event systems (RTDES) with ‘fairness of traces’ has been developed. Discrete event system (DES) modelling framework with provision for associating timing information with the transitions are required for handling real time systems. RTDES models and timed DES (TDES) models are examples of such modelling frameworks. Failure diagnosis in untimed DES models enables only the study of diagnosability of failures resulting in a change in the logical behaviour of the failed system. In addition to logical failures, failure diagnosis in RTDES and TDES models also enables diagnosability of failures that change the timing behaviour of the system but maintain the logical behaviour. Many systems exhibit fairness of traces with respect to transitions in the sense that any trace that visits a state infinitely often has infinitely many occurrences of all the transitions that emanate from that state. The abstraction employed in obtaining their (timed) DES models often obliterates this property. The RTDES and TDES diagnosability conditions, proposed in the literature and which do not consider fairness, are shown to be inadequate in this article. A new diagnosability condition is achieved by taking into account this fairness property in the RTDES models and shown to be necessary and sufficient for such systems. An analysis of time complexity for analysing the diagnosability of systems with fairness of traces is presented.     

Evaluating part designs for automatic feeding in robotic assembly systems: A geometric analysis of the nesting of polyhedral objects

One of the problems encountered by automatic feeding devices, such as vibratory bowl feeders, in robotic assembly systems is nesting which leads to inseparability of parts and jamming. In this paper, we describe a design evaluation procedure to determine whether a part is prone to nesting and to quantify the degree of nesting. The proposed methodology reduces the 3-D protrusion-hole polyhedral containment problem of nesting to a 2-D polygon containment problem by employing a loop-based feature recognition scheme. Subsequently, the 3-D containment configuration is reconstructed from that of the 2-D by using a strategy calleddrop, pull and push. In this context, we introduce the notion of axis as a characteristic direction of a feature that facilitates the analysis of generalized 3-D polyhedral containment. The algorithms are applicable to generic B-Rep CAD data, and their time and space complexities are polynomial.     

Probabilistic Boolean network modeling of an industrial machine

Theoretical modeling of manufacturing processes assists the design of new systems for predictions of future behavior, identifies improvement areas, and evaluates changes to existing systems. A novel approach is proposed to model industrial machines using probabilistic Boolean networks (PBNs) to study the relationship between machine components, their reliability and function. Once a machine is modeled as a PBN, through identification of regulatory nodes, predictors and selection probabilities, simulation and property verification are used to verify model correctness and behavior. Using real machine data, model parameters are estimated and a PBN is built to describe the machine, and formulate valid predictions about probability of failure through time. Two models were established: one with non-deterministic inputs (proposed), another with components’ MTBFs inputs. Simulations were used to generate data required to conduct inferential statistical tests to determine the level of correspondence between predictions and real machine data. An ANOVA test shows no difference between expected and observed values of the two models (p value = 0.208). A two-sample T test demonstrates the proposed model provides values closer to expected values; consequently, it can model observable phenomena (p value \(=\) 0.000). Simulations are used to generate data required to conduct inferential statistical tests to determine the level of correspondence between model prediction and real machine data. This research demonstrates that using PBNs to model manufacturing systems provides a new mechanism for the study and prediction of their future behavior at the design phase, assess future performance and identify areas to improve design reliability and system resilience.     

安全关键异构软件混合建模及代码生成方法

随着系统复杂性的急剧增加,未来安全关键软件越来越多地采用异构构件组合架构,各种构件可能使用不同的计算模型或实现语言,使得整个软件系统呈现异构性.因此,设计此类系统需要使用复杂的建模方法.AADL(architecture analysis and design language)是一种安全关键系统体系结构多范式建模语言...     

Towards scalable synthesis of stochastic control systems

Formal synthesis approaches over stochastic systems have received significant attention in the past few years, in view of their ability to provide provably correct controllers for complex logical specifications in an automated fashion. Examples of complex specifications include properties expressed as formulae in linear temporal logic (LTL) or as automata on infinite strings. A general methodology to synthesize controllers for such properties resorts to symbolic models of the given stochastic systems. Symbolic models are finite abstractions of the given concrete systems with the property that a controller designed on the abstraction can be refined (or implemented) into a controller on the original system. Although the recent development of techniques for the construction of symbolic models has been quite encouraging, the general goal of formal synthesis over stochastic control systems is by no means solved. A fundamental issue with the existing techniques is the known “curse of dimensionality,” which is due to the need to discretize state and input sets. Such discretization generally results in an exponential complexity over the number of state and input variables in the concrete system. In this work we propose a novel abstraction technique for incrementally stable stochastic control systems, which does not require state-space discretization but only input set discretization, and that can be potentially more efficient (and thus scalable) than existing approaches. We elucidate the effectiveness of the proposed approach by synthesizing a schedule for the coordination of two traffic lights under some safety and fairness requirements for a road traffic model. Further we argue that this 5-dimensional linear stochastic control system cannot be studied with existing approaches based on state-space discretization due to the very large number of generated discrete states.     

On the Observer Problem for Discrete-Time Control Systems

This paper studies the construction of observers for nonlinear time-varying discrete-time systems in a general context, where a certain function of the states must be estimated. Appropriate notions of robust complete observability are proposed, under which a constructive proof of existence of an observer is developed. Moreover, a "transitive observer property" is proven, according to which a state observer can be generated as the series connection of two observers. The analysis and the results are developed in general normed linear spaces, to cover both finite-dimensional and infinite-dimensional systems     

具有一致性的模糊控制系统的分解结构

本文提出模糊控制系统的一致性概念,并分别给出简单及多维模糊控制系统一种具有一致性的分解结构,从而改进了[1]文提出的多变量模糊方程的映射性质。     

An interactive approach for CBIR using a network of radial basis functions

An important requirement for constructing effective content-based image retrieval (CBIR) systems is accurate characterization of visual information. Conventional nonadaptive models, which are usually adopted for this task in simple CBIR systems, do not adequately capture all aspects of the characteristics of the human visual system. An effective way of addressing this problem is to adopt a "human-computer" interactive approach, where the users directly teach the system about what they regard as being significant image features and their own notions of image similarity. We propose a machine learning approach for this task, which allows users to directly modify query characteristics by specifying their attributes in the form of training examples. Specifically, we apply a radial-basis function (RBF) network for implementing an adaptive metric which progressively models the notion of image similarity through continual relevance feedback from users. Experimental results show that the proposed methods not only outperform conventional CBIR systems in terms of both accuracy and robustness, but also previously proposed interactive systems.     

A unified approach for studying the properties of transition systems

In this paper a systematic method for generating, comparing and proving the properties of transition systems is presented. It is assumed that any property of a system can be defined by giving a set of ‘target’ states and a type of reachability. Ten different types of reachability are proposed; by appropriately choosing the set of target states, a family of ten potentially different properties is generated. The main conclusion is that the reachability types and therefore the system properties, can be characterized by simple relations involving the set of the possible initial states and fixed points of certain continuous predicate trasformers depending on the set of target states. As a consequence, in order to prove a given property it is sufficient to compute iteratively greatest or least fixed points of continuous predicate transformers.Some examples are presented which show how the results can be applied to prove the properties of concurrent systems represented by non-deterministic models.     

Semi-passive replication and Lazy Consensus

This paper presents two main contributions: semi-passive replication and Lazy Consensus. The former is a replication technique with parsimonious processing. It is based on the latter; a variant of Consensus allowing the lazy evaluation of proposed values.Semi-passive replication is a replication technique with parsimonious processing. This means that, in the normal case, each request is processed by only one single process. The most significant aspect of semi-passive replication is that it requires a weaker system model than existing techniques of the same family. For semi-passive replication, we give an algorithm based on the Lazy Consensus.Lazy Consensus is a variant of the Consensus problem that allows the lazy evaluation of proposed values, hence the name. The main difference with Consensus is the introduction of an additional property of laziness. This property requires that proposed values are computed only when they are actually needed. We present an algorithm based on Chandra and Toueg's Consensus algorithm for asynchronous distributed systems with a S failure detector.     

The robustness of stability under link and node failures

In the area of communication systems, stability refers to the property of keeping the amount of traffic in the system always bounded over time. Different communication system models have been proposed in order to capture the unpredictable behavior of some users and applications. Among those proposed models the adversarial queueing theory (aqt) model turned out to be the most adequate to analyze an unpredictable network. Until now, most of the research done in this field did not consider the possibility of the adversary producing failures on the network structure. The adversarial models proposed in this work incorporate the possibility of dealing with node and link failures provoked by the adversary. Such failures produce temporal disruptions of the connectivity of the system and increase the collisions of packets in the intermediate hosts of the network, and thus the average traffic load. Under such a scenario, the network is required to be equipped with some mechanism for dealing with those collisions.In addition to proposing adversarial models for faulty systems we study the relation between the robustness of the stability of the system and the management of the queues affected by the failures. When the adversary produces link or node failures the queues associated to the corresponding links can be affected in many different ways depending on whether they can receive or serve packets, or rather that they cannot. In most of the cases, protocols and networks containing very simple topologies, which were known to be universally stable in the aqt model, turn out to be unstable under some of the newly proposed adversarial models. This shows that universal stability of networks is not a robust property in the presence of failures.