Introduction

Afin de comprendre ce que sont les algorithmes d'apprentissage multi-agents, quel est leur intérêt, dans quel cadre et dans quel but ils peuvent être mis en oeuvre; nous allons naturellement d'abord expliquer ce que sont l'apprentissage artificiel d'une part et les systèmes multi-agents d'autre part. Ensuite, fort de ces définitions nous pourrons expliciter plus clairement ce que sont les algorithmes d'apprentissage multi-agents.

1. L'apprentissage artificiel
2. Les systèmes multi-agents
   1. Le parallélisme
   2. Notion d'agent
   3. Notion d'Environnement
   4. Les systèmes multi-agents
3. Les algorithmes d'apprentissage multi-agents

- L'Apprentissage Artificiel -

Essentiellement, l'apprentissage artificiel est né de la nécessité de combler un manque dans les systèmes issus de l'intelligence artificielle historique, dont le paradigme est celui des systèmes experts.
Ces systèmes sont des programmes possédant un ensemble de règles qu'ils activent afin de fournir une certaine réponse en fonction de la donnée de l'environnement. De tels programmes sont donc définis une fois pour toutes, et réagissent aux sollicitations de l'environnement, toujours de la même façon.
La lacune principale de ces systèmes, c'est que le programme est figé, il n'a pas la possibilité de changer ses règles s'y elles s'avèrent incorrectes ou inefficaces. Ils sont incapables d'appendre de leurs expériences passées afin d'améliorer leurs réponses lors d'interactions futurs.
Ce qui manque, en un mot, à ce paradigme, c'est l'adapativité, c'est-à-dire la possibilité de modifier ses propres règles d'action, de s'adapter à un environnement changeant, d'apprendre.

L'apprentissage artificiel, c'est donc cette dimension nouvelle apportée aux programmes. Cela suppose naturellement un retour de la qualité de la réponse qu'ils donnent, on parle alors d'apprentissage totalement supervisé, semi supervisé ou non supervisé, pour indiquer le degré de retour sur leurs actions dont disposent les programmes.
Quelque soit le degré de retour dont ils disposent, la caractéristique essentiel de ces programmes, et qui les fait entrer dans le cadre de l'apprentissage artificiel, c'est que leur état interne se modifie au cours de leurs interactions avec l'environnement. On parle alors d'apprentissage.
Un algorithme d'apprentissage, c'est donc une procédure, un programme, qui fait évoluer une structure de données, qui est éventuellement un modèle du monde, en fonction de ses interactions avec l'environnement.
On distingue deux grands types d'apprentissage: l'appentissage supervisé et l'apprentissage non supervisé.

• Dans le cas de l'apprentissage supervisé, le modèle appris peut être guidé, supervisé, de deux façons différentes: soit à partir d'une explication, soit à partir d'exemples et de contre-exemples. Chaque étape de l'algorithme est alors soit une évaluation de la forme par rapport à l'explication initialement donnée, explication qui peut prendre la forme d'une fonction d'évaluation, soit un information supplémentaire sur la nature du modèle à apprendre et qui est généralement fourni sous la forme d'un exemple ou d'un contre-exemple
• Dans le cas de l'apprentissage non supervisé, l'algorithme modifie seul la forme initiale par itérations successives jusqu'à arriver à un point fixe, ou jusqu'à ce que la forme remplisse des propriétés données.

- Les Systèmes Multi-Agents -

Les systèmes multi-agents sont un renouvellement du parallélisme par l'introduction de la notion d'agent.

Le parallélisme

Notion d'agent

On peut distinguer cinq types fondamentaux d'agents : (se repporter à [Russel et Norvig, 2003] pour la classification)

Nom	Caractéristiques essentielles
Simple-reflex agent	C'est le modèle agent de base, qui agit selon un système de règles "condition-action"
Model-based reflex agent	C'est un modèle qui en plus d'un système de règles "condition-action" intègre une représentation du monde
Goal-based agent	C'est un modèle d'agent d'un niveau d'intégration supérieure qui en plus d'une représentation du monde possède des buts a atteindre dans ce monde et agit en fonction de l'état du monde et de ses buts, il est donc également capable de planification
Utility-based agent	Ces agents sont un raffinement des Goal-based agents, ils ont une appréciation plus fine de la résolution des buts, qui s'expriment sous la forme d'une optimisation de fonction à valeurs réelles et non plus simplement binaires
Learning agent	Tout les types d'agents peuvent par ailleurs augmenter leur efficacité en intégrant une capacité d'apprentissage qui leur permet selon un retour de qualité sur leurs actions de modifier leur comportement afin d'optimiser un critère de performance donné

Notion d'Environnement

Caractéristique	Description
Fully observable / partially observable	Caractérise le fait que l'environnement est totalement ou partiellement accessibles aux agents
Deterministic / stochastic / strategic	Si l'état future de l'environnement est totalement déterminé par son état courant et les actions des agents alors l'environnement est déterministe, il est stochastique sinon. Si l'environnement est déterministe execpté pour les actions des autres agents, il est dit stratégique
Episodic / sequential	Dans un environnement de type episodique, les interactions d'un agent avec l'environnement se font par bloc, par épisode, et les actions de l'agent lors d'un épisode n'affecte pas les actions prises dans les épisodes future. Un environnement est dit séquentiel dans le cas contraire
static / dynamic	Un environnement est dynamique s'il peut changer d'état pendant que l'agent est en train de réagir, il est statique sinon.
dicrete / continous	Qualifie les paramètres de l'environnement, s'ils sont a valeurs discrètes ou continues
single agent / multi-agents	L'environnement est simple-agent s'il n'y a qu'un seul agent, multi-agents sinon.

Système Multi-Agents

• Coopération
• Compétition

Du point de vue du parallélisme enfin, un système multi-agents peut être vue comme un calcul distribué dans lequel les agents sont des processus calculatoires qui s'effectuent plus ou moins en parallèle, selon la fréquence des interactions entre agents. (Voir [Wolfram (2002)] pour en savoir plus sur la dimension computationelle des systèmes complexes dans une approche originale et féconde!)

- Les Algorithmes d'Apprentissage Multi-Agents -

Les algorithmes d'apprentissage multi-agents sont donc des algorithmes d'apprentissage tels que nous les avons défini ci-dessus, ayant par ailleurs une structure multi-agents, c'est-à-dire pouvant être décrit comme un système constitué d'entités autonomes, d'agents, en interaction avec un environnement et interagissant éventuellement les uns avec les autres.
Les algorithmes d'apprentissage multi-agents sont donc issus de la rencontre entre l'apprentissage artificiel et le modèle, le paradigme, des systèmes multi-agents. C'est en quelque sorte et plus simplement, l'introduction du parallélisme dans les algorithmes d'apprentissage, augmenté de la notion d'agent. C'est une distribution de la tâche d'apprentissage dans laquelle chaque agent effectue une sous-tâche qui n'est pas en générale, prise isolément, capable de résoudre l'objectif global d'apprentissage, mais qui, ajouté à toutes les autres permet au système global d'effectuer l'apprentissage voulu.

On se trouve ici face à une propriété fascinante des systèmes complexes, "l'émergence", selon laquelle un ensemble d'éléments donnés, par le jeu de leurs interactions, font émerger, au niveau global, c'est à dire au niveau du système que constitue l'ensemble de ces éléments, des propriétés qu'aucun des élements constitutifs du système ne possède par ailleurs. Pour en savoir plus voir sur ce sujet en particulier et les systèmes complexes en général voir ici. Cette caractéristique des systèmes complexes est utilisé par les algorithmes d'apprentissage multi-agents pour effectuer l'apprentissage de tâches complexes.

Une classification intéressante des différents types d'algorithmes multi-agents peut être obtenu en considérant les capacités des agents. Au niveau le plus bas, on a des entités qui agissent en parallèles mais dont les propriétés ne permettent pas encore d'utiliser la notion d'agent à proprement parler, tel que nous l'avons défini ci avant. On se trouve alors encore dans le cas d'algorithmes d'apprentissage simplement parallèles, ou distribué, c'est le cas par exemple des réseaux de neurones, pour lequel chaque neurone peut être vu comme un "agent" primitif, un processus indépendant à tout le moins. Ensuite lorsque les entités considérées possèdent des propriétés d'agents, comme l'autonomie, la pro-activité (sous tendu par la présence de buts internes), on rentre dans la classe des algorithmes d'apprentissage multi-agents. Au sommet de cette classification, on trouve des agents ayant eux même des capacités d'apprentissage. Les algorithmes d'apprentissage multi-agents sont donc toujours utilisés sous une forme non supervisé au niveau global. Il s'agit en fait de laisser évoluer dynamiquement le système multi-agents jusqu'à ce que celui ci atteigne un point fixe, un point d'équilibre. L'état du système alors obtenu constitu, la solution du problème, le modèle recherché.
L'intérêt principal des systèmes multi-agents dans les algorithmes d'apprentissage tient essentiellement au fait que pour certains types de problèmes, le fait de distribuer entre plusieurs agents la résolution, rend celle-ci nettement plus accessible que si un seul agent devait le traiter d'un seul bloc. Pour certains problèmes, comme la recherche de modèles de coordination entre agents pour effectuer collectivement certaines tâches, un apprentissage centralisé paraît totalement exclu, l'apprentissage multi-agents est dans des cas comme celui-ci abolument nécessaire.