Abstract We present theSTLmcmodel checker for signal temporal logic (STL) properties of hybrid systems. TheSTLmctool can perform STL model checking up to a robustness threshold for a wide range of hybrid systems. Our tool utilizes the refutation-complete SMT-based bounded model checking algorithm by reducing the robust STL model checking problem into Boolean STL model checking. IfSTLmcdoes not find a counterexample, the system is guaranteed to be correct up to the given bounds and robustness threshold. We demonstrate the effectiveness ofSTLmcon a number of hybrid system benchmarks.

The shepherding task is a classical example of swarm intelligence which often utilizes one intelligent agent (sheepdog) to herd a flock of simple agents (sheep) towards a predefined destination. During the shepherding, the sheepdog usually employs two actions with one for collecting all sheep and another one for driving the flock to the destination, and switches between the two constantly according to the aggregation degree of the flock. Conventional collecting action, however, simply compels the sheepdog to run towards a sheep that is farthest away from the flock's center, while taking no account of the sheep's location relative to the destination. This paper proposes an alternative collecting action which selects a sheep from the flock as target that has maximum sum of distances from the sheep to both the flock's center and the destination. Moreover, in order to speed up the switch between the collecting and driving actions, the aggregation level of the sheep flock will be measured in terms of an elastic circular sector centered at the destination, rather than a rigid circular surrounding the sheep flock. Numerical experiments demonstrate that the destination-orientated actions can facilitate a more efficient gathering of scattered sheep, and hence, improve the efficiency of the shepherding tasks.

Signal temporal logic (STL) is widely used to specify and analyze properties of cyber-physical systems with continuous behaviors. However, STL model checking is still quite limited, as existing STL model checking methods are either incomplete or very inefficient. This paper presents a new SMT-based model checking algorithm for verifying STL properties of cyber-physical systems. We propose a novel translation technique to reduce the STL bounded model checking problem to the satisfiability of a first-order logic formula over reals, which can be solved using state-of-the-art SMT solvers. Our algorithm is based on a new theoretical result, presented in this paper, to build a small but complete discretization of continuous signals, which preserves the bounded satisfiability of STL. Our translation method allows an efficient STL model checking algorithm that is refutationally complete for bounded signals, and that is much more scalable than the previous refutationally complete algorithm.

This paper aims to analyze the influence of different driving behavior on multilane traffic flows, via extending the well-studied single-lane car-following model into a three-lane model. To this end, we classify all drivers’ characteristics into three types: calm, moderate and aggressive, in accordance with their differences in response coefficient, expectation safe distance, maximum speed and lane-changing intention. Based on Kerner’s three-phase traffic theory, our model can reproduce the empirical features of spontaneous traffic breakdown phenomena, revealing the mechanism of congestion formation and state transitions. In addition, we examine how the traffic accident, honking and fast-slow lanes could affect the heterogeneous traffic flows. Numerical experiments show that the drivers’ characteristics play an essential role in stabilizing the traffic flow on multilane roads. The results may contribute to traffic planning and control on the urban roadways.

The rapid development of mobile communication technologies prompts the emergence of mobile edge computing (MEC). As the key technology toward 5th generation (5G) wireless networks, it allows mobile users to offload their computational tasks to nearby servers deployed in base stations to alleviate the shortage of mobile resource. Nevertheless, various challenges, especially the edge-user-allocation problem, are yet to be properly addressed. Traditional studies consider this problem as a static global optimization problem where user positions are considered to be time-invariant and user-mobility-related information is not fully exploited. In reality, however, edge users are usually with high mobility and time-varying positions, which usually result in users reallocations among different base stations and impact on user-perceived quality-of-service (QoS). To overcome the above limitations, we consider the edge user allocation problem as an online decision-making and evolvable process and develop a mobility-aware and migration-enabled approach, named MobMig, for allocating users at real-time. Experiments based on real-world MEC dataset clearly demonstrate that our approach achieves higher user coverage rate and lower reallocations than traditional ones.

A Brownian cellular automaton (BCA) is an asynchronous cellular automaton (ACA) in which local configurations representing signals may move forth and back randomly, as if they were undergoing random walks. The random fluctuation offers a natural mechanism to propagate signals in the 2-dimensional cell space, and to cross signals moving in directions perpendicular to each other. As a result, the BCA in (Lee et al., 2016) employs 4 cell states and 17 transition rules to conduct universal computation, both of which are less than other equivalent ACAs in the literature. This paper aims to advance the fluctuation-based scheme one step further, via proposing a new BCA with 4 states and 14 rules that achieves a reduction in the number of transition rules. We show that the BCA is capable of implementing any arbitrary logic circuit, thereby proving its universality in computation. We illustrate this by implementing a circuit that converts a 4-bit number to its equivalent hexadecimal digit.

Signal temporal logic (STL) is a temporal logic formalism for specifying properties of continuous signals. STL is widely used for analyzing programs in cyber-physical systems (CPS) that interact with physical entities. However, existing methods for analyzing STL properties are incomplete even for bounded signals, and thus cannot guarantee the correctness of CPS programs. This paper presents a new symbolic model checking algorithm for CPS programs that is refutationally complete for general STL properties of bounded signals. To address the difficulties of dealing with an infinite state space over a continuous time domain, we first propose a syntactic separation of STL, which decomposes an STL formula into an equivalent formula so that each subformula depends only on one of the disjoint segments of a signal. Using the syntactic separation, an STL model checking problem can be reduced to the satisfiability of a first-order logic formula, which is decidable for CPS programs with polynomial dynamics using satisfiability modulo theories (SMT). Unlike the previous methods, our method can verify the correctness of CPS programs for STL properties up to given bounds.

Random fluctuations will be a major factor interfering with the operation of nanometer scale electronic devices. This article presents circuit architectures that can exploit such fluctuations, if signals have a particle-like (discrete, token-based) character. We define an abstract circuit primitive that, though lacking functionality when used with fluctuation-free signals, becomes universal when fluctuations are allowed. Key to the power of a signal’s fluctuations is the ability to explore the state space of a circuit. This ability is used to resolve deadlock situations, which could otherwise only be averted by increased design complexity. The results in this article suggest that in the design of future computers, signal fluctuations, rather than being an impediment to be avoided at any cost, may be an important ingredient to achieve efficient operation.

Asynchronous cellular automata (ACAs) have much promise as architectures for future computers with molecular-scale devices, since they are less likely to suffer from clock-related problems (i.e. wiring overhead, heat dissipation, etc.) and they are suitable for bottom-up manufacturing techniques due to their homogeneous structures. Computation on ACA can be accomplished by designing configurations on the cell space such that their evolutions emulate the operations of asynchronous circuits. However, these ACA models still require tens of transition rules, which may seem too high for efficient physical realizations. In this paper, we present a new cellular automaton in which each cell comprises a group of simple sub-cells that are locally coupled with each other. Based upon an effective set of asynchronous primitive operators, this novel ACA can be used to construct any arbitrary logic circuit, while the number of transition rules is less than half the number in previous ACA models.

We propose a self-replicating machine that is embedded in a two-dimensional asynchronous cellular automaton with von Neumann neighborhood. The machine dynamically encodes its shape into description signals, and despite the randomness of cell updating, it is able to successfully construct copies of itself according to the description signals. Self-replication on asynchronously updated cellular automata may find application in nanocomputers, where reconfigurability is an essential property, since it allows avoidance of defective parts and simplifies programming of such computers.

Delay-insensitive (DI) circuits are a class of asynchronous circuits whose correctness of operation is robust to arbitrary delays in modules or interconnection lines. Keller clarified the precise operating conditions of the class of DI-circuits and presented a universal set of primitive modules from which any circuit in the class is realizable. Later, Patra and Fussell presented an alternative universal set of primitive modules and claimed that there is no universal set of primitives satisfying Keller's conditions in which the largest number of input and output lines of each primitive module is less than five. We present new types of primitive modules, each having at most three input and output-lines and show they form a universal set of primitives. We achieve this reduction in complexity by allowing the input and output-lines of modules to be bidirectional and to be able to buffer signals. The use of buffers in interconnection lines allows higher throughput of signals and results in circuits requiring less feedback lines, thus improving the efficiency of DI-circuits. The proposed class of Dl-circuits is especially useful for implementations on cellular automata - an architecture that promises efficient implementations and manufacturing in nanotechnology due to its regular structure.