Efficient best-first search algorithms have been developed for deterministic two-player games with two-outcome.We present a formal framework to represent such best-first search algorithms.The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm.We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K.This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions.We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves.

Nous étudions l'algorithmique de deux problèmes centraux d'Intelligence Artificielle, pour des bases de connaissances représentées, notamment, par des formules propositionnelles de Horn, bijonctives, Horn-renommables ou affines. Nous traitons tout d'abord l'acquisition de connaissances à partir d'exemples : nous donnons notamment un algorithme efficace et général pour l'acquisition exacte, complétons l'état de l'art pour l'approximation et donnons un algorithme pour le PAC-apprentissage des formules affines. Nous étudions ensuite des problèmes de raisonnement : nous donnons un algorithme général pour l'abduction, qui nous permet d'exhiber de nouvelles classes polynomiales, et posons de premières pierres pour l'étude de ce processus lorsque la base de connaissances est approximative. L'étude des formules affines pour la représentation de connaissances n'avait jamais été réellement menée. Les résultats présentés dans ce mémoire montrent qu'elles possèdent de nombreuses bonnes propriétés.

Dans les sciences expérimentales telles que les sciences de l'aliment, les données jouent un rôle essentiel, puisque les théories du domaine sont fondées sur les données expérimentales, leur exploitation et leur analyse. Cependant, l'état de l'art montre que les données expérimentales disponibles sont souvent partielles, éparpillées sur des supports variés, ou sans modèle mathématique sous-jacent établi. Une autre source d'information est également disponible : les connaissances expertes, toutefois pas toujours formalisées sur des supports écrits. Les connaissances expertes peuvent exprimer des points de vue différents, potentiellement conflictuels s'ils visent des objectifs divergents. Un défi majeur est donc d'intégrer ces données et ces connaissances et de développer des méthodes permettant de les utiliser pour l'aide à la décision. Ce mémoire présente un ensemble de stratégies et méthodes complémentaires définies et développées pour, ensemble, traiter cette problématique. Il aborde trois thèmes de recherche : l'intégration de formalismes hétérogènes, les méthodes prédictives et l'argumentation pour l'aide à la décision.

Ancrer l'interaction: Gestion des connaissances pour la robotique interactive Avec le développement de la robotique cognitive, le besoin d'outils avancés pour représenter, manipuler, raisonner sur les connaissances acquises par un robot a clairement été mis en avant. Mais stocker et manipuler des connaissances requiert tout d'abord d'éclaircir ce que l'on nomme connaissance pour un robot, et comment celle-ci peut-elle être représentée de manière intelligible pour une machine. Ce travail s'efforce dans un premier temps d'identifier de manière systématique les besoins en terme de représentation de connaissance des applications robotiques modernes, dans le contexte spécifique de la robotique de service et des interactions homme-robot. Nous proposons une typologie originale des caractéristiques souhaitables des systèmes de représentation des connaissances, appuyée sur un état de l'art détaillé des outils existants dans notre communauté. Dans un second temps, nous présentons en profondeur ORO, une instanciation particulière d'un système de représentation et manipulation des connaissances, conçu et implémenté durant la préparation de cette thèse. Nous détaillons le fonctionnement interne du système, ainsi que son intégration dans plusieurs architectures robotiques complètes. Un éclairage particulier est donné sur la modélisation de la prise de perspective dans le contexte de l'interaction, et de son interprétation en terme de théorie de l'esprit. La troisième partie de l'étude porte sur une application importante des systèmes de représentation des connaissances dans ce contexte de l'interaction homme-robot : le traitement du dialogue situé. Notre approche et les algorithmes qui amènent à l'ancrage interactif de la communication verbale non contrainte sont présentés, suivis de plusieurs expériences menées au Laboratoire d'Analyse et d'Architecture des Systèmes au CNRS à Toulouse, et au groupe Intelligent Autonomous System de l'université technique de Munich. Nous concluons cette thèse sur un certain nombre de considérations sur la viabilité et l'importance d'une gestion explicite des connaissances des agents, ainsi que par une réflexion sur les éléments encore manquant pour réaliser le programme d'une robotique "de niveau humain".

L'autonomie d'un robot mobile se caractérise par sa capacité à agir et à se déplacer dans l'environnement sans intervention humaine. La planification de mission pour un robot mobile fait intervenir un raisonnement symbolique pour le choix des actions permettant d'accomplir la mission et un raisonnement géométrique pour le calcul des déplacements du robot afin de réaliser ces actions. Dans un premier temps, nous comparons différentes approches permettant de coupler un planificateur de tâches et un planificateur de mouvements. Les résultats obtenus en termes de messages échangés entre les deux modules de raisonnement et en termes de temps de calcul tendent à montrer qu'un couplage dans lequel les exécutions des deux planificateurs sont entrelacées est l'approche offrant les meilleures performances. À partir de ce constat, nous proposons une architecture de planification hybride mettant en oeuvre un planificateur de tâches et un planificateur de mouvements dont les exécutions sont entrelacées. Nous avons été amenés à étendre le concept d'opérateur de planification afin de permettre l'expression et la prise en compte de préconditions géométriques ainsi que d'effets géométriques. Ces préconditions, définissant géométriquement la manière de réaliser les actions, sont ensuite envoyées au module de raisonnement géométrique sous la forme de requêtes de planification. Les contraintes géométriques sont extraites des préconditions, traduites en fonctions mathématiques, puis satisfaites à l'aide d'un algorithme de programmation non linéaire. Un chemin est ensuite calculé entre la configuration actuelle du robot et la configuration solution à l'aide d'un algorithme de planification de mouvement appelé Cell-RRT. Les effets géométriques permettent de transmettre les modifications des ressources partagées au module de raisonnement symbolique et fournissent des références sur les configurations du robot en début ou en fin de réalisation d'une action. Ces références peuvent ensuite intervenir lors de la planification d'une nouvelle action. L'algorithme de planification de mouvements mis en oevre est un algorithme probabiliste incrémental qui s'appuie sur le principe de l'algorithme RRT. Il est couplé avec une phase de réduction de l'espace de recherche. Durant cette phase, l'environnement est décomposé en un ensemble de cellules puis un algorithme de recherche de plus court chemin est appliqué afin de définir un sous-ensemble de l'espace de recherche. Les échanges entre les deux planificateurs font également appel à la notion de conseil afin de permettre le guidage de la construction du plan par des heuristiques géométriques ainsi que de permettre des phases d'optimisation du plan. Cette architecture hybride est finalement testée sur des scénarios de missions mettant ainsi en avant la validité de nos propositions. Le planificateur de déplacement Cell-RRT est également évalué afin d'étudier les gains réalisés, en termes de distances parcourues et de temps de calcul, en fonction de l'ajustement de ses différents paramètres de configuration.

Dans cette thèse, nous explorons les diverses contributions que les systèmes multi-agents (SMA) et les architectures à base de composants (CBSA) peuvent mutuellement et complémentairement s'apporter l'un à l'autre. Dans un premier temps, nous définissons, illustrons, analysons et discutons une méthodologie du développement des SMA, un modèle de composants (SpeAD), un langage de description d'architecture (SpeADL) et une méthode de conception (SpEArAF) qui facilitent et guident la description et l'implémentation des SMA. Cette réponse complète au développement des SMA est assistée par un outil (MAY) et a été appliquée à un grand nombre d'applications. Dans un second temps, nous explorons à travers divers expériences l'aide que peuvent apporter les SMA auto-adaptatif aux CBSA. Les agents et leur réorganisation continuelle jouent à la fois le rôle de moteur de la construction et de l'adaptation dynamique de l'architecture, mais aussi du conteneur qui connecte ses éléments en pratique.

Dans le cadre de missions réalisées conjointement par un agent artificiel (robot, drone) et un agent humain, nous présentons un contrôleur de la dynamique de l'autorité, fondé sur un graphe de dépendances entre ressources génériques contrôlables par les deux agents, dont l'objectif est d'adapter le comportement de l'agent artificiel ou de l'agent humain en cas de conflit d'autorité sur ces ressources. Nous définissons l'autorité relative de deux agents par rapport au contrôle d'une ressource, ainsi que la notion de conflit d'autorité sur une ressource. La détection d'un conflit déclenche une révision du plan de l'agent artificiel, fondée sur l'état courant des ressources et des relations d'autorité. Le contrôleur de la dynamique de l'autorité est mis en œuvre par l'outil MNMS (Multiple (Petri) Nets Management System), développé au cours de la thèse, qui permet la manipulation des ressources génériques, dépendances entre ressources et relations d'autorité, ainsi que l'intégration au sein d'une architecture robotique.

La fouille de données et la Programmation Par Contraintes (PPC) sont deux domaines de l'informatique qui ont eu, jusqu'à très récemment, des destins séparés. Cette thèse est l'une des toutes premières à s'intéresser aux liens entre la fouille de données et la PPC, et notamment aux apports de cette dernière à l'extraction de motifs sous contraintes. Différentes méthodes génériques pour la découverte de motifs locaux ont été proposées. Mais, ces méthodes ne prennent pas en considération le fait que l'intérêt d'un motif dépend souvent d'autres motifs. Un tel motif est appelé motif n-aire. Très peu de travaux concernant l'extraction de motifs n-aires ont été menés et les méthodes développées sont toutes ad hoc. Cette thèse propose un cadre unifié pour modéliser et résoudre les contraintes n-aires en fouille de données. Tout d'abord, l'extraction de motifs n-aires est modélisée sous forme de problème de satisfaction de contraintes (CSP). Puis, un langage de requêtes à base de contraintes de haut niveau est proposé. Ce langage permet d'exprimer une large panoplie de contraintes n-aires. Plusieurs méthodes de résolution sont développées et comparées. Les apports principaux de ce cadre sont sa déclarativité et sa généricité. Il s'agit du premier cadre générique et flexible permettant la modélisation et la résolution de contraintes n-aires en fouille de données.

En psychologie cognitive, la notion de prototype apparaît de manière centrale dans les représentations conceptuelles. Dans le cadre de nos travaux, nous proposons d'introduire cette notion au sein des activités relevant de l'Ingénierie des Ontologies et de ses modèles de représentation. L'approche sémiotique que nous avons développée est fondée sur les trois dimensions d'une conceptualisation que sont l'intension (les propriétés), l'expression (les termes), et l'extension (les instances). Elle intègre, en sus de l'ontologie, des connaissances supplémentaires propres à l'utilisateur (pondération des propriétés, corpus, instances). Pratiquement, il s'agit de pondérer les liens "is-a", les termes et les instances d'une hiérarchie de concepts, au moyen de gradients de prototypicalité respectivement conceptuelle, lexicale et extensionnelle. Notre approche a été mise en oeuvre dans un système industriel de gestion documentaire et de recherche d'information pour la société Tennaxia - société de veille juridique dans le domaine de l'Environnement. Elle a conduit au développement d'une ontologie du domaine Hygiène-Sécurité-Environnement, et de deux applications logicielles : l'application TooPrag dédiée au calcul des différents gradients de prototypicalité, et le moteur de Recherche d'Information sémantique Theseus qui exploite les gradients de prototypicalité. Nous avons enfin étendu notre approche à la définition de deux nouvelles mesures sémantiques, en nous inspirant des lois de similarité et de proximité de la théorie de la perception : Semiosem, une mesure de similarité, et Proxem, une mesure de proximité.

L'interaction sociale en univers virtuel ouvre de nouveaux horizons dans le domaine des technologies de l'information et en particulier de l'usage des jeux vidéo à des fins professionnelles (" serious game "). En introduisant la possibilité de gérer avec un certain niveau de réalisme des interactions sociales et émotionnelles entre les agents conversationnels animés (ACA) représentant des acteurs humains, cette approche permet d'envisager de nombreuses applications professionnelles qui jusqu'alors ne pouvaient être envisagées que dans le cadre domaine de l'interaction homme-homme. La difficulté principale de cette approche est de produire une dynamique des interactions humaines qui ait un sens dans le cadre des taches et des actions qui doivent être accomplies par les acteurs. Afin d'ancrer théoriquement cette question, nous avons fait référence aux approches de la cognition située (afin de prendre en compte le rôle médiateur des objets de l'environnement) et aux approches représentationnelles pour la production des actes de langage. Le contexte applicatif de ce travail de recherche concerne la rééducation de patients cérébro-lésés. Dans un premier temps, nous nous sommes intéressés à la description de la dynamique des interactions visuelles, gestuelles, verbales entre un patient et un véritable thérapeute. Cette étude nous a permis de catégoriser les différentes phases de dialogue et d'élaborer un modèle de la dynamique de l'interaction prenant en compte la personnalité des acteurs, leurs intentions, leurs comportements gestuels et verbal. A partir de ce modèle, nous avons élaboré une architecture informatique générique qui s'articule autour d'un modèle comportemental et d'un modèle kinésique. Le modèle comportemental sélectionne les actes de langage et l'attitude du personnage (empathique, neutre, etc.). Le modèle kinésique gère les expressions faciales, corporelles et gestuelles résultant du modèle comportemental. D'un point de vue théorique, nous nous sommes intéressés à la notion de présence afin d'identifier quelle était la nature des couplages pertinents permettant de produire un sentiment de présence sociale (sentiment pour les acteurs humains qui animent leurs avatars de vivre une interaction sociale non médiatisée par les éléments du dispositif technique). Enfin, le dispositif a été utilisé dans le cadre d'un programme de recherche sur le concept de neurone miroir. L'hypothèse étant que la présentation au patient d'une image virtuelle de son membre handicapé lui permettrait de mieux récupérer. Des tests IRMf associés à chaque expérience devrait permettait de confirmer ou d'infirmer le rôle de ces neurones miroir dans le processus de récupération.