Page : 1 JFIADSMA'02 - 28-30 octobre 2002 Direction Générale Technique / Direction de la Prospective SCALA : Une approche Multi-Agent pour la Conception

Page : 1JFIADSMA'02 - 28-30 octobre 2002Direction Générale Technique / Direction de la Prospective

SCALA : SCALA : Une approche Multi-Agent pour la Une approche Multi-Agent pour la Conception de Systèmes ComplexesConception de Systèmes Complexes

Application à la Simulation de Missions AériennesApplication à la Simulation de Missions Aériennes

[email protected]

[email protected]

Irène Degirmenciyan-Cartault

Frédéric Marc


PlanPlan

Les objectifs de SCALA

SCALA : méthodologie et simulation

Un scénario d’interception aérienne

Les outils d'aide à la conception

Les apports de SCALA

Les limites et perspectives


SCALA : les objectifsSCALA : les objectifs((Système Coopératif d ’Agents Logiciel Autonomes)Système Coopératif d ’Agents Logiciel Autonomes)

• Fournir un outil de prototypage rapide de SMA intégrant une méthodologie partant des exigences fonctionnelles• Faciliter la modélisation et la conception par un langage de description de haut niveau d’abstraction• Simuler :

• différents types d’organisations• des algorithmes d’allocation de tâches• des algorithmes de coopération entre agents

• Constituer des bibliothèques de mécanismes réutilisables• Proposer des outils de visualisation du comportement du système

Outil d’aide à la conception de SMAOutil d’aide à la conception de SMA


SCALASCALA

• Définition du graphe de dépendances fonctionnelles• Définition des comportements élémentaires ou tâches• Définition des sous-graphes et buts associés• Identification des événements déclencheurs• Définition des agents• Définition des groupes d’agents

• Choix des organisations• Choix des mécanismes de coopération

Une méthodologie

Un outil de simulation


Une mission d’interceptionUne mission d’interception

Ordre de décollage

Données d’interception

Décollage

CAP

Navigation

TirTriangulation Acquisition

Dégagement

RetourReorganisation

DetectionDétection


Quelques caractéristiquesQuelques caractéristiques

• Comportements élémentaires, fonctions du système (décollage, naviguation guidée, acquisition, désignation, tir, dégagement)

• Le besoin en coopération est dirigé par les contraintes et les dépendances entre tâches (pré- et post-conditions, liens de dépendances)

• Evénements perturbateurs (apparition de menaces, défaillance d’un avion de la patrouille)

La patrouille doit se ré-organiser dynamiquement pour s'adapter à un environnement évolutif


1. Définition du graphe1. Définition du graphe

Graphe G_Retour

RETOUR

ATTERRISSAGEN

N

N

N

Graphe G_Depart_Mission

DECOLLAGE

RASSEMBLEMENT

S

2

Graphe G_Interception

LOCALISATION_RADAR TRIANGULATION2

PREGUIDAGEN

ACQUISITION

RECHERCHE IDENTIFICATIONLOCALISATION

D.O.

TIR

DEGAGEMENT

S

Graphe G_Nouvelle_menace

RECONNAISSANCE

RIPOSTE


Dépendances entre tâches (1)Dépendances entre tâches (1)

Task A Task B

Task C

Task A Task B

Task A Task B

OU

Task A Task B

Task C

Task C

Task BTask A

Dépendances simples

Precédence

ET (implicit)

Décomposition

Exclusion


Task A x

Multiplicité

Dépendances entre tâches (2)Dépendances entre tâches (2)

Task A x

N agentsou *ou group_nameou condition

With x =

Task A Task B

Synchronisation Série

Combinaison de dépendances

Task A Task BS

Task A Task B

S x


2. Description des tâches2. Description des tâches

Pré-conditions :• Tâches• Annulation• Ressources

Post-conditions :• Ressources• Evénements

LOCALISATION_RADAR TRIANGULATION2

PREGUIDAGEN

ACQUISITION

RECHERCHE IDENTIFICATIONLOCALISATION

• Compétences• Niveau de spécialisation• Cardinalité• Méthodes• Interruptibilité

D.O.

TIR

DEGAGEMENT

S


3. Association événements/sous-graphes3. Association événements/sous-graphes

Evénement Depart_Mission P=1, D=IGraphe G_DepartGraphe G_Interception

Evénement Interception P=2, D=PGraphe G_Interception

Evénement Nouvelle_Menace P=2, D=IGraphe G_Reconnaissance

Evénement Retour P=1, D=PGraphe G_Retour

• Niveau de priorité• Type de déclenchement


4. Définition des agents4. Définition des agents

Leader StrikeLeader Escorte

• Compétences • Niveau de spécialisation• Ressources• Evénements• But• Groupes d ’appartenance• Rôle courant• Rôles possibles• Protocoles de communications

Raid

Escorte

Equipier Escorte Equipier1 Strike Equipier3 StrikeEquipier2 Strike


5. Définition des groupes5. Définition des groupes

AWACS

Leader StrikeLeader EscorteLeader Sweep

Equipier Sweep Equipier Escorte Equipier1 Strike Equipier3 StrikeEquipier2 Strike

• Groupes fils• Groupe père• Type d’organisation• Type de coopération • Membres (rôle courant rôles possibles)• Evénements

Dispositif aérien

Raid

Escorte

Sweep


De l’événement au plan multi-agentDe l’événement au plan multi-agent

Sous graphe

Plan 1

Plan 2

Plan 3

Plan 4

Agent 1

Agent 2

Agent 3

Agent 4

Distribution du graphe sur les agents

Réseau de dépendances

Evénement


Le passage à la simulationLe passage à la simulation

• des événements et sous graphes associés• des agents• des groupes• des tâches et des contraintes sur leur exécution• de l'allocation des tâches et de la coopération entre agents en

fonction :– des contraintes exprimées sur le graphe de dépendances– du choix du type d'organisation et d'interaction (bibliothèques de

mécanismes prédéfinis)

Génération automatique

Implémentation des comportements élémentaires (côté applicatif)

• lois et modèles physiques (ex : modèles avions, trajectoires)• actions réponses aux événements (ex : décollage)


Processus de SimulationProcessus de Simulation

Sweep Leader

Sweep Equipier

Allocation dynamique des tâches

Raid Equipier

Raid Leader

Exécution

2

TAKE OFF

S

N

CAP N

Génération d’une instance du sous-graphe associé à l’événement

Evénement Départ_Mission

2

TAKE OFF

S

N

CAP N

GUIDED FLIGHTN

ACQUISITION T. D.

SHOT

RETRACT

S

Evénement Interception

Coordination

Sweep Leader

Sweep EquipierRaid Equipier

Raid Leader

Allocation dynamique des tâches

Execution


Les outils de modélisationLes outils de modélisation

L’éditeur de graphe SCALAPermet de :

• Concevoir facilement les graphes de dépendances• Associer les sous-graphes aux événements (les paires

événements/buts)• Construire des librairies de comportements réutilisables

Les éditeurs agents/groupesPermet de :

• Définir les agents (compétences, ressources, etc.) • Définir les groupes (rôles, type d'organisation,

type d'interaction, etc.)


Les outils SCALA (1)Les outils SCALA (1)


Les outils d'analyseLes outils d'analyse

L’outil de visualisationPermet de :

• Situer les agents dans l’environnement• Déclencher dynamiquement de nouveaux événements• Créer des nouveaux agents et groupes

Le diagramme d’activitésReprésente les activités des agents et le comportement multi-agent :

• L’évolution de la simulation• La coordination entre les agents• L’arrivée des nouveaux événements


Les outils SCALA (2)Les outils SCALA (2)

Friend1

Friend2

Friend3

Friend4

Bandit1

Bandit2

t

Guided Flight

Guided Flight Enter combat area

CAP

CAP

CAP

CAP

Guided Flight

Guided Flight

Guided Flight

Guided Flight

Enter combat area

Guided Flight

Guided Flight

Riposte

Ac

Ac

Eng

Eng

S

S

G. Flight

G. Flight

Flight


SCALA vue comme couche logicielleSCALA vue comme couche logicielle

SCALA

JACK

JAVA O1 O3O2

A1 A3A2


Les apports de SCALA pour ce type d ’applicationLes apports de SCALA pour ce type d ’application

• Une modélisation de plus haut niveau qui permet de :

• définir de nouveaux comportements au niveau modélisation

(sans recompilation)• dissocier des raisonnements et des actions (tâches)• modéliser la coordination entre avions

• Allocation dynamique des tâches :• en fonction de la situation courante• des caractéristiques et capacités des agents

• Réutilisation des comportements• Introduction de réactivité dans la simulation (création de nouvelles

menaces, réponses à des événements en cours de simulation)• Résolution de systèmes complexes, ouverts par simulation


Les limites actuelles de SCALALes limites actuelles de SCALA

• Pas de gestion du temps

• Pas de contraintes temporelles sur les tâches et buts

• Algorithme de re-organisation trop simpliste

• Problème du temps réel

• au niveau organisationnel

• au niveau de l ’exécution

• Pas de validation des plans générés


Travail en cours et perspectivesTravail en cours et perspectives

Amélioration du comportement global

Meilleure gestion des buts

Validation des plans générés

• Formalisation

Utilisation d ’une variante des automates temporisés d ’ALUR

• Planification réactive et exécution contrôlée des plans

• Existence d ’une horloge globale (actions jointes,

plans multi-agents synchronisés)

• Opérateurs de manipulation de plans

• concaténation, parallélisation, insertion

Documents

Page : 1 JFIADSMA'02 - 28-30 octobre 2002 Direction Générale Technique / Direction de la Prospective SCALA : Une approche Multi-Agent pour la Conception