Grand bain Petit bain Chercher Soumettre

Politique Comité S'inscrire Aide

Sommaire de JEDAI (grand bain)

Dynamical Revision Operator with Memory

We have proposed in previous work a construction that allows to define operators for iterated revision from classical AGM revision operators. We called those operators revision operators with memory and show that the operators obtained have nice logical properties. But those operators can be considered as too conservative, since the revision policy of the agent, encoded as a faithful assignment, do not change during her life. In this paper we propose an extension of those operators, that aims to add more dynamic in the revision process.

Le problème de la cohérence des réseaux de contraintes du formalisme INDU

Dans cette contribution, nous étudions le problème de la cohérence du formalisme temporel qualitatif INDU introduit par Pujari et al. Nous prouvons en premier lieu la NPcomplétude du problème de la cohérence pour le sous-ensemble des relations préconvexes. Nous montrons qu’en revanche ce problème est polynomial pour l’ensemble des relations fortement préconvexes. Nous définissons un autre ensemble de relations INDU pour lequel le problème de la cohérence peut être décidé au moyen de la méthode de o-fermeture, une méthode similaire à celle de la méthode habituelle de la chemin-cohérence. Enfin, nous montrons que la méthode de o-fermeture est également complete pour l'ensemble des relations singleton de INDU imposant l'égalité des durées des intervalles

Décomposition sémantique pour la résolution de systèmes de contraintes de distance

Les solveurs de systèmes de contraintes combinent des techniques de filtrage avec des techniques de recherche systématiques qui ne tiennent pas compte de la sémantique des contraintes. Nous proposons dans cet article une technique de décomposition de domaines guidée par la sémantique des contraintes de distance. Cette décomposition sémantique, que nous nommerons SDD (Semantic Domain Decomposition), isole les sous-espaces disjoints dans l’espace de recherche. Les domaines des coordonnées d’un même point sont décomposés et réduits par la SDD en utilisant les propriétés de monotonie et de convexité des contraintes de distance. Nous montrons comment cette technique peut être combinée avec différents filtrage locaux. L’apport de la SDD est mis en évidence sur différents CSP constitués d’équations de distance.

Résolution de contraintes quantifiées sur les domaines finis par arc-consistance quantifiée

La généralisation des problèmes de satisfaction de contraintes (CSP) autorisant des variables arbitrairement quantifiées représente un problème difficile, d’intérêt à la fois théorique et pratique. Problème emblématique de la classe PSPACE (et complet pour cette classe), sa résolution permet d’apporter de nouvelles solutions à des problématiques aussi diverses que le calcul de plans d’actions, la vérification (notamment, mais pas exclusivement, le model-checking), les jeux, ou les problèmes de décision soumis à des données incertaines. De fait, la résolution de la version booléenne du problème (appelée QBF - pour Quantified Boolean Formulae - ou QSAT selon le cas) a fait l’objet d’un grand nombre de contributions récentes. Pourtant, et de même que pour le cas des problèmes de contraintes classiques, il semble légitime de ne pas se restreindre au domaine booléen et de considérer le problème des CSP quantifiés sur des domaines finis arbitraires. Le but est ainsi de tirer profit des outils disponibles dans ce cadre légèrement plus général, parmi lesquels une meilleure gestion de l’arithmétique, la possibilité de propager des intervalles, ou l’emploi de contraintes globales. La notion centrale des résolveurs complets de CSP est celle de propagation, qui permet de limiter l’explosion combinatoire d’une recherche exhaustive par un raisonnement local, et en particulier la notion d’arc-consistance. Nous proposons donc une généralisation de l’arc-consistance pour les contraintes quantifiées.

Algorithmes pour la détection de rigidités dans les CSP géométriques

Le théorème de Laman permet de caractériser la rigidité des systèmes à barres en 2D. La rigidité structurelle est basée sur une généralisation de ce théorème. Elle est généralement considérée comme une bonne heuristique pour identifier des sous-parties rigides dans les CSP géométriques (GCSP), mais peut en réalité se tromper sur des sous-systèmes très simples car elle ne tient pas compte des propriétés géométriques vérifiées par les objets. Hoffmann et al. ont proposé en 1997 des algorithmes à base de flots s’appuyant sur la caractérisation par rigidité structurelle pour répondre aux principales questions liées au concept de rigidité : déterminer si un GCSP est rigide, identifier ses composantes rigide, sur-rigide et sous-rigide, en minimiser la taille, etc. La rigidité structurelle étendue, une nouvelle caractérisation de la rigidité, a été proposée par Jermann et al. en 2002. Elle permet de prendre en compte les propriétés géométriques du GCSP étudié et s’avère ainsi plus fiable. Dans le présent article, nous présentons des algorithmes qui répondent aux principales questions liées à la notion de rigidité en utilisant cette nouvelle caractérisation. Plus précisément, nous montrons que deux modifications de la fonction de distribution de flots utilisée dans les algorithmes de Hoffman et al. permettent l’obtention d’une famille d’algorithmes basés sur la rigidité structurelle étendue. Nous démontrons la correction et la complétude des nouveaux algorithmes et étudions leur complexité en pire cas.

Une contrainte Stretch expliquée

Nous montrons dans cet article comment étendre une contrainte globale, stretch, pour l’utiliser dans un contexte expliqué. Ceci se traduit notamment par la production d’explications précises pour chacune des décisions prises lors du filtrage. Les expérimentations montrent une amélioration notable de la résolution de problèmes mettant en œuvre une telle contrainte.

Hybridation de GWW avec de la recherche locale

Une nouvelle métaheuristique pour l’optimisation combinatoire, appelée “Go With the Winners” (GWW) a été proposée par Dimitriou et Impagliazzo en 1996. GWW gère plusieurs configurations en même temps, utilise un seuil pour éliminer les pires configurations, et inclut une étape de marche aléatoire qui permet une distribution uniforme des configurations visitées dans chaque sous-problème. Cet article propose de remplacer l’étape de marche aléatoire de GWW par de la recherche locale pour favoriser les meilleures solutions. Nous proposons une instance de cet algorithme hybride, appelée GWW-idw. Nous comparons difféerentes manières de baisser le seuil. Nous ajoutons un seul paramêtre pour intégrer la recherche locale dans le schéma existant. Nous montrons comment et dans quel ordre, régler les paramètres. Une étude expérimentale a été menée sur des instances difficiles de coloriage de graphe issues du challenge DIMACS et sur des problèmes d’affectation de fréquences du CELAR. Les meilleures bornes connues ont été trouvées sur toutes les instances.

Optimisation sous contraintes en contexte anytime

Cet article propose une nouvelle méthode hybride pour la résolution de problèmes d’optimisation sous contraintes en contexte anytime. Ces problèmes sont modélisés sous forme de WCSP. Notre méthode (VNS/LDS+CP) repose sur une recherche locale à voisinages de taille variable (VNS), dont l’exploration est assurée par une recherche arborescente tronquée (de type déviation limitée LDS), aidée par une propagation de contraintes (CP) à base de calcul de minorants. Les expérimentations menées sur les jeux tests du CELAR montrent des améliorations conséquentes sur les autres méthodes. Enfin, VNS/LDS+CP a été appliquée avec succès pour résoudre un problème de réservation de connexions dans les réseaux ATM.

Recherche arborescente bornée pour la résolution de CSP valués

Nous proposons une nouvelle méthode pour résoudre des problèmes de satisfaction de contraintes valués. Cette méthode est basée à la fois sur des techniques de backtracking (branch and bound) et sur la notion de décomposition arborescente d’un réseau de contraintes valué. Elle vise à bénéficier des avantages des deux approches, à savoir l’efficacité pratique de l’énumération et la garantie de bornes de complexité en temps offerte par les méthodes structurelles. En effet, la complexité en temps est en O(d^^(w+1)) avec w une approximation de la tree-width du graphe de contrainte et d la taille du plus grand domaine. L’obtention d’une telle borne de complexité repose sur l’exploitation de valuations locales qui fournissent des bornes optimales sur des sous-problèmes définis via la décomposition arborescente. De plus, nous associons ces valuations locales à des affectations partielles appelées "goods structurels valués". La mémorisation et l’emploi de ces goods permettent d’une part d’éviter de réexplorer plusieurs fois certaines parties de l’espace de recherche, et d’autre part, de limiter la quantité de mémoire qui est généralement requise par des méthodes basées sur la programmation dynamique. Enfin, cette méthode constitue une extension naturelle de la méthode BTD proposée dans le cadre des CSP classiques.

Un test de canonicité pour éliminer des configurations redondantes

Configurer consiste à simuler la réalisation d'un produit complexe à partir de composants choisis dans un catalogue de types, en s'appuyant sur les relations connues entre ces types, et en instanciant leurs attributs. C'est un problème combinatoire relevant de la programmation par contraintes, ayant fait l'objet de nombreuses approches différentes depuis le système R1. Une difficulté inhérente aux problèmes de configuration est l'existence de nombreux isomorphismes entre les interprétations. Nous décrivons une approche pour étendre de façon signicative les isomorphismes reconnus par les configurateurs, indépendamment du formalisme choisi, et sans nécessiter de modifier le modèle. Nous exploitons pour cela les propriétés d'un fragment reconnaissable de tout problème de configuration, le sous-problème structurel, dont les solutions canoniques peuvent être produites à coût réduit, pour des bénéfices considérables. Nous décrivons un algorithme pour le test de canonicité des configurations, pouvant être décliné comme une contrainte, dont nous donnons la complexité et le pouvoir de coupure.

Un CSP comme comportement d'agent. Application à la résolution d'équations en physique des milieux granulaires

En physique des milieux granulaires, des méthodes de simulations numériques sont utilisées notamment pour tenter de comprendre la connexion entre les grains et les structures mécaniques macroscopiques dans le tas. Par le passé, nous avons proposé une modélisation multi-agent originale qui permet de résoudre des tas de sable bidimensionnels à l'équilibre statique. Mais, le caractère stochastique de la recherche locale de solutions d'équilibre pose le problème de la couverture de l'espace des solutions par cet algorithme. La résolution de ce problème par une approche purement CSP se révèle dificile du fait de la taille gigantesque du problème à traiter. Nous proposons donc de mettre en oeuvre des techniques de CSP comme comportements de résolution local de l'équilibre d'agents-grains.

Etre ou ne pas être... une contrainte globale

La propagation de contraintes est un composant essentiel de la programmation par contraintes. Dans les dix dernières années, le concept de "contrainte globale" est devenu incontournable puisqu'il est important, dans beaucoup d'applications, d'obtenir un bon niveau de filtrage pour un coût raisonnable. Cependant, même si le nom de "contrainte globale" est parlant par lui-même, il n'existe pas de définition formelle de ce concept. Cet article propose diverses notions de globalité qui permettent de comprendre ce concept plus finement.

Algorithme d'itération sur les politiques avec approximation linéaire

Nous utilisons, dans le cadre d'un espace continu, les résultats de majoration en norme L2 [Munos03] de la performance des politiques calculées par un algorithme d'itération sur les politiques avec approximation. Ces majorations sont plus fines que celles usuelles en norme sup [Bertsekas96] et sont pertinentes lorsque l'on considère des approximations de type régression par les moindres carrés (car la régression se fait en minimisant une erreur L2). Nous présentons deux approches d'approximation basées sur le résidu de Bellman et sur les différences temporelles, indiquons leur possible implémentation par un algorithme d'apprentissage par renforcement, et les expérimentons sur un problème de remplacement optimal.

Approche connexionniste du contrôle optimal

Les algorithmes connexionnistes sont inspirés de la manière dont le cerveau traite l'information : ils impliquent un grand nombre d'unités simples fortement interconnectées, manipulant des informations numériques de manière distribuée et massivement parallèle. Le contrôle optimal est une théorie computationnelle qui permet d'écrire l'interaction entre un agent et un environnement : elle permet de formaliser précisément le problème consistant à atteindre un certain nombre de buts via l'interaction. Si le contrôle optimal caractérise un "but" (l'optimisation d'un critère), l'approche connexionniste suggère, elle, une "manière" de calculer. Nous décrivons plusieurs problématiques s'inscrivant dans le cadre du contrôle optimal et montrons qu'elles admettent des solutions qui sont connexionnistes : 1) Le contrôle optimal et sa variante adaptative (l'apprentissage par renforcement) dans un petit espace d'états 2) L'apprentissage d'une représentation pour approximer le problème de contrôle optimal ayant un grand espace d'états.

Influence de la structure de modélisation en planification probabiliste

Nous présentons dans cet article un formalisme innovant de planification stochastique en vue de résoudre des problèmes d'exploration autonome en présence d'incertitudes sur le résultat des actions. Bien que les Processus Décisionnels Markoviens (PDM) soient bien adaptés aux problèmes de navigation stochastique, leur formalisme classique impose une énumération explicite et non structurée de tous les états du système. Ce formalisme ne permet donc pas de résoudre des problèmes d'exploration réalistes, dont le nombre important de variables d'état induit une explosion combinatoire. Ainsi, nous proposons de résoudre la composante de navigation du problème d'exploration à l'aide de PDM décomposés qui tirent profit de la topologie de l'espace d'états géographique en regroupant les états géographiques au sein de régions faiblement couplées, qui définissent un PDM abstrait structuré de moindre taille. Nous présentons et comparons également deux algorithmes de résolution des PDM décomposés.

Représentation d'actions et planification en environnement partiellement observable: une approche fondée sur la logique épistémique

Nous proposons une approche purement logique pour la planification en environnement partiellement observable. Les états de connaissance sont exprimés dans un fragment adéquat de la logique épistémique S5. Nous montrons comment les effets des actions (tant physiques qu'épistémiques) peuvent se transposer du niveau objectif au niveau des états de croyance. Nous montrons comment la progression, la régression et génération de plans peuvent être réalisées in ce cadre.

L'apprentissage par renforcement indirect dans les systèmes de classeurs

Les systèmes de classeurs sont des systèmes à base de règles qui combinent une capacité d'apprentissage par renforcement et une capacité de généralisation. Au lieu d'associer des valeurs à des couples (état, action), comme c'est le cas dans le cadre de l'apprentissage par renforcement tabulaire, ils associent des valeurs à des couples (condition, action), dans lesquels la partie condition peut être vérifiée par plusieurs états, ce qui permet la généralisation. Les mécanismes d'apprentissage par renforcement habituels peuvent alors être appliqués à une telle représentation. Récemment, une nouvelle famille de systèmes de classeurs, dits à << anticipation >>, est apparue, dans laquelle l'apprentissage par renforcement réalisé est un apprentissage indirect, ce qui signifie que l'agent construit un modèle de ses interactions avec son environnement, et se sert de ce modèle pour accélerer la convergence de l'apprentissage. Les architectures de la famille Dyna sont toutes construites sur ce modèle. L'objet de cette contribution est de présenter un système de classeurs à anticipation, MACS, et de montrer comment on peut considérer MACS comme un cas particulier de la famille des architectures Dyna.

Processus Décisionnels de Markov décentralisés et interactifs avec des contraintes temporelles

Nous proposons, dans cet article, une approche pour la planification multi-agent dans des environnements incertains. Les méthodes de planification existantes ne sont pas adaptées à certains problèmes de planification sous incertitude comme par exemple les robots planétaires. En effet, elles présentent de nombreuses limitations : 1) elles utilisent une modélisation simple du temps et des actions, 2) elles ne considèrent que des contraintes temporelles simples (échéances sur les tâches), 3) et elles ne peuvent être utilisées que pour de petits problèmes. De plus, ces méthodes ne permettent de planifier que les actions d'un seul agent et leur adaptation à des systèmes multi-agents n'est pas immédiate. Il n'est pas possible de planifier les actions de chaque agent indépendamment des autres agents, il est nécessaire de trouver des moyens de coordination permettant aux agents de coopérer.
Nous proposons un système de planification multi-agent permettant de considérer un modèle plus complexe du temps et des actions. Notre approche tient compte de l'incertitude sur les durées des actions et les consommations de ressources. Elle permet également de traiter différents types de contraintes, et plus particulièrement les contraintes temporelles et de précédence. Nous traitons des problèmes dans lesquels des agents doivent maximiser la valeur globale de l'exécution d'un ensemble de tâches appelé "mission". Pour ce faire, nous avons recours à des Processus Décisionnels de Markov (MDP) distribués. Notre approche consiste à mettre en place un MDP pour chaque agent permettant de planifier les actions individuelles de celui-ci. Afin de synchroniser et de coordonner les politiques des agents, nous avons recours à la notion de coût occasionné. Cette dernière permet une coordination sans communication entre agents.
Après avoir décrit notre système de planification, nous présenterons différents résultats expérimentaux montrant la robustesse de notre approche.

Analyse d'accessibilité dans l'espace des plans partiels

Nous présentons ici de nouvelles solutions algorithmiques pour le contrôle de la recherche de planificateurs non linéaires. Notre approche est fondée sur l'utilisation d'analyses d accessibilité dans l'espace des plans partiels. Nous proposons l'exploitation d une structure disjonctive permettant de circonscrire une portion pertinente de l'espace de recherche et nous montrons comment en dériver un estimateur heuristique. Une contribution importante de ce travail est la mise en avant d'une estimation uniforme des différentes transformations possibles d'un plan partiel, tant les etablisseurs de buts non-expliqués que les contraintes permettant d'écarter des conflits potentiels.

Une approche dynamique pour instancier des réseaux de contraintes spatiales qualitatives

L'objet de cet article est de proposer une instanciation consistante de tout réseau chemin-consistant de contraintes atomiques de RCC-5. L'idée de base est d'associer à chaque élément d'un réseau de RCC-5 un sous-ensemble de N qui ne contient que des multiples de nombres premiers spécifiques, dont on fixera la nature en cours de construction.

Raisonnement automatique pour la logique modale KD45 quantifiée à domaine uniforme

Cet article s'intéresse à la question de la déduction automatique pour la conception de systèmes « intelligents » de dialogues coopératifs fondés sur la théorie de l'interaction rationnelle. Nous présentons d'abord le système de raisonnement automatique proposé par Bretier. Il est basé sur le principe de résolution qui étend celui de Robinson à la logique modale des prédicats KD45 à domaine uniforme. Pour la skolémisation, Bretier utilise l opérateur bullet de Konolige. Les résolvantes obtenues sont des formules modales quantifiées. Nous étudions ce système et montrons à travers des exemples qu il n'est ni adéquat, ni complet pour la réfutation. Nous proposons alors un nouveau système intégrant au système de Bretier la traduction et la skolémisation proposées par Herzig. La solution exposée enchaîne récursivement des fonctions de traduction, skolémisation et dé-traduction, tout en contrôlant soigneusement la déskolémisation : il s'agit de reconstruire un quantificateur aussitôt qu'une règle a été appliquée, pour recentraliser aussitôt l'information distribuée par la skolémisation. L'adéquation et la complétude du nouveau système sont démontrées.

Étude Comparative d'Algorithmes d'Apprentissage de Structure dans les Réseaux Bayésiens

Les réseaux bayésiens sont un formalisme de raisonnement probabiliste de plus en plus utilisé pour des tâches aussi diverses que le diagnostic médical, la fouille de texte ou encore la robotique. Dans certains cas, la structure du réseau bayésien est fournie a priori par un expert. Par contre, la détermination de cette structure à partir de données est une problématique NP-difficile pour laquelle de nombreuses méthodes d'apprentissage automatique ont été proposées ces dernières années (recherche d'un arbre optimal, recherche gloutonne, prise en compte de données incomplètes, etc). Après un bref rappel des principales méthodes existantes, nous proposons deux séries de tests destinés tout d'abord à évaluer la précision de ces méthodes en essayant de retrouver un graphe connu, et ensuite à tester leur efficacité face à des problèmes de classification. Les résultats obtenus nous permettent d'étudier par exemple la robustesse des méthodes pour la détection de relations "faibles" entre les variables, ou encore leur comportement en fonction du nombre d'exemples.

L'opérationalisation des ontologies : une méthodologie et son application au modèle des Graphes Conceptuels

Le travail présenté dans cet article s'inscrit dans le cadre de l'ingénierie ontologique, et traite plus particulièrement de l'intégration des ontologies de domaine au sein de Systèmes à Base de Connaissances (SBC) à des fins opérationnelles. De nombreux travaux ont été menés, relatifs à la construction et la structuration d'ontologies de domaine, mais les problèmes liés à leur utilisation pratique au sein de systèmes opérationnels ont été encore peu abordée. Au travers de la mise en oeuvre d une ontologie opérationnelle de la géométrie, nous avons dégagé des règles d opérationalisation d'une ontologie dans le modèle des Graphes Conceptuels, permettant de passer d'une représentation ontologique des connaissances du domaine, indépendante de tout contexte d'usage, à des formes opérationnelles adaptées aux différents types d'applications visées. Ces règles ont été implémentées dans un outil d'édition et d'opérationalisation d'ontologie baptisé TooCoM.

Application de l'apprentissage par renforcement µa la gestion du risque

La programmation dynamique stochastique est un principe de décomposition classique pour l'optimisation dynamique. Elle permet l'optimisation de tout critère séparable. En particulier, l'espérance est un critère séparable. Par contre, l'ajout d'une prise en compte du risque par une mesure de type Value-At-Risk rend le problème non séparable, donc le traitement par programmation dynamique stochastique standard est impossible. Cet article présente une application de techniques d'apprentissage par renforcement compatibles avec un critère non séparable. La mise en oeuvre pratique est faite dans le cadre de la production électrique par le parc de production thermo-hydraulique d'EdF. Les courbes de Value-At-Risk obtenues montrent le succès de l'approche : augmenter le paramètre alpha du critère (1 - alpha)E + alphaVaR conduit à des risques plus faibles.

Identification à la limite d'automates probabilistes résiduels avec probabilité un

Les automates probabilistes (PFA) sont des objets permettant de modéliser des distributions de probabilités définies sur des ensembles de mots. Ils ont la même expressivité que les modèles de Markov cachés (HMM) utilisés dans de très nombreuses applications. Pour une sous-classe des PFA, les automates probabilistes déterministes (PDFA), des algorithmes d identification à la limite ont été élaborés. Malheureusement les PDFA sont beaucoup moins expressifs que les PFA. Aussi étudions-nous une classe d expressivité intermédiaire : les automates probabilistes résiduels (PRFA). Nous montrons que les PRFA à paramètres rationnels sont identifiables à la limite avec une probabilité de 1.

Learning Typed Automata from Automatically Labeled Data

In this paper, we propose a way of incorporating additional knowledge in probabilistic automata inference, by using typed automata. We compare two kinds of knowledge that are introduced into the learning algorithms. A statistical clustering algorithm and a part-of-speech tagger are used to label the data according to statistical or syntactic information automatically obtained from the data. The labeled data is then used to infer correctly typed automata. Compared to a previously proposed method which improved grammatical inference, our approach yields better automata. The inference of typed automata with statistically labeled data provides language models competitive with state-of-the-art n-grams on Air Travel Information Systems (ATIS) task.

Etude sur Amélioration du Boosting : Réduction de l'Erreur et Accélération de la Convergence

Le boosting est la méthode d agrégation de classifieurs, non seulement la plus efficace en pratique, mais également celle reposant sur les propriétés théoriques les plus solides. La mise à jour adaptative de la distribution des exemples, visant à augmenter le poids de ceux mal appris par le classifieur précédent, permet d améliorer les performances de n'importe quel algorithme d'apprentissage. Néanmoins, ses capacités à être immunisé contre le surapprentissage ont été remises en cause dès qu il s'agit d'appliquer le boosting à des donn´ees fortement bruitées. Cette situation est fréquente avec les bases modernes, issues des nouvelles technologies d'acquisition de données, comme le Web. La vitesse de convergence du boosting se trouve également pénalisée sur ce type de bases, où le degré de chevauchement des densités de probabilités des classes à apprendre peut être grand (erreur bayésienne importante). Dans cet article, nous proposons une légère modification de la mise à jour des exemples telle qu'elle est effectée dans l algorithme ADABOOST. Nous montrons qu'en exploitant une mesure d'entropie locale adaptative, issue d'un graphe de voisinage construit sur les exemples, il est possible de déterminer non seulement les outliers mais aussi les exemples situés en zone d'erreur bayésienne. Nous montrons qu'il est possible d'améliorer, en corrigeant le poids des exemples, les performances du boosting. Une large étude expérimentale montre l'intérêt de notre nouvel algorithme, appelé iADABOOST.