Apprentissage mono-agent et multi-agents

Définir ce qu'est un agent, ou ce qu'est un système multi agents (SMA), dépasse le cadre de ce travail, aussi nous ne citerons que quelques définitions pour situer le sujet. D'ailleurs, les définitions sont multiples: dans ce domaine de recherches très actuel les avis n'ont pas encore convergé et il existe même des articles publiés qui ont uniquement pour sujet la définition d'un agent, par exemple "Is it an Agent, or just a Program?" [Franklin & Graesser, 1996].

En 1995, Ferber a défini un agent par:
"Les agents sont des entités matérielles ou logicielles qui effectuent un ensemble d'opérations, au nom d'un utilisateur ou d'un programme, avec un certain degré d'indépendance ou d'autonomie."
Et un système multi agents par:
"On appelle système multi-agents (ou SMA) un système composé des éléments suivants:

1) Un environnement E, c'est à dire un espace disposant généralement d'une métrique.
2) Un ensemble d'objets O. Ces objets sont situés, c'est à dire que, pour tout objet, il est possible à un moment donné d'associer une position dans E. Ces objects sont passifs, c'est à dire qu'ils peuvent être perçus, crées, détruits et modifiés par les agents.
3) Un ensemble A d'agents, qui sont des objects particuliers (A inclus dans ou egal à O), lesquels représentent les entités actives du système.
4) Un ensemble de relations R qui unissent des objets (et donc des agents) entre eux.
5) Un ensemble d'opérations Op permettant aux agents de A de percevoir, produire, consommer, transformer et manipuler des objects de O.
6) Des opérateurs chargés de représenter l'application de ces opérations et la réaction du monde à cette tentative de modification, que l'on appellera les lois de l'univers."

Certaines définitions sont très larges, telle celle qui nous a été donnée par J. P. Sansonnet:
"Un agent est une entité autonome possédant une intention privée manifestée dans un champ social avec des interactions avec un environnement ouvert";
mais nous restreindrons dans ces pages le concept d'agent aux agents artificiels: programmes informatiques, robots incarnés, etc.
Toutes les techniques informatiques d'apprentissage peuvent être appliquées par des agents; c'est ce que nous montrerons dans les divers chapitres de ces pages.

Pour en savoir plus voyez les développements d sujets suivants :

Architecture de subsomption de Brooks (Mary Felkin)
Technologies de robots autonomes (Sylvain Le-Beux)
Apprentissage situé mono robot (Kevin Sejourne)
Technologies de robots autonomes (exemples d'applications) (Xavier Bahar)
Apprentissage situé multi-robot (robotique collective) (Geneviève Temporal)
Agents et ambiant (objets pro-actifs, 'smart objects', CHIPS) (Sylvain Chevallier)
Technologie et exemples d'application des robots autonomes (Guillaume Payen)

Introduction aux principales m éthodes d'apprentissage

Classification des méthodes d'apprentissage:

Les méthodes d'apprentissage peuvent être classées de différentes manières.

Apprentissage supervisé vs. apprentissage non supervisé.
Suivant les caractéristiques de l'espace de recherche: données propositionnelles vs. données relationnelles, données discrètes (ou "nominales") vs. données continues (ou "numériques").
Suivant les proprietés recherchées de la solution: minimisation de l'erreur en généralisation vs. compréhensibilité du résultat (ce qui séparerait les méthodes statistiques des méthodes symboliques comme les arbres de décision).

D'autres distinctions, permettant une classification secondaire, existent:

Suivant le type de problème: satisfaction de contraintes, optimisation d'une fonction... En ce qui concerne les méthodes d'apprentissages des agents ou des systèmes multi-agents, c'est le classement choisi par par [Weiss 1997] le numéro spécial de "Lecture Notes in Computer Science" consacré à l'apprentissage dans les systèmes multi-agents. Ils distinguent l'apprentissage du comportement (par exemple l'apprentissage de la coopération ou de la compétition entre agents), l'apprentissage par mimétisme d'un agent s'inspirant d'autres agents et l'apprentissage de la communication 'inter-agents'.
Suivant l'origine de la théorie sous-jacente: les méthodes inspirées des processus naturels vs. celles d'inspiration mathématique/logique.
Les méthodes déterministes vs. les méthodes stochastiques.

Leur classification la plus didactique, cependant, est une liste non ordonnée comprenant 4 groupes:

Algorithmes génétique, programmation génétique et stratégies d'évolution
Apprentissage par renforcement et/ou statistique, incluant "Naive Bayes" et l'apprentissage de réseaux Bayesiens ainsi que les méthodes connextionistes, les SVMs et le Q-learning [Ross, 1984].
Méthodes de classification et de clustérisation par règles et graphes d'induction
L'apprentissage non paramétrique ou CBR, "apprentissage à base de cas".

Principes des méthodes d'apprentissage :

Algorithmes génétiques

[Holland, 1975] a découvert que le proccessus de l'évolution naturelle décrit par [Darwin, 1859] pouvait être simulé pour une population d'individus (de longueur fixe) où chaque individu représente une solution possible d'un problème.

Au temps zéro, une population est générée aléatoirement. Chaque individu est testé et se voit attribuer une valeur de fitness correspondant à sa performance. Les meilleurs individus auront plus de chance que les moins bons de devenir les parents de la génération suivante.
L'algorithme boucle sur un cycle - Sélection des meilleurs individus - Croisements stochastiques entre individus et/ou mutation stochastique, ce qui génère de nouveaux individus appelés "enfants" - re-Selection des meilleurs, etc. Le critère d'arrêt dépend de l'implémentation, le plus simple est d'arrêter lorsqu'une performance donnée est atteinte par au moins un individu.

Ce shéma montre comment les opérateurs de croisement et de mutation peuvent être utilisés pour générer de nouveaux individus (dans ce cas des fonctions mathématiques) de taille variable. Comme la structure d'arbre de ces individus permet également de représenter des programmes informatiques cette technique s'appelle la programmation génétique.

[Koza, 1993] a utilisé cette technique pour faire évoluer le contrôleur d'un robot muni d'une architecture de subsomption, expérience décrite dans la partie apprentissage des architectures de subsomption.

Les agents incarnés dans des robots, virtuels ou simulés, [Godzik, Schoenauer & Sebag, 2004], ainsi que les populations d'automates cellulaires [Kazakov & Sweet, 2004], sont particulièrement bien adaptés à cette stratégie.

Apprentissage par renforcement et apprentissage statistique

Sous cette dénomination se regroupent plusieurs algorithmes qui ont pour point commun un apprentissage à partir du "vécu", de l'expérience passée évaluée mathématiquement. Des stratégies de réduction d'erreurs sont ensuite calculées à partir de cette évaluation.

L'algorithme le plus célébre de cette catégorie est sans conteste "Naive Bayes". Il permet de faire de l'apprentissage supervisé en se basant sur le théorème de Bayes:
P(A, B) = P(A) * P(B|A).
De là P(B|A) = P(B) * P(A|B) / P(A).
Lorsqu'on tente de prédire une "classe" B en fonction d'attributs connus A (qu'on suppose indépendants) on énumère les cas correspondants figurant parmi exemples connus. Il n'y a pas plus simple et cet algorithme fait parfois des prévisions plus précises que des algoritmes bien plus sophistiqués.
Les réseaux probabilistes bayesiens, également appropriés à l'apprentissage dans les systèmes multi-agents [Maes, Meganck & Manderick 2004], sont presque aussi simples, mais leur apprentissage est très cher en terme de temps de calcul.

Dans les sytèmes multi-agents coopératifs, l'apprentissage de la coordination est cruciale. Dans ce contexte, la coordination est définie comme la capacité de deux ou plusieurs agents à atteindre conjointement un consensus au sujet des actions désirables dans un environement. Spiros Kapetanakis et Daniel Kudenko, par exemple, ont utilisé le Q-learning pour qu'une population d'agents indépendants, ne pouvant pas s'observer les uns les autres, puisse apprendre à coordonner leurs efforts [Kapetanakis, 2002].

Règles et graphes d'induction

L'induction, dans ces systèmes, est la capacité de généraliser à partir de données. L'exemple classique de cette méthode de raisonnement est le tennis (parfois remplacé par le golf). J'observe mes voisins durant 15 jours et je remarque que durant cette période ils n'ont pas joué au tennis lorsqu'il pleuvait, sauf lorsque la température était supérieure à 35 degrés. J'en conclus qu'il s'agit là d'une règle générale: il ne jouent jamais au tennis si il pleut et si la température est inférieure à 35 degrés. J'utilise les règles induites pour prédire ce qu'ils feront aujourd'hui :

Règle numéro 1:

Si il ne pleut pas mes voisins joueront au tennis.
Si il pleut, passer à la règle numéro 2.

Règle numéro 2:

Si la température est supérieure à 35 degrés mes voisins joueront au tennis.
Si la température est inférieure à 35 degrés ne voisins ne joueront pas au tennis.

De nombreux algorithmes permettent de faire de telles prédictions à partir de données, les plus célébres étant probablement les systèmes à base d'arbres de décision (dont un exemple illustrant les règles ci-dessus est présenté ci-dessous): C4.5 [Quinlan, 1993] et CART ("Classification and Regression Tree") [Breiman, Friedman, Olshen & Stone, 1984].

Dans les systèmes multi-agents ils sont utilisés pour, par exemple, apprendre à prédire les actions des autres agents et autres tâches de planification [McEleney & O'Hare, 2004].

Raisonnement par analogie et apprentissage à base de cas

Le Raisonnement par Analogie (RA) et le Raisonnement Basé sur les Cas (RBC ou RàBC) sont deux approches utilisant des solutions de problèmes résolus antérieurement. Le RBC, manipulant des cas relatifs à un seul et même domaine, est souvent considéré comme une forme plus restreinte du RA. La première implémentation du RA remonte au programme d'Evans [Evans, 1968 ] en 1968, programme résolvant des tests d'intelligence basés sur des analogies entre figures géométriques.

Cependant l'une des premières descriptions exhaustives des différentes étapes du processus n'a été publiée qu'en 1989-90 par Campbell et Wolstencroft [Wolstencroft, 1989 ] [Campbell & Wolstencroft 1990 ].

Les 7 étapes qu'ils ont identifiées sont les suivantes (cf.figure fichier joint):

1. Identification du fait que le RA peut aider à la résolution du problème cible courant.
2. Recherche d'un problème base analogue au problème cible.
3. Elaboration ou élimination des aspects non pertinents du problème de base.
4. Mapping ou mise en correspondance des parties du problème de base avec les aspects similaires du problème cible.
5. Inférence ou déduction de caractéristiques (solutions) attribuées au problème cible à partir de celles présentes dans le problème de base.
6. Justification ou vérification du bien fondé des conclusions inférées.
7. Apprentissage, c'est à dire mémorisation du problème cible enrichi de sa solution.

Prasad, Lesser, et Lander, par exemple, ont appliqué cette technique à une population d'agents mettant en commun leur base de cas [Prasad, Lesser & Lander, 1998 ].