Master Informatique

Sujets de TER pour l'année 2015-16

Université d'Artois

  TER 01
Titre :   Calcul de valeurs de paramètres structurels sur des graphes via SAT
Encadrants : Jean-Marie Lagniez, Pierre Marquis, Stefan Mengel
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : lagniez@cril.univ-artois.fr, marquis@cril.univ-artois.fr, mengel@cril.fr
Description :

De nombreux problèmes sur les graphes peuvent être résolus par des algorithmes (à base par exemple de programmation dynamique [1]) opérant en temps polynomial dans la taille du graphe d’entrée, mais exponentielle dans la valeur d’un paramètre structurel de ce graphe, comme sa largeur d’arbre (treewidth) ou plus simplement sa largeur de chemin (pathwidth).

Les valeurs de ces paramètres et les décompositions correspondantes (et/ou les ordres d’élimination associés) sont généralement difficiles à calculer (les problèmes correspondants sont NP-difficiles). En pratique, on peut à cet effet utiliser des algorithmes d’optimisation s’appuyant sur un oracle SAT (voir les articles [2, 3, 4]).

L’objectif de ce stage est double. Il s’agit dans un premier temps d’étudier les algorithmes existants qui relèvent de cette approche, puis de proposer de nouveaux codages vers SAT et enfin de programmer et d’évaluer empiriquement ces codages. L’étudiant recherché devra avoir un goût certain pour la théorie mais aussi pour le développement logiciel efficace.

Références
[1] Olivier Bournez: http://www.lix.polytechnique.fr/~bournez/cours/CoursMaitrise/programmation-dynamique-01.pdf
[2] Jeremias Berg, Matti Järvisalo: SAT-Based Approaches to Treewidth Computation: An Evaluation. ICTAI 2014: 328-335.
[3] Marijn Heule, Stefan Szeider: A SAT Approach to Clique-Width. ACM Trans. Comput. Log. 16(3): 24 (2015).
[4] Marko Samer, Helmut Veith: Encoding Treewidth into SAT. SAT 2009: 45-50.
  TER 02
Titre :   Comptage de modèles pondérés
Encadrants : Frédéric Koriche, Jean-Marie Lagniez, Pierre Marquis
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : koriche@cril.univ-artois.fr, lagniez@cril.univ-artois.fr, marquis@cril.univ-artois.fr
Description :

Etant donnés un ensemble X de variables et une application W associant à chaque littéral sur X un nombre, le poids WMC_W(I) d’une interprétation I (I est une application de X dans les booléens) vaut le produit des W(l) pour tous les littéraux l sur X satisfaits par I. Plus généralement, le poids WMC_W(C) d’une formule C sur X vaut la somme des WMC_W(I) pour tous les modèles I de C (i.e., les I qui satisfont C).

Le comptage de modèles pondérés (weighted model counting, WMC) d’une formule propositionnelle C étant donné W est le processus qui consiste à calculer WMC_W(C). Ce comptage est à la base d’algorithmes pour le calcul de la probabilité d'une évidence donnée, à partir d'un réseau bayésien ou d'un champ aléatoire de Markov [1, 2]. En toute généralité, ces problèmes sont calculatoirement difficiles (#P-complets), tout comme le problème de comptage MC(C) de modèles non pondérés (i.e., quand le poids associé à chaque littéral vaut 1, on compte simplement le nombre de modèles de C sur X).

Théoriquement, il est possible de réduire polynomialement le problème du comptage de modèles pondérés au problème du comptage de modèles sans pondération. Très récemment, des réductions ont été mises en évidence [3].

L’objectif du stage est d’étudier la réduction donnée en [3] et d’écrire un traducteur associant à une formule propositionnelle C sous forme normale conjonctive (suivant le format DIMACS) et un fichier donnant une table W qui associe à chaque variable x de C le poids (entier) de x et le poids (entier) de sa négation, une nouvelle formule C’ sous forme normale conjonctive telle que MC(C’) = WMC_W(C). Des expérimentations seront réalisées pour tester l’intérêt pratique de la réduction, en utilisant plusieurs compteurs de modèles (pondérés ou non) existants en aval.

Références
[1] M. Chavira and A. Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence,172(6-7):772–799, 2008.
[2] T. Sang, P. Beame, and H. A. Kautz. Performing Bayesian inference by weighted model counting. In Proc. of AAAI’05, pages 475–482, 2005.
[3] S. Chakraborty, D. Fried, K. S. Meel and M. Y. Vardi. From Weighted to Unweighted Model Counting. In Proc. of IJCAI'15, pages 689-695, 2015.
  TER 03
Titre :   Reconnaissance d’images sur application mobile: Application à la reconnaissance automatique de menus avec une application Smartphone
Encadrants : Karim Tabia
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : tabia@cril.univ-artois.fr
Description :

Ces dernières années, une multitude d’applications mobiles et d’objets connectés orientés santé et bien-être ont fait leur apparition pour des utilisations grand public. On peut citer les applications de suivi d’activités physiques, les bracelets connectés, les capteurs de sommeil, etc. Ces solutions sont très intéressantes et offrent beaucoup de fonctionnalités. Leurs coûts décroissants et l’attrait de ces objets pour plusieurs catégories d’utilisateurs en font une opportunité intéressante en particulier dans le domaine de la santé et de la nutrition.

Le but de ce stage est de développer une application mobile pour reconnaître automatiquement à partir d'une photo prise par un Smartphone le menu choisi par l'utilisateur. L'application va cibler dans un premier les usagers de restaurants collectifs comme les RU (restaurants universitaires). Ainsi, depuis une photo prise par un utilisateur, l'application devrait, par exemple, reconnaître que l'usager a choisi une crudité en entrée, une viande rouge accompagnée de frites, et un yaourt en dessert. Le sujet de ce TER fait partie d'un projet de recherche sur "Objets connectés intelligents dans le domaine de la nutrition". Ainsi la finalité de ce projet est de développer un suivi intelligent des repas consommés par un utilisateur afin de prévenir certaines carences ou certains écarts, faire des recommandations pour le choix d'un bon menu tenant compte des repas pris les jours précédents, des contraintes/objectifs/préférences/profil de l'utilisateur… Cette application pourra également être utilisée en restauration collective afin de promouvoir une meilleure alimentation via un système de suivi des menus choisi par les utilisateurs. Une autre utilisation possible est d'extraire les préférences des utilisateurs afin d'améliorer les menus proposés, éviter des gaspillages, etc.

L’approche à utiliser pour la reconnaissances d’objets dans les images est la classification supervisée multi-label. Il s’agit d’apprendre automatiquement un modèle capable d’associer à une image un sous-ensemble de labels (ici, les différents éléments qu’on peut choisir dans un RU). Pour ce faire, on prépare un ensemble représentatifs de photos de plateaux qu’on étiquette manuellement puis on construit un modèle (classifieur) à partir de ces données. Ce sujet nécessite un travail de développement (applications mobiles, acquisition et pré-traitements sur les images) et un travail de modélisation, analyse, test et validation de classifieurs multi-labels (fouille de données).

Le travail à réaliser comprend les éléments suivants :
- Etat de l’art sur la classification multi-label.
- Modélisation du problème de reconnaissance automatique de menus.
- Mise en œuvre d’un prototype sur Smatphone.
- Test et validation sur des photos réelles préalablement préparées.

Références
- Contribution à la détection et à la reconnaissance d'objets dans les images : https://tel.archives-ouvertes.fr/tel-00623278/document
- Classification supervisée : http://perso.univ-lyon1.fr/alexandre.aussem/cours/ANAD_cours.pdf
- Applications mobiles de reconnaissances d'images : http://www.teasy.mobi/ et http://www.eyesnap.fr/
  TER 04
Titre :   Utilisation de techniques d’argumentation pour synthétiser des débats en ligne
Encadrants : Pierre Marquis et Sébastien Konieczny
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : marquis@cril.fr, konieczny@cril.fr
Description :

Le but de ce sujet est d’étudier comment les techniques issues de la théorie formelle de l’argumentation peuvent être utilisées pour synthétiser des débats en ligne. Ce TER s’inscrit dans un projet de collaboration entre le projet ANR AMANDE (http://amande.lip6.fr) auquel le CRIL participe et la société ConsultVox (http://www.consultvox.fr).

La société ConsultVox propose des solutions technologiques pour les débats en ligne. Ces solutions peuvent êtres utilisées par exemple pour effectuer des consultations citoyennes pour des projets de politique publique, ou pour décider d'actions à entreprendre dans un club sportif ou une association.

Le but de ce TER est d’étudier l’application développée par ConsultVox, de réaliser un état de l’art sur les technologies associées, et d’étudier comment ajouter à l'application de gestion de débats en ligne existante une structure argumentative, et les outils de raisonnement correspondants, de façon à pouvoir synthétiser les débats (dégager les arguments les plus significatifs, par exemple). Ce projet est donc un projet de recherche, mais avec une composante applicative forte.

Le TER se déroulera majoritairement au sein des locaux de la société ConsultVox, mais le stagiaire aura des contacts fréquents avec ses encadrants au CRIL.

  TER 05
Titre :   Communications inter-véhicule et gestion d’événements sur la route avec SUMO
Encadrants : David Mercier, Gildas Morvan, Frédéric Pichon
Laboratoire d'accueil : Laboratoire de Génie Informatique et Automatique de l’Artois (LGI2A EA 3926), Béthune
Contacts : david.mercier@univ-artois.fr, gildas.morvan@univ-artois.fr, frederic.pichon@univ-artois.fr
Description :

À Béthune, au LGI2A, des méthodes ont été développées afin que des véhicules puissent s’échanger des messages au regard d’événements sur la route (accidents, embouteillages, véhicules en panne, …) sans infrastructure centralisatrice des événements : seuls les véhicules possèdent des bases internes d’événements. Dès que deux véhicules sont à portée de connexion, ils peuvent s’échanger des informations. À chaque instant, pour chaque véhicule, une synthèse de la base est communiquée au conducteur.

L’objectif est d’implémenter et de mettre en œuvre ces méthodes à l’aide du simulateur de trafic SUMO (Simulation of Urban MObility) afin de pouvoir les tester au travers de simulations plus fines que ce qui a pu se faire jusque là.

Liens vers SUMO : http://www.dlr.de/ts/en/desktopdefault.aspx/tabid-9883/16931_read-41000/ et http://sumo.dlr.de/wiki/Main_Page

Langages de programmation : XML, C++
  TER 06
Titre :   Détection de visage dans des séquences vidéo
Encadrants : Eric Lefèvre, David Mercier, Frédéric Pichon
Laboratoire d'accueil : Laboratoire de Génie Informatique et Automatique de l’Artois (LGI2A EA 3926), Béthune
Contacts : eric.lefevre@univ-artois.fr, david.mercier@univ-artois.fr, frederic.pichon@univ-artois.fr
Description :

Dans le cadre d'une collaboration avec la SNCF, des membres du LGI2A travaillent sur la détection de visage dans des séquences vidéo dans le but de flouter ses visages pour pouvoir conserver et exploiter ses vidéos dans le respect de la législation.

Des méthodes implémentées en C++ ont été développées à partir de la fusion de classifieurs en charge de la détection de visages (classifieurs de type Adaboost, cf méthode de Viola Jones, et SVM).

Ce travail de TER comportera deux objectifs principaux :
  1. Le premier concerne la prise en main et la pérennisation du code déjà développé avec l’utilisation de git.
  2. Le second est lié aux tests des méthodes développées : réalisations et configurations de nouveaux tests et recherche de nouvelles bases de tests.

Enfin, en concertation avec les membres du projet, l’étudiant pourra aussi chercher à développer les méthodes existantes. Actuellement la détection de visage se fait image par image, nous pourrions voir par exemple comment exploiter une séquence vidéo c’est-à-dire comment exploiter les liens entre les images se succédant dans le temps. Une autre piste consiste à chercher des couleurs de peau sur une image.

Lien (méthode de Viola Jones) : https://fr.wikipedia.org/wiki/Méthode_de_Viola_et_Jones

Langage de programmation : C++
  TER 07
Titre :   Parallélisation Métaheuristique sur GPGPU
Encadrants : Gilles Goncalves, Tienté Hsu
Laboratoire d'accueil : Laboratoire de Génie Informatique et Automatique de l’Artois (LGI2A EA 3926), Béthune
Contacts : gilles.goncalves@univ-artois.fr, tiente.hsu@univ-artois.fr
Description :

Aujourd'hui tous les ordinateurs du marché sont parallèles grâce à la technologie multi-coeurs, c'est le cas par exemple pour les processeurs Intel Core I7 où le nombre de coeurs varie de 6 à 8, mais l'évolution la plus spectaculaire se trouve dans les GPU, où actuellement le nombre de coeurs dépasse largement le millier ! En terme de puissance de calcul les 2 architectures sont assez proches [1] pour un coût d'achat plutôt en faveur des CPU. D'un côté nous avons une programmation classique où il est possible d'exécuter simultanément quelques dizaines de traitements et de l'autre côté c'est plusieurs milliers de traitements qui peuvent s'exécuter. Ce passage à l'échelle fait que beaucoup d'algorithmes implémentés sur des processeurs classiques peuvent être améliorés en transférant certains traitements sur les processeurs graphiques. De nombreux algorithmes d'optimisation basés sur les métaheuristiques ont été portés sur les GPU : Recherche tabou, Algorithmes génétiques, Colonies de fourmies, etc.

On se propose dans le cadre de ce stage TER 2016 d'étudier les impacts d'une architecture intégrant une carte NVIDIA Titan Black, où le GPU intègre 2880 coeurs, sur des algorithmes génétiques.

L'objectif est de réaliser le portage d'un algorithme simple de type "permutation problem" largement utilisé pour coder des problèmes (Flow Shop, TSP ... ) avec des algorithmes génétiques sur une architecture intégrant un GPU.

Planning :

Les plateformes utilisées :

Système/Languages :

Références
  TER 08
Titre :   Programmation en Java d’algorithmes permettant de résoudre le problème de tournées de véhicules avec demandes incertaines.
Encadrants : Eric Lefèvre, Frédéric Pichon, Daniel Porumbel
Laboratoire d'accueil : Laboratoire de Génie Informatique et Automatique de l’Artois (LGI2A EA 3926), Béthune
Contacts : eric.lefevre@univ-artois.fr, frederic.pichon@univ-artois.fr, daniel.porumbel@cnam.fr
Description :

Des recherches sont actuellement en cours au LGI2A sur le problème de tournées de véhicules (en anglais Vehicle Routing Problem (VRP)). Dans ce problème, il s'agit de déterminer les tournées d’un ensemble de véhicules afin de livrer un ensemble de clients, le but étant de minimiser le coût de livraison.

Plus précisément, les recherches menées portent sur une variante du VRP où les demandes des clients sont incertaines et où les véhicules ont une capacité d’emport limitée. Pour résoudre ce problème, un premier algorithme basé sur une approche dite de recuit simulé, a été développé en Java.

L’objectif de ce TER est de programmer d’autres algorithmes basés sur d’autres approches, par exemple les algorithmes génétiques, afin de résoudre ce problème, puis de comparer les performances respectives de ces algorithmes sur différents jeux de données.

Lien problème de tournées de véhicules : https://fr.wikipedia.org/wiki/Problème_de_tournées_de_véhicules

Langage de programmation : Java
  TER 09
Titre :   Elaboration de jeux stochastiques avec observations partielles pour la communauté GGP (General Game Playing).
Encadrants : Eric Piette
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : epiette@cril.fr
Description :

De toutes les activités humaines, les jeux amènent l’un des exemples de comportement intelligent les plus illustratifs. En effet, un joueur doit faire face à de nombreuses taches complexes, telles que la compréhension de règles abstraites, l’évaluation de la situation courante, choisir le meilleur mouvement possible et finalement élaborer une stratégie gagnante.

Dans le cadre de l’intelligence artificielle, le challenge General Game Playing (GGP) propose de développer des joueurs informatisés qui comprennent les règles de jeux précédemment inconnues et d’apprendre à y jouer efficacement sans intervention humaine. Dans le General Game Playing, les règles d’un jeu sont décrites dans un formalisme de représentation déclaratif de haut niveau, nommé le Game Description Language (GDL). La première version de ce langage (GDL-I) est restreinte aux jeux déterministes avec informations complètes. Tandis qu’un jeu GDL-I peut impliquer plusieurs joueurs, chaque participant a une connaissance complète de l'état courant du jeu, des actions de ces adversaires et des effets de l’ensemble des actions. Dans le but de soulever ces restrictions, Schiffel et Thielscher ont récemment proposé une nouvelle version du Game Description Language (GDL-II) permettant de représenter les jeux avec informations incomplètes. Dans un jeu GDL-II, les joueurs peuvent avoir un accès limité aux informations de l'état courant et les effets de l’ensemble des actions sont incertains. A ce titre, GDL-II est assez expressif pour représenter les jeux stochastiques avec observation partielle, qui couvrent une large variété de problèmes multi-agents de décisions séquentielles.

La seconde version de GDL-II (datant seulement de 2011) propose actuellement peu de jeux. L'objectif de ce TER serait de participer à l'élaboration de jeux stochastiques avec observations partielles afin de permettre à la communauté GGP d'expérimenter de nouveaux programmes-joueurs sur ces jeux.

Dans un premier temps, il sera demandé d'étudier GDL-I en commençant par le développement d'un jeu déterministe afin de rendre aisé la pratique logique de ce langage. Puis, de travailler à l'élaboration de plusieurs jeux GDL-II comme par exemple, quelques jeux de cartes (Poker, Belote, Bridge,...), des jeux de plateaux (Monopoly) ou encore de gestion et négociation (Civilisation, Diplomacy). Suite à cela, vous serez amenés à communiquer avec la communauté GGP et à participer au développement du programme-joueur de notre laboratoire : WoodStock.

Pré-requis : pratique de la programmation logique (par exemple du prolog)
Références :
  TER 10
Titre :   Pont vers un site de jeu en ligne de jeu de cartes
Encadrants : Sylvain Lagrue
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : lagrue@cril.fr
Description :

Ce TER porte sur la création d’une API REST permettant l’accès générique à un site de jeu de cartes en ligne partenaire, ceci dans le but d’automatiser certaines fonctionnalités et d’interfacer le site avec différents outils créés dans le cadre de projets de recherche.

L’objectif de ce TER est de :

  1. permettre la récupération de données à partir du site et de générer des statistiques ;
  2. améliorer l’interface Web actuelle en utilisant des couches de virtualisation (JQuery/WebSocket, etc.) ;
Langages de programmation :Golang, JavaScript
  TER 11
Titre :   Reconnaissance optique de cartes
Encadrants : Sylvain Lagrue
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : lagrue@cril.fr
Description :

L’objectif de ce TER est de reconnaître automatiquement les cartes jouées par des joueurs humains pour une diffusion automatique sur le Web. Pour cela, on utilisera des méthodes standards auxquelles on injectera des connaissances supplémentaires (règles du jeu, contenu initial des mains, jeu d’une IA, etc.) et des méthodes de révision développées au laboratoire.

Langages de programmation :Golang, C++, JavaScript
  TER 12
Titre :   Amélioration de l'intelligence artificielle du jeu 0AD
Encadrants : Sylvain Lagrue et Daniel Le Berre
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : lagrue@cril.fr, leberre@cril.fr
Description :

Le jeu 0AD est développé depuis près de 15 ans par des passionnés de jeux de stratégie temps réel historiques. De grandes améliorations fonctionnelles et visuelles/graphiques ont été apportées ces dernières années. Le point faible du jeu est la gestion de son "intelligence artificielle", c'est à dire le comportement des joueurs logiciels (bot), qui a des difficultés à passer à l'échelle.

Le but de ce TER est d'identifier dans le jeu actuel les techniques d'IA utilisées dans le joueur logiciel PetraBot et de proposer des solutions alternatives permettant un meilleur passage à l'échelle.

Une première étude du jeu a été réalisée l'année dernière par deux étudiants de M1 : elle a permis d'identifier le mode de fonctionnement de l'intelligence artificielle du jeu. En se basant sur ce travail, l'objectif cette année est de proposer une nouvelle intelligence artificielle, capable de rivaliser avec celle fournie par défaut avec 0ad.

Ce TER nécessite une bonne connaissance de l'anglais car la communication avec l'équipe de développement de 0AD se fera en anglais.

Le TER nécessite aussi une bonne connaissance du milieu du logiciel libre, et des outils utilisés pour le développement communautaire (SVN ou git, gestionnaire de ticket TRAC, listes de diffusion, IRC). L'objectif du stage est de pouvoir proposer une nouvelle IA plus performante qui puisse être intégrée dans une version future du jeu. De bonnes capacités de communication seront nécessaires pour que ce travail puisse être accepté par l'équipe de développement.

Enfin, ce TER nécessite une bonne expertise en C++ et surtout en JavaScript, et la capacité d'adopter les conventions de codage de l'équipe de développement de 0AD.

  TER 13
Titre :   Evolution du plugin Alloy pour Eclipse
Encadrants : Daniel Le Berre
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : leberre@cril.fr
Description :

Le plugin Alloy pour Eclipse (A4E) est développé par des étudiants de M1 de l'université d'Artois depuis le printemps 2007.

La première version était une simple intégration du moteur Alloy dans Eclipse. Cependant, les fonctionnalités de l'éditeur restaient limitées pour un habitué d'Eclipse (pas de refactoring par exemple).

Une deuxième version du plugin a été développée à partir de l'outil Xtext : l'intégration avec Eclipse est devenue plus complète (on y retrouve les principales fonctionnalités trouvées dans l'éditeur Java) au prix d'une intégration de bas niveau avec Alloy.

La dernière version du plugin date de juin 2012. Une mise à niveau basée sur la dernière version d'Xtext est nécessaire. La construction du plugin doit être migrée sur Tycho, pour pouvoir faire de l'intégration continue.

Le but de ce stage est de mettre à niveau le plugin A4E pour la dernière version d'eclipse, d'identifier les nouvelles fonctionnalités d'Xtext qui pourraient améliorer l'expérience utilisateur de A4E, et améliorer le support d'Alloy dans Eclipse.

le studio OCCIware. Il faudra pour cela supporter une fonctionnalité cachée de Alloy 4 concernant le support des chaînes de caractères.

Ce stage nécessite une bonne connaissance de l'anglais car la documentation disponible pour les outils utilisés est uniquement en anglais et il sera probablement nécessaire de demander de l'aide à la communauté d'utilisateurs via des listes de diffusion ou des forums en langue anglaise. De plus, les communications avec l'équipe de développement d'Alloy, au MIT, se fera aussi en anglais.

Philippe Merle, CR INRIA, et chef du projet OCCIware, servira de Project Owner pour la partie intégration avec OCCIware.

  TER 14
Titre :   Correction Automatique de TOEIC blancs
Encadrants : Julien Caron-Boilly et Bertrand Mazure
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : julien.caronboilly@univ-artois.fr, bertrand.mazure@cril.univ-artois.fr
Description :

Le TOEIC constitue, pour le monde professionnel, une référence en matière d'évaluation des compétences en langue anglaise. C'est un test payant organisé par un institut privé (ETS Global).

Chaque étudiant de seconde année du master informatique de l'Université d'Artois passera en fin de second semestre un test de TOEIC. Afin de préparer au mieux les étudiants à la réussite de ce test, des épreuves de TOEIC blancs sont organisées au cours de la seconde année du master.

L'objectif de ce TER est de réaliser un logiciel permettant l'évaluation automatique de ces épreuves de TOEIC blancs.

Les tests de TOEIC se présentent sous la forme d'un QCM prérempli où chaque étudiant grise ses réponses. Le programme à développer devra permettre de lire via un scanner un QCM de référence contenant les bonnes réponses puis les QCM complétés par les étudiants et d'afficher les résultats via une feuille de calculs excel.

Une version mobile de cette application pourra également être envisagée, le scanner sera remplacé par l'appareil photo du smartphone.

  TER 15
Titre :   Implémentation des labellings dans le solver d'argumentation abstraite CoQuiAAS
Encadrants : Jean-Marie Lagniez et Emmanuel Lonca
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : lagniez@cril.univ-artois.fr, lonca@cril.univ-artois.fr
Description :

L'argumentation est aujourd'hui un des mots-clés prépondérants en ce qui concerne l'intelligence artificielle. Elle a notamment sa place dans des thématiques comme les systèmes multi-agent, où elle permet la mise en place de protocoles de dialogue (à base de persuasion, de négociation, ...) ou l'analyse de discussions en ligne ; mais aussi dans le cas où un unique agent doit raisonner en présence d'informations conflictuelles (inférence en présence d'incohérence, mesures d'incohérence). Ce cadre très riche offre la possibilité de raisonner suivant un nombre important de sémantiques et propose deux politiques d'inférence pour chaque sémantique.

À l'heure actuelle, une des tendances fortes dans la communauté de l'argumentation est de développer des approches logicielles pour calculer diverses tâches d'inférence à partir d'un système d'argumentation pour les sémantiques usuelles. Dans cette optique, des chercheurs du CRIL ont développé le logiciel CoQuiAAS (Constraint-Based Quick Abstract Argumentation Solver), qui a remporté l'été dernier la première compétition internationale sur le sujet parmi une vingtaine de concurrents.

CoQuiAAS n'est capable à l'heure actuelle que d'exprimer des solutions en terme d'extensions, c'est-à-dire de déterminer des ensembles d'arguments respectant les propriétés dictées par la sémantique considérée. Or, il existe un formalisme plus expressif, dit des labellings, qui consiste à attribuer à chaque argument une étiquette plutôt que de simplement dire s'il doit être accepté ou non. Le but du stage est d'implémenter dans le logiciel CoQuiAAS ce formalisme pour l'ensemble des sémantiques et tâches qu'il sait réaliser.

Le stagiaire devra posséder de solides compétences en programmation avec le langage C, et devra aussi posséder de bonnes aptitudes en modélisation.

  TER 16
Titre :   Similitude entre graphes
Encadrants : Thomas Caridroit et Jérôme Delobelle
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : caridroit@cril.univ-artois.fr, delobelle@cril.univ-artois.fr
Description :

Les graphes sont des structures de données utilisées pour représenter l'information et sur lesquels plusieurs algorithmes sont développés (des programmes, des jeux, des automates, planification). Pour certaines applications, il est intéressant de savoir les similitudes et les différences entre deux représentations. Pour cela l'étude de la similitude des graphes est importante.

L'objectif de ce projet est d'implémenter différents algorithmes capables de mesurer la similitude entre graphes. Pour ce faire, l'étudiant devra dans un premier temps adapter un algorithme de minimalisation de graphes.

Il lui sera également demandé d'implémenter une méthode permettant d'obtenir un arbre à partir d'un graphe.

  TER 17
Titre :   Programmation d'algorithmes permettant la fusion d'extensions en argumentation abstraite
Encadrants : Jérôme Delobelle et Emmanuel Lonca
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : delobelle@cril.univ-artois.fr, lonca@cril.univ-artois.fr
Description :

L’argumentation est basée sur le principe d’interaction et d’évaluation des arguments. La théorie d’argumentation de Dung s’appuie sur la notion de système d’argumentation (AF) représenté par un graphe binaire. Ce système prend en entrée un ensemble d’arguments et une relation binaire qui exprime une notion de contrariété (et plus particulièrement d’attaque) entre arguments. Le but étant de déterminer les ensembles d’arguments, appellé extension, pouvant être conjointement acceptés à partir d’un graphe.

La fusion de systèmes d'argumentation s'avère être un problème important pour les systèmes multi-agents : supposons que chaque membre d'un groupe d'agents possède son propre système d'argumentation, représentant ses croyances, le problème est de définir un système d'argumentation/extension qui représente les croyances du groupe. Il existe deux possibilités visant à fusionner les systèmes d'argumentation: 1) fusionner directement les graphes ou 2) fusionner les extensions. Nous travaillerons dans le cas de fusion des extensions (cas 2).

Récemment, des chercheurs du CRIL ont développé le logiciel CoQuiAAS (Constraint-Based Quick Abstract Argumentation Solver), qui a remporté l'été dernier la première compétition internationale sur le sujet parmi une vingtaine de concurrents. Ce logiciel est capable de déterminer très rapidement les extensions d'un système d'argumentation en respectant les propriétés dictées par la sémantique considérée.

L'objectif de ce stage sera, dans un premier temps, d'utiliser le logiciel CoQuiAAS afin de calculer les extensions de chaque système d'argumentation en entrée. Puis, l'étudiant devra implémenter des méthodes existantes, à base de distance, visant à sélectionner les meilleurs extensions qui représenteront le résultat de la fusion.

Pré-requis : Algorithmique et logique (base)
  TER 18
Titre :   Modèles probabilistes pour les préférences collectives et individuelles: Application dans le domaine de la restauration collective
Encadrants : Karim Tabia
Laboratoire d'accueil : Centre de Recherche en Informatique de Lens (CRIL CNRS UMR 8188)
Contacts : tabia@cril.univ-artois.fr
Description :

L'extraction ou l'apprentissage d'un modèle de préférences à partir de données est un problème rencontré dans plusieurs applications. Par modèle de préférences, on entend un modèle encodant les préférences d'un utilisateur ou d'un ensemble d'utilisateurs dans un formalisme dédié. Ce modèle peut servir à des fins d'analyse ou de prédiction, de recommandation, etc. Un modèle de préférences extrait de manière automatique peut être très utiles pour certaines tâches d'autant plus que les données peuvent être facilement collectées et traitées. Dans le cadre de ce stage, on s'intéressera aux préférences des usagers de restaurants collectifs (de type restaurants universitaires).

L'objectif principal est d'apprendre à partir de données empiriques des modèles de préférences collectives et individuelles d'un ensemble d'utilisateurs. Une fois les modèles construits, il sera question des différents types de raisonnements que l'on pourrait effectuer sur ces modèles. Le type de modèles de préférences à étudier concerne les modèles graphiques et probabilistes comme les CP-Net probabilistes.

Le travail à réaliser concernera en particulier :

Références :
  1. Probabilistic Conditional Preference Networks (https://www.irit.fr/publis/ADRIA/PapersFargier/uai13.pdf)
  2. Learning Probabilistic CP-nets from Observations of Optimal Items (https://zanuttini.users.greyc.fr/data/articles/Bigot.STAIRS.2014.pdf
  3. Updates and Uncertainty in CP-nets (http://www.nickmattei.net/docs/updates.pdf)