Informatique ubiquitaire : techniques de curage d'informations perverties
Institution:
ArtoisDisciplines:
Directors:
Abstract EN:
This thesis studies a possible approach of artificial intelligence for detecting and filtering inconsistent information in knowledge bases of intelligent objects and components in ubiquitous computing. This approach is addressed from a practical point of view in the SAT framework;it is about implementing a techniques of filtering inconsistencies in contradictory bases. Several contributions are made in this thesis. Firstly, we have worked on the extraction of one maximal information set that must be satisfiable with multiple assumptive contexts. We have proposed an incremental approach for computing such a set (AC-MSS). Secondly, we were interested about the enumeration of maximal satisfiable sets (MSS) or their complementary minimal correction sets (MCS) of an unsatisfiable CNF instance. In this contribution, a technique is introduced that boosts the currently most efficient practical approaches to enumerate MCS. It implements a model rotation paradigm that allows the set of MCS to be computed in an heuristically efficient way. Finally, we have studied a notion of consensus to reconcile several sources of information. This form of consensus can obey various preference criteria, including maximality one. We have then developed an incremental algorithm for computing one maximal consensus with respect to set-theoretical inclusion. We have also introduced and studied the concept of admissible consensus that refines the initial concept of consensus.
Abstract FR:
Cette thèse étudie une approche possible de l'intelligence artificielle pour la détection et le curage d'informations perverties dans les bases de connaissances des objets et composants intelligents en informatique ubiquitaire. Cette approche est traitée d'un point de vue pratique dans le cadre du formalisme SAT; il s'agit donc de mettre en œuvre des techniques de filtrage d'incohérences dans des bases contradictoires. Plusieurs contributions sont apportées dans cette thèse. Premièrement, nous avons travaillé sur l'extraction d'un ensemble maximal d'informations qui soit cohérent avec une série de contextes hypothétiques. Nous avons proposé une approche incrémentale pour le calcul d'un tel ensemble (AC-MSS). Deuxièmement, nous nous sommes intéressés à la tâche d'énumération des ensembles maximaux satisfaisables (MSS) ou leurs complémentaires les ensembles minimaux rectificatifs (MCS) d'une instance CNF insatisfaisable. Dans cette contribution, nous avons introduit une technique qui améliore les performances des meilleures approches pour l'énumération des MSS/MCS. Cette méthode implémente le paradigme de rotation de modèle qui permet de calculer des ensembles de MCS de manière heuristique et efficace. Finalement, nous avons étudié une notion de consensus permettant réconcilier des sources d'informations. Cette forme de consensus peut être caractérisée par différents critères de préférence, comme le critère de maximalité. Une approche incrémentale de calcul d'un consensus maximal par rapport à l'inclusion ensembliste a été proposée. Nous avons également introduit et étudié la concept de consensus admissible qui raffine la définition initialement proposée du concept de consensus.