Wyniki wyszukiwania - BazTech

1

Waiting Nets: State Classes and Taxonomy

Loïc Hélouët, Pranay Agrawal

Fundamenta Informaticae

|

2024

|

Vol. 190, nr 2-4

63--107

EN

In time Petri nets (TPNs), time and control are tightly connected: time measurement for a transition starts only when all resources needed to fire it are available. Further, upper bounds on duration of enabledness can force transitions to fire (this is called urgency). For many systems, one wants to decouple control and time, i.e. start measuring time as soon as a part of the preset of a transition is filled, and fire it after some delay and when all needed resources are available. This paper considers an extension of TPN called waiting nets that dissociates time measurement and control. Their semantics allows time measurement to start with incomplete presets, and can ignore urgency when upper bounds of intervals are reached but all resources needed to fire are not yet available. Firing of a transition is then allowed as soon as missing resources are available. It is known that extending bounded TPNs with stopwatches leads to undecidability. Our extension is weaker, and we show how to compute a finite state class graph for bounded waiting nets, yielding decidability of reachability and coverability. We then compare expressiveness of waiting nets with that of other models w.r.t. timed language equivalence, and show that they are strictly more expressive than TPNs.

2

Study and analysis of discrete event-driven autonomous system with a case study for a robotics task

Raj Ravi, Kos Andrzej

Przegląd Elektrotechniczny

|

2023

|

R. 99, nr 9

50--56

EN

Highly probabilistic, potential, and dynamic domains are only relatively known to contribute classical techniques for complex system establishment impossible. Currently available technologies and strategies do not adequately address these novel needs. Thus, by enabling autonomous systems to adapt, decision-making and learning abilities, we can empower them with sufficient and appropriate expertise to recognize and address such issues. To address these requirements, discrete event-driven systems (DEDS) have been developed. This system can help the technologists of future autonomous systems by simulating the effect of auxiliary designs on the performance of the autonomous system. For modeling regular feedback of performance that is influenced by traditional techniques and depends on trust, the discrete event-driven method is most suited. This paper describes the DEDS system, the modeling of this system, and as well as the supervisory control system by explaining the supervisor, and partial supervisor. A comprehensive literature survey has been carried out in this article to explain the controllability, diagnosability, and observability potential of the DEDS system for various applications. Some of the major areas of applications such as healthcare, logistics, robotics, and banking sectors, have been discussed. Also, we have explained this system with the help of modeling a discrete event system for a queuing problem associated with robotics tasks as an example by the simulation with MATLAB 2022a. Lastly, the possible future research directions in the DEDS advancement have been provided.

PL

Wysoce probabilistyczne, potencjalne i dynamiczne domeny są znane z tego, że niemożliwe jest wniesienie klasycznych technik do tworzenia złożonych systemów. Obecnie dostępne technologie i strategie nie zaspokajają odpowiednio tych nowych potrzeb. Zatem, umożliwiając autonomicznym systemom adaptację, podejmowanie decyzji i zdolność uczenia się, możemy wyposażyć je w wystarczającą i odpowiednią wiedzę fachową, aby rozpoznawać i rozwiązywać takie problemy. Aby spełnić te wymagania, opracowano dyskretne systemy sterowane zdarzeniami (DEDS). System ten może pomóc technologom przyszłych systemów autonomicznych, symulując wpływ podsystemów pomocniczych na wydajność systemu autonomicznego. Do modelowania regularnych informacji zwrotnych na temat wyników, na które wpływają tradycyjne techniki i które zależą od zaufania, najbardziej odpowiednia jest metoda dyskretnych zdarzeń. W artykule opisano system DEDS, modelowanie tego systemu, a także system kontroli nadzorczej poprzez opisanie nadzorcy i kierownika częściowego. W tym artykule przeprowadzono obszerny przegląd literatury w celu wyjaśnienia sterowalności, diagnozowalności i potencjału obserwowalności systemu DEDS w różnych zastosowaniach. Omówiono niektóre z głównych obszarów zastosowań, takich jak sektor opieki zdrowotnej, logistyki, robotyki i bankowości. Wyjaśniliśmy również ten system za pomocą modelowania systemu zdarzeń dyskretnych dla problemu kolejkowania związanego z zadaniami robotyki na przykładzie symulacji z MATLAB 2022a. Na koniec przedstawiono możliwe przyszłe kierunki badań w zakresie rozwoju DEDS.

3

Capacity assessment of the airport cargo screening system under disruptions

Skorupski Jacek, Uchroński Piotr

Prace Naukowe Politechniki Warszawskiej. Transport

|

2023

|

z. 136

101--122

EN

Cargo shipments are a growing part of the transport carried out by many air carriers. One of the critical elements in this area of activity is shipment security inspection, which is a mandatory part of the transportation process. This article aimed to study the inspection system's capacity under disruption conditions and determine its dependence on possible technical and organizational improvements. For this purpose, simulation modeling was applied using a microscale model of the cargo security inspection process realized in a colored, timed, stochastic Petri net. Bayesian networks representing the actual process were used to validate the model. As a result of the research, experiments showed that for Katowice Airport in Pyrzowice, more advanced technical solutions can increase capacity by up to 50%. On the other hand, introducing modifications to the procedure, involving at least two checks using specialized assistive devices, can reduce it by up to 40%. Relatively small changes in capacity are expected with changes in the training and experience of screening operators. Based on these results, it can be recommended that airport managers consider using technical solutions with the parameters analyzed in the article. In addition, it is necessary to maintain the level of training at least at the current level. At the same time, any changes in control procedures should be made prudently, only when necessary, due to the need to strengthen the effectiveness of controls during periods of increased terrorist threat.

PL

Przesyłki cargo stanowią coraz większą część przewozów realizowanych przez wielu przewoźników lotniczych. Jednym z kluczowych elementów w tym obszarze działalności jest kontrola bezpieczeństwa przesyłek, która jest obowiązkowym elementem procesu przewozowego. Celem artykułu było zbadanie przepustowością systemu kontroli w warunkach zakłóceń, a także określenie jej zależności od możliwych ulepszeń technicznych i organizacyjnych. W tym celu zastosowano modelowanie symulacyjne z wykorzystaniem mikroskalowego modelu procesu kontroli bezpieczeństwa cargo zrealizowanego w postaci kolorowanej, czasowej, stochastycznej sieci Petriego. Do walidacji modelu wykorzystano sieci Bayesowskie reprezentujące rzeczywisty przebieg procesu. W wyniku przeprowadzonych eksperymentów badawczych wykazano dla lotniska Katowice w Pyrzowicach, że użycie bardziej zaawansowanych rozwiązań technicznych może zwiększyć przepustowość nawet o 50%. Z kolei wprowadzenie modyfikacji procedury, polegające na co najmniej dwukrotnej kontroli z wykorzystaniem specjalizowanych urządzeń wspomagających, może doprowadzić do jej zmniejszenia nawet o 40%. Stosunkowo niewielkie zmiany przepustowości są spodziewane w przypadku zmian w zakresie wyszkolenia i doświadczenia operatorów kontroli bezpieczeństwa. Na podstawie tych wyników można rekomendować, aby zarządzający portem lotniczym rozważyli użycie rozwiązań technicznych o parametrach, które były analizowane w artykule. Dodatkowo, konieczne jest utrzymanie poziomu wyszkolenia na co najmniej dotychczasowym poziomie, zaś wszelkie zmiany procedur kontroli należy wprowadzać rozważnie, tylko wówczas kiedy jest to niezbędne z powodu konieczności wzmocnienia skuteczności kontroli w okresach zwiększonego zagrożenia terrorystycznego.

4

Structural Liveness of Immediate Observation Petri Nets

Jančar Petr, Valůšek Jiří

Fundamenta Informaticae

|

2022

|

Vol. 188, nr 3

179--215

EN

We look in detail at the structural liveness problem (SLP) for subclasses of Petri nets, namely immediate observation nets (IO nets) and their generalized variant called branching immediate multi-observation nets (BIMO nets), that were recently introduced by Esparza, Raskin, and Weil-Kennedy. We show that SLP is PSPACE-hard for IO nets and in PSPACE for BIMO nets. In particular, we discuss the (small) bounds on the token numbers in net places that are decisive for a marking to be (non)live.

5

Maximal and Minimal Dynamic Petri Net Slicing

Llorens Marisa, Oliver Javier, Silva Josep, Tamarit Salvador

Fundamenta Informaticae

|

2022

|

Vol. 188, nr 4

239--267

EN

Petri net slicing is a technique to reduce the size of a Petri net to ease the analysis or understanding of the original Petri net. Objective: Presenting two new Petri net slicing algorithms to isolate those places and transitions of a Petri net (the slice) that may contribute tokens to one or more places given (the slicing criterion). Method: The two algorithms proposed are formalized. The maximality of the first algorithm and the minimality of the second algorithm are formally proven. Both algorithms together with three other state-of-the-art algorithms have been implemented and integrated into a single tool so that we have been able to carry out a fair empirical evaluation. Results: Besides the two new Petri net slicing algorithms, a public, free, and open-source implementation of five algorithms is reported. The results of an empirical evaluation of the new algorithms and the slices they produce are also presented. Conclusions: The first algorithm collects all places and transitions that may contribute tokens (in any computation) to the slicing criterion, while the second algorithm collects the places and transitions needed to fire the shortest transition sequence that contributes tokens to some place in the slicing criterion. Therefore, the net computed by the first algorithm can reproduce any computation that contributes tokens to any place of interest. In contrast, the second algorithm loses this possibility, but it often produces a much more reduced subnet (which still can reproduce some computations that contribute tokens to some places of interest). The first algorithm is proven maximal, and the second one is proven minimal.

6

Design optimization of the Petri net-based production process supported by additive manufacturing technologies

Patalas-Maliszewska Justyna, Wiśniewski Remigiusz, Topczak Marcin, Wojnakowski Marcin

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2022

|

Vol. 70, nr 2

art. no. e140693

EN

In the era of smart manufacturing and Industry 4.0, the rapid development of modelling in production processes results in the implementation of new techniques, such as additive manufacturing (AM) technologies. However, large investments in the devices in the field of AM technologies require prior analysis to identify the possibilities of improving the production process flow. This paper proposes a new approach to determine and optimize the production process flow with improvements made by the AM technologies through the application of the Petri net theory. The existing production process is specified by a Petri net model and optimized by AM technology. The modified version of the system is verified and validated by the set of analytic methods safeguarding against the formal errors, deadlocks, or unreachable states. The proposed idea is illustrated by an example of a real-life production process.

7

Verification and Parameter Synthesis for Real-Time Programs using Refinement of Trace Abstraction

Cassez Franck, Jensen Peter Gjøl, Guldstrand Larsen Kim

Fundamenta Informaticae

|

2021

|

Vol. 178, nr 1/2

31--57

EN

We address the safety verification and synthesis problems for real-time systems. We introduce real-time programs that are made of instructions that can perform assignments to discrete and real-valued variables. They are general enough to capture interesting classes of timed systems such as timed automata, stopwatch automata, time(d) Petri nets and hybrid automata. We propose a semi-algorithm using refinement of trace abstractions to solve both the reachability verification problem and the parameter synthesis problem for real-time programs. All of the algorithms proposed have been implemented and we have conducted a series of experiments, comparing the performance of our new approach to state-of-the-art tools in classical reachability, robustness analysis and parameter synthesis for timed systems. We show that our new method provides solutions to problems which are unsolvable by the current state-of-the-art tools.

8

The Complexity of Synthesis of b-Bounded Petri Nets

Tredup Ronny

Fundamenta Informaticae

|

2021

|

Vol. 183, nr 1-2

125--167

EN

For a fixed type of Petri nets τ, τ-SYNTHESIS is the task of finding for a given transition system A a Petri net N of type τ(τ-net, for short) whose reachability graph is isomorphic to A if there is one. The decision version of this search problem is called τ-SOLVABILITY. If an input A allows a positive decision, then it is called τ-solvable and a sought net N τ-solves A. As a well known fact, A is τ-solvable if and only if it has the so-called τ-event state separation property (τ-ESSP, for short) and the τ-state separation property (τ-SSP, for short). The question whether A has the τ-ESSP or the τ-SSP defines also decision problems. In this paper, for all b ∈ ℕ, we completely characterize the computational complexity of τ-SOLVABILITY, τ-ESSP and τ-SSP for the types of pure b-bounded Place/Transition-nets, the b-bounded Place/Transitionnets and their corresponding ℤb+1-extensions.

9

Symbolic and Structural Model-Checking

Thierry-Mieg Yann

Fundamenta Informaticae

|

2021

|

Vol. 183, nr 3-4

319--342

EN

Brute-force model-checking consists in exhaustive exploration of the state-space of a Petri net, and meets the dreaded state-space explosion problem. In contrast, this paper shows how to solve model-checking problems using a combination of techniques that stay in complexity proportional to the size of the net structure rather than to the state-space size. We combine an SMT based over-approximation to prove that some behaviors are unfeasible, an under-approximation using memory-less sampling of runs to find witness traces or counter-examples, and a set of structural reduction rules that can simplify both the system and the property. This approach was able to win by a clear margin the model-checking contest 2020 for reachability queries as well as deadlock detection, thus demonstrating the practical effectiveness and general applicability of the system of rules presented in this paper.

10

On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Finkel Olivier, Skrzypczak Michał

Fundamenta Informaticae

|

2021

|

Vol. 183, nr 3-4

243--291

EN

To identify the causes of performance problems or to predict process behavior, it is essential to have correct and complete event data. This is particularly important for distributed systems with shared resources, e.g., one case can block another case competing for the same machine, leading to inter-case dependencies in performance. However, due to a variety of reasons, real-life systems often record only a subset of all events taking place. To understand and analyze the behavior and performance of processes with shared resources, we aim to reconstruct bounds for timestamps of events in a case that must have happened but were not recorded by inference over events in other cases in the system. We formulate and solve the problem by systematically introducing multi-entity concepts in event logs and process models. We introduce a partial-order based model of a multi-entity event log and a corresponding compositional model for multi-entity processes. We define PQR-systems as a special class of multi-entity processes with shared resources and queues. We then study the problem of inferring from an incomplete event log unobserved events and their timestamps that are globally consistent with a PQR-system. We solve the problem by reconstructing unobserved traces of resources and queues according to the PQR-model and derive bounds for their timestamps using a linear program. While the problem is illustrated for material handling systems like baggage handling systems in airports, the approach can be applied to other settings where recording is incomplete. The ideas have been implemented in ProM and were evaluated using both synthetic and real-life event logs.

11

Free-choice Nets with Home Clusters are Lucent

van der Aalst Wil M. P.

Fundamenta Informaticae

|

2021

|

Vol. 181, nr 4

273--302

EN

A marked Petri net is lucent if there are no two different reachable markings enabling the same set of transitions, i.e., states are fully characterized by the transitions they enable. Characterizing the class of systems that are lucent is a foundational and also challenging question. However, little research has been done on the topic. In this paper, it is shown that all free-choice nets having a home cluster are lucent. These nets have a so-called home marking such that it is always possible to reach this marking again. Such a home marking can serve as a regeneration point or as an end-point. The result is highly relevant because in many applications, we want the system to be lucent and many “well-behaved” process models fall into the class identified in this paper. Unlike previous work, we do not require the marked Petri net to be live and strongly-connected. Most of the analysis techniques for free-choice nets are tailored towards well-formed nets. The approach presented in this paper provides a novel perspective enabling new analysis techniques for free-choice nets that do not need to be well-formed. Therefore, we can also model systems and processes that are terminating and/or have an initialization phase.

12

Extensions of Elementary Cause-Effect Structures

Czaja Ludwik

Fundamenta Informaticae

|

2021

|

Vol. 179, nr 2

93--111

EN

Cause-effect structures are objects of a formal system devised for modeling, testing and verifying properties of tasks, where parallel execution of actions is the most characteristic feature. This is an algebraic system called a quasi-semiring. In this paper elementary cause-effect structures, a system behaviourally equivalent to 1-safe Petri nets, are extended by the following features: weighted edges, multi-valued nodes having capacities (counterpart of place/transition Petri nets), inhibitors and a model of time. The extensions are accomplished by modifying the notion of state and semantics, but leaving unchanged structure of the quasi-semiring expressions.

13

Causal Semantics for BPP Nets with Silent Moves

Gorrieri Roberto

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 3

179--249

EN

BPP nets, a subclass of finite Place/Transition Petri nets, are equipped with some causal behavioral semantics, which are variations of fully-concurrent bisimilarity [3], inspired by weak [28] or branching bisimulation [12] on labeled transition systems. Then, we introduce novel, efficiently decidable, distributed semantics, inspired by team bisimulation [17] and h-team bisimulation [19], and show how they relate to these variants of fully-concurrent bisimulation.

14

Assessment of the possibility of using Bayesian nets and Petri nets in the process of selecting additive manufacturing technology in a manufacturing company

Topczak Marcin, Śliwa Małgorzata

Applied Computer Science

|

2021

|

Vol. 17, no 1

5--16

EN

The changes caused by Industry 4.0 determine the decisions taken by manufacturing companies. Their activities are aimed at adapting processes and products to dynamic market requirements. Additive manufacturing technologies (AM) are the answer to the needs of enterprises. The implementation of AM technology brings many benefits, although for most 3D printing techniques it is also relatively expensive. Therefore, the implementation process should be preceded by an appropriate analysis, in order, finally, to assess the solution. This article presents the concept of using the Bayesian network when planning the implementation of AM technology. The use of the presented model allows the level of the success of the implementation of selected AM technology, to be estimated under given environmental conditions.

15

Using Free-Choice Nets for Process Mining and Business Process Management

van der Aalst Will M. P.

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

9--15

EN

Free-choice nets, a subclass of Petri nets, have been studied for decades. They are interesting because they have many desirable properties normal Petri nets do not have and can be analyzed efficiently. Although the majority of process models used in practice are inherently free-choice, most users (even modeling experts) are not aware of free-choice net theory and associated analysis techniques. This paper discusses free-choice nets in the context of process mining and business process management. For example, state-of-the-art process discovery algorithms like the inductive miner produce process models that are free-choice. Also, hand-made process models using languages like BPMN tend to be free-choice because choice and synchronization are separated in different modeling elements. Therefore, we introduce basic notions and results for this important class of process models. Moreover, we also present new results for free-choice nets particularly relevant for process mining. For example, we elaborate on home clusters and lucency as closely-related and desirable correctness notions. We also discuss the limitations of free-choice nets in process mining and business process management, and suggest research directions to extend free-choice nets with non-local dependencies.

16

Modelling and control of discrete-event systems using petri nets and arduino microcontrollers

Kučera Erik, Haffner Oto, Leskovský Roman

Journal of Automation Mobile Robotics and Intelligent Systems

|

2020

|

Vol. 14, No. 3

20--27

EN

The main aim of proposed article is the design of new software system for modelling and control of discrete‐event and hybrid systems using Arduino and similar microcontrollers. In this paper we propose a new tool. It is based on Petri nets and it is called PN2ARDUINO. It offers a capability of communication with the microcontroller. Communication with the microcontroller is based on modified Firmata protocol so control algorithm can be implemented on all microcontrollers that support this type of protocol. The developed software tool was successfully verified for control of laboratory systems. It can also be used for education and also for research purposes as it offers a graphical way for designing control algorithm for hybrid and mainly discrete‐event systems. Proposed tool can enrich education and practice in the field of cyberphysical systems (Industry 4.0).

17

Target-oriented Petri Net Synthesis

Best Eike, Devillers Raymond, Erofeev Evgeny, Wimmel Harro

Fundamenta Informaticae

|

2020

|

Vol. 175, nr 1-4

97--122

EN

When a Petri net is synthesised from a labelled transition system, it is frequently desirable that certain additional constraints are fulfilled. For example, in circuit design, one is often interested in constructing safe Petri nets. Targeting such subclasses of Petri nets is not necessarily computationally more efficient than targeting the whole class. For example, targeting safe nets is known to be NP-complete while targeting the full class of place/transition nets is polynomial, in the size of the transition system. In this paper, several classes of Petri nets are examined, and their suitability for being targeted through efficient synthesis from labelled transition systems is studied and assessed. The focus is on choice-free Petri nets and some of their subclasses. It is described how they can be synthesised efficiently from persistent transition systems, summarising and streamlining in tutorial style some of the authors’ and their groups’ work over the past few years.

18

Logic and Algebra in Unfolded Petri Nets : on a Duality Between Concurrency and Causal Dependence

Bernardinello Luca, Ferigato Carlo, Pomello Lucia

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

39--56

EN

An orthogonality space is a set endowed with a symmetric and irreflexive binary relation (an orthogonality relation). In a partially ordered set modelling a concurrent process, two such binary relations can be defined: a causal dependence relation and a concurrency relation, and two distinct orthogonality spaces are consequently obtained. When the condition of N-density holds on both these orthogonality spaces, we study the orthomodular poset formed by closed sets defined according to Dacey. We show that the condition originally imposed by Dacey on the orthogonality spaces for obtaining an orthomodular poset from his closed sets is in fact equivalent to N-density. The requirement of N-density was as well fundamental in a previous work on orthogonality spaces with the concurrency relation. Starting from a partially ordered set modelling a concurrent process, we obtain dual results for orthogonality spaces with the causal dependence relation in respect to orthogonality spaces with the concurrency relation.

19

Integrating Petri Nets and Flux Balance Methods in Computational Biology Models : a Methodological and Computational Practice

Pernice Simone, Follia Laura, Balbo Gianfranco, Milanesi Luciano, Sartini Giulia, Totis Niccoló, Lió Pietro, Merelli Ivan, Cordero Francesca, Beccuti Marco

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

367--392

EN

Computational Biology is a fast-growing field that is enriched by different data-driven methodological approaches and by findings and applications in a broad range of biological areas. Fundamental to these approaches are the mathematical and computational models used to describe the different states at microscopic (for example a biochemical reaction), mesoscopic (the signalling effects at tissue level), and macroscopic levels (physiological and pathological effects) of biological processes. In this paper we address the problem of combining two powerful classes of methodologies: Flux Balance Analysis (FBA) methods which are now producing a revolution in biotechnology and medicine, and Petri Nets (PNs) which allow system generalisation and are central to various mathematical treatments, for example Ordinary Differential Equation (ODE) specification of the biosystem under study. While the former is limited to modelling metabolic networks, i.e. does not account for intermittent dynamical signalling events, the latter is hampered by the need for a large amount of metabolic data. A first result presented in this paper is the identification of three types of cross-talks between PNs and FBA methods and their dependencies on available data. We exemplify our insights with the analysis of a pancreatic cancer model. We discuss how our reasoning framework provides a biologically and mathematically grounded decision making setting for the integration of regulatory, signalling, and metabolic networks and greatly increases model interpretability and reusability. We discuss how the parameters of PN and FBA models can be tuned and combined together so to highlight the computational effort needed to perform this task. We conclude with speculations and suggestions on this new promising research direction.

20

Discovering Object-centric Petri Nets

van der Aalst Wil M. P., Berti Alessandro

Fundamenta Informaticae

|

2020

|

Vol. 175, nr 1-4

1--40

EN

Techniques to discover Petri nets from event data assume precisely one case identifier per event. These case identifiers are used to correlate events, and the resulting discovered Petri net aims to describe the life-cycle of individual cases. In reality, there is not one possible case notion, but multiple intertwined case notions. For example, events may refer to mixtures of orders, items, packages, customers, and products. A package may refer to multiple items, multiple products, one order, and one customer. Therefore, we need to assume that each event refers to a collection of objects, each having a type (instead of a single case identifier). Such object-centric event logs are closer to data in real-life information systems. From an object-centric event log, we want to discover an object-centric Petri net with places that correspond to object types and transitions that may consume and produce collections of objects of different types. Object-centric Petri nets visualize the complex relationships among objects from different types. This paper discusses a novel process discovery approach implemented in PM4Py. As will be demonstrated, it is indeed feasible to discover holistic process models that can be used to drill-down into specific viewpoints if needed.