Table of Contents

MFE 2008-2009 : Intelligence Artificielle

Introduction

Le laboratoire IRIDIA aborde des problèmes dans le domaine de l'Intelligence Artificielle. Si l'on reprend les dires d'un de ses pioniers Marvin Lee Minsky, l'Intelligence Artificielle est définit comme “la construction de programmes informatiques qui s'adonnent à des tâches qui sont, pour l'instant, accomplies de façon plus satisfaisante par des êtres humains car elles demandent des processus mentaux de haut niveau tels que : l'apprentissage perceptuel, l'organisation de la mémoire et le raisonnement critique”. L'IA a beaucoup évolué depuis et s'inspire largement de phénomènes biologiques, physiques, cognitifs ou encore écologiques. C'est donc définitivement une approche transdisciplinaire qui s'accorde principalement à traîtrer des problèmes très complexes. Les domaines principaux de compétence d'IRIDIA sont : l'intelligence en essaim, les métaheuristiques, l'étude des réseaux biologiques et l'application de Business Intelligence. C'est dans cette perspective que les sujets de MFE présentés ci-après s'inscrivent.

Ces sujets sont prêt à être encadrer, mais il va s'en dire qu'ils ne sont pas uniques. Les étudiants sont vivement encouragés à prendre contact avec Hugues Bersini (bersini AT ulb.ac.be) ou Marco Dorigo (mdorigo AT ulb.ac.be) afin de discuter de l'une ou l'autre initiative inspirée pouvant faire l'objet dun autre sujet de MFE ou de préciser le cadres, le contenu et les attentes relatives au sujets présentés.

Data/text mining - Traitement automatique de documents sur base de leur contenu

Ce sujet est destiné aux étudiants en Informatique ou en Sciences Appliquées. Il pourrait être traité par un groupe de deux étudiants.

Au cours de ce travail, nous nous interesserons a l'application d'algorithmes de traitement automatique de documents dans le cadre d'un projet (projet STRATEGO) avec les sociétés IRIS, Mentis et Denali. Nous serons confrontés par exemple à la categorisation (classification) de documents sur base de leur contenu ainsi qu'au clustering de documents.

Les developpements seront effectués en Java, C++, Perl, Python, Matlab ou S-Plus (R).

Il s'agit donc d'un travail de recherche et développement.

Etude de la topologie de réseaux lexicaux extraits de documents

De plus en plus de scientifiques sont convaincus qu’une même topologie de réseaux (c'est-à-dire la manière dont les nœuds en sont connectés) se retrouve dans de nombreux réseaux, pourtant extraits de réalités très diverses (Web, Internet, réseaux sociaux, biologiques, épidémiques). Cette topologie leur conférerait des propriétés intéressantes comme une plus grande robustesse ou une communication réduite entre les nœuds. Il est possible de construire des réseaux lexicaux à partir d’un document quelconque, par exemple, en connectant deux mots qui apparaissent dans une même phrase. Le MFE consistera en un développement logiciel ayant pour but la réalisation automatique de ces réseaux lexicaux à partir d’une variété de documents et l’étude automatisée de leur topologie : distance inter-nœuds, degré de clustering, etc …

Expérimentation des designs patterns pour la modélisation de systèmes biologiques complexes

Tout bon informaticien se doit aujourd’hui de maîtriser ces recettes de conception OO que sont les designs patterns. Au-delà des langages de programmation ou de modélisation (UML), ils sont devenus le sujet d’étude et de développement le plus prisé de la communauté informatique. Leur maîtrise permet à ces mêmes informaticiens d’attaquer la simulation de procédés complexes avec plus de facilité. Le MFE consistera en la mise en pratique de ces designs patterns pour la modélisation de systèmes biologiques complexes comme le système immunitaire ou les mécanismes de régulations génétiques. Le travail devrait déboucher sur une adaptation de ces mêmes designs patterns au monde et aux problèmes de la biologie.

Mélange des techniques de planification Min-Max et d’apprentissage par renforcement à la mise au point d’un logiciel capable de jouer au Go

Alors que les meilleurs joueurs d’échec (par une approche de type Min-Max) et de backgammon (par une approche de type apprentissage par renforcement) se sont définitivement inclinés devant l’ordinateur, le jeu de Go semble toujours farouchement lui résisté. Ce MFE tentera de mêler deux approches traditionnelles de l’Intelligence Artificielle, la planification par le biais des algorithmes de Min-Max et l’apprentissage par renforcement (apprenant par essais et erreurs), déjà fort exploitées dans les jeux mais très rarement en commun, dans la mise au point d’un joueur de Go de qualité acceptable.

Programmation d’une cellule minimale

De nombreux biologistes aujourd’hui s’interrogent sur les propriétés minimales nécessaires que doit posséder un organisme pour être caractérisé de « vivant ». Parmi celles-ci, on retrouve un métabolisme chimique, la compartimentalisation par une membrane et la possession d’une matrice informationnelle capable de s’auto-répliquer. De nombreux informaticiens leur ont emboîté le pas, et tente par le biais de simulations informatiques de reproduire ces propriétés, surtout la manière dont celles-ci dépendent les unes des autres. Le MFE consistera en la simulation d’un de ces modèles, appelé le « chemoton », ainsi que son expérimentation. C’est l’effort à fournir afin qu’une vie artificielle puisse réellement émerger un jour de l’ordinateur !!

Mise au point d’un système automatique de génération de code à partir d’un diagramme d’état-transition

Le diagramme d’état-transition représente le cycle de vie d’un objet, de sa naissance à sa disparition, en suivant les différents états par lesquels cet objet transite. Il est par exemple très largement mis à l’œuvre dans la modélisation des procédures parlementaires (l’évolution des décrets de loi). C’est le cas dans plusieurs parlements belges avec lesquels IRIDIA collabore. Le MFE étudiera la possibilité d’une génération automatique de code fidèle à ces diagrammes et tout ce qui les compose.

Etude de la topologie de réseaux de musiciens de Jazz

De plus en plus de scientifiques sont convaincus qu’une même topologie de réseaux (c'est-à-dire la manière dont les nœuds en sont connectés) se retrouve dans de nombreux réseaux, pourtant extraits de réalités très diverses (Web, Internet, réseaux sociaux, biologiques, épidémiques). Cette topologie leur conférerait des propriétés intéressantes comme une plus grande robustesse ou une communication réduite entre les nœuds. Il est possible de construire un réseau de musiciens de Jazz connectant deux musiciens dès lors qu’ils ont joué sur un même disque. Le MFE consistera en un développement logiciel ayant pour but la réalisation automatique de ces réseaux de musiciens à partir de documentations sur les disques téléchargés automatiquement de sites de vente en ligne.

Evolution de circuits logiques

Depuis quelques années, de nouvelles techniques d'optimisations comme les algorithmes évolutionnistes servent de méthodologie d'aide à la conception. De par leur nature, ces techniques offrent une approche “bottom-up” qui peut sortir des sentiers battus que sont les les approches classiques dite “top-down”. C'est par exemple le cas en conception de circuits logiques et électroniques. Ainsi, cette nouvelle méthodologie de conception assistée par des algorithmes d'optimisation permet de parfois souligner de nouvelles idées inconnues de l'homme jusqu'à ce jour. Ce mémoire se concentrera sur les algorithmes évolutionnistes comme aide à la conception de circuits logiques. Il s'inscrira dans la continuité d'un mémoire effectué en 2007-2008 sur le même sujet. Il s'agira, par exemple, de mettre en oeuvre des techniques pour détecter des motifs récurrents de portes qui peuvent apparaitre, et ainsi permettre une construction automatique de la modularité de la solution. Ou encore de développer une approche multi-objective de la question.

Détection de modularités appliquée à la biochimie

En biochimie, la simulation et l'optimisation des systèmes font intervenir tant et tant de variables que les dimensions sont plus que nombreuses. Ce caractère hyperdimensionnel fait exploser d'une part l'espace de recherche, mais augmente également la difficulté de l'espace de recherche. En effet, les variables d'états du système sont souvent corrélées non-linéairement. La force de ces dépendances délimite d'ailleurs souvent des modules fonctionnels qui, une fois détectés, peuvent être mis à profit. Les nouvelles techniques d'optimisation trouvent ainsi un écho logique dans le domaine de la bioinformatique ou de la chimie pharmaceutique. Au cours de ce mémoire, l'étudiant mettra en oeuvre diverses techniques se basant sur un principe de modularité. Il les analysera et les comparera sur un problème appliqué dans les domaines précités (diverses possibilités envisageables). Ce travail se constitue donc principalement comme une recherche appliquée où une méthodologie expérimentale rigoureuse sera requise.

Software framework for Ant Colony Optimization

Ants have inspired a number of computational techniques and among the most successful is ant colony optimization (ACO). ACO is an optimization technique that can be applied to tackle a wide variety of computational problems that arise in computer science, telecommunications, and engineering. While ACO has a very wide applicability, the development times for effective ACO algorithms can be relatively high. This is due to the fact that each time a new problem is to be tackled by an ACO algorithm, a researcher needs to implement the algorithms almost from scratch.

The goal of the project is to provide a software framework to support the application and the implementation of ACO algorithms to new problems. The software framework will offer all the standard procedures that are used in ACO algorithms and will allow for the rapid prototyping of ACO algorithms. The application of this software framework will be tested on a number of optimization problems.

Required skills: The candidate should be well acquainted with programming in object oriented languages.

Swarm robotics using the e-puck platform

The e-Puck is a robot developed by the Ecole Polytechnique Fédérale de Lausanne, Switzerland. It is equipped with a dsPIC micro-controller, it has an RS232 and a bluetooth interface, 8 infrared proximity sensors, a 3 axis accelerometer, 3 microphones and a speaker, a color camera with a resolution of 640×480 pixels and 8 red leds for displaying patterns.

In the last years, a number of projects carried out at IRIDIA developed a set of tools and a fully functional platform to work efficiently with e-puck robots. In particular, a precise description of the properties of the robots, software libraries and an accurate simulator are now available. A number of controllers were developed and successfully tested on the robots.

The goal of the project ``Swarm robotics using the e-puck platform'' is to design and carry out experiments of swarm robotics that are typically bio-inspired and involve several robots. Possible experiments include p2p communication networks for path finding, flocking for exploration, transport of objects and aggregation of robots. 12 e-Puck will be available for the project.

The project is tightly connected to the research in swarm robotics carried out at IRIDIA and in particular to the EU funded Swarmanoid project, the aim of which is to study new approaches to the design and implementation of self-organizing and self-assembling artifacts. See http://www.swarmanoid.org for more details.

Required skills: The candidates should be acquainted with C/C++ programming and have a working knowledge of the English language.

Evolution of Cooperation

Often the selfish and strong are believed to be favored by natural selection, even though cooperative and fair interactions thrive at all levels of organization in living systems. This project tackles this paradox in the context of Evolutionary Game Theory (EGT), having kin-selection, direct and indirect reciprocity as conceptual starting points. Contrary to what is usual, models will also take into account the intricate ties of modern social networks and its topological evolution.

In spite of its relevance, understanding the evolution of cooperation remains one of the most fundamental challenges to date, tackled by scientists from fields as diverse as anthropology, biology, sociology, ecology, economics, psychology, political science, mathematics, physics, etc., who often adopt EGT as a common mathematical framework. Hence, students who choose this proposal should be strongly interested in interdisciplinary research.

Required skills: The candidates should have good mathematical skills, be acquainted with C/C++ programming and have a working knowledge of the English language.

* Contact : Francisco C. Santos (IRIDIA)



The project is in collaboration with Jorge M. Pacheco (University of Lisbon), Sven Van Segbroeck (IRIDIA and COMO, VUB) and Tom Lenaerts (SWITCH, VUB).