Au cours des trois dernières décennies, les algorithmes heuristiques ont permis de réaliser des progrès remarquables dans la résolution des problèmes difficiles d'optimisation combinatoire. Cependant, la conception de ces algorithmes relève encore plusieurs challenges importants - en particulier, il semble qu'il est toujours difficile d'intégrer dans une heuristique une vue d'ensemble sur l'évolution de la recherche ou sur sa trajectoire. Prenant comme cadre expérimental le problème bien connu de la coloration de graphe, nous présentons de nouvelles stratégies qui font appel à certains mécanismes d'apprentissage pour rendre le processus de recherche plus "auto-conscient". Nous introduisons un algorithme qui est capable d'enregistrer sa trajectoire et d'interpréter sa propre évolution. Une analyse de l'espace de recherche a montré que les meilleures configurations visitées sont relativement proches les unes des autres, regroupées dans des sphères de rayon fixe. Avec ce type d'informations apprises, nous avons conçu : (i) des algorithmes de diversification qui "prennent garde" à ne pas visiter la même sphère à plusieurs reprises, (ii) des algorithmes d'intensification qui se focalisent sur l'exploration d'un périmètre limité en utilisant un parcours en largeur des sphères de ce périmètre, et (iii) des approches évolutionnistes pour gérer la diversité de sorte que les individus soient à la fois de bonne qualité eu égard à la fonction objectif et suffisamment distants les uns des autres. En fait, nous présentons une gamme de techniques (e.g. nouvelles fonctions d'évaluation) qui peuvent rendre la recherche heuristique "bien informée".

La formation industrielle est un domaine applicatif émergent pour la réalité virtuelle. GVT (Generic Virtual Training) est une plateforme de création d'environnements virtuels permettant une formation individuelle à des procédures industrielles de type maintenance. Cependant, les demandes industrielles évoluent et un nouveau besoin concerne la formation à des procédures collaboratives. Dans cette thèse nous proposons des modèles pour étendre les possibilités de GVT à la formation à des procédures collaboratives où des utilisateurs réels collaborent avec des humains virtuels. Nous présentons un modèle de l'activité des acteurs permettant de remplacer dynamiquement un apprenant par un humain virtuel. Ce modèle permet à un acteur de réaliser des actions en tenant compte de ses caractéristiques, du scénario, de l'environnement ainsi que de l'activité de ses partenaires. Nous proposons également une extension du langage de scénario LORA afin de décrire un scénario collaboratif. Un tel scénario décrit l'assignation des personnes aux actions et intègre des actions collaboratives. Le scénario a également été simplifié en rendant implicites des actions basiques comme la prise et la pose d'outils. Enfin, nous présentons le mécanisme de sélection d'action que nous avons mis en place et dont l'objectif est double : permettre à un humain virtuel de sélectionner une action à réaliser et donner des conseils à l'apprenant sur l'action à choisir. Il se compose de deux parties~: un module global de répartition des actions, chargé de déterminer le meilleur candidat pour chaque action du scénario, et des modules décisionnels dont dispose chaque acteur. Un acteur va ainsi se servir de son profil collaboratif (ensemble de règles de comportement) et de la suggestion du module de répartition pour choisir la prochaine action qu'il souhaiterait réaliser.Ces différents modèles ont été intégrés à GVT au sein d'un prototype. Dans cette thèse nous présentons un scénario applicatif réalisé dans GVT qui consiste à monter collaborativement un meuble livré en kit.

Actuellement, les applications interactives sont utilisées dans de nombreux domaines (guichets automatiques, tours de contrôle...), par des publics très différents (enfants, experts, handicapés...) et par un nombre important d'utilisateurs (interfaces de téléphones portables...) ou au contraire très spécifiques (logiciels conçus spécifiquement pour une entreprise). Elles sont de ce fait très diverses. De par la multiplicité des paramètres à prendre en compte, la conception et le développement des applications interactives sont devenus très coûteux. Afin de réduire ces coûts, des recherches sont actuellement menées sur le processus de conception. Cette thèse s'inscrit dans ces travaux. L'un des axes étudiés pour réduire le coût de production des applications interactives est la détection des erreurs le plus en amont possible pendant le processus de conception. Nous proposons de faciliter la vérification et la validation de la dynamique des applications (plus spécifiquement dénommée dialogue) tout au long de la conception, en fonction des spécifications recueillies auprès des futurs utilisateurs, exprimés sous forme de modèles de tâches. Les modèles de dialogue et les modèles de tâches représentent deux points de vue différents et complémentaires pour une même application. Nous proposons une approche de vérification de cohérence entre ces deux modèles tout au long du cycle de vie de l'application. Pour cela, nous avons défini des règles de cohérence entre les modèles que nous vérifions formellement en utilisant une méta-modélisation des formalismes que nous avons choisis après évaluation de leur utilisation pour une conception centrée-utilisateur.

La thématique principale des recherches présentées dans le présent travail concerne la modélisation de comportement d'agents informatiques hybrides au sein de Systèmes multi-agents (SMA). Un agent hybride est un agent qui dispose à la fois de comportements réactifs et de comportements cognitifs. S'inspirant à la base d'une réflexion principalement psychophysiologique du vivant, ce travail s'insère dans la problématique plus vaste de l'Intelligence artificielle distribuée et de la Vie artificielle. Partant du principe qu'un être humain, même s'il est cognitif, est aussi une espèce issue de la nature, le présent travail a pour objectif de mettre en place une architecture hybride générique d'agents artificiels dont la base du comportement est la motivation naturelle existant dans ces agents. La particularité de cette étude est que nous intégrons les concepts d'instinct, pulsion, faim, soif, etc. dans les agents cognitifs ou hybrides alors que dans la plupart des cas, ces notions ont toujours été l'apanage des modèles d'agents réactifs, particulièrement ceux basés sur les animâts. A terme, le raisonnement et les attitudes mentales ne seront donc plus les seuls facteurs à prendre en compte pour comprendre le comportement de ces agents cognitifs ou hybrides. Au niveau de l'architecture, nous obtenons ainsi à la base un modèle générique basé uniformément sur le concept de motivation naturelle et ce, quel que soit le type de l'agent étudié (réactif, cognitif, hybride). Au niveau du comportement, nous proposons de fournir un cadre hybride permettant de gérer, à un niveau générique, la sélection d'actions et plus précisément pour le présent contexte, la sélection de motivations. Le terme "générique" signifie que l'ensemble des critères fournis dans le mécanisme de sélection ne dépend pas de l'application mais permettra à l'utilisateur du système de se préoccuper au minimum des stratégies de sélection. Pour ce faire, il appartient au modèle de fournir les règles de positionnement pour chaque motivation. Sur le plan de la conception, nous adoptons un modèle issu d'un travail déjà existant dans le monde de la psychologie. Il s'agit de la pyramide du psychologue américain Abraham Maslow, portant sur les cinq besoins abstraits des humains. Le choix d'un modèle issu de l'étude du monde réel est important. Nous évitons en effet de devoir fournir des hypothèses théoriques de conception. Notre cadre d'application concerne en premier lieu une application cas d'école axée sur des agents fourrageurs qui se déplacent pour transporter des objets. Puis, dans un cadre plus réel, l'étude porte sur la simulation du comportement des paysans dans une région à Madagascar.

Les travaux de cette thèse se situent dans le cadre de la discrimination conceptuelle. Notre objectif est de caractériser des classes d'objets imprécis et structurés, à partir de concepts imprécis. Le modèle de représentation des données utilise un formalisme objet pour décrire les relations de dépendance entre les attributs et modélise l'imprécision à l'aide de termes linguistiques organisés en structure de treillis. Dans un premier temps, nous avons défini des fonctions de reconnaissances floues permettant de mesurer l'appartenance graduelle d'une observation à un concept. Ces fonctions sont construites à partir de métriques qui prennent en compte les différents aspects du modèle. Ensuite, à partir des notions de complétude et de consistance, nous avons élaboré des critères évaluant la qualité de discrimination d'un concept au contour imprécis. L'utilisation de quantificateurs et modificateurs linguistiques permet de préciser cette qualité de discrimination en tenant compte des erreurs de classement. Enfin, nous avons développé des méthodes d'acquisition de concepts imprécis à partir d'exemples et de contre-exemples. Ces méthodes déterminent un recouvrement des exemples à partir de descriptions reconnaissant au plus, un nombre fixe de contre-exemples. Nos méthodes de discrimination s'appuient, pour déterminer efficacement des concepts, sur les opérateurs de généralisation et sur la structure de treillis des descriptions discriminantes. Afin d'améliorer la qualité et la fiabilité des résultats, une procédure de sélection des attributs les plus discriminants a été proposée. Implantées dans un système d'apprentissage, ces différentes méthodes sont appliquées à plusieurs expérimentations.

Cette thèse propose des modèles multi-agents réactifs fondés sur un cadre formel pour la vérification de propriétés et les valider par la simulation et l'expérimentation en considérant la navigation multi-véhicules comme domaine d'application. La navigation multi-véhicules soulève plusieurs problématiques : perception de l'environnement, communication inter-véhicule, évitement d'obstacle, ... Dans ce contexte, nous avons abordé plus particulièrement les aspects suivants : - Concernant la navigation multi-véhicules nous avons abordé deux problèmes spécifiques : la conduite en convoi ou platooning et la navigation autonome. En ce qui concerne la navigation autonome, nous avons mis l'accent sur l'évitement d'obstacles. - Concernant l'approche proposée : nous adoptons les systèmes multi-agents réactifs, dont les interac- tions sont inspirée de la physique. Pour la conduite en convoi, nous proposons un modèle d'interaction basé sur la physique classique. En ce qui concerne l'évitement d'obstacles, nous adoptant un modèle inspiré de la physique statistique. - Nous plaçons les systèmes multi-agents réactifs dans un cadre formel pour la vérification des pro- priétés, compte-tenu des contraintes de sécurité imposées par la classe d'applications cible. Pour faire face à la complexité des modèles, nous proposons une règle et une méthode de vérification compositionnelle. Cela nous a permis de vérifier la satisfaction d'une propriété de sûreté essentielle : la non-collision entre véhicules lors de la conduite en convoi. - Nous abordons également la question de la validation du système multi-agents par la simulation et l'expérimentation : nous avons contribué au développement d'un simulateur de la conduite en convoi et la navigation autonome. Le simulateur prend en compte les caractéristiques physiques des véhicules et est couplé à un outil de visualisation 3D. Nous avons aussi expérimenté nos modèles sur des véhicules tels que le Cycab et le GEM Car.

En raison de problèmes opérationnels et d'autres événements inattendus, un grand nombre d'incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d'entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d'incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d'Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d'envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d'analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d'algorithmes itératifs avec l'objectif d'améliorer progressivement la solution quand le temps d'exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d'un incident font qu'il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d'évaluer la probabilité qu'un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l'optimum pour les instances de petite taille et moyenne alors qu'une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d'autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge

La prévention du risque volcanique est un enjeu majeur, notamment pour l'Etna, dont les éruptions fréquentes menacent la province de Catane. Sont exposés les éléments physiques nécessaires à la compréhension des mécanismes intervenant dans un écoulement de lave basaltique. Un système d'information intégrant les principaux aspects du risque volcanique et permettant la création de cartes de risques est alors proposé. Ce système comprend un modèle, basé sur les automates cellulaires et intégrant le traitement d'images satellitaires. Il permet de simuler l'évolution d'une coulée ainsi que son débit. Ce système est alors intégré dans un Système d'Information Géographique. Il est validé sur les éruptions 2001, 2006 et 2007. Enfin, nous développons, pour l'enrichir, un modèle numérique pour le refroidissement d'une coulée de lave à l'aide des Smoothed Particle Hydrodynamics. Ce modèle, validé sur différents cas test, est appliqué au refroidissement d'un lac et d'une coulée de lave. Keywords : risque volcanique, automates cellulaires, système de veille, information élaborée, système d'information géographique, Smoothed Particle Hydrodynamics

Gestion de l'accès aux données dans les réseaux sans fil en mode ad hoc

Cette thèse a pour cadre la spécification et la vérification de systèmes informatiques distribués, concurrents ou réactifs au moyen de graphes infinis associés à des spécifications de Thue et à certaines machines. Nous montrons que la classe des graphes des spécifications de Thue est fermée par produit synchronisé. Nous établissons aussi ce fait pour la classe des graphes des machines de Turing et pour certaines de ses sous-classes. Nous nous intéressons également à la conservation par produit synchronisé de la décidabilité de la théorie du premier ordre de graphes infinis. Nous montrons que le produit synchronisé de graphes de machines à pile restreint à sa partie accessible depuis un sommet donné à une théorie du premier ordre qui n'est pas décidable. Cependant, le produit synchronisé de graphes sans racine distinguée et dont la théorie du premier oordre est décidable a une théorie du premier ordre qui est décidable. Enfin nous mettons en évidence des liens qui unissent les graphes des machines de Turing à ceux des spécifications de Thue.