A computer network based control architecture for autonomous distributed multirobot systems

This paper presents the specification and implementation procedure using a microcomputer network based autonomous distributed control architecture for industrial multirobot systems. The procedure is based on the concept of data flow network controlled by communicating sequential processes to perform coordinated tasks. Robots and other computerized industrial devices such as conveyors and manufacturing machines are defined as object-oriented Petri nets. A modular and hierarchical approach is adopted to define a set of Petri net type diagrams which represent concurrent activities of control processes for such devices. Asynchronous and synchronous interactions are modelled by places and transitions, respectively, in global process interaction nets. The control software is implemented on a computer network using Inmos transputers with true parallel processing and message passing primitives efficiently handled in hardware. Petri net based models are directly and efficiently transformed to corresponding codes in occam, the high level parallel programming language defined for the transputer.     

Behavior and Instantiation of High–Level Net Processes

Processes for high-level nets N are often defined as processes of the low-level net Flat(N) which is obtained from N via the well-known flattening construction. This low-level notion of processes for high-level nets, however, is not really adequate, because the high-level structure is completely lost. For this reason we have introduced in a previous paper a new notion of high-level net processes for high-level nets which captures the high-level structure. The key notion is a high-level occurrence net K, which generalizes the well-known notion of occurrence nets from low-level to high-level nets. In contrast to the low-level case we consider high-level occurrence nets together with a set of initial markings of the input places. In this paper we show under which conditions the behavior of low-level occurrence nets and processes can be generalized to the high-level case. A key notion is the instantiation L of a high-level occurrence net K, where L is a low-level subnet of the flattening Flat(K) with isomorphic net structures of L and K. One of our main results characterizes under which conditions a high-level occurrence net - and hence a high-level net process - has unique and nonoverlapping instantiations and can be represented by the union of all its instantiations.     

Liveness-enforcing supervision of bounded ordinary Petri nets usingpartial order methods

This paper combines and refines recent results into a systematic way to verify and enforce the liveness of bounded ordinary Petri nets. The approach we propose is based on a partial-order method called network unfolding. Network unfolding maps the original Petri net to an acyclic occurrence net. A finite prefix of the occurrence net is defined to give a compact representation of the original net reachability graph while preserving the causality between net transitions. A set of transition invariants denoted as base configurations is identified in the finite prefix. These base configurations capture all of the fundamental executions of the net system, thereby providing a modular way to verify and synthesize supervisory net systems. This paper proves necessary and sufficient conditions that characterize the original net liveness and the existence of maximally permissive supervisory policies that enforce liveness     

A Modified Double Gyre with Ground Truth Hyperbolic Trajectories for Flow Visualization

The model of a Double Gyre flow by Shadden et al. is a standard benchmark data set for the computation of hyperbolic Lagrangian Coherent Structures (LCS) in flow data. While structurally extremely simple, it generates hyperbolic LCS of arbitrary complexity. Unfortunately, the Double Gyre does not come with a well‐defined ground truth: the location of hyperbolic LCS boundaries can only be approximated by numerical methods that usually involve the gradient of the flow map. We present a new benchmark data set that is a small but carefully designed modification of the Double Gyre , which comes with ground truth closed‐form hyperbolic trajectories. This allows for computing hyperbolic LCS boundaries by a simple particle integration without the consideration of the flow map gradient. We use these hyperbolic LCS as a ground truth solution for testing an existing numerical approach for extracting hyperbolic trajectories. In addition, we are able to construct hyperbolic LCS curves that are significantly longer than in existing numerical methods.     

Dataflow Architectures for GALS

In Kahn process network (KPN), the processes (nodes) communicate by unbounded unidirectional FIFO channels (arcs), with the property of non-blocking writes and blocking reads on the channels. KPN provides a semantic model of computation, where a computation can be expressed as a set of asynchronously communicating processes. However, the unbounded FIFO based asynchrony is not realizable in practice and hence requires refinement in real hardware. In this work, we start with KPN as the model of computation for GALS, and discuss how different GALS architectures can be realized. We borrow some ideas from existing dataflow architectures for our GALS designs.     

MADIDS：一种基于移动代理的新型分布式入侵检测系统

When traditional Intrusion Detection System(IDS)is used to detect and analyze the great flow data transfer in high-speed network,it usually causes the computation bottleneck.This paper presents a new Mobile Agent Distributed IDS(MADIDS) system based on the mobile agents.This system is specifically designed to process the great flow data transfer in high-speed network.In MADIDS,the agents that are set at each node process the data transfer by distributed computation architecture.Meanwhile by using the reconfiguration quality of the mobile agents,the load balance of distributed computation can be dynamically implemented to gain the high-performance computing ability.This ability makes the detecting and analyzing of high-speed network possible.MADIDS can effectively solve the detection and analysis performance bottleneck caused by the great flow data transfer in high-speed network.It enhances the performance of IDS in high-speed network.In this paper,we construct the infrastructure and theoretical model of MADIDS,and the deficiencies of MADIDS and future research work are also indicated.     

基于攻击图的扩充Petri网攻击模型

鉴于网络攻击过程中存在攻击者被检测到的可能性,将攻击图转化成Petri网并进行扩展生成EPN模型,依据库所的攻击成本值求解网络攻击的最佳攻击路径和攻击成本,基于最大流概念定义系统最大承受攻击能力。从二维角度分析网络攻击,提出攻击可行性概念及基于攻击图的扩充Petri网攻击模型,该模型相关算法的遍历性由EPN推理规则保证。当原攻击图的弧较多时,算法的复杂度低于Dijkstra算法,攻击图的攻击发起点和攻击目标点间的路径越多,算法越有效。实验结果证明,该模型可以对网络攻击过程进行高效的综合分析。     

Universal Sleptsov net

We construct a universal Sleptsov net (USN) with 13 places and 26 transitions that runs in polynomial time; a Sleptsov net is a place-transition net that allows multiple instances of transition firing within a single step. We simulate Neary and Woods’ small weakly universal Turing machine with two states and four symbols. Compared to previous results, we do not use separate encoding and decoding subnets, which implement such operations as: multiplication by a constant combined with addition and division by a constant combined with modulo, respectively, but overlap them in a special way that reduces the number of USN nodes by four. Besides, we present a thorough analysis of the source data encoding complexity. The obtained universal net is a prototype of a processor in the SN paradigm of computing that promises hyper-performance.     

Optimal Channel Choice for Lossy Data Flow Transmission

We consider the optimal control problem for the load of several communication channels defined by independent Markov jump processes. Implicit information on the state of a channel is available in the form of a flow of losses whose intensity is proportional to the controllable load of this channel. The optimized functionals take into account the total throughput of channels and energy costs for data transmission over a fixed interval of time. We obtain optimal filtering equations for joint estimation of channel states. We construct a locally optimal strategy that explicitly depends on the set of state estimates.     

Extension of the lower bound of monitor solutions of maximally permissive supervisors to non-α net systems

Traditional region-based liveness-enforcing supervisors focus on (1) maximal permissiveness of not losing legal states, (2) structural simplicity of minimal number of monitors, and (3) fast computation. Lately, a number of similar approaches can achieve minimal configuration using efficient linear programming. However, it is unclear as to the relationship between the minimal configuration and the net structure. It is important to explore the structures involved for the fewest monitors required. Once the lower bound is achieved, further iteration to merge (or reduce the number of) monitors is not necessary. The minimal strongly connected resource subnet (i.e., all places are resources) that contains the set of resource places in a basic siphon is an elementary circuit. Earlier, we showed that the number of monitors required for liveness-enforcing and maximal permissiveness equals that of basic siphons for a subclass of Petri nets modelling manufacturing, called α systems. This paper extends this to systems more powerful than the α one so that the number of monitors in a minimal configuration remains to be lower bounded by that of basic siphons. This paper develops the theory behind and shows examples.     

Algebraic approaches for fault identification in discrete-event systems

In this note, we develop algebraic approaches for fault identification in discrete-event systems that are described by Petri nets. We consider faults in both Petri net transitions and places, and assume that system events are not directly observable but that the system state is periodically observable. The particular methodology we explore incorporates redundancy into a given Petri net in a way that enables fault detection and identification to be performed efficiently using algebraic decoding techniques. The guiding principle in adding redundancy is to keep the number of additional Petri net places small while retaining enough information to be able to systematically detect and identify faults when the system state becomes available. The end result is a redundant Petri net embedding that uses 2k additional places and enables the simultaneous identification of 2k-1 transition faults and k place faults (that may occur at various instants during the operation of the Petri net). The proposed identification scheme has worst-case complexity of O(k(m+n)) operations where m and n are respectively the number of transitions and places in the given Petri net.     

Techniques and applications of computation slicing

Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems should be able to operate properly even in the presence of software faults. Monitoring the execution of a distributed system, and, on detecting a fault, initiating the appropriate corrective action is an important way to tolerate such faults. This gives rise to the predicate detection problem which requires finding whether there exists a consistent cut of a given computation that satisfies a given global predicate.Detecting a predicate in a computation is, however, an NP-complete problem in general. In order to ameliorate the associated combinatorial explosion problem, we introduce the notion of computation slice. Formally, the slice of a computation with respect to a predicate is a (sub)computation with the least number of consistent cuts that contains all consistent cuts of the computation satisfying the predicate. Intuitively, slice is a concise representation of those consistent cuts of a computation that satisfy a certain condition. To detect a predicate, rather than searching the state-space of the computation, it is much more efficient to search the state-space of the slice.We prove that the slice of a computation is uniquely defined for all predicates. We also present efficient algorithms for computing the slice for several useful classes of predicates. For an arbitrary predicate, we establish that the problem of computing the slice is NP-complete in general. Nonetheless, for such a predicate, we develop an efficient heuristic algorithm for computing an approximate slice. Our experimental results demonstrate that slicing can lead to an exponential improvement over existing techniques for predicate detection in terms of time and space.Received: 19 November 2003, Revised: 29 July 2004, Published online: 7 February 2005Vijay K. Garg: Supported in part by the NSF Grants ECS-9907213, CCR-9988225, Texas Education Board Grant ARP-320, an Engineering Foundation Fellowship, and an IBM grant.Parts of this paper have appeared earlier in conference proceedings [GM01,MG01a,MG03a].     

Hierarchical Kohonenen net for anomaly detection in network security.

A novel multilevel hierarchical Kohonen Net (K-Map) for an intrusion detection system is presented. Each level of the hierarchical map is modeled as a simple winner-take-all K-Map. One significant advantage of this multilevel hierarchical K-Map is its computational efficiency. Unlike other statistical anomaly detection methods such as nearest neighbor approach, K-means clustering or probabilistic analysis that employ distance computation in the feature space to identify the outliers, our approach does not involve costly point-to-point computation in organizing the data into clusters. Another advantage is the reduced network size. We use the classification capability of the K-Map on selected dimensions of data set in detecting anomalies. Randomly selected subsets that contain both attacks and normal records from the KDD Cup 1999 benchmark data are used to train the hierarchical net. We use a confidence measure to label the clusters. Then we use the test set from the same KDD Cup 1999 benchmark to test the hierarchical net. We show that a hierarchical K-Map in which each layer operates on a small subset of the feature space is superior to a single-layer K-Map operating on the whole feature space in detecting a variety of attacks in terms of detection rate as well as false positive rate.     

An efficient Earth Mover's Distance algorithm for robust histogram comparison

We propose EMD-L1: a fast and exact algorithm for computing the Earth Mover's Distance (EMD) between a pair of histograms. The efficiency of the new algorithm enables its application to problems that were previously prohibitive due to high time complexities. The proposed EMD-L1 significantly simplifies the original linear programming formulation of EMD. Exploiting the L1 metric structure, the number of unknown variables in EMD-L1 is reduced to O(N) from O(N2) of the original EMD for a histogram with N bins. In addition, the number of constraints is reduced by half and the objective function of the linear program is simplified. Formally, without any approximation, we prove that the EMD-L1 formulation is equivalent to the original EMD with a L1 ground distance. To perform the EMD-L1 computation, we propose an efficient tree-based algorithm, Tree-EMD. Tree-EMD exploits the fact that a basic feasible solution of the simplex algorithm-based solver forms a spanning tree when we interpret EMD-L1 as a network flow optimization problem. We empirically show that this new algorithm has an average time complexity of O(N2), which significantly improves the best reported supercubic complexity of the original EMD. The accuracy of the proposed methods is evaluated by experiments for two computation-intensive problems: shape recognition and interest point matching using multidimensional histogram-based local features. For shape recognition, EMD-L1 is applied to compare shape contexts on the widely tested MPEG7 shape data set, as well as an articulated shape data set. For interest point matching, SIFT, shape context and spin image are tested on both synthetic and real image pairs with large geometrical deformation, illumination change, and heavy intensity noise. The results demonstrate that our EMD-L1-based solutions outperform previously reported state-of-the-art features and distance measures in solving the two tasks.     

航班延误波及链的有色出现网模型

针对基本Petri网的出现网在描述有色Petri网动态行为时的局限性,在基本出现网的基础上定义了一种扩展的出现网,即有色出现网,直观地反映了有色Petri网系统中资源流动及变化之间的顺序和并发关系,也大大减小了图形的复杂程度.同时,将有色Petri网和这种有色出现网应用于航班延误波及链的建模中,反映了航班执行时所需的多种资源的分布及流动情况,描述了航班在执行过程中与机场之间的相互影响及延误的链式波及反应.     

On using prototype reduction schemes to optimize kernel-based fisher discriminant analysis.

Fisher's linear discriminant analysis (LDA) is a traditional dimensionality reduction method that has been proven to be successful for decades. Numerous variants, such as the kernel-based Fisher discriminant analysis (KFDA), have been proposed to enhance the LDA's power for nonlinear discriminants. Although effective, the KFDA is computationally expensive, since the complexity increases with the size of the data set. In this correspondence, we suggest a novel strategy to enhance the computation for an entire family of the KFDAs. Rather than invoke the KFDA for the entire data set, we advocate that the data be first reduced into a smaller representative subset using a prototype reduction scheme and that the dimensionality reduction be achieved by invoking a KFDA on this reduced data set. In this way, data points that are ineffective in the dimension reduction and classification can be eliminated to obtain a significantly reduced kernel matrix K without degrading the performance. Our experimental results demonstrate that the proposed mechanism dramatically reduces the computation time without sacrificing the classification accuracy for artificial and real-life data sets.     

Design of Optimal Petri Net Supervisors for Flexible Manufacturing Systems via Weighted Inhibitor Arcs

This paper develops an approach to the design of an optimal Petri net supervisor that enforces liveness to flexible manufacturing systems. The supervisor contains a set of observer places with weighted inhibitor arcs. An observer place with a weighted inhibitor arc is used to forbid a net from yielding an illegal marking by inhibiting the firing of a transition at a marking while ensuring that all legal markings are preserved. A marking reduction technique is presented to decrease the number of considered markings, which can dramatically lower the computational burden of the proposed approach. An integer linear program is presented to simplify the supervisory structure by minimizing the number of observer places. Finally, several examples are used to shed light on the proposed approach which can lead to an optimal supervisor for the net models that cannot be optimally controlled via pure Petri net supervisors.