Le test d’identification d’état d’un système à événement discret (SED) a pour but d’en identifier l’état final, lorsque son état initial est inconnu. Une solution classique à ce problème, en supposant que le SED n’ait pas de sorties observables, consiste à déterminer une séquences de synchronisation, c.à-d., une séquence d’événements d’entrée qui conduit le SED sur un état connu. Ce problème a été résolu dans les années 60’ à l’aide des automates. L’objectif principal de cette thèse est d’utiliser les réseaux de Petri (RdP) pour obtenir une résolution plus optimal de ce problème et pour une plus large classe de systèmes.Initialement, nous montrons que la méthode classique peut être aisément étendue aux RdP synchronisés. Pour cette classe de réseaux non-autonomes, toute transition est associée à un événement d’entrée.L’approche proposée est générale, dans la mesure où elle s’applique à des RdP bornés arbitraires. Cependant, elle engendre le problème d’explosion combinatoire du nombre d’états. Pour obtenir des meilleures solutions, nous considérons une classe spéciale de RdP : les graphes d’état (GdE). Pour ces réseaux, nous considérons d’abord les GdE fortement connexes et proposons des approches pour la construction de SS, qui exploitent les propriétés structurelles du réseau en évitant ainsi une énumération exhaustive de l’espace d’état. Ces résultats s’étendent aux GdE non fortement connexes et à tout RdP synchronisé composé de GdE. Enfin, nous considérons la classe des RdP non bornés et proposons des séquences qui synchronisent le marquage des places non bornées. Une boîte à outils fournit toutes les approches décrites et est appliquée à des différents bancs d’essai. / State-identification experiments are designed to identify the final state of a discrete event system (DES) when its initial state is unknown. A classical solution, assuming the DES has no observable outputs, consists in determining a synchronizing sequence (SS), i.e., a sequence of input events that drives the system to a known state. This problem was essentially solved in the 60’ using automata. The main objective of this thesis is to use Petri nets (PNs) for solving the state-identification problem more efficiently and for a wider class of systems.We start showing that the classical SS construction method based on automata can be easily applied to synchronized PNs, a class of non-autonomous nets where each transition is associated with an input event. The proposed approach is fairly general and it works for arbitrary bounded nets with a complexity that is polynomial with the size of the state space. However, it incurs in the state-space explosion problem.Looking for more efficient solutions, we begin by considering a subclass of PNs called state machines (SMs). We first consider strongly connected SMs and propose a framework for SS construction that exploits structural criteria, not requiring an exhaustive enumeration of the state space of the net. Results are further extended to larger classes of nets, namely non strongly connected SMs and nets containing SM subnets. Finally we consider the class of unbounded nets that describe infinite state systems: even in this case we are able to compute sequences to synchronize the marking of bounded places. A Matlab toolbox implementing all approaches previously described has been designed and applied to a series of benchmarks.
| Identifer | oai:union.ndltd.org:theses.fr/2013AIXM4336 |
| Date | 23 September 2013 |
| Creators | Pocci, Marco |
| Contributors | Aix-Marseille, Università degli studi (Cagliari, Italie), Demongodin, Isabel, Giua, Alessandro, Giambiasi, Norbert |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0027 seconds