Decomposition of first-order hybrid Petri nets for hierarchical control of manufacturing systems

Although hybrid Petri net (HPN) is a popular formalism in modelling hybrid production systems, the HPN model of large scale systems gets substantially complicated for analysis and control due to large dimensionality of such systems. To overcome this problem, a typical approach is to decompose the net into subnets and then control the plant through hierarchical or decentralized structures. Although this concept has been widely discussed in the literature for discrete PNs, there is a lack of research for HPNs. In this paper, a new method of decomposition of first-order hybrid Petri nets (FOHPNs) is proposed first and then the hierarchical control of the subnets through a coordinator is introduced. The advantage of using the proposed approach is validated by an existing example. A sugar milling case study is analysed by using a decomposed FOHPN model and the optimization results are compared against the results of the approaches presented in other papers. Simulation results show not only an improvement in production rate, but also show the ability to control the plant online. In addition, by using the hierarchical control structure for an FOHPN model, it is possible to reduce the cost of communication links, improve the reliability of the system, maintain the plant locally, and partially redesign the system.     

Approximation algorithms for hierarchical location problems

We formulate and (approximately) solve hierarchical versions of two prototypical problems in discrete location theory, namely, the metric uncapacitated k-median and facility location problems. Our work yields new insights into hierarchical clustering, a widely used technique in data analysis. For example, we show that every metric space admits a hierarchical clustering that is within a constant factor of optimal at every level of granularity with respect to the average (squared) distance objective. A key building block of our hierarchical facility location algorithm is a constant-factor approximation algorithm for an “incremental” variant of the facility location problem; the latter algorithm may be of independent interest.     

Consistent hierarchical economic NMPC for a class of hybrid systems using neighboring-extremal updates

A hierarchical two-layer control algorithm is developed for a class of hybrid (discrete-continuous dynamic) systems to support economically optimal operation of batch or continuous processes with a predefined production schedule. For this class of hybrid systems, the optimal control moves as well as the controlled switching times between two adjacent modes are determined online. In contrast to closely related schemes for integrated scheduling and control, the sequence of modes is not optimized. On the upper layer, the economic optimal control problem is solved rigorously by a slow hybrid economic model predictive controller at a low sampling rate. On the lower layer, a fast hybrid neighboring-extremal controller is based on the same economic optimal control problem as the slow controller to ensure consistency between both layers. The fast neighboring-extremal controller updates rather than tracks the optimal trajectories from the upper layer to account for disturbances. Consequently, the fast controller steers the process to its operational bounds under disturbances and the economic potential of the process is exploited anytime. The suggested two-layer control algorithm provides fully consistent control action on the fast and slow time-scale and thus avoids performance degradation and even infeasibilities which are commonly encountered if inconsistent optimal control problems are formulated and solved.     

Synthesis of hierarchical systems

In automated synthesis, given a specification, we automatically create a system that is guaranteed to satisfy the specification. In the classical temporal synthesis algorithms, one usually creates a “flat” system “from scratch”. However, real-life software and hardware systems are usually created using preexisting libraries of reusable components, and are not “flat” since repeated sub-systems are described only once.In this work we describe an algorithm for the synthesis of a hierarchical system from a library of hierarchical components, which follows the “bottom-up” approach to system design. Our algorithm works by synthesizing in many rounds, when at each round the system designer provides the specification of the currently desired module, which is then automatically synthesized using the initial library and the previously constructed modules. To ensure that the synthesized module actually takes advantage of the available high-level modules, we guide the algorithm by enforcing certain modularity criteria.We show that the synthesis of a hierarchical system from a library of hierarchical components is Exptime-complete for μ-calculus, and 2Exptime-complete for Ltl, both in the cases of complete and incomplete information. Thus, in all cases, it is not harder than the classical synthesis problem (of synthesizing flat systems “from scratch”), even though the synthesized hierarchical system may be exponentially smaller than a flat one.     

Approximation of infinite-dimensional systems

A Fourier series-based method for approximation of stable infinite-dimensional linear time-invariant system models is discussed. The basic idea is to compute the Fourier series coefficients of the associated transfer function T_d(Z) and then take a high-order partial sum. Two results on H^∞ convergence and associated error bounds of the partial sum approximation are established. It is shown that the Fourier coefficients can be replaced by the discrete Fourier transform coefficients while maintaining H^∞ convergence. Thus, a fast Fourier transform algorithm can be used to compute the high-order approximation. This high-order finite-dimensional approximation can then be reduced using balanced truncation or optimal Hankel approximation leading to the final finite-dimensional approximation to the original infinite-dimensional model. This model has been tested on several transfer functions of the time-delay type with promising results     

On the capabilities of systolic systems

This paper studies transformations of systems into systolic systems with related functionality. It distinguishes two antithetical transformation methods: one syntactic, the other semantic.The syntactic method considers the topology of the system, but ignores its behavior and the behavior of its combinational units. We use retiming and introduce two new basic syntactic techniques: tiling and bypassing. Using these, we present syntactic transformations that perform the following: conversion of a semisystolic system to a systolic one; elimination of either broadcast or instant-accumulation from a system that is otherwise systolic; and speeding up a systolic system by any constant factor. Leiserson and Saxe [10] have developed transformations to accomplish the first two tasks, but failed to preserve the behavior of the system. Our transformations leave the behavior of the system intact.The semantic method considers the functionality of the system as a whole, but ignores its internal structure. A system is called -homogeneous if all its combinational units are identical and equal to the given unit . We show that every semisystolic system can be transformed into a -homogeneous systolic system, where depends only on the alphabet used by the system to communicate with the external world. As a special case, any regular language L ^* is defined by some -homogeneous systolic system, where depends only on .For binary systems, this technique produces a systolic system with a feasible clock period ofO(i + log(o)), wherei ando are the numbers of input and output ports of the system. This clock period is independent of the size and complexity of the given system.Part of this work was done while the authors were with Bellcore, 445 South Street, Morristown, NJ 07960-1910, USA.     

Parallel hierarchical radiosity on hybrid platforms

Achieving an efficient realistic illumination is an important aim of research in computer graphics. In this paper a new parallel global illumination method for hybrid systems based on the hierarchical radiosity method is presented. Our solution allows the exploitation of systems that combine independent nodes with multiple cores per node. Thus, multiple nodes work in parallel in the computation of the global illumination for the same scene. Within each node, all the available computational cores are used through a shared-memory multithreading approach. The good results obtained in terms of speedup on several distributed-memory and shared-memory configurations show the versatility of our hybrid proposal.     

Increasing capabilities of geometric modelling systems

Geometric modelling is the basis for design and technological planning. The integration of these tasksis the goal of the Norwegian-German APS project (Advanced Production System). In this project, the geometric model is created as a module within a solid model that handles analytic and nonanlytic geometry. The module has two interfaces: to the object-oriented operational database and to applications via a geometry-definition interface that will be enlarged to become an application interface. The geometric module can be integrated into vendor environments which normally have two-dimensional capabilities. The functional capabilities are based in COMPAC and the GPM-sculptured surface system. Both systems are merged in such a way that the data structures are integrated and one database management system is used.     

Approximation by bernstein systems

Theory of Computing Systems - LetK denote an arbitrary compact subset of realL 2. Letf be any causal continuous function onL 2. Then there is a linear differential...     

Dependability evaluation of hierarchical systems

Hierarchical design represents a natural solution for managing the growing complexity of computing systems. This leads to systems that are hierarchically structured from a logical or physical viewpoint. Because of the inherent complexity of such systems, the incorporation of fault-tolerance features is highly recommended, to achieve the required dependability level. Hence, it is important to develop evaluation tools that allow to analyse the effectiveness of different fault-tolerance mechanisms. We present a systematic procedure for the construction and evaluation of Markov models for transient dependability analysis, which fully exploits the hierarchical structure of the system under evaluation. A thorough time/space complexity analysis of the proposed procedure shows that it allows a considerable time and space saving with respect to a naive approach to the same problem.Work partially supported by CNR, Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo, under grant no. 91.00905 PF96, and by MURST, Progetto 40% Performability di sistemi distributi e paralleli     

Approximation of linear constant systems

In this paper two problems are considered, the problem of modeling a given constant linear system by a constant linear system of fixed lower order, and the problem of finding a filter of fixed order to estimate a time-invariant random process from a related time-invariant random process. A quadratic criterion is used to select the optimum system in both cases. It is shown that the filtering problem reduces to the problem of modeling the corresponding Wiener filter. Necessary conditions for a solution are developed and stated in terms of standard Wiener filter theory notation. Numerical solution of the equations embodying the necessary conditions is considered and several examples are presented.     

一种动态分级的混合粒子群优化算法

针对粒子群算法早熟收敛和搜索精度不高的问题,提出一种动态分级的混合粒子群优化算法．该算法采取３种级别的并行粒子群算法,分别用于全局搜索和局部搜索及二者的结合,并根据搜索阶段动态调整各种级别中并行变量的数目．在全局搜索中,将混沌机制引入算法中以增强算法的全局搜索能力;在局部搜索中,采用单纯形法对适应度最优解进行局部寻优．仿真实验表明,该算法比其他优化算法具有更好的性能．     

Approximation capabilities of multilayer fuzzy neural networks on the set of fuzzy-valued functions

This paper first introduces a piecewise linear interpolation method for fuzzy-valued functions. Based on this, we present a concrete approximation procedure to show the capability of four-layer regular fuzzy neural networks to perform approximation on the set of all d_p continuous fuzzy-valued functions. This approach can also be used to approximate d_∞ continuous fuzzy-valued functions. An example is given to illustrate the approximation procedure.     

Simulation of hierarchical multiprocessor database systems

The paper is dedicated to issues concerning simulation and analysis of hierarchical multiprocessor systems oriented to database applications. Requirements for a parallel database system model are given. A survey and comparative analysis of known parallel database system models are presented. A new multiprocessor database system model is introduced. This model allows us to simulate and evaluate arbitrary hierarchical multiprocessor configurations in the context of the OLTP class database applications. Examples of using the database multiprocessor model for simulation study of multiprocessor database systems are presented.     

Approximation of almost solvable bilinear systems

The complexity of the Wei-Norman integration for a bilinear system can be reduced by approximating the associated Lie algebra by one of lower dimension. An algorithm is given for approximating a class of bilinear systems in this way in the case their Lie algebras are almost solvable.     

Embedding deductive capabilities in relational database systems

The basic idea of our work is to include deductive capabilities in a relational database system by fully using the operands of relational algebra and without using any theorem prover. We present a deductive database system where the user can formulate deduction laws as logical formulas, but which works on an underlying relational database system by fully using the data manipulation routines of such a system. Generally, it is not possible to express the deduction laws by means of expressions of relational algebra (see Ref. 1). In our system, a relational algebra expression is associated with every database deduction law. The result of its evaluation (with respect to an underlying database) is the set of all database entries that can be deduced from the database by applying the respective law once (Theorem 1). By successively applying all these relational expressions for all the database deduction laws it is possible to generate the whole extensional database (i.e. all tuples deducible from the database).     

A hierarchical hybrid framework for modelling anomalous behaviours

The presence of anomalies in collected information, i.e. data that deviates substantially from what is normally expected, is a valuable source of knowledge and its discovery has many practical applications. Anomaly-detection approaches rely on building models that suitably describe data patterns deemed as normal, however they may incur the generation of a considerable amount of false positives. Signature-based techniques, which exploit a prior knowledge base of anomalous patterns, are able to effectively detect them but fail in identifying anomalies which did not occur previously. Hybrid anomaly detection systems combine the two approaches in order to obtain better detection performances. This paper proposes a framework, called HALF, that allows to develop hybrid systems by combining available techniques, coming from both approaches. HALF is able to operate on any data type and provides native support to online learning, or concept drifting. This enables the incremental updating of the knowledge bases used by the techniques. HALF has been designed to accommodate multiple mining algorithms by organizing them in a hierarchical structure in order to offer an higher and flexible detection capability. The framework effectiveness is demonstrated through two case studies concerning a network intrusion detection system and a steganography hunting system.     

Information integration via hierarchical and hybrid bayesian networks

A collaboration scheme for information integration among multiple agencies (and/or various divisions within a single agency) is designed using hierarchical and hybrid Bayesian networks (HHBNs). In this scheme, raw information is represented by transactions (e.g., communication, travel, and financing) and information entities to be integrated are modeled as random variables (e.g., an event occurs, an effect exists, or an action is undertaken). Each random variable has certain states with probabilities assigned to them. Hierarchical is in terms of the model structure and hybrid stems from our usage of both general Bayesian networks (BNs) and hidden Markov models (HMMs, a special form of dynamic BNs). The general BNs are adopted in the top (decision) layer to address global assessment for a specific question (e.g., "Is target A under terrorist threat?" in the context of counterterrorism). HMMs function in the bottom (observation) layer to report processed evidence to the upper layer BN based on the local information available to a particular agency or a division. A software tool, termed the adaptive safety analysis and monitoring (ASAM) system, is developed to implement HHBNs for information integration either in a centralized or in a distributed fashion. As an example, a terrorist attack scenario gleaned from open sources is modeled and analyzed to illustrate the functionality of the proposed framework.