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.

Si les maîtres du jeu d'échecs ont définitivement jeté les armes aux pieds de l'ordinateur, on ne peut pas en dire autant pour un jeu comme le Go. Les logiciels de joueurs de Go peinent à atteindre un niveau moyen, très loin des amateurs forts et encore plus des professionnels ! Pourquoi ? Deux raisons à cela : tout d'abord, il y a beaucoup plus de coups possibles au Go qu'aux échecs. Le jeu de Go se joue traditionnellement sur un plateau de jeu (goban en japonais) de 19 lignes et 19 colonnes, ce qui fait plus de 200 coups possibles dans une position typique, contre une quarantaine aux échecs. La combinatoire est donc beaucoup plus grande au Go. Ensuite, la taille de l'arbre des possibilités du jeu de Go est de l'ordre de 10170 positions possibles (c'est-à-dire beaucoup plus grande que le nombre d'atomes dans l'univers) tandis que celle du jeu d'échecs n'est " que " de 1050 environ. Pour les informaticiens en général et les chercheurs - en modélisation statistique et en intelligence artificielle - en particulier, le jeu de Go est un problème très intéressant, qui soulève des problématiques difficiles dont les solutions pourraient s'appliquer dans d'autres domaines. C'est un défi de s'attaquer à un tel problème, d'autant plus que les techniques utilisées sont très proches de leurs domaines de recherche. Ainsi, ces travaux de recherche sont appliqués à un problème concret, difficile et ludique. Depuis quelques années, plusieurs logiciels commencent à menacer les maîtres humains, en mélangeant à loisir deux facettes de l'Intelligence Artificielle qui ont longtemps été tenues distantes: l'apprentissage et la plannification. Cette années, trois étudiants ont consacré leur MFE au sujet en travaillant ensemble sur la mise au point d'un logiciel mélangeant en effet ces différentes facettes (et en rajoutant un troisième aspect :"la reconnaissance de formes"), il serait idéal que ce sujet puisse être repris l'année prochaine de manière à progresser davantage sur la voie du champion informatique et de contribuer à mettre à jour un peu plus encore les ingrédients de l'intelligence humaine.

Supervisors:

		Hugues Bersini

Le comportement « normal » d'un OS se mesure par les séquences de « system call » les plus courantes. Par comparaison, le comportement anormal, dû éventuellement à une attaque virale, se singularise par des séquences de system call inhabituelles. Le MFE consistera en une étude statistique de la normalité informatique afin de mettre au point des méthodes bien plus fiables et efficaces de détection d'un ordinateur en « mauvaise santé » et qu'il serait grand temps de "soigner". Ces méthodes ont ceci de différent et d'original par rapport aux méthodes antivirales classiques qu'elles s'intéressent à ce qui se passe à l'intérieur de la boîte et ne tentent pas uniquement d'éviter de se faire contaminer par des virus extérieurs, qu'il n'est pas toujours possible de prévoir et de contrer.

Supervisors:

		Hugues Bersini

Ce MFE consistera en la simulation informatique, type « automate cellulaire » d'un système immunitaire très primitif incluant les antigènes, les lymphocites B et T ainsi que les cellules présentatrices d'antigènes. Lors de la réponse immunitaire, le lymphocite T qui s'en charge passe par plusieurs états: naïf, excité, proliférant, mémoire... Ces transitions d'état peuvent être exprimés par le biologiste sous forme d'un diagramme UML d'état-transition. Le système à mettre au point (et dont la portée applicative serait beaucoup plus grande que la seule immunologie) serait capable de générer automatiquement un code capable de simuler cette réponse uniquement à partir de ce diagramme. La génération automatique de code à partir des seuls diagrammes UML est la voie du future pour les développements logiciels. A ce jour, alors que les diagrammes classe et de séquence ont déjà fait l'objet de beaucoup d'attention, il n'en va pas de même pour le diagramme d'état-transition.

Supervisors:

		Hugues Bersini

Les concepteurs de circuits usent habituellement d'une approche dite top-down comme les tables de Karnaugh afin de réaliser une fonction logique donnée. Une méthodologie bien rodée qui a su faire ses preuves jusqu'ici. Avec la complexité grandissante des fonctions à réaliser et du nombre de données à traiter, il a fallu découper celles-ci en de sous-fonctions dont on possédait déjà une solution. Ainsi, par modularité, l'homme simplifie son problème initiale. Mais cela pose la question de la véritable efficacité des circuits obtenus. N'existe-t-il pas de solutions intégrant la totalité des sous-fonctions ? Une méthode dite bottom-up pourrait ainsi offrir une nouvelle voie de résolution. C'est par exemple le cas des algorithmes évolutionnaires qui, inspirés par la biologie, consistent à faire évoluer une population de circuits ensemble pour trouver une nouvelle solution. Plusieurs études ont montré que cette approche donne au moins de nouvelles idées de conception que l'humain n'avait jamais envisagées auparavant. L'objectif de ce MFE sera de mettre au point un framework logiciel afin de tester différentes types d'algorithmes évolutionnaires et de comparer les résultats obtenus avec les solutions classiques et connues.

Supervisors:

		Hugues Bersini
		Christophe Philemotte

Particle Swarm Optimization (PSO) is a computational intelligence technique inspired by the social behavior of animals such as birds or fish. In PSO algorithms, simple agents (called particles) move in a high-dimensional landscape exchanging only information about the altitude of the terrain they have explored. Their goal is to locate, as fast as possible, the tallest peak or the deepest valley of the landscape starting from random initial positions. The collective behavior of the agents resembles that of insect swarms. Technically speaking, particles are potential solutions to an optimization problem that is specified through a mathematical or computational model (the landscape). Particles exploit their individual memory to explore the solution space. However, the swarm as a whole has no means of exploiting its collective memory to guide its search. This causes a re-exploration of already known bad regions of the search space, wasting computing time. Estimation of distribution algorithms (EDAs) use information obtained during the optimization process to build ``profiles'' of good solutions. These profiles are ``learned'' on-line and are used to generate new candidate solutions. The goal of the project is to combine these two approaches to create a ``learning'' particle swarm algorithm that exploits the best of both approaches. On one hand, PSO algorithms are known to have a fast convergence into promising regions but fail to refine their search once particles are already in one of them. On the other hand, given that EDAs ``learn'' what a good solution should look like, they are good in focusing a search on very narrow regions.

Required Skills: Good background in mathematics, specially on statistics and probability. Basic programming skills in any language.

Supervisors:

		Marco Dorigo
		Thomas Stützle
		Mauro Birattari
		Marco Montes de Oca

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.

Supervisors:

		Marco Dorigo
		Thomas Stützle
		Mauro Birattari
		Prasanna Balaprakash

Particle Swarm Optimization (PSO) is a computational intelligence technique inspired by the social behavior of animals such as birds or fish. In PSO algorithms, simple agents (called particles) move in a high-dimensional landscape exchanging only information about the altitude of the terrain they have explored. Their goal is to locate, as fast as possible, the tallest peak or the deepest valley of the landscape starting from random initial positions. The collective behavior of the agents resembles that of insect swarms. Technically speaking, particles are potential solutions to an optimization problem that is specified through a mathematical or computational model (the landscape). Information exchange among particles obeys the topology of a communication network. Depending on some features of the network topology, the behavior of the algorithm can change dramatically. Although there has been work on the determination of the effects of using networks with different topological properties, is is still unclear what kind of topology should be chosen for different classes of problems. The goal of the project is to generate, through evolutionary computation techniques, optimal topologies for specific classes of problems. By analyzing the resulting networks, we could start characterizing the relationship between topologies and problem features.

Required Skills: Good programming skills in any language.

Supervisors:

		Marco Dorigo
		Thomas Stützle
		Mauro Birattari
		Marco Montes de Oca

Ants have inspired a number of artificial intelligence techniques among which the most successful is the general purpose optimization technique known as ant colony optimization. Probability Collectives, a very new optimization approach developed at NASA, primarily for aerospace systems, is based on a theory that deals with players and games.

The goal of the project is to understand the behavior of probability collectives by comparing it with ant colony optimization when applied to the traditional optimization problems. This involves implementation of both approaches and a systematic experimental analysis. The final goal is to the hybridize these two approaches by which ants will play games to tackle complex optimization problems.

Required Skills: The candidate should be fairly acquainted with C programming.

Supervisors:

		Marco Dorigo
		Thomas Stützle
		Mauro Birattari
		Prasanna Balaprakash

Il s'agit d'un mémoire de "text mining", c'est-à-dire de traitement automatique de documents. L'objectif principal est de développer des algorithmes de catégorisation de documents, basés sur des modèles d'apprentissage automatique de type "support vector machine", très en vogue actuellement. Il s'agit donc de catégoriser un document sur base de son contenu, à savoir les mots qu'il contient, dans une des catégories predefinies. La validation des algorithmes s'effectuera sur une base de donnee réelle, fournie par la societe IRIS. Tous les développements s'effectueront en Java ou C++.

Supervisors:

		Amin Mantrach
		Hugues Bersini

Ant Colony Optimization (ACO) is a successful optimization technique that has been inspired by the pheromone trail laying and following behavior of real ant colonies. ACO algorithms have mainly been applied to academic, combinatorial optimization techniques and only recently, an increasing number of real-world applications of ACO is being developed. One such application is the conformational analysis of flexible molecules. In this problem, the goal is to determine, given the structure of the molecule, the orientation of rotational bonds such that the molecule's internal energy is minimized. This problem is very relevant in a number of applications including the structure-based design of new drugs. Recently, a first Ant Colony Optimization (ACO) algorithm for the conformational analysis of molecules, called antconf, has been developed at MolMo Services. The goal of this project is to (i) further improve the performance of antconf, (ii) fine-tune the parameters of antconf, (iii) develop a genetic algorithm for the same problem and (iv) compare the performance of all developed algorithms based on a sound experimental methodology.

Required Skills: The candidate should be well acquainted with procedural and object oriented programming languages.

MolMo Services BVBA: MolMo is a company specialized in the solution of difficult optimization problems arising in computational chemistry.

Supervisors:

		Marco Dorigo
		Thomas Stützle
		Frits Daeyaert
		Mauro Birattari

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 640x480 pixels and 8 red leds for displaying patterns. Last year, a project carried out at IRIDIA developed a number 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.

Supervisors:

		Marco Dorigo
		Mauro Birattari
		Alexandre Campo