\chapter{Intelligence artificielle distribuée}

Dans ce chapitre  on cherche à constuire un  agent logiciel effectuant
plusieurs activités,  on choisit donc une  architecture modulaire dans
laquelle il y a autant  de modules que d'activités différentes. Un tel
découpage se prête très bien à une conception en langage objet.\\

Il y a  beaucoup de raisons qui poussent à  implémenter ou à adopter des
approches  de  raisonnement distribué  dans  un système  d'intelligence
artificielle:
\begin{itemize}
\item Les humains raisonnent ainsi.
\item Les machines parallèles existent (autant au niveau hardware que software).
\item  Certaines  applications  peuvent  gagner en  efficacité  et  en
rapidité (toutes les procédures ne sont pas parallélisables).
\item  Un développement  modulaire du  système. Facile  à écrire  et à
maintenir   ainsi  que   d'ajouter  ou   supprimer  des   domaines  de
connaissances et de façon de raisonner.
\item  Des techniques  de raisonnement  multiples. On  peut  avoir une
varieté  de  techniques dont  certaines  fonctionnent  mieux dans  des
domaines particuliers.
\item Des points de vue différents.
\item Relaiement.  Si un  module faillit le  système peut  continuer à
fonctionner.\\
\end{itemize}

Un système  de raisonnnement distribué est composé  de modules séparés
(appelés agents),  et d'un ensemble  de chemins de  communications entre
eux.
\begin{itemize}
\item Chaque agent agit comme une entité de résolution de problème.
\item Plusieurs  systèmes existent allant d'un système  de contrôle et
de connaissance centralisé à un système complètement décentralisé.\\
\end{itemize}

Un tel système doit permettre:
\begin{itemize}
\item une bonne coordination entre les agents;
\item une bonne structure de communication;
\item une technique de raisonnement distribué.\\
\end{itemize}

Nous allons d'abord voir la  technique des tableaux noirs, qui est une
utilisation   particulière  des   systèmes   multi-agents  avec   une
communication  centralisée  et  indirecte.  Nous  verrons  ensuite  les
systèmes  multi-agents  communiquant directement  avec  un système  de
contrôle décentralisé.

\section{Tableau noir (ou Blackboard)}
  
\subsection{Principe}

Une  architecture   de  tableau  noir   est  ainsi  appelée   car  son
fonctionnement est  analogue à celui de la  résolution collective d'un
problème par  une classe  d'écoliers. L'exemple généralement  pris est
celui de la construction d'un  puzzle. Les écoliers n'ont pas le droit
de communiquer  entre eux,  mais observent sur  le tableau  les pièces
déjà posées.  Dès qu'un élève  s'aperçoit qu'il peut poser  une pièce,
c'est-à-dire  contribuer  à la  résolution  du  problème,  il lève  le
doigt. Le professeur (qui assure le contrôle) choisit parmi les doigts
levés  qui  doit  aller  poser  sa  pièce au  tableau.  La  somme  des
contributions individuelles permet finalement de terminer le puzzle.

\subsection{Les composants}

De l'exemple on degage plusieurs composants:

\begin{description}
  \item [KS (Knoledge source)]: la source de connaissances (l'élève de
notre exemple).
\begin{itemize}
  \item Chaque  KS peut  lire, créer et  modifier les  informations du
  tableau noir;
  \item Chaque KS  est indépendant, il a sa façon  de raisonner et ses
  connaissances propres.
  \item Chaque KS  n'a pas à connaître les  autres experts en présence
  ni leurs compétences.
  \item  Chaque KS  accepte des  événements  auxquels il  réagit à  sa
  manière.  Ces  événements proviennent  soit  du  contrôleur soit  du
  tableau noir (selon l'implémentation).
  \item  Lorsqu'un  KS  est  actif (c'est-à-dire  que  ses  conditions
  d'activations  sont vraies),  un  KSAR  est créé  et  ajouté dans  un
  agenda.
  % C quoi un KSAR ? un agenda?
\end{itemize}

\item [Le Tableau noir]: ``le bureau de travail''.
  \begin{itemize}
    \item Contient  les informations produites  depuis le début  de la
    résolution.
    \item   Contient  des   solutions  partielles,   les  alternatives
    possibles, les solutions finales et des informations de contrôle.
    \item Affiche l'état d'avancement du travail. Il se met à jour par
    étape. Le problème est résolu incrémentalement.
    \item Il sert comme moyen de communication.
    \item  La manière  dont sont  organisées les  informations affecte
    beaucoup l'efficacité  du système. Les  KS doivent continuellement
    chercher les informations qui leur permettent d'être activées.
    \item On tend à avoir plusieurs niveaux d'abstraction, une
    classification des informations et plusieurs tableaux noir afin
    d'optimiser la recherche d'information.
  \end{itemize}

\item [Le contrôleur]: joue le rôle du professeur.
  \begin{itemize}
    \item Choisit le KSAR de l'agenda qui sera activé.
    \item   L'algorithme    de   selection   dépend    des   buts   de
    l'application. Il est à déterminer par le développeur.
    \item Le choix peut dépandre de l'avancement du problème.
    \item Intéragit avec les KS à l'aide d'événements.
  \end{itemize}

\end{description}

\subsection{Algorithme}

La figure illustre le fonctionnement d'un tableau noir. Il s'agit d'un
fonctionnement  séquentiel -- il  n'y a  qu'une seule  KS active  à un
instant donné,  et opportuniste -- on  ne sait pas  d'avance quelle KS
sera active à un instant donné.\\

\begin{figure}[h]
  \begin{center}
    \includegraphics{images/blackboard.ps}
  \end{center}
  \caption{Cycle de base d'un tableau noir}
\end{figure}

Le cycle de fonctionnement d'un tableau noir est assez simple dans son
principe :
\begin{itemize}
  \item Selon  les éléments présents dans  le tableau noir,  si une KS
  peut  être activée, le  contrôleur crée  un KSAR  correspondant dans
  l'agenda. Cette  étape est répétée  autant de fois  qu'il y a  de KS
  dont les conditions d'activation sont réalisées.

  \item  Les   KSAR  de  l'agenda  sont   ordonnés  selon  différentes
  stratégies et  selon le type  de contrôle. Le KSAR  correspondant le
  plus à la stratégie de sélection est finalement choisi.
    
  \item La KS du KSAR choisi à l'étape précédente est déclenchée. Ceci
  a  généralement pour  conséquence de  modifier le  tableau  noir par
  ajouts de  nouveaux éléments, destructions de  certains éléments, ou
  modifications  d'éléments  déjà  présents.  Le cycle  reprend  à  la
  première étape et le fonctionnement continue tant qu'il y a des KSAR
  dans l'agenda.
\end{itemize}

\subsection{Intérêts}

Les raisons poussant à utiliser un tel système sont les suivantes:
\begin{itemize}
  \item  On   nécessite  plusieurs  differentes   représentations  des
  connaissances. Chaque KS représente alors une forme de connaissance.
  \item Il n'existe  pas de méthode directe pour  obtenir la solution,
  on  peut  l'obtenir  uniquement  à  partir  d'étapes  intermediaires
  débloquant à chaque fois de nouvelles methodes.
  \item Le developpement de l'application recquiert un grand nombre de
  developpeur  effectuant  des   tâches  indépandantes  les  unes  des
  autres. Les tableaux noirs  permettent de développer et tester chaque
  KS séparement.
  \item La  connaissance partielle du  problème ou l'accés limité  à des
  données ne permet pas une détermination immédiate de la solution mais
  une approche incrementale permet de continuer de s'en approcher.
  \item  Des  raisonements à  plusieurs  niveaux  ou  flexibles et  un
  contrôle dynamique de la résolution est nécessaire.
\end{itemize}

\section{Systèmes multi-agents}

\subsection{Définition d'un agent}

Tout  d'abord  essayons de  définir  ce  qu'est  un agent.  Voici  ces
différentes caractéristiques:
\begin{description}
\item  [situé]: l'agent  est capable  d'agir sur  son  environnement à
partir des entrées sensorielles qu'il reçoit de ce même environnement;
\item [autonome]: l'agent est  capable d'agir sans l'intervention d'un
tiers (humain ou agent) et  contrôle ses propres actions ainsi que son
état interne;
\item  [proactif]: l'agent  doit exhiber  un comportement  proactif et
opportuniste,  tout en étant  capable de  prendre l'initiative  au bon
moment;
\item  [capable de  répondre à  temps]: l'agent  doit être  capable de
percevoir son  environnement et d'élaborer  une réponse dans  le temps
requis;
\item [social]: l'agent doit être capable d'interagir avec des autres
agents (logiciels ou humains) afin d'accomplir des tâches ou d'aider ces
agents à accomplir les leurs.
\end{description}

\subsection{Caractéristiques}

Un système multi-agent est  un système distribué composé d'un ensemble
d'agents.   Contrairement aux  systèmes  d'IA, qui  simulent dans  une
certaine  mesure les capacités  du raisonnement  humain, les  SMA sont
conçus   et   implantés   idéalement   comme  un   ensemble   d'agents
interagissants, le  plus souvent, selon  des modes de  coopération, de
concurrence ou de coexistence.

Un SMA est généralement caractérisé par:
\begin{itemize}
\item chaque agent  a des informations ou des  capacités de résolution
de problèmes limitées, ainsi chaque agent a un point de vue partiel,
\item il n'y a aucun contrôle global du système multi-agent,
\item les donnés sont décentralisées,
\item le calcul est asynchrone.
\end{itemize}

Il faut une interaction à un niveau supérieur pour:
\begin{itemize}
\item de la coordination entre les agents;
\item de la communication pour échanger des inforations entre les agents;
\item organiser les actions des agents;
\item effectuer une résolution distibuée du problème.
\end{itemize}


\subsection{Principe}

Chaque   agent  va   réceptionner  des   informations   provenant  de
l'environnement grâce à ses  capteurs. Il va ensuite ``réflechir'', en
prenant compte des interactions qu'il a avec les autres agents. Ce qui
va  l'amener à  effectuer  des actions  et  changer d'état,  ce qui  va
influencer les  autres agents  et modifier l'environnement.  Le système
est donc  en continuelle évolution,  lorsque celui ci se  stabilise on
peut considerer que la solution a été trouvée.

\subsection{Interaction entre agents}

Toute la difficulté de l'implémentation d'un système multiagent réside
dans  la méthode de  communication et  de coordination  des différents
agents, car contrairement au système  de tableau noir, on veut que les
agents puissent dialoguer directement entre eux. Il faut donc un moyen
efficace de dialogue et une méthode de contrôle des échanges.

Une   méthode   d'intéraction   entre   agents  coopératifs   est   la
\textit{Planification partielle  globale} (en anglais  GPP pour Global
and Partial Planification). C'est  un approche flexible qui permet aux
divers agents d'un système  de se coordonner dynamiquement. Les agents
interagissent en  se communiquant leurs  plans et leurs buts  selon un
niveau d'abstraction approprié. Ces communications permettent à chacun
d'anticiper quelles  seront les actions  futures d'un ou  de plusieurs
autres  agents,  augmentant  ainsi  la  cohérence  de  l'ensemble  des
agents.  Comme les  agents coopèrent,  le receveur  d'un  message peut
utiliser   les   informations   reçues   afin  d'ajuster   sa   propre
planification.

   Une autre  méthode de coordination des agents  consiste à modéliser
explicitement  le  travail d'équipe  qu'effectuent  les agents.  Cette
approche s'avère  très pratique dans des  environnements dynamiques où
les membres de l'équipe peuvent  échouer dans leurs tâches ou découvrir
de nouvelles  opportunités. Dans  de telles situations,  l'équipe doit
pouvoir évaluer sa performance et  être en mesure de se réorganiser en
conséquence.  Dans cet  ordre d'idées,  on parle  alors du  modèle des
"intentions conjointes".  Un tel  modèle est d'ailleurs  une extension
naturelle  du raisonnement  pratique.  Dans ce  modèle,  on cherche  à
modéliser  l'état mental  d'une équipe  en action.  L'équipe  aura une
intention  conjointe  si  chaque  membre  de  l'équipe  est  engagé  à
compléter  l'action  de  l'équipe.  Préalablement  à  cette  intention
collective, tous  les membres de l'équipe auront  établi les croyances
et les engagements communs appropriés, et ce en s'échangeant des actes
(du langage naturel) de requête et de confirmation.

Une  autre  solution  est  d'evaluer  chaque  décision  prise  par  un
agent. Il  faut aussi que  chaque agent soit omniscient  et connaisse
les résultats  de tous  les autres.  On peut ainsi  créer un  arbre de
décisions  et  appliquer  toutes   les  méthodes  de  la  théorie  des
jeux. Chaque partie pourra  alors choisir l'alternative qui maximisera
son  utilité.  Malgré l'élégance  mathématique  de  cette méthode,  de
telles négociations s'appliquent mal à des problèmes du monde réel où:
\begin{itemize}
  \item les négociations se déroulent dans une certaine incertitude;
  \item  les  négociations   impliquent  des  critères  beaucoup  plus
complexes qu'une utilité à une seule dimension;
   \item les utilités des agents sont secrètes;
   \item les agents ne sont pas omniscients dans la réalité.
\end{itemize}
Une  telle méthode permettrait  aussi d'inférer  les plans  des autres
agents et ainsi de minimiser les communications entre agents.

\subsection{Communication entre agents}

  La  communication  inter  agent   est  primordiale  pour  avoir  une
intelligence  de  groupe  efficace.  On  dispose  alors  de  plusieurs
techniques:
\begin{itemize}
  \item  propagations de  signaux:  Un  agent émet  un  signal qui  est
transmis  dans  l'environnement;  l'intensité  du signal  décroît  par
rapport à la distance.
  \item  Les   traces.  Les  agents  laissent   tomber  des  "morceaux
  radioactifs" en  faisant ainsi des  traces. Puis les  agents suivent
  les traces faisant diminuer la trace jusqu'à la disparition de celle-
  ci.
  \item Des  systèmes de  messages reposant sur  de gros  protocole de
communications afin  d'établir des règles de  communication, comme par
exemple le modèle Acteur.
  \item Des tableaux noirs comme vue précédement.
  \item Des langages spécifiques tels que KQML ou FIPA-ACL.
\end{itemize}

 Les langages de communication  entre agents (ACL: Agent Communication
Language)  peuvent communiquer  des  propositions, des  règles et  des
actions et pas uniquement des  objets sans une sémantique associée. Un
message ACL décrit un état  désiré dans un langage déclaratif et n'est
pas une simple  invocation de méthode. Les ACLs  partent de la théorie
des  actes de  langage  (ou  de discours)  ("Speech  Act Theory").  La
communication peut être structurée dans des conversations.

Le KQML (Knowledge Query and  Manipulation Language) est un langage de
communication  de haut niveau  orienté messages  et un  protocole pour
l'échange  des  informations qui  est  indépendant  de  la syntaxe  du
contenu (KIF, SQL, Prolog,...) et de l'ontologie de l'application.

  KQML sépare  la sémantique  du protocole de  communication protocole
(indépendante de  domaine) de la sémantique du  message (dépendante de
domaine).

   Puis plus  récemment le langage  ACL propose un rafinement  de KQML
tant au niveau  de certains protocoles qui sont  plus explicites qu'au
niveau de la sémantique des messages.

\section{Comparaison des architectures}

Les deux types d'architectures du paradigme de l'IAD mettent en oeuvre
deux  types différents  de résolution  de problèmes  :  une résolution
ascendante et une résolution descendante.

Dans une architecture de tableau  noir, les KS peuvent être vues comme
l'implantation  d'un  ensemble  d'expertises.  L'expression  ``système
multi-experts''  est d'ailleurs également  utilisée pour  désigner une
telle architecture. Les experts interviennent selon leurs compétences,
c'est-à-dire que  chacun d'eux n'est capable de  résoudre qu'un nombre
restreint de sous-problèmes  relativement bien circonscrits. Autrement
dit, dans une  architecture de tableau noir, la  résolution ne peut se
faire que si le problème est décomposable en sous-problèmes. Il s'agit
donc d'une démarche descendante de  résolution. On sait par avance que
le  problème est  résolvable grâce  à  sa décomposition.  À partir  de
solutions partielles qui sont assemblées et transformées, une solution
complète  est finalement  produite.  Pour résumer,  nous dirons  qu'il
s'agit d'une méthode de résolution individuelle de sous-problèmes avec
troncature explicite du problème à résoudre.

Avec  une architecture  multi-agents, ``une  intelligence collective''
apparaît.  Une  intelligence  collective   n'est  pas  la  somme  des
intelligences   individuelles    mais   le   résultat   d'interactions
intelligentes entre les individus. Elle  ne peut apparaître que si les
agents peuvent  directement interagir entre  eux, ce qui n'est  pas le
cas dans une architecture de tableau noir. La résolution d'un problème
par  les  agents   ne  peut  donc  pas  se   faire  par  étapes,  mais
progressivement et surtout globalement,  puisque les agents opèrent en
parallèle.  Cela   revient  à  adopter  cette   fois-ci  une  démarche
ascendante  de  résolution. On  ne  sait  pas  à l'avance  comment  le
problème peut être résolu ou  bien même s'il existe une solution, mais
on   connaît   les   éléments   élémentaires   intervenant   dans   sa
résolution. L'interaction  de ces  divers éléments peut  faire émerger
une solution  unique lorsque  le système devient  stable (c'est-à-dire
qu'il n'y  a plus de  modification de l'environnement). Si  le système
oscille  périodiquement d'un état  à un  autre, c'est  qu'il y  a deux
solutions possibles.  Pour résumer cette démarche  de résolution, nous
dirons  qu'il  s'agit  d'une  méthode de  résolution  collective  sans
troncature explicite du problème à résoudre.