Search

Automata networks model all finite discrete dynamics. Each automaton has a state, evolving in discrete time steps, according to the states of other automata. The structure of interactions is described by a graph and local transition functions. A global dynamics is obtained with an update schedule, describing which automata apply their local function to change state, deterministically or nondeterministically. This rich expressivity allows to modelize phenomena observed in nature, where the paradigm of going from local rules to global behavior captures the essence of "complex" systems.An automata network is encoded by the (Boolean) circuits of its local functions. Since space is finite, the whole dynamics can be computed. We intend to understand variants of the model, through characterizing the computational complexities of problems: related to computing the graph of interactions, related to the asymptotic dynamics of a given automata network, related to the asymptotic dynamics of all possible networks on a given structure of interactions, and related to update schedules. It indirectly deals with the capacity to embed computation in different aspects of the model.We will draw key elements on the structure of interactions, the principle of locality, the importance of state alphabets, and encodings. This work will result in long term perspectives, on the extension of some partial information on a network, and the statement of "Rice-like" theorems formalized using model theory., Les réseaux d'automates modélisent toute dynamique discrète finie. Chaque automate possède un état, qui évolue en étapes de temps discrètes, selon l'état des autres automates. La structure des interactions est décrite par un graphe et des fonctions locales de transition. Une dynamique globale est obtenue avec un mode de mises à jour, décrivant quels automates appliquent leur fonction locale pour changer d'état, de façon déterministe ou non déterministe. Cette grande expressivité permet la modélisation de phénomènes observés dans la nature, où le paradigme du passage des règles locales au comportement global capture l'essence des systèmes « complexes ».Un réseau d'automates est encodé par les circuits (booléens) de ses fonctions locales. Puisque l'espace est fini, toute la dynamique peut être calculée. Nous proposons une compréhension des variantes du modèle, à travers la caractérisation des complexités algorithmiques de problèmes: liés au calcul du graphe des interactions, liés à la dynamique asymptotique d'un réseau d'automates donné, liés à la dynamique asymptotique de tous les réseaux possibles sur une structure d'interactions donnée, et liés à plusieurs modes de mises à jour. Il s'agira indirectement d'appréhender la capacité à implémenter du calcul dans les différentes facettes du modèle.Nous dégagerons des éléments clés sur la structure des interactions, le principe de localité, l'importance des alphabets d'états, et les encodages. Ce travail aboutira à des perspectives sur le long terme, guidées par l'extension d'informations partielles sur un réseau, et l'énoncé de théorèmes « à la Rice » formulés grâce à la théorie des modèles.

An automata network (AN) is a network of entities, each holding a state from a finite set and related by a graph structure called an interaction graph. Each node evolves according to the states of its neighbors in the interaction graph, defining a discrete dynamical system. This thesis work explores two main questions : a) what is the link between dynamical and computational properties of an AN ? and b) what is the impact of the interaction graph topology on the global dynamics of an AN ?.In order to tackle the first question a notion of computational complexity of an AN family is defined in terms of the computational complexity of decision problems related to the dynamics of the network. On the other hand, dynamical complexity of a particular AN family is defined in terms of the existence of attractors of exponential period. A strong link between these two last definitions is presented in terms of the notion of simulation between AN families. In this context, complexity is characterized from a localized standpoint by studying the existence of structures called coherent gadgets which satisfy two properties : i) they can locally interact in a coherent way as dynamical systems and ii) they are capable of simulating a finite set of functions defined over a fixed finite set.Finally, the second question is addressed in the context of a well-known family called freezing automata networks. An AN is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. A general model checking problem capturing many classical decision problems is presented. In addition, when three graph parameters, the maximum degree, the treewidth and the alphabet size are bounded, a fast-parallel algorithm that solves general model checking problem is presented. Moreover, it is shown that the latter problem is unlikely to be fixed-parameter tractable on the treewidth parameter as well as on the alphabet size when considered as single parameters.; Un réseau d’automates (RA) est un réseau d’entités (les automates) en interaction. Ces automates ont un nombre fini d’états possibles et sont reliés les uns aux autres par une structure de graphe appelée graphe d’interaction. Chaque automate évolue au cours du temps discret en fonction des états de ses voisins dans le graphe d’interaction, ce qui définit un système dynamique. Ce travail de thèse explore deux questions principales : a) quel est le lien entre les propriétés dynamiques et calculatoires d’un RA ? et b) quel est l’impact de la topologie du graphe d’interaction sur la dynamique globale d’un RA ?.Pour aborder la première question, une notion de complexité calculatoire est définie au regard de problèmes de décision liés à la dynamique des RA. De même, une notion de complexité dynamique est définie en termes de l’existence d’attracteurs de période exponentielle. Un lien fort entre ces deux définitions est présenté qui met en exergue le concept de simulation entre familles de RA. Dans ce contexte, la complexité se caractérise d’un point de vue localisé en étudiant l’existence de structures appelées gadgets qui satisfont deux propriétés : i) ils peuvent interagir localement de manière cohérente comme des systèmes dynamiques et ii) ils sont capables de simuler un ensemble fini de fonctions définies sur un ensemble fini.La deuxième question est quant à elle abordée dans le contexte des RA “freezing”. Un RA est “freezing” s’il y a un ordre sur les états de telle sorte que l’évolution de l’état de n’importe quel automate ne diminue pas quelle que soit l’orbite. Un problème général de model-checking capturant de nombreux problèmes de décision classiques est présenté. De plus, lorsque trois paramètres de graphe, le degré maximum, la largeur arborescente et la taille de l’alphabet sont bornés, un algorithme parallèle efficace résolvant le problème mentionné est donné. De plus, il est montré que ce problème est peu susceptible d’être FPT (fixed-parameter tractable) lorsque le paramètre de largeur arborescente ou celui de taille de l’alphabet sont considérés comme unique paramètre.

We explore different generalisations about natural computation models. The most theoretical is the notion of simulation between models, for which we describe a series of proposed definitions, by discussing the interests and the flaws of each of them. We take advantage of the most promising definitions to broaden the discussion on the possible consequences of simulation in complexity theory, such as the construction of new complexity classes by proposing the substitution of polynomial reduction by simulation.Our more applied approach consists in the generalisation of automata networks by means of modules that have inputs. This formalism makes it possible to approach the questions of the dynamics of interaction networks from a new angle : we explore its usefulness as a modular tool capable of flexibly simulating many similar objects, as well as the expressiveness of acyclic modules. These allow the characterisation of the dynamics of automata networks in the form of output functions. This expressiveness allows us to describe a process for optimising automata networks that reduces certain networks in size while retaining equivalent attractors., Nous explorons différentes généralisations concernant les modèles de calcul naturel. La plus théorique est la notion de simulation entre modèles, pour laquelle nous décrivons une série de propositions de définition, en discutant des intérêts et des failles de chacune d’elles. Nous profitons des définitions les plus prometteuses pour élargir le propos sur les possibles conséquences de la simulation en théorie de la complexité, comme la construction de nouvelles classes de complexité en proposant la substitution de la réduction polynomiale par la simulation. Notre approche plus appliquée consiste en la généralisation des réseaux d’automates sous formes de modules, qui possèdent des entrées. Ce formalisme permet d’approcher les questions de la dynamique des réseaux d’interactions sous un nouvelangle : nous explorons son utilité en tant qu’outil modulaire propre à simuler de façon flexible de nombreux objets similaires, ainsi que l’expressivité des modules acycliques. Ceux-ci permettent la caractérisation de la dynamique des réseaux d’automates sous la forme de fonctions de sortie. Cette expressivité nous autorise la description d’unprocessus d’optimisation de réseaux d’automates, qui réduit certains réseaux en taille tout en conservant des attracteurs équivalents.

The objects at the center of this thesis are discrete dynamical systems, understood through finite automata networks, defined as vectors of local transition functions (so that one function is associated with one automaton). These automata networks can be tools for modeling natural interaction systems (biological networks, particle networks in physics...) and the phenomena they induce. They can also be seen as a model of computation that can be studied per se. These objects are approached through the prism of complexity and (theoretical) simulation, each of these concepts forming the core of a part of the document.The first part is devoted to the relations between the interaction graph of a network, that represents the influences between its automata, and the underlying dynamics. First, the focus is put on the fixed points problem that aims to understand the information that gives an interaction graph on the number of fixed points of a network, and more precisely on the algorithmic complexity of this counting. Then, our interest is focused on a somewhat opposite property, namely expansiveness. A network is expansive if one can predict its initial configuration by observing only one of its components for a long enough time. In other words, a network is expansive if its dynamics is unstable and if any initial local perturbation has visible repercussions on each automaton. We characterize the interaction graphs that admit an expansive network and study the possibility of a network to be expansive according to several parameters like the size of the alphabet, the "expansiveness time" or the type of the computed functions (linear, abelian...).The second part is devoted to intrinsic simulation, namely the capacity of a network to contain the behavioral complexity and computational richness of another network. Specifically, we are interested in a specific simulation based on the ability of one network to simulate step by step the dynamics of another network. One of the parameters that is emphasized is the update mode, which represents the time steps in which automata update their state. It is well known that the dynamics of a network strongly depends on update modes. A natural question in this context is to understand what kind of dynamics can be simulated with a given update mode. First, we highlight that a sequentially updated network is less "powerful" than a network updated in parallel. While any dynamics can be simulated by a network evolving in parallel, we show that to be simulated sequentially, it may require larger networks for which we give bounds on the size. Next, we present the characteristics of "complete" networks in the sense that they can simulate all networks of a given size by varying their update modes. Finally, we emphasize several networks of minimum size, or of minimal "simulation time", and study the relations between these two parameters.; Les objets qui se trouvent au centre de cette thèse sont les systèmes dynamiques discrets, appréhendés à travers les réseaux d’automates finis, qui se définissent comme des vecteurs de fonctions locales de transition associées à chaque automate. Ces réseaux d’automates peuvent aussi bien être vus comme un outil pour modéliser des systèmes d’interactions naturels (réseaux biologiques, réseaux de particules physiques…) et les phénomènes qu’ils induisent que comme modèle de calcul que l’on peut étudier per se. Ces objets sont abordés à travers le prisme de la complexité et selon celui de la simulation (théorique), chacun de ces concepts formant le cœur d’une partie du document.La première partie est consacrée au rapport entre le graphe d’interaction d’un réseau, qui permet de représenter les influences entre ses automates, et la dynamique sous-jacente. Dans un premier temps, le focus est mis sur le problème des points fixes, ou configurations stables du réseau, qui vise à comprendre les informations que donne un graphe d’interaction sur le nombre de points fixes d’un réseau, et plus précisément sur la complexité algorithmique de ce comptage. Dans un second temps, l’intérêt est porté sur une propriété quelque peu opposée, à savoir l’expansivité. Un réseau est expansif si on peut prédire sa configuration de départ en observant une seule de ses composantes pendant suffisamment longtemps. Autrement dit, un réseau est expansif si sa dynamique est instable et que toute perturbation locale initiale a des répercussions visibles sur chaque automate. Nous caractérisons les graphes d’interactions qui admettent un réseau expansif et étudions la possibilité d’un réseau d’être expansif en fonction de plusieurs paramètres comme la taille de l’alphabet, le « temps d’expansivité » ou le type des fonctions calculées (linéaires, abéliennes...).La seconde partie est consacrée à la simulation intrinsèque, c’est-à-dire la capacité d’un réseau à contenir la complexité comportementale et la richesse calculatoire d’un autre réseau. Plus précisément, nous nous intéressons à une simulation spécifique fondée sur la capacité d’un réseau à simuler pas à pas toute la dynamique d’un autre réseau. L’un des paramètres sur lesquels l’accent est mis est le mode de mise à jour, qui représente les étapes de temps au cours desquelles les automates du réseau mettent à jour leur état. Il est bien connu que la dynamique d’un réseau dépend fortement des modes de mise à jour. Une question naturelle dans ce contexte est de comprendre quel type de dynamique peut être simulé avec un mode de mise à jour donné. Pour commencer, nous mettons en évidence le fait qu’un réseau mis à jour séquentiellement est moins « puissant » qu’un réseau mis à jour en parallèle. Alors que toute dynamique peut-être simulée par un réseau évoluant en parallèle, nous montrons que pour être simulée séquentiellement, elle peut nécessiter des réseaux plus grands dont nous bornons la taille. Ensuite, nous donnons les caractéristiques de réseaux « complets » dans le sens qu’ils peuvent simuler tous les réseaux d’une taille donnée en faisant varier leurs modes de mise à jour. Nous présentons enfin plusieurs réseaux de taille minimale, ou de « temps de simulation » minimal, et étudions les relations entre ces deux paramètres.

National audience; Cet article présente une nouvelle approche de modélisation et de supervision d’expérience interactive. Cette approche a été utilisée pour concevoir un jeu sérieux avec un robot Nao. Ce jeu permet aux plus jeunes, de découvrir de manière ludique l’exposition dédiée à l’ethnographie au muséum d’histoire naturelle de La Rochelle et l’exposition consacrée à l’archéologie au musée Sainte Croix de Poitiers. La phase de modélisation du jeu est divisée en deux parties. La première consiste à définir des comportements atomiques, regroupable en patterns. La seconde étape vise à définir des agents implémentant les patterns précédemment définis, en spécifiant les contenus et les comportements réels exécutés sur le procédé contrôlé, dans notre cas le robot Nao. Le premier objectif de cette approche est d’externaliser les contenus du jeu et les comportements réels du procédé (les différents postures et gestures de Nao) en base de données. Le second objectif est de pouvoir définir un jeu sérieux sans aucune contrainte concernant le procédé piloté.

Over the last few decades, the emergence of a wide range of new technologies has produced a massive amount of biological data (genomics, proteomics...). Thus, a very large amount of time series data is now produced every day. The newly produced data can give us new ideas about the behavior of biological systems. This leads to considerable developments in the field of bioinformatics that could benefit from these enormous data. This justifies the motivation to develop efficient methods for learning Biological Regulatory Networks (BRN) modeling a biological system from its time series data. Then, in order to understand the nature of system functions, we study, in this thesis, the dynamics of their BRN models. Indeed, we focus on developing original and scalable logical methods (implemented in Answer Set Programming) to deciphering the emerging complexity of dynamics of biological systems. The main contributions of this thesis are enumerated in the following. (i) Refining the dynamics of the BRN, modeling with the automata Network (AN) formalism, by integrating a temporal parameter (delay) in the local transitions of the automata. We call the extended formalism a Timed Automata Network (T-AN). This integration allows the parametrization of the transitions between each automata local states as well as between the network global states. (ii) Learning BRNs modeling biological systems from their time series data. (iii) Model checking of discrete dynamical properties of BRN (modeling with AN and T-AN) by dynamical formal analysis : attractors identification (minimal trap domains from which the network cannot escape) and reachability verification of an objective from a network global initial state.; Au cours des dernières décennies, l’émergence d’une large gamme de nouvelles technologies a permis de produire une quantité massive de données biologiques (génomique, protéomique...). Ainsi, une grande quantité de données de séries temporelles est maintenant élaborée tous les jours. Nouvellement produites, ces données peuvent nous fournir des nouvelles interprétations sur le comportement des Systèmes Biologiques (SB). Cela conduit alors à des développements considérables dans le domaine de la bioinformatique qui peuvent tirer profit de ces données. Ceci justifie notre motivation pour le développement de méthodes efficaces qui exploitent ces données pour l’apprentissage des Réseaux de Régulation Biologique (RRB) modélisant les SB. Nous introduisons alors, dans cette thèse, une nouvelle approche qui infère des RRB à partir des données de séries temporelles. Les RRB appris sont présentés avec un nouveau formalisme, introduit dans cette thèse, appelé " réseau d’automates avec le temps" (T-AN). Ce dernier assure le raffinement de la dynamique des RRB, modélisés avec le formalisme des réseaux d’automates (AN), grâce à l’intégration d’un paramètre temporel (délai) dans les transitions locales des automates. Cet enrichissement permet de paramétrer les transitions entre les états locaux des automates et aussi entre les états globaux du réseau. À posteriori de l’apprentissage des RRB, et dans le but d’avoir une meilleure compréhension de la nature du fonctionnement des SB, nous procédons à l’analyse formelle de la dynamique des RRB. Nous introduisons alors des méthodes logiques originales (développées en Answer Set Programming) pour déchiffrer l’énorme complexité de la dynamique des SB. Les propriétés dynamiques étudiées sont : l’identification des attracteurs (ensemble d’états globaux terminaux dont le réseau ne peut plus s’échapper) et la vérification de la propriété d’atteignabilité d’un objectif (un ensemble de composants) à partir d’un état global initial du réseau.

This works presents both theoretical and applied contributions in the field of discrete dynamical systems regarded as models of biological regulation networks. It puts forward the idea that to increase our comprehension of the living now requires a better understanding of the fundamental principles that govern it and that can be captured mathematically. With this baseline, the present thesis establishes and develops several theoretical bioinformatics reflections on the grounds of the formalism of automata networks -- especially Boolean. The three main themes it discusses are environmental robustness, behavioral combinatorics and structural robustness. Environmental robustness is approached through a study of how automata networks behave under the influence of fixed boundary conditions (in this setting, we give a generalisation to the non-linear case of a result known in the area of cellular automata). Behavioural combinatorics groups together in this document some in-depth investigations of interaction cycles, that is, structural motifs that are well known to play an important role in the dynamics of networks. We derive combinatorial characterisations as well as comparisons of the asymptotic behaviours in parallel of these cycles when they are isolated and when they interact through intersections. Finally, structural robustness is discussed using general transition graphs. With these, we propose in particular a formal general description of all possible behaviours of interaction cycles. We also establish a classification of networks robustness towards synchronism (in the changes they undergo) which leads to further analyses of non-monotony in automata interactions and the impact it has on a network global behaviour., Ce travail présente des contributions théoriques et appliquées dans le contexte des systèmes dynamiques discrets vus comme modèles des réseaux de régulation biologique. En mettant en avant le fait qu'accroître les connaissances du vivant nécessite aujourd'hui de mieux comprendre les propriétés mathématiques qui le régissent, il développe diverses réflexions menées en bio-informatique théorique en se fondant sur le formalisme des réseaux d'automates, notamment booléens. Les trois principaux thèmes abordés sur ces réseaux sont la robustesse environnementale, la combinatoire comportementale et la robustesse structurelle. La robustesse environnementale est notamment évoquée à travers une étude de la manière dont les réseaux d'automates réagissent face à l'influence de conditions de bord fixées (on y retrouve une généralisation au cas non-linéaire d'un résultat connu dans le domaine des automates cellulaires). La combinatoire comportementale est quant à elle abordée par les cycles d'interaction dont on connaît l'importance sur la dynamique des réseaux. Pour ces motifs particuliers et leurs intersections sont présentées des caractérisations combinatoires de leur comportement asymptotique en parallèle, qui font ensuite l'objet de comparaisons. Enfin, le thème de la robustesse structurelle est traité au travers du concept de graphe de transition général, qui a mené à mettre en évidence tous les comportements possibles des cycles d'interaction, à donner une classification de la robustesse des réseaux vis-à-vis de leur asynchronisme/synchronisme, de laquelle se sont imposées des études plus précises sur le rôle de la non-monotonie dans ces réseaux.

We consider the problem of automatic abstraction, from a low-level model given in term of network of interacting automata to a high-level message sequence chart. This allows the designer to play in a coherent way with the local and global views of a system, and opens new perspectives in reverse model engineering of concurrent systems. Our technique is based on a partial order semantics of synchronous parallel automata and the construction of a complete finite prefix of an event-structure coding all the behaviors. We present the models and algorithms. The examples presented in the report have been processed by a small software prototype we have implemented. \\ Nous considérons le problème de l'abstraction automatique d'un modèle de bas niveau donné en terme d'un réseau d'automates finis communicants, en un ensemble de scénarios donné sous la forme d'un HMSC ("High-level Message Sequence Chart"). Ceci permet au concepteur d'un modèle d'utiliser de façon cohérente les vues locale et globale d'un système, et ouvre de nouvelles perspectives pour la rétro-ingénierie des modèles e la répartition. Notre technique est fondée sur la sémantique d'ordre partiel d'automates parallèles synchronisés et la construction d'un préfixe fini complet de la structure d'événements codant l'ensemble des comportements. Nous présentons les modèles et les algorithmes. Les exemples présentés dans ce rapport ont été calculés par un prototype logiciel que nous avons développé.

Jury Jean-Claude POMEROL Jean Pierre MULLER C. MILLIER P. DUMOLARD D. MICHELLAND Philippe JORRAND Yves DEMAZEAU; This thesis addresses multi-agent systems (MAS) used for decision and negotiation support for land-use planning. In a first part, we discuss expertise, decision making and negotiation for linear infrastructures planning. We introduce MAS therefore with a design oriented approach. We build on various sociological references to analyze artificial social systems. In a second part, we discuss MAS for modelling, simulating and problem solving, and reactive vs. cognitive MAS. We describe the SMARRPS library dediacted to spatial problem solving. We finally give three formal models assessing convergence. In a third part, we describe two applications : SMAALA, for linear planning. This expertise support system computes a set of alternatives based on environmental sensitivity maps, on structural constraints, and on actors preferences models. We also present SANPA, an internet negotiation support system for land use planning. It uses an assistant agent community. They exchange with project support agents and SMAALA like models. SANPA uses structured messages, based on speach act theory. Nous conclude on some perspectives for environmental information systems using multi-agent approaches.; Cette thèse porte sur l'utilisation de systèmes multi-agents (SMA) pour l'aide à la décision et la négociation en aménagement du territoire, et a été conduite en collaboration avec la société CERREP SA. Dans une première partie, nous présentons les problèmes de l'expertise, de la décision et de la négociation pour des projets d'infrastructures linéaires. Puis nous introduisons les SMA, avec une définition orientée vers la conception. Nous proposons diverses références sociologiques pour structurer l'analyse des systèmes sociaux artificiels. Dans une deuxième partie, nous abordons l'utilisation de SMA, pour la modélisation, la simulation et la résolution de problèmes, mais aussi la dialectique entre SMA réactifs et cognitifs et l'apport de la sociologie. Nous présentons la bibliothèque SMARRPS dédiée à la résolution de problèmes spatialisés. Et nous poursuivons avec trois modèles formels abordant le problème de la convergence. Dans une troisième partie, nous décrivons deux applications réalisées : tout d'abord, le système SMAALA, pour l'aide à la localisation d'infrastructures. Ce système d'aide à l'expertise, calcule les ensembles de choix possibles (fuseaux) à partir de cartes de sensibilité environnementale de contraintes structurelles, et de descriptions des préférences des acteurs. Il s'appuie sur une architecture SMARRPS, proche des représentations utilisées par les experts, ajustable dynamiquement, et autorisant la spécification de contraintes hétérogènes. Puis nous présentons SANPA, un système pour l'aide à la négociation de projets en aménagement , de façon distribuée et asynchrone (sur internet). Ce système s'appuie sur une communauté d'agents assistants, échangeant avec un agent gestionnaire de projets, et des structures de type SMAALA pour la représentation spatiale. SANPA utilise des messages structurés, fondés sur la théorie des actes de langage. Nous concluons en indiquant les perspectives d'intégration de systèmes d'information en environnement sur les bases multi-agents.

Cette thèse consiste a modéliser un réseau neuronal situe en aval de la cochlee, qui constitue les premières couches de traitement des signaux de la parole issus du système auditif périphérique. Le cadre général du travail présente concerne la modélisation mathématique du réseau de neurones en question, la description de la machine massivement parallèle hypercube FPS T-40 utilisée comme outil de nos simulations, l'implantation du modèle neuronal sur cette machine parallèle et enfin les réalisations et interprétations de résultats de simulation. Ces travaux sont présentés en quatre chapitres comme suit: le premier chapitre s'inscrit dans le cadre général des réseaux de neurones, en commençant par les premiers modèles fondes sur des réseaux dits d'automates a seuil conçus par W. S. Mcculloch et W. Pitts des 1943, des réseaux d'automates cellulaires conçus par J. Von Neumann des 1948, etc... Le deuxième chapitre introduit la mesure de Gibbs, champs aléatoires et modèles de réseaux (déterministes et stochastiques). Puis, il présente l'étude du probleme d'ergodicité des réseaux de neurones probabilistes. Le troisième chapitre concerne l'environnement technique ou nos simulations de réseaux de neurones ont été effectuées. Il consiste en une description générale du principe du parallélisme et en une présentation détaillée de la machine massivement parallèle hypercube FPS T-40. Enfin, le quatrième chapitre comprend l'implantation de l'algorithme du réseau de neurones sur la machine massivement parallèle hypercube FPS T-40, l'expérimentation numérique et l'interprétation des résultats numériques. Ensuite, on a représente graphiquement ces résultats, a l'aide de mesures statistiques adéquates résumant le comportement dynamique du réseau, sur station de travail vinix (ordinateur spécialisé dans le traitement d'images)

Universités : Université scientifique et médicale de Grenoble et Institut national polytechnique de Grenoble; On s'intéresse à l'analyse et la simulation du comportement itératif de réseaux d'automates et plus particulièrement des réseaux d'automates à seuil (avec éventuellement introduction d'une période de réfraction). On donne, on approfondit des résultats concernant la longueur du cycle limite, le nombre de pas nécessaires pour l'atteindre, ainsi que l'organisation spatiale des cellules dans le cycle.

A lot of vision applications, for instance in robotics, require identification of 3D objects. Use of complex methods, based on model matching, is not always necessary, and may be too computationally expensive. We propose a fast and simple method for recognition of 3D objects. The method takes profit of the learning capabilities of a neural network. The idea is to train a neural network on some views of each object. In order to reduce the amount of data, the object is characterized by its silhouette. At the end of the learning phase, the generalization capabilities of the network allow it to recognize non-learned views. After a description of the proposed method, we will present experimental results obtained on a data base of 216 images., De nombreuses applications de vision, notamment en robotique, nécessitent l’identification d’objets tridimensionnels. L’emploi de méthodes complexes, à base de mise en correspondance avec des modèles, n’est pas toujours justifié, et peut être jugé trop coûteux en temps de calcul. Nous proposons une méthode rapide, et de mise en œuvre aisée, pour la reconnaissance d’objets 3D. La méthode exploite les capacités d’apprentissage et de généralisation d’un réseau d’automates. L’idée consiste à faire apprendre à un tel réseau un certain nombre de vues de chaque objet possible. Pour réduire la quantité de données à traiter, l’objet est caractérisé par sa silhouette. Enfin d’apprentissage, les capacités de généralisation du réseau d’automates lui permettent une reconnaissance sur des vues non apprises. Après une description de la méthode proposée, nous présenterons les résultats obtenus sur une base de données de 216 images