III. La planification multi-agents
La recherche dans la planification multi-agents est
prometteuse pour des problèmes réels : d'une part, les techniques
de planification d'AI fournissent des outils puissants pour résoudre des
problèmes dans le cadre des agents singulier ; et d'une autre part, les
systèmes multi-agents, qui ont fait une grande progression au cours de
ces dernières années, sont identifiés comme technologie
principale pour aborder des problèmes complexes dans des domaines
d'application réalistes.
(1) Knowledge Query and Manipulation Language
(2) Foundations of Intelligent Physical Agents-Agent
Communication Language
En planification multi-agents (référée
aussi par planification distribuée), le domaine de planification est
réparti sur l'ensemble des agents. Chaque agent est capable de
réaliser un certain nombre d'actions: ses compétences. C'est la
mise en commun et l'ordonnancement des compétences de chaque agent, dans
le but de résoudre un problème donné, qui va permettre de
faire émerger un plan solution.
III.1. Planification et coordination
Dans de nombreux cas les dépendances entre les taches
des agents rendent une planification indépendante impossible.
C'est-à-dire, si les agents ne tiennent pas compte des
dépendances entre leurs plans, ils peuvent arrivés à des
conflits quand ils essayent d'exécuter leurs plans.
Pour résoudre leurs dépendances, les agents doivent
coordonner leurs efforts.
Clairement, un problème de planification multi-agents a
deux composants : la planification et la coordination. Le problème de
planification multi-agents peut être donc défini comme suit
[8]:
Le problème de planification multi-agents est le
problème suivant : Etant donné une description de l'état
initial, un ensemble de buts globaux, un ensemble d'agents (au moins de deux),
et pour chaque agent un ensemble de ses capacités et de ses buts
privés, trouver un plan pour chaque agent qui réalise ses buts
privés, tel que ces plans ensemble sont coordonnés et les buts
globaux sont aussi bien atteints.
|
En résumant,
|
Planification multi-agents = Planification + Coordination
|
III.2. Modèles de la planification
multi-agents
Pour distinguer les différents modèles de la
planification multi-agents, on doit référer au problème de
la planification multi-agents en tant que problème de planification
distribuée. Le terme de planification distribuée est toutefois
ambigu car il n'explicite pas ce qui est distribué. En effet, les plans
peuvent être construits de manière centralisée puis
distribués aux agents, ou bien chaque agent peut construire localement
son propre plan puis le coordonner de manière distribuée. Dans le
premier cas, seule l'exécution du plan est distribuée. En
revanche, dans le second, la synthèse de plans, le processus de
coordination ainsi que l'exécution sont réalisés de
manière complètement distribuée [1].
III.2.1. Planification centralisée :
Repose toujours sur l'existence d'un agent coordinateur. Cet agent
centralise l'ensemble des plans des agents du système et résout
les conflits potentiels entre leurs activités en introduisant des
actions de synchronisation. L'agent coordinateur peut:
· soit planifier pour l'ensemble des agents et, dans ce
cas, il doit décomposer le plan global en sous-plans synchronisés
pouvant être exécutés par les agents ;
· soit chaque agent peut planifier localement et, dans ce
cas, le rôle de l'agent coordinateur se limite à la
synchronisation des plans reçus.
III.2.2. Planification distribuée : Le
processus de planification est distribué. Deux modèles sont
envisageables dans cette approche :
Planification distribuée avec plan
centralisé : Dans ce modèle, Le but global des agents
est d'accomplir une tâche T. Cette tâche va être
décomposée en plusieurs sous-tâches non ordonnées
Tj. Après l'assignement de ces sous-tâches aux différents
agents, chaque agent du système élabore un sous-plan pour
résoudre la sous-tâche lui est assignée. En fin, une
synchronisation entre les agents arrive à élaborer un plan global
centralisé permettant de réaliser la tache T.
Décomposition Planification
Synchronisation
Entre agents
T {Ti, Tj, ..., Tk} {PTi, PTj, ..., PTk}
PT
Tàche globale
|
Ensemble de tâches
non ordonnées
|
Plans associés
|
Plan
centralisé
|
|
Planification distribuée avec plan
distribué : Dans ce modèle, le processus de
synthèse et d'exécution d'un plan multi-agents sont les deux
distribués. Deux approches sont envisageables à nouveau dans
cette approche orientée tâches et orienté
agents. La différence réside dans l'existence d'un but
global ou non.
En résumant, les différents modèles de la
planification multi-agents peuvent être résumé dans le
schéma de la figure suivante :
Planification multi-agents
Un planificateur
Plusieurs exécutants
Planification centralisée
Chaque agent
planifie et exécute
Planification distribuée
Orienté tâche
Décomposition
Orienté agent Coordination
Figure1.4 : Modèles de la planification
multi-agents
| 
