Introduction
Le thème des systèmes
multi-agents, s'il n'est pas récent, est actuellement un champ
de recherche très actif. Cette discipline est à la connexion de
plusieurs domaines en particulier de l'intelligence artificielle, des
systèmes informatiques distribués et du génie logiciel.
C'est une discipline qui s'intéresse aux comportements collectifs
produits par les interactions de plusieurs entités autonomes et
flexibles appelées agents. Ces agents peuvent
être en effet classifiés en deux catégories selon les
techniques qu'ils emploient dans leurs décisions : les agents
réactifs, basent leur décision suivante seulement sur
l'entrée sensorielle courante et les agents planificateur,
prennent en compte une anticipation des développements futures du monde
pour décider sur l'action favorable.
La planification est aussi un autre
thème ayant depuis les années 60 une grande importance dans
plusieurs domaine et surtout celui de la robotique. C'est une discipline de
l'intelligence artificielle qui vise le développement d'algorithmes pour
produire des plans, typiquement pour l'exécution par un robot ou tout
autre agent. Les logiciels de planification qui incorporent ces algorithmes se
nomment planificateurs.
La planification dans les systèmes multi-agents, ou
planification multi-agents considère alors le problème de
planification dans le contexte des systèmes multi agent. Elle
étend la planification traditionnelle en intelligence artificielle aux
domaines où plusieurs agents sont impliqués dans un plan et ont
besoin d'agir simultanément.
Pour parler donc sur la planification multi-agents, il faut
passer premièrement par une description de la planification classique et
des principaux concepts des SMA.
I. La planification
I.1. Définition et
aspects
La planification est une sous-discipline de l'intelligence
artificielle qui se propose [9]:
1- Etant donnée une représentation de
l'état initial du monde.
2- Etant donné un ensemble d'opérateurs de
changement d'état du monde (qui représentent les actions qu'il
est possible d'effectuer dans le monde).
3- Etant donné un but à atteindre (problème
à résoudre).
De donner les moyens à un système informatique de
trouver une suite d'actions (c-à-d
d'opérateurs directement
exécutables) à appliquer sur le monde pour le faire passer de
l'état initial
à un état qui satisfait le but à atteindre.
Un plan est un ensemble structuré d'actions qui mène au but. Le
plan est élaboré par une partie du système appelée
générateur de plan (ou planificateur).
Idéalement, pour résoudre ces problèmes
de planification, il faut un algorithme général au
résonnement des problèmes de planification. Cependant, un tel
algorithme peut être non-existant. Nous commençons alors à
concentrer sur une simplification du problème de planification
général nommé « problème de planification
classique ».
I.2. La planification classique I.2.1. Modèle de
base
Le cadre formel de référence, relativement
auquel on définit généralement la sémantique des
représentations utilisées en planification, est celui des graphes
de transition d'états étiquetés. C'est un quadruplets G =
(S, A, E, ã) où :
· S = {s1, s2, ..., sn} est un ensemble fini et
récursivement énumérable d'états ;
· A = {a1, a2, ..., an} est un ensemble fini et
récursivement énumérable d'actions ;
· E = {e1, e2, ..., en} est un ensemble fini et
récursivement énumérable d'événements ;
· ã: S × A × E ? 2^S est une fonction de
transition entre états. Elle est définie par : si a est une
action et ã(s, a) est non vide alors a est applicable à
l'état s.
Ce système de transition d'états peut être
représenté par un graphe direct dont les noeuds sont les
états de S. Les arcs sont appelés transitions d'états.
Planifier dans ce cadre revient à trouver un chemin
dans G entre un état initial et un but [10]. Ayant un problème
spécifié par G, un état initial s0 E S, et un
sous-ensemble d'états buts Sg ? S, on cherche une séquence
d'actions (a1, a2, ..., an), telle que: an(...a2(a1(s0))..) soit un état
de Sg .
I.2.2. Représentation et langages
Pour travailler, tout algorithme de planification à
besoin d'une description de l'univers (représentation) sous une forme
facilement compréhensible. Le choix d'une représentation
adaptée aux problèmes à résoudre est un des
éléments les plus importants pour la conception d'un
système efficace; de nombreuses approches peuvent être
employés parmi [1, 10]:
La représentation dans la théorie des
ensembles : chaque état du monde est un ensemble de
propositions et chaque action est une expression spécifiant les
propositions qui doivent appartenir à l'état courant pour que
l'action puisse être exécutée, ainsi que celles qui seront
ajoutées et enlevées de l'état suite à
l'exécution de l'action ;
La représentation classique :
contrairement à la représentation
précédente, des prédicats du premier ordre et des
connecteurs logiques sont utilisés à la place des propositions
;
La représentation par variables d'états
: chaque état est représenté par un tuple de n
variables d'états valuées {x1, x2, ..., xn} et chaque action est
représentée par une fonction partielle qui permet de passer d'un
tuple à un autre tuple de variables d'états instanciées
;
Le but est de trouver un langage qui est à la fois
suffisamment expressif pour décrire une grande variété de
problèmes mais assez restrictif pour permettre à des algorithmes
efficaces d'agir. Pour cette raison plusieurs langages sont apparus comme
STRIPS, ADL mais le langage le plus
utilisé est PDDL [11].
| 
