Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Graphical models in probability and statistics are a core concept in the area of probabilistic reasoning and probabilistic programming—graphical models include Bayesian networks and factor graphs. For modeling and formal verification of probabilistic systems, probabilistic automata were introduced. This paper proposes a coherent suite of models consisting of Mixed Systems, Mixed Bayesian Networks, and Mixed Automata, which extend factor graphs, Bayesian networks, and probabilistic automata with the handling of nondeterminism. Each of these models comes with a parallel composition, and we establish clear relations between these three models. Also, we provide a detailed comparison between Mixed Automata and Probabilistic Automata PubDate: 2023-10-19
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This paper contributes with a multi-level, hierarchical control system for a fleet of mobile robots sharing a common 2D motion space. The system consists of three levels, with the top level being a supervisor based on a discrete representation of the Multiple Mobile Robot System (MMRS), in which robot motion processes are seen as sequences of stages. The supervisor controls centrally the changes of their stages by robots, ensuring their collision-, and deadlock-free concurrent movement. The intermediate control level supervises locally the execution of robot motion on individual stages in a manner consistent with the decisions of the top level. The lowest level, robot control, is responsible for motion execution as determined by the local supervisor. We capitalize on some earlier results concerning the supervisory control of MMRS and propose a common framework for three supervisory control models. Then we propose relevant solutions for the local supervisors, in particular, a DES-based robot-motion-mode control and application of the Artificial Potential Field model for ensuring collision-free motion of two robots sharing a space sector. Next we assume simple robot control and subject the system to simulation experiments aimed at comparing the impact of the different solutions on the performance of MMRS. PubDate: 2023-10-18
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Control systems should enforce a desired property for both expected/modeled situations as well as unexpected/unmodeled environmental situations. Existing methods focus on designing controllers to enforce the desired property only when the environment behaves as expected. However, these methods lack discussion on how the system behaves when the environment is perturbed. In this paper, we propose an approach for analyzing discrete-state control systems with respect to their tolerance against environmental perturbations. We formally define this notion of tolerance and describe a general technique to compute it, for any given regular property. We also present a more efficient method to compute tolerance with respect to invariance properties. Moreover, we show that there exists an inherent trade-off between permissiveness and tolerance that we capture via Pareto optimality conditions. We also study the problem of synthesizing Pareto optimal controllers that achieve a minimum level of tolerance and permissiveness. We demonstrate our framework on examples involving surveillance protocols and robotic motion planning. PubDate: 2023-10-17
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Heterogeneity among equipment in industrial production lines may have a major impact on energy consumption and makespan. The Supervisory Control Theory of discrete event systems proved to be especially useful to model the production system respecting its constraints and ensuring the safe execution on a real plant, such that an optimized production plan can be picked among the safe sequences. In this work, the makespan and the energy consumption minimization problem in discrete event systems with multiple production routes is addressed as a multi-objective problem. A multi-objective modeling is proposed, which considers the information regarding the power demanded by the system in each state of each equipment and the expected duration of each operation in the system. A dedicated Multi-Objective Variable Neighborhood Search (MOVNS) algorithm is also proposed to estimate an adequate set of trade-off solutions. A multi-criteria decision aid method is used to support the selection of an appropriate solution for the problem. The combination of the proposed modeling with both the MOVNS and a decision-making support has shown to be efficient regarding the solution of four test instances considered in this work. PubDate: 2023-10-13
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The paper mentioned in the title used an incorrect implementation of the algorithms to produce the experimental results. The mistake significantly impacts the computational efficiency of the algorithms, on which they are evaluated. In this correction we explain the mistake, present the new results, and update our conclusions based on the new results. PubDate: 2023-10-03
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Switching max-plus linear system (SMPLS) models are an apt formalism for performance analysis of discrete-event systems. SMPLS analysis is more scalable than analysis through other formalisms such as timed automata, because SMPLS abstract pieces of determinate concurrent system behavior into atomic modes with fixed timing. We consider discrete-event systems that are decomposed into a plant and a Supervisory Controller (SC) that controls the plant. The SC needs to react to events, concerning e.g. the successful completion or failure of an action, to determine the future behavior of the system, for example, to initiate a retrial of the action. To specify and analyze such system behavior and the impact of feedback on timing properties, we introduce an extension to SMPLS with discrete-event feedback. In this extension, we model the plant behavior with system modes and capture the timing of discrete-event feedback emission from plant to SC in the mode matrices. Furthermore, we use I/O automata to capture how the SC responds to discrete-event feedback with corresponding mode sequences of the SMPLS. We define the semantics of SMPLS with events using new state-space equations that are akin to classical SMPLS with dynamic state-vector sizes. To analyze the extended models, we formulate a transformation from SMPLS with events to classical SMPLS with equivalent semantics and properties such that performance properties can be analyzed using existing techniques. Our approach enables the specification of discrete-event feedback from the plant to the SC and its performance analysis. We demonstrate our approach by specifying and analyzing the makespan of a flexible manufacturing system. PubDate: 2023-08-29 DOI: 10.1007/s10626-023-00382-y
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: This survey gives an overview of the current research on compositional algorithms for verification and synthesis of modular systems modelled as interacting finite-state machines. Compositional algorithms operate by repeatedly simplifying individual components of a large system, replacing them by smaller so-called abstractions, while preserving critical properties. In this way, the exponential growth of the state space can be limited, making it possible to analyse much bigger state spaces than possible by standard state space exploration. This paper gives an introduction to the principles underlying compositional methods, followed by a survey of algorithmic solutions from the recent literature that use compositional methods to analyse systems automatically. The focus is on applications in supervisory control of discrete event systems, particularly on methods that verify critical properties or synthesise controllable and nonblocking supervisors. PubDate: 2023-08-21 DOI: 10.1007/s10626-023-00378-8
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This note concerns with semi-Markov decision chains evolving on a denumerable state space. The system is directed by a risk-averse controller with constant risk-sensitivity, and the performance of a decision policy is measured by a long-run average criterion associated with bounded holding cost rates and one-step cost function. Under mild conditions on the sojourn times and the transition law, restrictions on the cost structure are given to ensure that the optimal average cost can be characterized via a bounded solution of the optimality equation. Such a result is used to establish a general characterization of the optimal average cost in terms of an optimality inequality from which an optimal stationary policy can be derived. PubDate: 2023-08-21 DOI: 10.1007/s10626-023-00376-w
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract An epistemic model for decentralized discrete-event systems with non-binary control is presented. This framework combines existing work on inference-based control decisions with existing work on formal reasoning about knowledge in discrete-event systems. The novelty in the epistemic formalism is in providing an approach to derive problem solvability conditions and problem solutions. The derived expressions directly encapsulate the actions that supervisors must take. PubDate: 2023-08-21 DOI: 10.1007/s10626-023-00381-z
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Network Calculus (NC) is an algebraic theory that represents traffic and service guarantees as curves in a Cartesian plane, in order to compute performance guarantees for flows traversing a network. NC uses transformation operations, e.g., min-plus convolution of two curves, to model how the traffic profile changes with the traversal of network nodes. Such operations, while mathematically well-defined, can quickly become unmanageable to compute using simple pen and paper for any non-trivial case, hence the need for algorithmic descriptions. Previous work identified the class of piecewise affine functions which are ultimately pseudo-periodic (UPP) as being closed under the main NC operations and able to be described finitely. Algorithms that embody NC operations taking as operands UPP curves have been defined and proved correct, thus enabling software implementations of these operations. However, recent advancements in NC make use of operations, namely the lower pseudo-inverse, upper pseudo-inverse, and composition, that are well-defined from an algebraic standpoint, but whose algorithmic aspects have not been addressed yet. In this paper, we introduce algorithms for the above operations when operands are UPP curves, thus extending the available algorithmic toolbox for NC. We discuss the algorithmic properties of these operations, providing formal proofs of correctness. PubDate: 2023-08-18 DOI: 10.1007/s10626-022-00373-5
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The aim of this manuscript is to understand the dynamics of matrix products in a max algebra. A consequence of the Perron-Fröbenius theorem on periodic points of a nonnegative matrix is generalized to a max algebra setting. The same is then studied for a finite product associated to a p-lettered word on N letters arising from a finite collection of nonnegative matrices, with each member having its maximum circuit geometric mean at most 1. PubDate: 2023-08-10 DOI: 10.1007/s10626-023-00380-0
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Artificial neural networks (ANNs) comprise parallel and distributed computational tools that can learn from data and make inferences (i.e., predictions) for highly nonlinear systems. By its turn, Petri nets (PNs) consist of well established modeling tools for parallel and distributed discrete event systems with a number of successful contributions to automation and control of complex industrial tasks. Thus, motivated by a long lasting interest in using the formalism of PNs either to emulate or to design neural network architectures, we revisit this research topic by resorting to the powerful modeling framework of hierarchical timed colored PNs (HTCPNs) to introduce a novel approach that builds a fully adaptive one-hidden-layered multilayer perceptron (MLP) model trained by the famed backpropagation algorithm. The resulting proposed model is called HTCPN-MLP and consists of a general structure capable of handling classification and regression tasks. In order to develop the HTCPN-MLP model, a perceptron-like colored PN (perceptron-CPN) model is first built upon a novel McCulloch-Pitts colored PN (McCulloch-Pitts-CPN) model of a neuron, this being another contribution of the current work. A pedagogical set of experiments is presented in order to highlight the learning capability of the proposed HTPCN-MLP model and its advantages with respect to alternative models available in the literature. PubDate: 2023-06-30 DOI: 10.1007/s10626-023-00377-9
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we investigate the use of supervisory control to maximize mean time to failure in a discrete event system framework. A complex engineering system is modeled as a discrete event system. Some of the states of the system are essential to the functionality of the system and are called required states. Some other states represent failures in the system and are called failure states. The control objective is to maximize the mean time to failure (MTTF) while allowing the system to visit all required states. The control is achieved by a supervisor that disables some controllable events based on monitoring the observable events as in classical supervisory control. To design such a supervisor, the MTTF of a supervised system is calculated by converting a discrete event system into a Markov chain having the same MTTF. Based on MTTF, two algorithms are developed that together allow us to design an optimal supervisor. The theoretical results are applied to power systems by investigating the maintenance management of equipment such as transformers. PubDate: 2023-06-10 DOI: 10.1007/s10626-023-00374-y
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we compare the infinitesimal perturbation analysis (IPA) and likelihood ratio (LR) derivative estimators for the steady-state system time of the M/M/1 queue. We derive the explicit formulas for the variances of both estimators. We then show IPA has smaller variance, which is often considered as a rule-of-thumb in the simulation literature. This is the first theoretical result that proves IPA has smaller variance than LR for steady-state performance measures. PubDate: 2023-05-23 DOI: 10.1007/s10626-022-00370-8
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Intermittent computing is an emerging paradigm for systems without batteries and powered by intermittent energy sources. This paradigm promises a more energy-efficient design of computing systems. It seems particularly well suited to the field of connected sensors that form the first level of the Internet of Things. This application domain requires a reactive computing model. The definition of an intermittent and reactive model is a problem that has not yet been fully explored in the literature. In this paper, we focus on the modeling and analysis of intermittent reactive systems. We first introduce an extension of Time Petri Nets with cost to model the different dimensions of the system: concurrency, real time, energy consumption and reward representing the gains generated by the system when it has succeeded in carrying out certain actions. We then aim to synthesize optimal runs of the model that achieve the highest possible reward under a given cost (energy) constraint. We propose a symbolic algorithm for constrained-cost state space computation and prove its termination. We then present algorithms for the synthesis of the optimal traces from an exhaustive or partial state space exploration. We finally illustrate the cost-optimal traces synthesis on a case study and show how that can be used online for joint management of computing time and energy. PubDate: 2022-12-20 DOI: 10.1007/s10626-022-00372-6
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract This paper presents an overview of the networked supervisory control frameworks for discrete event systems with imperfect communication networks, which are divided into the centralized setup, the decentralized setup and the distributed setup. The state-of-the-art works on networked supervisory control of discrete-event systems addressing the channel imperfections that are caused by channel delays, data losses or non-FIFO channels are discussed. By presenting the key concepts and main results of each representative work, we analyze the pros and cons of different approaches. Finally, we also provide a summary of the existing works, which roughly follow two different lines of thinking and result in two different verification or synthesis approaches. The first approach utilizes simple, non-networked plant models but relies on the development of sophisticated concepts of network controllability and observability to capture network imperfections, while the second approach embeds relatively complex yet verifiable channel models into the model of the networked plant and adopts the standard concepts of controllability and observability for the (verification and) synthesis of networked supervisors. Some future research topics are also presented. PubDate: 2022-12-16 DOI: 10.1007/s10626-022-00368-2
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A fundamental step in circuit design is the placement of pipeline stages, which can drastically increase the data throughput. Retiming allows optimizing the pipeline with regard to a criterion, for example the required number of registers. This article presents an extension of Timed Petri Net to model synchronous electronic circuits, in order to explore the design space of pipelines. The Timed Petri Nets “à la Ramchandani” with a maximal step firing rule, have notably been used for the modeling of electronic circuits. The RTPN extension, through the reset which model the pipeline stages, and through the delayable transitions which relax some temporal constraints, makes it possible to widen the design space of pipelined systems, and thus to deal with both the retiming and the verification. After a formal definition of this model, we present a method to explore pipelines verifying temporal properties. We apply our approach to a time-multiplexing property allowing the mutualization of operators while minimizing the number of registers. PubDate: 2022-12-15 DOI: 10.1007/s10626-022-00371-7
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Semi-Markov model is one of the most general models for stochastic dynamic systems. This paper deals with a two-person zero-sum game for semi-Markov processes. We focus on the expected discounted criterion with state-action-dependent discount factors. The state and action spaces are both Polish spaces, and the reward rate function is ω-bounded. We first construct a fairly general model of semi-Markov games under a given semi-Markov kernel and a pair of strategies. Next, based on the standard regularity condition and the continuity-compactness condition for semi-Markov games, we derive a “drift condition” on the semi-Markov kernel and suppose that the discount factors have a positive lower bound, under which the existence of the value function and an optimal pair of stationary strategies of our semi-Markov game are proved by using a general Shapley equation. Moreover, in the scenario of finite state and action spaces, a value iteration-type algorithm for approximating the value function and an optimal pair of stationary strategies is developed. The convergence and the error bound of the algorithm are also proved. Finally, we conduct numerical examples to demonstrate the main results. PubDate: 2022-11-05 DOI: 10.1007/s10626-022-00366-4
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Hybrid journal (It can contain Open Access articles)
[2468 journals]
