<p>In recent years, there has been much advancement in the area of verification of infinite-state systems. A system can have an infinite state-space due to unbounded data structures such as counters, clocks, stacks, queues, etc. It may also be infinite-state due to parameterization, i.e., the possibility of having an arbitrary number of components in the system. For parameterized systems, we are interested in checking correctness of all the instances in one verification step. </p><p>In this thesis, we consider systems which contain both sources of infiniteness, namely: (a) real-valued clocks and (b) parameterization. More precisely, we consider two models: (a) the timed Petri net (TPN) model, which is an extension of the classical Petri net model; and (b) the timed network (TN) model in which an arbitrary number of timed automata run in parallel. </p><p>We consider verification of safety properties for timed Petri nets using forward analysis. Since forward analysis is necessarily incomplete, we provide a semi-algorithm augmented with an acceleration technique in order to make it terminate more often on practical examples. Then we consider a number of problems which are generalisations of the corresponding ones for timed automata and Petri nets. For instance, we consider zenoness where we check the existence of an infinite computation with a finite duration. We also consider two variants of boundedness problem: syntactic boundedness in which both live and dead tokens are considered and semantic boundedness where only live tokens are considered. We show that the former problem is decidable while the latter is not. Finally, we show undecidability of LTL model checking both for dense and discrete timed Petri nets. </p><p>Next we consider timed networks. We show undecidability of safety properties in case each component is equipped with two or more clocks. This result contrasts previous decidability result for the case where each component has a single clock. Also ,we show that the problem is decidable when clocks range over the discrete time domain. This decidability result holds when the processes have any finite number of clocks. Furthermore, we outline the border between decidability and undecidability of safety for TNs by considering several syntactic and semantic variants.</p>

In recent years, there has been much advancement in the area of verification of infinite-state systems. A system can have an infinite state-space due to unbounded data structures such as counters, clocks, stacks, queues, etc. It may also be infinite-state due to parameterization, i.e., the possibility of having an arbitrary number of components in the system. For parameterized systems, we are interested in checking correctness of all the instances in one verification step. In this thesis, we consider systems which contain both sources of infiniteness, namely: (a) real-valued clocks and (b) parameterization. More precisely, we consider two models: (a) the timed Petri net (TPN) model, which is an extension of the classical Petri net model; and (b) the timed network (TN) model in which an arbitrary number of timed automata run in parallel. We consider verification of safety properties for timed Petri nets using forward analysis. Since forward analysis is necessarily incomplete, we provide a semi-algorithm augmented with an acceleration technique in order to make it terminate more often on practical examples. Then we consider a number of problems which are generalisations of the corresponding ones for timed automata and Petri nets. For instance, we consider zenoness where we check the existence of an infinite computation with a finite duration. We also consider two variants of boundedness problem: syntactic boundedness in which both live and dead tokens are considered and semantic boundedness where only live tokens are considered. We show that the former problem is decidable while the latter is not. Finally, we show undecidability of LTL model checking both for dense and discrete timed Petri nets. Next we consider timed networks. We show undecidability of safety properties in case each component is equipped with two or more clocks. This result contrasts previous decidability result for the case where each component has a single clock. Also ,we show that the problem is decidable when clocks range over the discrete time domain. This decidability result holds when the processes have any finite number of clocks. Furthermore, we outline the border between decidability and undecidability of safety for TNs by considering several syntactic and semantic variants.

A necessidade de aumento de produção, da redução de custos e do aumento da qualidade de bens de consumo, tem motivado a constante evolução dos sistemas de produção, migrando os tradicionais sistemas de produção para os modernos e complexos sistemas de manufatura, onde a performance depende da eficiência dos equipamentos e do controle do processo. Por outro lado, a eficiência dos equipamentos depende de sua confiabilidade e manutenabilidade. Neste trabalho a análise de performance é avaliada com o uso de Rede de Petri p-t-Temporizada e através de simulações, incluindo a avaliação da confiabilidade do processo pela análise da otimização da saída do sistema, isto é, quantidade de itens produzidos. Nesta abordagem, uma lógica linear foi desenvolvida e validada utilizando-se uma comparação de resultados das classes de estados do algoritmo proposto com a ferramenta de simulação Tina para um modelo de um esquema produtor consumidor. Apresenta-se um estudo de caso na indústria automotiva, consistindo na análise dos problemas reais enfrentados em uma fábrica de carrocerias, com o uso da Rede de Petri p-t-Temporizada. / The necessity of growing in production, with reduction of costs and improvement in the quality of consumption good, has motivated the constant evolution of production systems, transforming traditional production systems into the modern and complex manufacturing systems, where the performance depends on the efficiency of the equipment and process control. On the other hand, the equipment efficiency depends of their reliability and maintainability. In this work it is proposed a performance evaluation and analysis with the use of p-t- Timed Petri Nets using simulations, including process reliability analysis of the system through the throughput optimization, i.e., produced amount of goods. In this approach, a linear logic statement was developed and validated using a comparison of results of classes of states between the Tina simulation environment and the algorithm considered for a model of a producing consuming system. A case study in the automotive industry is presented, consisting of the analysis of the real problems found in a body shop plant, with the use of Timed Petri Net.

A necessidade de aumento de produção, da redução de custos e do aumento da qualidade de bens de consumo, tem motivado a constante evolução dos sistemas de produção, migrando os tradicionais sistemas de produção para os modernos e complexos sistemas de manufatura, onde a performance depende da eficiência dos equipamentos e do controle do processo. Por outro lado, a eficiência dos equipamentos depende de sua confiabilidade e manutenabilidade. Neste trabalho a análise de performance é avaliada com o uso de Rede de Petri p-t-Temporizada e através de simulações, incluindo a avaliação da confiabilidade do processo pela análise da otimização da saída do sistema, isto é, quantidade de itens produzidos. Nesta abordagem, uma lógica linear foi desenvolvida e validada utilizando-se uma comparação de resultados das classes de estados do algoritmo proposto com a ferramenta de simulação Tina para um modelo de um esquema produtor consumidor. Apresenta-se um estudo de caso na indústria automotiva, consistindo na análise dos problemas reais enfrentados em uma fábrica de carrocerias, com o uso da Rede de Petri p-t-Temporizada. / The necessity of growing in production, with reduction of costs and improvement in the quality of consumption good, has motivated the constant evolution of production systems, transforming traditional production systems into the modern and complex manufacturing systems, where the performance depends on the efficiency of the equipment and process control. On the other hand, the equipment efficiency depends of their reliability and maintainability. In this work it is proposed a performance evaluation and analysis with the use of p-t- Timed Petri Nets using simulations, including process reliability analysis of the system through the throughput optimization, i.e., produced amount of goods. In this approach, a linear logic statement was developed and validated using a comparison of results of classes of states between the Tina simulation environment and the algorithm considered for a model of a producing consuming system. A case study in the automotive industry is presented, consisting of the analysis of the real problems found in a body shop plant, with the use of Timed Petri Net.

This thesis is focused on distributed systems modeling using Petri nets. Distributed systems are increasingly being implemented in applications and computing systems, where their task is to ensure sufficient performance and stability for a large number of its users. When modeling a distributed systems, stochastic behavior of Petri nets is important, which will provide more realistic simulations. Therefore, this thesis focuses mainly on timed Petri nets. The theoretical part of this thesis summarizes distributed systems, their properties, types and available architectures, as well as Petri nets, their representation, types and the principle of an operation. In the practical part, two models were implemented, namely a horizontally scaled web application divided into several services with a distributed database and a large grid computing system, more precisely the BOINC platform with the Folding@home project. Both models were implemented using the PetNetSim library of Python. The goal of this thesis is to perform simulations on the created models for different scenarios of their behavior.

Ce mémoire, réalisé dans le cadre d’une thèse sous convention CIFRE avec la société Schneider-Electric et l’Université de Lorraine à travers le laboratoire du CRAN, porte sur l’évaluation des performances temporelles des architectures de contrôle-commande distribuées sur un réseau de communication. Le besoin industriel s’exprime sous la forme d’un outil d’aide au dimensionnement des architectures en phase d’avant-vente caractérisée par une connaissance partielle de ces dernières. Le problème scientifique sous-jacent est relatif à la génération automatique des modèles servant de support à l’évaluation. En effet, l’évaluation des performances doit être réalisée pour un ensemble important d’architectures, dans un temps court, difficilement compatible avec une construction manuelle des modèles. Notre contribution porte sur la définition formelle, à l’aide de réseaux de Petri colorés et temporisés, d’un modèle « constructeur » d’architectures embarquant des mécanismes de configuration, d’instanciation et de paramétrage. Plusieurs algorithmes sont proposés pour, d’une part, construire automatiquement le modèle d’une architecture donnée, à partir d’une description formelle de sa topologie et d’une librairie de modèles d’équipements de contrôle-commande, et, d’autre part, pour générer les observateurs requis à partir d’une description formelle des performances à évaluer. Ces différents algorithmes ont été implantés dans un outil interfacé, d’une part avec l’outil Schneider de description des architectures, et, d’autre part avec le simulateur de l’outil CPN Tools qui fournit une estimation des performances via des simulations de Monte-Carlo. L’intérêt de cette approche a été illustrée sur la base de quelques architectures types fournies par la société Schneider-Electric / This PhD dissertation, supported by CIFRE convention between the company Schneider-Electric and the University of Lorraine through the CRAN laboratory, deals with the assessment of temporal performances for a networked distributed control system. The industrial need was the development of a quotation and sizing tool of industrial control architecture during pre-sales stage. This stage is characterized by limited information about the process and the customers’ needs. The underlying scientific problematic was the ability to generate automatically models serving as support for the evaluation. In fact, performance assessment is realized for a wide range of architecture during a small amount of time, which is not compliant with a manual definition of the models. Our contribution is mainly based on a formal definition of a “builder” model with Colored and Timed Petri Nets which embeds mechanisms for configuration, instantiation and parameters setting of the architecture models. Several algorithms have been proposed for firstly build automatically the architecture Petri Nets model from a formal description of the topology and from a component model library and, secondly, for generating performance observers. Theses algorithms have been implemented on a tool gathering a user interface developed by Schneider –Electric and the Petri Nets simulator called CPN Tools which provides the performance assessment through Monte-Carlo simulation. The added value of this approach has been illustrated through case studies provided by Schneider-Electric

Presently information systems are increasingly penetrating to our daily life. Recently it is relevant to integrate the newest technologies. In that way traditional system becomes “smart” who are more economical, optimal, and self-sufficient. The biggest problem is to make a model of “smart” system. There were analyzed modeling methods, heating and cooling control systems in this job. Mathematical model for heating and cooling controller using timed Petri nets was presented. According to analyzed problems it was made verification with Matlab during experimental phase. There was made comparison evaluation of mathematical model made with timed Petri nets and fuzzy logic.

Cette thèse a pour objectif la génération de séquences de franchissement dans les Réseaux de Petri Temporisés (RdPT) en utilisant une approche incrémentale. Le verrou principal auquel est confronté ce travail est l’explosion combinatoire qui résulte de la construction classique du graphe d’accessibilité du RdPT. Nous proposons d’utiliser la notion de séquence de steps temporisés, afin d’exprimer progressivement l’ensemble des séquences de franchissements permettant de passer d’un état courant à un état cible. La notion de step temporisé correspond à une abstraction logique du comportement du système considéré. Le caractère incrémental de l’approche a pour objectif de gagner en efficacité. En effet, il consiste à exprimer tout nouvel état de la résolution par rapport à une profondeur K+1, en fonction d’un état atteint à la profondeur K. Ainsi, nous proposons plusieurs algorithmes de recherche incrémentale permettant d'améliorer l'efficacité de la résolution des problèmes d'accessibilité. Nous utilisons ensuite la programmation par contraintes pour modéliser le problème de recherche d’accessibilité dans un RdPT et mettre en œuvre notre approche incrémentale. Notre approche permet également d’ajouter des contraintes spécifiques à un contexte de résolution. Nous avons notamment utilisé cette possibilité pour proposer des techniques d'identification des jetons dans un RdPT borné, dans le cadre de la reconfiguration des systèmes manufacturiers. Nous concluons par l’évaluation de différentes applications constituant des « benchmarks » permettant d’illustrer l'efficacité des approches proposées / This PhD thesis is dedicated to the generation of firing sequences in Timed Petri Net (TPN) using an incremental approach. To reduce the influence of the well-known combinatorial explosion issue, a unique sequence of timed steps is introduced to represent implicitly the underlying reachability graph of the TPN, without needing its whole construction. This sequence of timed steps is developed based on the logical abstraction technique. The advantage of the incremental approach is that it can express any state just from the last step information, instead of representing all states before.Several incremental search algorithms are introduced to improve the efficiency of our methodology. Constraint programming techniques are used to model and solve our incremental model, in which search strategies are developed that can search for solutions more efficiently. Our methodology can be used to add specific constraints to model realistic systems. Token identification techniques are developed to handle token confusion issues that appear when addressing the reconfiguration of manufacturing systems. Experimental benchmarks illustrate the effectiveness of approaches proposed in this thesis

L’objectif de ce travail est d’exploiter les potentialités offertes par la conduite coopérative afin de fluidifier le trafic au niveau des intersections isolées. Pour ce faire, nous avons proposé un nouveau système de régulation au sein des intersections en s’inspirant du principe de l’intersection autonome. Nous avons appelé notre système : SVAC (système du véhicule-actionneur coopératif). Il repose sur la possibilité des échanges d’information entre le véhicule et son environnement de conduite.Le SVAC permet une régulation plus précise du trafic puisqu’il se base sur les requêtes de droit de passage envoyées par les véhicules réellement présents dans l’intersection. En outre, grâce à la signalisation à bord, la régulation consiste à définir les séquences de passage des véhicules, ce qui permet de personnaliser la signalisation. Le gain de précision soulève plusieurs obstacles. D’une part, nous nous heurtons systématiquement à l’absence de modèles mathématiques permettant d’aborder le problème. D’autre part, la simple énumération des séquences implique une explosion combinatoire, ce qui ne convient pas à l’application temps-réelle de la régulation des intersections. Pour s’affranchir des deux problématiques nous avons utilisé les réseaux de Petri P-temporisés. Le modèle nous a permis de décrire sous la forme d’équations mathématiques les compteurs des différents évènements observés par les véhicules. Deux objectifs de régulation ont été dégagés après avoir déduit le temps moyen d’attente basé sur la formule de Little. Le premier consiste à vider les intersections au plus tôt. Nous avons proposé un algorithme de programmation dynamique et deux heuristiques. La première heuristique est directement issue de l’analyse des propriétés du problème posé. La deuxième est basée sur l’algorithme de colonies de fourmis. En effet, le problème défini est un cas particulier du problème du voyageur de commerce. Le deuxième objectif de régulation consiste à minimiser instantanément la longueur de la file d’attente. Dans ce cadre, nous avons supposé le fonctionnement à vitesse maximale du réseau de Petri. L’utilisation des contraintes sur les ressources nous a permis de définir des règles simples de régulation en utilisant le mapping.Dans ce mémoire, nous avons utilisé la simulation microscopique basée sur les lois de poursuite pour s’approcher du comportement de conduite. La simulation a servi pour la comparaison des différentes approches proposées dans ce mémoire avec les régulateurs adaptatifs et les intersections autonomes. Dans tous les cas notre approche se distingue par un gain de capacité, ce qui nous a encouragé de reproduire le SVAC à travers un prototype de robots. Cette maquette montre la faisabilité du système au moins pour des applications industrielles. / The aim of this work is to benefit from the potential of the cooperative driving in order to optimize the traffic throughput at isolated intersections. To achieve this objective, we have proposed a new traffic control system for isolated intersections: Cooperative Vehicle-Actuation Signalization (CVAS). The concept of this new system is based on the assumption of the ability of exchanging information between each vehicle and the surrounding vehicles or the nearby infrastructure.The system allows more precise control of the traffic since it determines the right-of-way of each vehicle according to its corresponding data sent by the embedded wireless device. The right-of-way is displayed to the driver by means of the onboard signalization. The control system determines the sequence of the vehicles to be directed through the intersection. For the sake of benefiting the improvement brought by the new system, we face several challenges. On the one hand, we are confronted with the absence of a mathematical model to address the control problem. On the other hand, despite the fact that the optimal passing sequence of vehicles can be found by the simple enumeration of all feasible sequences, the exhaustive search does not fulfill the requirements of the real-time application. To overcome these two problems, we seek help from the P-timed Petri nets. This mathematical modeling tool is able to describe the events observed by the position markers in the form of mathematical equations. Two different objectives of the control have been derived from the Little's formula. The first one aims to minimize the maximum exit time of vehicles present in the intersection. An algorithm of dynamic programming and two heuristics have been proposed to achieve this objective. The first heuristic is based on the analysis of the properties of the control problem. The second heuristic is based on the analogy between the dealt problem and the problem of Traveling Salesman Problem, which can be solved successfully by the algorithm of ant colony system. The second objective of the control is to instantly minimize the queue length. A protocol of relaying the right of way has been determined from the assumption of a Petri net that operates at its maximum speed. This simple protocol of control can be extended to all possible layouts of the isolated intersections by using the technique of “mapping”.In this work, a microscopic model (car-following model) is used to simulate the driving behavior. The simulations show that the CVAS system outperforms the other systems which are popularly used at present. It is even better than some innovative systems based on the technology of the cooperative driving. The good results encouraged us to replicate the system under real conditions through a prototype of NXT robots. The tests of this prototype prove the feasibility of the system at least for industrial applications.

Turn-taking is a fundamental process that governs social interaction. When humans interact, they naturally take initiative and relinquish control to each other using verbal and nonverbal behavior in a coordinated manner. In contrast, existing approaches for controlling a robot's social behavior do not explicitly model turn-taking, resulting in interaction breakdowns that confuse or frustrate the human and detract from the dyad's cooperative goals. They also lack generality, relying on scripted behavior control that must be designed for each new domain. This thesis seeks to enable robots to cooperate fluently with humans by automatically controlling the timing of multimodal turn-taking. Based on our empirical studies of interaction phenomena, we develop a computational turn-taking model that accounts for multimodal information flow and resource usage in interaction. This model is implemented within a novel behavior generation architecture called CADENCE, the Control Architecture for the Dynamics of Embodied Natural Coordination and Engagement, that controls a robot's speech, gesture, gaze, and manipulation. CADENCE controls turn-taking using a timed Petri net (TPN) representation that integrates resource exchange, interruptible modality execution, and modeling of the human user. We demonstrate progressive developments of CADENCE through multiple domains of autonomous interaction encompassing situated dialogue and collaborative manipulation. We also iteratively evaluate improvements in the system using quantitative metrics of task success, fluency, and balance of control.