Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
JEAN-FRANCOIS MORISSETTE
Algorithmes de gestion de ressources en
temps-reel : positionnement et planification lors
d’attaques aeriennes
Memoire presentea la Faculte des etudes superieures de l’Universite Lavaldans le cadre du programme de maıtrise en Informatiquepour l’obtention du grade de Maıtre es sciences (M.Sc.)
FACULTE DES SCIENCES ET DE GENIEUNIVERSITE LAVAL
QUEBEC
Novembre 2004
c©Jean-Francois Morissette, 2004
Resume
Depuis plusieurs annees, Recherche et Developpement pour la Defense Canada
(RDDC) et Lockheed Martin Canada (LMC) travaillent en collaboration afin de moder-
niser le systeme de Commande et Controle (C2) present sur une fregate. Un tel systeme
a pour but d’analyser et de gerer un flot d’informations considerable afin d’effectuer
les bonnes actions face a une situation donnee. Notre role au sein de ce projet se situe
au niveau de la prise de decision. Nous devons etudier les possibilites que peut offrir la
technologie agent a un tel systeme.
Dans ce memoire, nous proposons un modele formel d’interaction entre les differentes
ressources disponibles sur la fregate et les menaces auxquelles elle doit faire face. Nous
proposons aussi une technique de positionnement et une approche de planification afin
de maximiser les chances de survie de la fregate. Enfin, nous presentons les resultats
que nous avons obtenus au moyen de simulations.
Avant-propos
J’aimerais profiter de ces quelques lignes pour remercier les personnes qui ont
contribue a l’aboutissement de ce memoire. Je voudrais tout d’abord remercier mon
directeur de recherche, Dr. Brahim Chaib-draa, un homme extremement devoue pour
ses etudiants. Il a toujours ete present pour repondre a mes questions et me donner de
judicieux conseils. J’ai appris beaucoup lors de ces deux annees passees avec lui.
Je voudrais aussi remercier tous les etudiants et ex-etudiants du laboratoire DAMAS
avec qui j’ai travaille. Vous avez toujours su repondre a mes questions et vous avez
tous contribue a votre facon a ce travail. Je voudrais remercier plus specialement mon
collegue Etienne Bolduc qui m’a beaucoup aide lors des dernieres semaines de cette
maıtrise. Merci aussi a Abder Rezak Benaskeur (RDDC) pour son expertise qui m’a
permis de faire de ce travail, un travail de qualite.
Je voudrais egalement remercier tous mes amis qui m’ont supporte dans les mo-
ments plus difficiles. Je pense specialement a mes 2 colocs et amis : Christian (F !zZ) et
Mathieu. Vous etes des chums extraordinaires et vous pouvez considerer que vous avez
beaucoup contribue au travail present dans ce memoire. Je pense aussi a Genevieve
qui a toujours su me changer les idees et me remonter le moral dans les moments diffi-
ciles. Et je ne peux oublier Francois et Jean-Lou qui ont toujours represente une source
d’inspiration et de motivation pour moi.
Enfin, je voudrais dedier ce memoire a mes parents sans qui tout cela n’aurait pas
ete possible. Ils m’ont toujours supporte et appuye dans ce que j’ai entrepris. Pierre
et Helene, vous etes des parents extraordinaires, je vous adore et je suis extremement
reconnaissant pour tout ce que vous avez fait pour moi.
Jean-Francois Morissette
Table des matieres
1 Introduction 1
1.1 Problematique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Intervenants dans le projet NEREUS . . . . . . . . . . . . . . . . . . . 2
1.3 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Organisation du memoire . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Agents et IA dans les systemes Commande et Controle (C2) 6
2.1 Agents intelligents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Definition d’un agent . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Environnement d’un agent . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Architectures d’agents . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Planification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Espace de contingences . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Representation de plans . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 Algorithmes “a tout moment” (anytime) . . . . . . . . . . . . . 15
2.3 Systemes temps-reel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2 Structure d’un systeme temps-reel . . . . . . . . . . . . . . . . . 18
2.3.3 Categories de systeme temps-reel . . . . . . . . . . . . . . . . . 18
2.4 Systemes de Commande et Controle (C2) . . . . . . . . . . . . . . . . . 20
2.4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.2 Boucle OODA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.3 Un probleme de C2 : l’allocation de ressources sur des menaces . 21
2.5 Travaux sur l’automatisation des systemes de commande et controle . . 24
2.5.1 TNO Physics and Electronics Laboratory (TNO-FEL) . . . . . 25
2.5.2 Defense Advanced Research Projects Agency (DARPA) . . . . . 25
2.5.3 Stanford Research Institute International (SRI) . . . . . . . . . 26
2.5.4 Defence Science and Technology Organisation (DSTO) . . . . . 27
2.5.5 Autres entreprises . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Travaux anterieurs sur NEREUS . . . . . . . . . . . . . . . . . . . . . 28
2.6.1 Division en secteurs de defense et apprentissage . . . . . . . . . 28
v
2.6.2 Positionnement bayesien . . . . . . . . . . . . . . . . . . . . . . 29
2.6.3 Planification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.7 Sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Simulation et methode Monte-Carlo 31
3.1 Notions de simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.1 Definition de la simulation . . . . . . . . . . . . . . . . . . . . . 32
3.1.2 Processus complet de simulation . . . . . . . . . . . . . . . . . . 32
3.1.3 Taxonomie des systemes dynamiques . . . . . . . . . . . . . . . 32
3.2 Simulation par evenements discrets . . . . . . . . . . . . . . . . . . . . 35
3.2.1 Elements d’un simulateur par evenements discrets . . . . . . . . 36
3.2.2 Deroulement d’une simulation par evenements discrets . . . . . 37
3.2.3 Analyse des resultats . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.4 Exemple : simulation d’une file d’attente . . . . . . . . . . . . . 39
3.3 Methode Monte-Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Description de la methode . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Exemple d’application de la methode Monte-Carlo : Calcul d’une
integrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.3 Autre exemple : Estimation de la valeur de π . . . . . . . . . . 43
3.4 Simulateur de defense navale (NDS) . . . . . . . . . . . . . . . . . . . . 45
3.4.1 Fonctionnalites en mode demonstration . . . . . . . . . . . . . . 46
3.4.2 Representation du modele fregate-ressources . . . . . . . . . . . 48
3.4.3 Evolution de la gestion du temps et des evenements . . . . . . . 48
3.4.4 Deroulement d’une simulation . . . . . . . . . . . . . . . . . . . 50
3.4.5 Utilitaire de tests et compilation des resultats . . . . . . . . . . 52
3.5 Utilisation de la methode Monte-Carlo dans le simulateur NDS . . . . . 54
3.6 Sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4 Positionnement de la fregate 57
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Modele pour reduire la complexite de calcul lors du positionnement . . 58
4.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.2.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2.3 Generateur de combinaisons menaces-secteurs
(GenTSC ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3 Heuristique PNH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1 Module d’apprentissage . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.2 Discussion sur les resultats du module d’apprentissage . . . . . 65
4.3.3 Choix de la metrique pour l’efficacite des secteurs . . . . . . . . 66
4.3.4 Calcul de l’heuristique PNH . . . . . . . . . . . . . . . . . . . . 67
4.4 Choix final de la position . . . . . . . . . . . . . . . . . . . . . . . . . . 68
vi
4.4.1 Methode “Final Positioning” (PosFin) . . . . . . . . . . . . . . 69
4.4.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4.3 Avantages de la methode PosFin . . . . . . . . . . . . . . . . . 70
4.5 Synthese de la methode de positionnement . . . . . . . . . . . . . . . . 73
4.5.1 Algorithme complet . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.5.2 Analyse de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . 73
4.6 Experimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.6.1 Banc de tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.6.2 Resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.6.3 Analyse des resultats . . . . . . . . . . . . . . . . . . . . . . . . 76
4.7 Travaux futurs pour le positionnement . . . . . . . . . . . . . . . . . . 80
4.7.1 Limitation des algorithmes de positionnement . . . . . . . . . . 80
4.7.2 Ameliorations possibles . . . . . . . . . . . . . . . . . . . . . . . 82
4.8 Sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5 Planification des actions de defense 84
5.1 Objectifs specifiques a atteindre . . . . . . . . . . . . . . . . . . . . . . 84
5.2 Approche Diviser Pour Regner (DPR) . . . . . . . . . . . . . . . . . . 85
5.2.1 Definition de l’approche DPR . . . . . . . . . . . . . . . . . . . 86
5.2.2 Structure d’un algorithme DPR . . . . . . . . . . . . . . . . . . 86
5.2.3 Analyse d’un algorithme DPR general . . . . . . . . . . . . . . 86
5.2.4 Exemple d’algorithme DPR : Tri par fusion . . . . . . . . . . . 87
5.3 Application de DPR a NEREUS . . . . . . . . . . . . . . . . . . . . . . 89
5.3.1 Determination du seuil et des sous-ensembles . . . . . . . . . . . 90
5.3.2 Planification pour les sous-groupes . . . . . . . . . . . . . . . . 91
5.3.3 Solution globale . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.4 Algorithme DPR complet . . . . . . . . . . . . . . . . . . . . . 92
5.3.5 Analyse de l’algorithme DeliberatifDPR . . . . . . . . . . . . . 93
5.3.6 Avantages d’une telle approche . . . . . . . . . . . . . . . . . . 95
5.4 Proposition d’une strategie de replanification . . . . . . . . . . . . . . . 97
5.4.1 Modifications possibles des sous-groupes . . . . . . . . . . . . . 97
5.4.2 Divers cas possibles a traiter . . . . . . . . . . . . . . . . . . . . 99
5.4.3 Traitement des divers cas possibles . . . . . . . . . . . . . . . . 100
5.4.4 Retour sur la classification des contingences . . . . . . . . . . . 101
5.5 Experimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.5.1 Hypotheses sur le modele . . . . . . . . . . . . . . . . . . . . . . 102
5.5.2 Banc de tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.5.3 Resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.5.4 Analyse des resultats . . . . . . . . . . . . . . . . . . . . . . . . 104
5.6 Ameliorations possibles . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
vii
5.6.1 Eliminer l’hypothese simplificatrice . . . . . . . . . . . . . . . . 107
5.6.2 Agir tout en positionnant . . . . . . . . . . . . . . . . . . . . . 108
5.6.3 Ameliorer la replanification . . . . . . . . . . . . . . . . . . . . 108
5.7 Travaux futurs sur la planification . . . . . . . . . . . . . . . . . . . . . 108
5.7.1 Diminution du seuil pour l’approche DPR . . . . . . . . . . . . 109
5.7.2 Rendre l’approche DPR a tout moment (anytime) . . . . . . . . 109
5.7.3 Interaction entre les 3 planificateurs . . . . . . . . . . . . . . . . 110
5.7.4 Planificateur de haut niveau . . . . . . . . . . . . . . . . . . . . 110
5.7.5 Trouver la solution optimale . . . . . . . . . . . . . . . . . . . . 111
5.8 Sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6 Conclusion 112
6.1 Retour sur les objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.2 Travaux futurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.2.1 Rendre le modele plus realiste . . . . . . . . . . . . . . . . . . . 114
6.2.2 Probleme d’assignation de ressources sur des menaces . . . . . . 114
6.2.3 Interaction avec le commandant . . . . . . . . . . . . . . . . . . 115
A Modele de simulation pour le projet NEREUS 119
A.1 Explications des differentes ressources a gerer . . . . . . . . . . . . . . 119
A.2 Doctrines a respecter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
A.3 Specifications des ressources . . . . . . . . . . . . . . . . . . . . . . . . 121
A.4 Secteurs engendres par les limitations des ressources . . . . . . . . . . . 123
A.5 Specifications de la fregate . . . . . . . . . . . . . . . . . . . . . . . . . 124
A.6 Specifications des menaces ennemies . . . . . . . . . . . . . . . . . . . . 124
Liste des tableaux
4.1 Representation de la combinaison menaces-secteurs quelconque a atteindre. 61
4.2 Valeur des variables pour l’exemple de la figure 4.3. . . . . . . . . . . . 62
4.3 Ressources disponibles dans chacun des secteurs. . . . . . . . . . . . . . 64
4.4 Resultats du module d’apprentissage. . . . . . . . . . . . . . . . . . . . 65
4.5 Exemple pour comparer 2 metriques d’evaluation. . . . . . . . . . . . . 67
4.6 Intervalle de rotation pour chaque menace. . . . . . . . . . . . . . . . . 69
4.7 Analyse de l’algorithme FRIGATE POSITIONING. . . . . . . . . . . . 74
5.1 Exemple de rotation choisie en fonction de la prochaine rotation. . . . . 96
A.1 Specifications des ressources de la fregate. . . . . . . . . . . . . . . . . 122
A.2 Ressources disponibles dans chacun des secteurs. . . . . . . . . . . . . . 123
Table des figures
2.1 Classification des contingences. . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Exemple de plan conditionnel. . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Qualite d’un algorithme standard et d’un algorithme a tout moment. . 16
2.4 Structure d’un systeme temps-reel. . . . . . . . . . . . . . . . . . . . . 18
2.5 Categories de systemes temps-reel. . . . . . . . . . . . . . . . . . . . . 19
2.6 Exemple de 3 contraintes temps-reel. . . . . . . . . . . . . . . . . . . . 19
2.7 La boucle OODA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1 Processus complet de simulation . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Caracteristiques d’un systeme . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Deroulement d’une simulation par evenements discrets . . . . . . . . . 36
3.4 Schema qui illustre la methode de Monte-Carlo . . . . . . . . . . . . . 41
3.5 Calcul d’une integrale par la methode de Monte-Carlo . . . . . . . . . . 42
3.6 Construction de la figure pour evaluer π . . . . . . . . . . . . . . . . . 44
3.7 Evaluation de la valeur de π . . . . . . . . . . . . . . . . . . . . . . . . 44
3.8 Capture d’ecran du simulateur (1 de 4) . . . . . . . . . . . . . . . . . . 47
3.9 Capture d’ecran du simulateur (2 de 4) . . . . . . . . . . . . . . . . . . 47
3.10 Capture d’ecran du simulateur (3 de 4) . . . . . . . . . . . . . . . . . . 49
3.11 Capture d’ecran du simulateur (4 de 4) . . . . . . . . . . . . . . . . . . 49
3.12 Probleme avec un intervalle de 200ms entre les tours . . . . . . . . . . 50
3.13 Probleme avec un intervalle de 80ms entre les tours . . . . . . . . . . . 50
3.14 Lois normales gerant l’apparition des menaces. . . . . . . . . . . . . . . 51
3.15 Loi normale gerant la detection des menaces. . . . . . . . . . . . . . . . 52
3.16 Utilitaire pour faire des bancs de tests . . . . . . . . . . . . . . . . . . 53
3.17 Calcul de la probabilite de survie avec des simulations . . . . . . . . . . 55
3.18 Calcul du pourcentage de menaces detruites avec des simulations. . . . 55
4.1 Exemple de 2 combinaisons menaces-secteurs . . . . . . . . . . . . . . . 59
4.2 Rotation pour amener la menace dans le secteur 2. . . . . . . . . . . . 61
4.3 Exemple de combinaison a atteindre et rotation de ∆min. . . . . . . . . 62
4.4 Secteurs engendres par la restriction des ressources. . . . . . . . . . . . 64
4.5 Graphique des resultats du module d’apprentissage. . . . . . . . . . . . 65
4.6 Intervalle des rotations possibles pour la fregate. . . . . . . . . . . . . . 72
x
4.7 Efficacite des algorithmes de mouvement avec le planificateur reactif. . 77
4.8 Efficacite des algorithmes de mouvement avec le planificateur deliberatif. 77
4.9 Efficacite des algorithmes de mouvement avec le planificateur deliberatif
avec amelioration tabu. . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.10 Efficacite des algorithmes de mouvement (moyenne des trois planificateurs). 78
4.11 Temps utilise par les algorithmes de mouvement pour retourner une
reponse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.12 Exemple de cas ou le mouvement PNH ne serait pas optimal. . . . . . . 81
5.1 Exemple de fonctionnement du tri par fusion. . . . . . . . . . . . . . . 89
5.2 Comparaison des planifications standard et DPR a tout moment. . . . 97
5.3 Classification des contingences. . . . . . . . . . . . . . . . . . . . . . . 101
5.4 Comparaison des algorithmes standard avec les algorithmes DPR. . . . 105
5.5 Efficacite de la replanification. . . . . . . . . . . . . . . . . . . . . . . . 105
5.6 Amelioration de la recherche tabu. . . . . . . . . . . . . . . . . . . . . 106
5.7 Temps utilise par les algorithmes de planification pour retourner une
reponse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
A.1 Secteurs engendres par la restriction des ressources. . . . . . . . . . . . 123
Chapitre 1
Introduction
De nos jours, la technologie agent, domaine de l’intelligence artificielle, devient de
plus en plus populaire et contribue a resoudre divers problemes provenant de differents
domaines. La technologie agent vise a concevoir des entites autonomes capables d’inter-
agir, raisonner, apprendre, etc. Dans ce memoire, les agents sont consideres comme des
systemes informatiques autonomes, situes dans un environnement et agissant de maniere
flexible (i.e capables de repondre a temps, d’interagir avec les autres agents et d’avoir
un comportement rationnel) pour atteindre leurs objectifs. Pour cela, les agents doivent
percevoir leur environnement et planifier les actions qu’il convient d’entreprendre afin
d’atteindre leurs buts.
Lorsque l’on concoit des agents devant agir dans un environnement tres complexe,
l’utilisation de la simulation permet souvent de valider les facons de raisonner de l’agent.
En effet, lors de la conception d’un agent devant agir dans un environnement com-
plexe, l’utilisation d’un modele simplifie de cet environnement est souvent de mise.
L’idee est de faire des hypotheses simplificatrices sur l’environnement pour permettre
un developpement plus facile de l’agent. On tentera par la suite de retirer certaines
hypotheses lorsque cela est possible.
Le present memoire s’interesse particulierement a la technologie agent et aux tech-
niques d’intelligence artificielle pouvant etre utilisees par les agents. Ces differentes
techniques sont validees au moyen de simulations sur un modele simplifie de l’environ-
nement reel. Les differentes techniques envisagees ici doivent respecter des contraintes
temps-reel presentes dans l’environnement afin d’assurer un comportement de bonne
qualite des agents.
Chapitre 1. Introduction 2
1.1 Problematique
Les environnements maritimes sont connus pour etre des environnements tres com-
plexes. Avec l’amelioration continuelle de la technologie, il devient de plus en plus
difficile, lors d’une guerre navale, de prendre les bonnes decisions. En effet, du au tres
grand flot de donnees a traiter, l’etre humain peut parfois avoir de la difficulte a bien
traiter ces donnees afin de prendre les bonnes decisions. C’est le cas, entre autres, pour
le commandant d’une fregate qui doit se defendre face a une vague de menaces ennemies
qui l’attaquent.
Devant une situation d’attaque, le temps de reponse doit etre tres court, habituel-
lement moins de deux minutes. Il est donc primordial de donner une reponse rapide.
Ainsi, il peut etre tres difficile pour le commandant d’une fregate de prendre la bonne
decision en raison du peu de temps dont il dispose pour analyser la situation et du
stress que cette situation peut engendrer. Dans de telles conditions, il pourrait arriver
que le commandant prenne la mauvaise decision, une mauvaise decision qui pourrait
etre fatale pour la fregate et son equipage.
Le projet NEREUS (Naval Environment for Resource Engagement in Unpredictable
Situation) vise a etudier les systemes agents et multi-agents (expliques au prochain
chapitre) ainsi que diverses techniques d’intelligence artificielle afin d’implementer un
systeme d’aide a la decision dans le but de gerer efficacement les ressources a bord
d’une fregate canadienne de classe HALIFAX. Un tel systeme d’aide a la decision peut
considerablement faciliter la tache au commandant d’une fregate. En effet, il est beau-
coup plus facile pour le commandant de valider un plan de defense qui lui est propose
plutot que d’avoir a construire ce plan.
1.2 Intervenants dans le projet NEREUS
Le projet NEREUS est fait en collaboration avec differents intervenants. Chaque
intervenant apporte son expertise ce qui donne beaucoup de credibilite au projet. Voici
donc les differents intervenants.
Laboratoire DAMAS
Le laboratoire DAMAS (Dialogue, Apprentissage et Multi-AgentS) est un groupe
de recherche supervise par Dr. Brahim Chaib-draa, professeur au departement d’infor-
Chapitre 1. Introduction 3
matique et de genie logiciel de l’Universite Laval. Les champs d’interets du laboratoire
DAMAS sont les suivants :
1. Dialogues et communication inter-agents.
2. Negociation et coordination entre agents.
3. Environnements multi-agents temps reel.
4. Apprentissage dans les environnements multi-agents.
5. Cooperation et competition entre agents.
Lockheed Martin Canada (LMC)
Lockheed Martin Canada est une entreprise tres diversifiee qui travaille principale-
ment dans la recherche, le design, la conception et l’integration de produits possedant
une technologie tres evoluee. LMC est un leader dans les technologies avancees qui ap-
portent des solutions aux problemes complexes. Il excelle dans la gestion et l’integration
des systemes. A ce jour, LMC emploie plus de 600 personnes a travers la Canada. Son
representant sur le projet NEREUS, Dr. Dale Blodgett, a contribue a concevoir le
modele simplifie de la fregate que nous presentons en annexe.
Recherche et Developpement pour la Defense Canada (RDDC)
RDDC est une agence relevant du ministere de la Defense nationale (MDN) et qui
fournit un service scientifique et technologique de pointe aux Forces canadiennes. RDDC
fournit un leadership de recherche et developpement sur les plans national et internatio-
nal en donnant aux Forces canadiennes des technologies pertinentes et opportunes tout
en offrant d’attrayantes possibilites de collaboration aux autres ministeres, au secteur
prive, au monde universitaire et aux differents allies de par le monde.
RDDC exploite six centres de recherches au Canada, dont chacun a une combinaison
unique d’expertise et d’installations qui lui permettent de se charger d’activites de
recherche-developpement de calibre mondial. RDDC est bien positionnee pour offrir
une recherche et developpement novatrice, plongeant loin dans l’avenir, dans tous les
domaines des technologies de defense.
Dans le cadre du projet NEREUS, nous avons travaille en etroite collaboration avec
le centre de recherche de Valcartier. Une personne ressource est affectee au projet, Dr.
Abder Rezak Benaskeur. Son role est de s’assurer que les recherches n’aillent pas a
l’encontre des regles etablies dans le milieu militaire canadien. Il a de plus contribue
a raffiner et a ameliorer le modele de la fregate lorsque certains problemes survenaient
avec ce modele.
Chapitre 1. Introduction 4
Conseil de Recherche en Sciences Naturelles et en Genie du Canada
(CRSNG)
Le Conseil de recherches en sciences naturelles et en genie du Canada (CRSNG) est
l’organisme national charge d’effectuer des investissements strategiques dans la capacite
scientifique et technologique du Canada. Le CRSNG appuie, d’une part, la recherche
fondamentale universitaire au moyen de subventions a la decouverte et, d’autre part,
des projets de recherche dans le cadre de partenariats entre les universites, les gouver-
nements et le secteur prive, et favorise en outre la formation de pointe de personnel
hautement qualifie. Le projet NEREUS est subventionne en partie par le CRSNG.
1.3 Motivations
Les principales motivations qui nous ont incites a effectuer ce travail sont :
1. Une problematique issue du monde reel dans un environnement tres complexe et
ayant des contraintes temps-reel fortes (hard real-time constraints).
2. La possibilite d’etudier differentes techniques d’intelligence artificielle pouvant
etre utilisees dans cet environnement complexe.
3. L’absence d’un modele formel pour l’interaction entre les menaces et les ressources
disponibles au niveau d’une fregate.
4. L’absence de justifications permettant de valider les resultats obtenus a l’aide de
la simulation.
1.4 Objectifs
L’objectif de la presente maıtrise est de specifier, developper et valider un systeme
d’aide a la decision pour la gestion de ressources sur une fregate canadienne de type
Halifax. Ce systeme d’aide a la decision se devra de respecter les contraintes des systemes
temps-reel et aura comme objectif de maximiser les chances de survie des fregates. Dans
ce contexte, les objectifs specifiques de la presente maıtrise sont :
1. D’etudier les differentes architectures d’agents.
2. D’etudier les systemes temps-reel, en particulier les systemes de commande et
controle (C2).
Chapitre 1. Introduction 5
3. De valider la plate-forme de simulation (NDS), developpee prealablement sur le
projet NEREUS, afin de s’assurer qu’elle respecte bien le modele de simulation
presente en annexe.
4. D’etudier la simulation d’un point de vue theorique afin de valider les resultats
obtenus via le NDS.
5. De developper un modele formel d’interaction entre les ressources disponibles et
les menaces presentes dans l’environnement.
6. De developper une technique de positionnement de la fregate afin de maximiser
l’utilisation des ressources.
7. De developper une approche de planification qui permet une gestion efficace des
ressources afin de maximiser les chances de survie de la fregate.
1.5 Organisation du memoire
Ce memoire est organise comme suit. Tout d’abord, le chapitre 2 presente les agents
intelligents, les systemes temps-reel ainsi que les systemes de commande et controle.
La chapitre 3 introduit la simulation et les facons de valider divers concepts avec la
simulation. Ensuite, le chapitre 4 propose une technique pour positionner la fregate
efficacement en cas d’attaques aeriennes. Par apres, le chapitre 5 propose une approche
pour la construction d’un plan de defense en cas d’attaques aeriennes. Enfin, le chapitre
6 conclut ce memoire et propose quelques avenues possibles pour la suite du projet. Il
convient de noter ici que le nom de certaines methodes proposees est donne en anglais
car ces methodes ont deja ete publiees dans une conference au moment de la redaction
du memoire. Elles sont donc donnees en anglais, dans ce memoire, afin d’etre conforme
a ce que nous avons deja propose.
Chapitre 2
Agents et IA dans les systemes
Commande et Controle (C2)
Maintenant que nous avons explique en detail dans le chapitre precedent ce qu’est
le projet NEREUS, nous expliquons dans celui-ci la theorie qui sous-tend un tel projet.
Nous commencons par expliquer ce qu’est un agent et nous donnons diverses tech-
niques d’intelligence artificielle qui peuvent etre utilisees par les agents. Par la suite, les
systemes temps-reel et les systeme de Commande et Controle (C2) sont expliques en
detail. Nous donnons aussi une liste de groupes de recherche travaillant sur le C2, tout
en detaillant leurs projets de recherche. Enfin, nous expliquons en details les travaux
anterieurs effectues sur le projet NEREUS.
2.1 Agents intelligents
Afin de permettre au lecteur de mieux comprendre le concept d’“agent”, nous don-
nons ici une definition de ce qu’est un agent. Nous donnons aussi les caracteristiques
d’un environnement dans lequel peut se retrouver un agent.
2.1.1 Definition d’un agent
Dans le domaine de l’intelligence artificielle, on parle souvent du concept d’“agent”.
Cependant, les chercheurs de ce domaine ont toujours eu de la difficulte a s’entendre
sur ce qu’est vraiment un agent. La definition suivante, proposee par Jennings et al.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 7
(1998), est une definition qui semble satisfaire la plupart des chercheurs du domaine :
Un agent est un systeme informatique, situe dans un environnement,
qui agit de facon autonome et flexible pour atteindre les objectifs pour
lesquels il a ete concu.
Dans cette definition, nous retrouvons trois concepts cles qui se doivent d’etre
presents lorsque nous parlons d’agents intelligents :
1. Autonome : L’agent doit pouvoir prendre des initiatives et agir sans l’intervention
directe d’un humain (ou d’un autre agent). Il a le controle de ses actions et de
son etat interne.
2. Situe : L’agent peut recevoir des informations de l’environnement au moyen de
capteurs. Il peut aussi effectuer des actions susceptibles de modifier l’environne-
ment dans lequel il se trouve.
3. Flexible : Par flexible, on entend que l’agent est :
(a) Capable de repondre a temps : il peut percevoir son environnement et repon-
dre rapidement aux changements qui s’y produisent.
(b) Proactif : il est capable d’avoir un comportement opportuniste, dirige par ses
buts ou sa fonction d’utilite, et prendre des initiatives au moment approprie.
(c) Social : il est capable d’interagir avec les autres agents presents dans l’envi-
ronnement afin de completer ses taches ou aider les autres a completer les
leurs.
Dans le meme ordre d’idee, nous pouvons decrire un agent et l’environnement dans
lequel il evolue a l’aide de la description mise de l’avant par Russell et Norvig (2003)
et faisant intervenir la performance, l’environnement, les effecteurs et les senseurs. Les
auteurs l’ont appele PEAS (Performance, Environment, Actuators, Sensors). Cette des-
cription comporte les 4 elements suivants :
1. La mesure de performance : l’agent possede une fonction d’evaluation qui permet
de mesurer l’efficacite d’une action qu’il pourrait poser. Cette mesure de perfor-
mance est utilisee afin de choisir la meilleure action possible selon une certaine
situation.
2. L’environnement : les specifications de l’environnement dans lequel l’agent evolue.
Les caracteristiques d’un environnement sont decrites dans la section suivante.
3. Les effecteurs : les effecteurs sont utilises par l’agent pour modifier l’environne-
ment. Ce sont les effecteurs qui posent les actions sur l’environnement.
4. Les senseurs : les senseurs sont utilises par l’agent pour observer l’environnement.
Les entrees d’information se font via les senseurs.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 8
2.1.2 Environnement d’un agent
On ne peut specifier convenablement un agent sans bien specifier l’environnement
dans lequel il evolue. Selon Russell et Norvig (2003), voici les caracteristiques qui doi-
vent etre determinees pour bien specifier un environnement :
Completement observable vs. partiellement observable
Un environnement est completement observable lorsqu’un agent a une vue complete
de l’environnement. Lorsque l’agent a une vue incomplete de l’environnement ou qu’il
y a certaines informations incertaines, on dit que l’environnement est partiellement
observable.
Deterministe vs. stochastique
Lorsque les actions d’un agent ont un seul effet possible, on dit que l’environnement
est deterministe. Autrement dit, l’agent connaıt a l’avance le resultat des actions. Un
environnement est dit stochastique s’il y a plusieurs consequences possibles pour une
action.
Statique vs. dynamique
Un environnement statique est un environnement qui change seulement sous l’in-
fluence des actions d’un agent. Lorsque l’agent ne fait rien, l’environnement ne change
pas. Un environnement dynamique peut changer a tout moment du a des composantes,
autres que l’agent, presentes dans l’environnement. Un jeu d’echec est un exemple d’en-
vironnement statique alors qu’un environnement naval comme celui du projet NEREUS
est un environnement dynamique.
Discret vs. continu
Dans un environnement discret, le temps, les actions et les perceptions sont denom-
brables et fixes. Dans un environnement continu, les actions et les perceptions ne
peuvent etre discretisees. L’environnement du projet NEREUS est continu. En effet,
le temps est continu et les actions que peut entreprendre la fregate ne peuvent etre
discretisees. Par exemple, une rotation de la fregate peut prendre une valeur dans l’in-
tervalle [−180, 180], ce qui est continu et non discret.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 9
2.1.3 Architectures d’agents
Il existe differents types d’agents. Pour resoudre une problematique, on se doit de
choisir le type d’agent qui convient le mieux aux besoins du probleme. Certains agents
sont utilises afin de donner une reponse rapide (reactifs) alors que d’autres sont utilises
pour donner une reponse de bonne qualite (deliberatifs). Selon Russell et Norvig (2003)
et Wooldridge (2002), il existe deux types d’agents reactifs et deux types d’agents
deliberatifs :
1. Reactifs
(a) Agents a reflexes simples
(b) Agents conservant une trace du monde
2. Deliberatifs
(a) Agents ayant des buts
(b) Agents utilisant une fonction d’utilite
Agents a reflexes simples
Ce type d’agent agit uniquement sur les perceptions courantes qu’il a de l’environne-
ment. Il utilise un ensemble de regles predefinies pour choisir l’action a entreprendre. Ces
regles sont du type SI condition ALORS action. Ce type de comportement retourne
tres rapidement l’action a executer mais cette action n’est souvent pas la meilleure
action que pourrait executer l’agent.
Agents reactifs conservant une trace du monde
Ce type d’agent conserve en memoire les informations sur le monde ainsi que les
actions qu’il a executees precedemment. Cette information supplementaire permet a
l’agent de se faire une meilleure representation du monde dans lequel il evolue. En effet,
il ne possede pas seulement les observations du moment present mais bien une evolution
du monde jusqu’au moment present. Tout comme les agents a reflexes simples, ce type
d’agent est reactif et il fonctionne donc selon des regles predefinies.
Agents ayant des buts
Ce type d’agent possede des buts precis qu’il voudrait atteindre. Ce sont ces buts qui
dictent le comportement de l’agent car ce dernier executera les actions necessaires a l’at-
teinte de ses buts. Contrairement aux agents reactifs, les agents deliberatifs raisonnent
sur le futur. Ainsi, ils peuvent prevoir a l’avance certaines actions a executer.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 10
Lorsque cela est possible, un agent ayant des buts peut executer une simple action
pour atteindre un but. Lorsque cela n’est pas possible, il doit recourir a des methodes
de planification afin de prevoir une sequence d’actions qui le meneront au but vise. Des
methodes de planification sont expliquees a la section 2.2 qui suit.
Agents utilisant une fonction d’utilite
Il peut souvent arriver que les buts ne sont pas un bon moyen de dicter le com-
portement d’un agent. Par exemple, sur le projet NEREUS, si le but de l’agent est de
detruire une menace qui l’attaque, plusieurs comportements seront possibles (plusieurs
actions de defense possibles). Or, dans une telle situation, il faut avoir un moyen de
mesurer quel comportement est le meilleur. Les buts ne sont qu’un moyen de determiner
les etats ou l’agent est satisfait.
Un agent utilisant une fonction d’utilite est un agent qui peut mesurer son degre de
satisfaction dans un certain etat. Si l’on reprend l’exemple precedent, plusieurs actions
sont possibles pour detruire une menace qui attaque la fregate. Or, la meilleure action
sera celle qui maximise les chances de detruire cette menace. La probabilite de detruire
une menace serait donc la fonction d’utilite dans cet exemple.
La fonction d’utilite est une fonction qui attribue une valeur numerique a l’etat
dans lequel l’agent se trouve et va se retrouver. Il convient de noter ici que dans un
environnement stochastique, l’agent ne peut pas etre certain de l’effet d’une action sur
l’environnement. Il devient donc difficile pour l’agent de calculer sa fonction d’utilite
(ou mesure de performance) car il n’est pas certain de la consequence de l’action. Il peut
arriver cependant que l’agent sache la liste des diverses consequences possibles d’une
action (avec les probabilites qu’elles surviennent). Dans un tel cas, la fonction d’utilite
de l’agent est l’esperance mathematique de l’utilite de cette action. Autrement dit,
l’utilite totale est calculee en fonction de l’utilite de chacune des consequences possibles
en tenant compte de la probabilite que ces consequences surviennent.
Par exemple, supposons qu’un agent execute une action ou les consequences possibles
sont les suivantes :
Consequence Probabilite Utilite
A 80% 10
B 20% 5
Le calcul de l’utilite de cette action se fait comme suit :
U = (0, 8)(10) + (0, 2)(5) = 8 + 1 = 9
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 11
C’est ce type d’agent (utilisant une fonction d’utilite) qui est utilise pour le projet
NEREUS. Etant un agent deliberatif, il raisonne sur les actions a poser dans le futur.
Il se doit donc de prevoir a l’avance les actions a effectuer. De plus, l’environnement du
projet NEREUS etant stochastique, l’agent se devra de composer avec des situations
imprevues. Pour ce faire, il devra recourir a diverses methodes de planification utilisees
en intelligence artificielle. Dans la section qui suit, nous proposons quelques methodes
de planification qui pourraient etre utiles pour ce type d’agent.
2.2 Planification
Etant une entite autonome, un agent doit decider des actions qu’il convient d’en-
treprendre afin d’atteindre le ou les buts fixes pour cet agent. Le processus par lequel
passe l’agent pour choisir ses actions est la planification, un sous-domaine de l’intel-
ligence artificielle permettant de repondre a la question : Que doit faire l’agent ? Le
processus de planification a donc pour but, face a une certaine situation, de :
1. Choisir les actions a executer.
2. Ordonnancer ces actions.
3. Evaluer le moment et les conditions d’execution de chaque action.
2.2.1 Espace de contingences
Tout au long de l’execution de son plan, un agent se devra de composer avec
differents evenements imprevus, hors de son controle, qui sont susceptibles d’influen-
cer ses activites. De tels evenements sont nommes contingences. En d’autres mots, une
contingence represente un evenement imprevu pour lequel il n’y a pas d’action planifiee.
L’espace de contingences represente donc l’ensemble des contingences pour un champ
d’application.
Selon l’application, l’espace de contingences peut etre tres grand, voire infini. Il
existe plusieurs facons pour un agent de traiter une contingence. C’est pourquoi, nous
divisons les contingences en quatre categories :
1. Contingence a laquelle l’agent doit faire face et qui est representee dans un plan
conditionnel (voir section 2.2.2) contenant toutes les eventualites possibles.
2. Contingence pour laquelle l’agent possede une solution immediate.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 12
3. Contingence pour laquelle l’agent ne possede pas de solution immediate mais a le
temps de trouver une nouvelle solution contenant cette contingence.
4. Contingence ignoree par l’agent et non traitee par ce dernier.
L’emploi de cette classification est etroitement lie au fait qu’un agent possede des
ressources limitees. Des lors, seulement un faible nombre de contingences peuvent etre
considerees dans un plan conditionnel complet (explique a la section suivante) qui tient
compte de toutes les eventualites. Les contraintes temporelles et les ressources limitees
d’un agent n’autorisent pas le traitement complet d’un grand nombre de contingences.
Cependant, un agent peut preparer a l’avance des solutions pour certaines contin-
gences. Ces solutions sont dites reactives car elles ne sont pas produites au moment ou
la contingence survient. Le temps de reponse d’une solution reactive est tres rapide.
Cependant, il peut arriver qu’une solution reactive ne soit pas de grande qualite.
Bien entendu, dans le cas ou le temps le permet, l’agent peut proceder a une re-
planification de ses actions afin d’inclure dans son plan la contingence. Ce processus
consiste a modifier le plan existant afin de l’adapter a la nouvelle situation ou encore a
refaire le plan au complet.
Enfin, il peut arriver que l’agent ignore completement une contingence. Un agent
peut ignorer une contingence si :
1. Cette derniere n’affecte pas ses actions et ses performances.
2. Aucune solution n’est possible pour traiter cette contingence.
3. Cette contingence est peu importante et peut etre traitee plus tard.
Très urgentPeu important
Rien faire Replanifier Réagir Plan conditionnel
Fig. 2.1 – Classification des contingences.
La figure 2.1 montre une echelle lineaire pour representer l’espace de contingences
que nous venons d’expliquer (Ash et Dabija, 2000). Tel qu’explique ci-haut, les contin-
gences peuvent etre regroupees selon leur importance a etre traitees par l’agent. Cette
echelle est tres utilisee pour faire de la planification et replanification dans les systemes
temps-reel expliques a la section 2.3.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 13
2.2.2 Representation de plans
Le plan d’un agent peut etre represente sous differentes formes. Par exemple, un
plan pourrait simplement etre une liste d’actions a executer. L’agent pourrait executer
les actions du plan une a la suite de l’autre sans se soucier du moment ou commence et
ou se termine chaque action. Une telle representation peut etre utilisee lorsque l’ordre
des actions est important mais le moment ou elles sont executees ne l’est pas.
Or, les agents evoluant dans des environnements tres souvent stochastiques, l’utili-
sation de plans conditionnels est souvent de mise. Un plan conditionnel est represente
sous forme d’arbre. Nous allons illustrer la representation d’un plan conditionnel a l’aide
d’un exemple de plan qui pourrait etre utilise pour le projet NEREUS.
Supposons que la fregate fait face a 2 menaces et doit se defendre. La figure 2.2
illustre un plan de defense possible. Le plan de defense fonctionne comme suit. On
assigne un SAM sur le menace 1. Si le SAM ne reussit pas, on assigne le CIWS sur la
menace 1. Si le CIWS ne reussit pas, on evalue les dommages sur la fregate. Si la fregate
a reussit a se defendre ou a survecu a la menace 1, on assigne le CIWS a la menace 2.
Si ce dernier ne reussit pas, on evalue les dommages sur la fregate. Ce plan est donc un
plan conditionnel puisqu’il attend de voir le resultat des actions avant d’entreprendre
la prochaine action. De plus, le choix de la prochaine action du plan depend du resultat
de l’action precedente.
On utilise un plan conditionnel car on ne peut prevoir le resultat des actions. En
effet, il se peut qu’une action de defense ne reussisse pas. Dans un tel cas, la fregate se
doit d’avoir une action de rechange. Lorsqu’une action echoue, nous nous retrouvons en
situation d’urgence car une menace se trouve a proximite et la fregate a des chances de
se faire detruire. C’est dans un tel cas que nous devons nous replier sur la solution de
plan conditionnel pour traiter cette contingence tel qu’explique a la section 2.2.1.
La production de plans conditionnels peut s’averer parfois tres longue. En effet,
lorsqu’il y a beaucoup d’incertitude, l’agent doit planifier pour plusieurs situations, ce
qui peut etre tres long. Un probleme peut survenir lorsque l’agent doit mettre son plan
a execution avant une certaine echeance (deadline). Si la construction du plan n’est
pas terminee avant cet echeance, le plan sera invalide et l’utilite de ce plan sera nulle.
Pour resoudre ce probleme, nous expliquons, dans la section suivante, une methode de
planification tres utile lorsque le temps alloue pour produire un plan est tres court : les
algorithmes a tout moment.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 14
SAM sur menace 1
menace 1 détruite?
CIWS sur menace 1
CIWS sur menace 2
non oui
menace 1 détruite?
non oui
frégate détruite?
oui non
menace 2 détruite?
CIWS sur menace 2
oui non
CIWS sur menace 2
menace 2 détruite?
oui non
menace 2 détruite?
oui non
frégate détruite?
frégate détruite?
oui non
non oui
frégate détruite?
non oui
X sur menace Y
?
Utilisation de la ressource X sur la menace Y
Évaluation d'un événement (destruction d'une menace ou impact sur la frégate)
Frégate détruite
Frégate survivante
Fig. 2.2 – Exemple de plan conditionnel.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 15
2.2.3 Algorithmes “a tout moment” (anytime)
Depuis plusieurs annees, certains domaines de recherche se sont attaques a des
problemes tres complexes. Certains problemes sont tellement complexes qu’ils n’est
pas possible de trouver la meilleure solution au probleme dans un delai raisonnable.
Par exemple, le probleme du commis-voyageur1 est un probleme NP-complet classique
ou trouver la solution optimale est tres difficile, voire meme impossible. Le probleme
survient lorsque nous devons trouver une solution a un probleme de ce type a l’interieur
d’un certain delai de temps.
Pour resoudre ce type de probleme, nous devons donc approximer la solution op-
timale. Lorsqu’en plus, nous sommes contraints par le temps, un type d’algorithme
efficace pour resoudre ce type de probleme sont les algorithmes a tout moment (any-
time). Les algorithmes a tout moment possedent les caracteristiques suivantes :
1. Ils peuvent etre suspendus a tout moment de leur execution et il est possible de
reprendre l’execution ou elle etait rendue avant l’interruption.
2. Peu importe le moment de l’interruption, ils retournent toujours une solution.
3. La qualite de la solution produite s’ameliore au fil du temps.
Ainsi, lorsque l’on cherche la solution d’un probleme, un algorithme a tout mo-
ment peut chercher une approximation d’une solution optimale et retourner la solution
trouvee le moment venu. Plus le temps disponible pour executer l’algorithme est grand,
plus la solution retournee sera precise. La figure 2.3 nous illustre la difference entre les
algorithmes a tout moment et les algorithmes standards. Un algorithme a tout moment
ameliore la qualite de la solution au fil du temps et retourne la solution le moment
venu. Un algorithme standard s’execute au complet et retourne la solution trouvee.
S’il n’a pas le temps de terminer son execution avant l’echeance, aucune solution n’est
retournee.
Le terme “anytime algorithm” a ete utilise pour la premiere fois vers la fin des
annees 80 par Dean et Boddy (Boddy et T.Dean, 1989; Dean, 1988; Dean et Boddy,
1988) dans leur travaux sur la planification temporelle. A cette epoque, Horvitz (1987)
et Suermondt (1989) ont introduit l’idee de calcul flexible pour resoudre les problemes de
prise de decision sous des contraintes temporelles fortes. Il a fallu attendre jusqu’en 1991
pour que Russel et Zilberstein completent leurs travaux sur la composition d’algorithme
a tout moment dans le but de resoudre des problemes complexes (Russel et Zilberstein,
1991; Zilberstein, 1993; Zilberstein et Russel, 1996).
Il existe plusieurs facons d’implementer un algorithme a tout moment. Cependant,
1http ://www.tsp.gatech.edu//index.html
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 16
standard
à tout moment
Temps
Qualité
T
Q1
1
Fig. 2.3 – Qualite d’un algorithme standard et d’un algorithme a tout moment.
la plupart des algorithmes a tout moment sont formes des trois composantes suivantes.
Fonction iterative d’amelioration Cette fonction permet d’ameliorer la qua-
lite de la solution par petits increments. A chaque iteration, cette fonction doit
tenter de trouver une meilleure solution que la precedente.
Fonction d’evaluation Cette fonction est une mesure de la qualite de la solu-
tion retournee par l’algorithme. Selon le probleme, elle peut etre presentee sous
differentes formes. Les differentes formes sont detaillees dans (Soucy, 2003).
Profil de performance Le profil de performance estime la qualite du resultat
retourne selon les parametres d’entrees utilises et le temps d’execution accorde
a l’algorithme. Avec une telle information, il est possible d’estimer le temps que
l’on doit allouer a l’algorithme pour obtenir un resultat satisfaisant l’etat de l’en-
vironnement courant.
Les algorithmes a tout moment sont tres utilises dans les systemes temps-reel ex-
pliques a la prochaine section. Les systemes temps-reel sont des systemes ou il y a de
fortes contraintes temporelles. Sous de telles contraintes, il est bon de pouvoir utiliser
le maximum de temps pour produire une solution tout en etant capable de retourner
une solution le moment venu. C’est pourquoi les algorithmes a tout moment sont tres
utilises dans les systemes temps-reel.
2.3 Systemes temps-reel
Les systemes temps-reel sont une categorie de systemes permettant de bien repre-
senter la realite. En effet, de tels systemes permettent de modeliser les contraintes
temporelles qui sont presentes dans le monde reel. Dans un systeme temps-reel, le prin-
cipe fondamental est d’offrir une solution au moment ou cette derniere est necessaire.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 17
Le concept d’echeance (deadline) est donc omnipresent dans ces systemes.
2.3.1 Definition
Il existe plusieurs definitions d’un systeme temps-reel. Celle que nous avons retenue
provient du web :
Un systeme temps-reel est un systeme ayant la capacite de repondre
a divers evenements avec un delai de reponse plus petit que le delai
alloue pour traiter ces evenements2.
A noter qu’une operation temps-reel n’est pas necessairement tres rapide. Executer
une action en temps-reel veut simplement dire que cette action doit etre executee avant
une echeance precise (deadline). Voici deux exemples de systemes temps-reel, un ou le
temps de reponse est grand et un ou le temps de reponse est tres petit :
1. Prenons un systeme qui calcule les depenses et les revenus d’une compagnie pour la
semaine qui vient de se terminer et qui doit produire un rapport de comptabilite.
Si la semaine se termine le vendredi a 17h00 et commence le lundi a 8h00, le
systeme doit commencer son rapport apres 17h00 le vendredi et doit avoir termine
avant 8h00 le lundi. Cela laisse donc 63h00 au systeme pour produire son rapport.
C’est un systeme temps-reel ou le temps de reponse est echelonne sur une longue
periode de temps.
2. Prenons un systeme de controle d’une centrale nucleaire qui doit gerer les sur-
chauffes. Si en cas de surchauffe, on doit ajuster le controleur en moins de 2ms
pour retablir la situation correctement, cela laisse donc 2ms au systeme pour trai-
ter la surchauffe afin d’eviter une catastrophe. C’est un systeme temps-reel ou le
temps de reponse est tres petit.
Selon Gillies (2004), la qualite d’un systeme temps-reel ne depend pas seulement du
moment ou le resultat est produit (exactitude temporelle), mais aussi de l’exactitude
du resultat produit (exactitude logique). Voici ce qu’on entend par exactitude logique
et temporelle :
1. Exactitude logique : Le systeme offre des sorties adequates en fonction des entrees,
assurant ainsi le comportement desire pour le systeme suite aux evenements sur-
venus.
2. Exactitude temporelle : Le systeme respecte les contraintes temporelles en offrant
les sorties au bon moment.
2http ://www.wordiq.com/definition/Real-time
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 18
2.3.2 Structure d’un systeme temps-reel
Un systeme temps-reel consiste en un systeme de controle et un systeme controle.
La figure 2.4 represente une architecture generique d’un systeme temps-reel.
Senseurs Système contrôlé
Opérateur
Effecteurs Système de
contrôle Interface utilisateur
Environnement
Fig. 2.4 – Structure d’un systeme temps-reel (Krishna et Shin, 1997).
Ce modele est compose d’un systeme de controle et d’un systeme controle. L’in-
formation de l’environnement et du systeme controle parvient au systeme de controle
via les senseurs. Le systeme de controle est responsable des actions a entreprendre
pour repondre aux changements de l’environnement. Lorsque le systeme de controle
a determine l’action qu’il convient de faire, il affiche cette information, via l’interface
utilisateur, afin que l’operateur en prenne connaissance. Dans le cas ou l’operateur in-
tervient, le systeme en tient compte. Dans le cas contraire, le systeme de controle agit
sur le systeme controle conformement a ce qu’il a evalue.
2.3.3 Categories de systeme temps-reel
Les systemes temps-reel peuvent etre classes selon leurs contraintes temporelles.
En effet, certains systemes permettent le non-respect (sous certaines conditions) des
contraintes temporelles alors que d’autres ne le permettent pas. Il y a trois categories
de systemes temps-reel (voir figure 2.5) :
1. Souple : le non-respect de l’echeance entraıne une degradation de la solution sans
toutefois entraıner un echec du systeme.
2. Ferme : comporte deux echeances.
(a) Le non-respect de la premiere echeance entraıne une degradation de la solu-
tion jusqu’a la deuxieme echeance.
(b) Le non-respect de la deuxieme echeance entraıne un echec du systeme.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 19
Temps
Qualité
D
Souple
Temps
Qualité
D1
Ferme
Temps
Qualité
D
Fort
Correct
Dégradé
D2
Correct Dégradé
Innacceptable Innacceptable
Correct
Fig. 2.5 – Categories de systemes temps-reel (Chlique, 2004).
3. Fort : le non-respect de l’echeance entraıne un echec du systeme.
Nous pouvons illustrer les differents systemes a l’aide d’un exemple. Supposons
qu’un etudiant doit faire un examen d’une duree de 2h qui commence a 14h00. Une
contrainte souple permettrait a l’etudiant d’arriver en retard. Cependant, plus il arrivera
en retard, plus son resultat s’en ressentira en raison du manque de temps pour faire
l’examen. Une contrainte forte ne permettrait pas a l’etudiant d’arriver en retard. Un
retard entraınerait la note 0. Une contrainte ferme permettrait a l’etudiant d’arriver au
maximum une heure en retard. Plus d’une heure de retard entraınerait la note 0. La
figure 2.6 illustre l’impact des trois contraintes sur le resultat de l’etudiant.
Arrivée
Résultat
14h00
Souple
Arrivée
Résultat
Ferme
Arrivée
Résultat
Fort
16h00 14h00 15h00 14h00
Fig. 2.6 – Exemple de 3 contraintes temps-reel.
La structure des systemes temps-reel etant tres generale, nous desirons maintenant
nous interesser a une categorie plus specifique de systeme temps-reel : les systemes de
commande et controle (C2). Les systemes de commande et controle sont utilises dans
le milieu militaire et le projet NEREUS entre dans cette categorie de systeme. Nous les
expliquons donc dans la section qui suit.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 20
2.4 Systemes de Commande et Controle (C2)
Cette section touche plus en detail le champ de recherche specifique au projet NE-
REUS, soit les systemes de commande et controle. Dans la mesure ou il est centre sur la
prise de decision, le projet NEREUS entre dans cette categorie de systeme. Nous com-
mencons tout d’abord par definir ce que sont les systemes de commande et controle.
Nous expliquons ensuite ce qu’est la boucle OODA, utilisee dans les systemes de com-
mande et controle. Nous terminons cette section en donnant un probleme typique de
commande et controle, l’allocation de ressources sur des menaces.
2.4.1 Definitions
Nous donnons ci-apres les definitions de : commande et controle, systeme de com-
mande et controle et systeme de commande et controle automatise.
Commande et controle C’est l’execution des directives ordonnees par un com-
mandant designe, faisant partie et ayant l’autorite sur un groupe des forces armees,
dans le but d’accomplir une mission specifique3.
Systeme de commande et controle C’est le systeme comportant les instal-
lations, equipements, communications, procedures et ressources permettant au
commandant de planifier, diriger et controler les operations des forces armees
poursuivant une mission3.
Systeme de commande et controle automatise C’est un systeme de com-
mande et controle qui utilise les avantages d’un systeme informatique pour l’eva-
luation des menaces et l’optimisation de l’utilisation des ressources dans le but de
maximiser le resultat d’un affrontement4.
Maintenant que les systemes de commande et controle sont definis, nous pouvons
passer a un modele permettant de decrire le processus d’un systeme de commande et
controle. Ce modele decrit toutes les phases du processus, allant de l’observation de
l’environnement jusqu’aux actions entreprises.
3http ://www.bandwidthmarket.com/resources/glossary/C6.html4http ://www.radwar.com.pl/eng/eng/prmi stn.htm
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 21
2.4.2 Boucle OODA
Le concept de boucle Observer-Orienter-Decider-Agir (OODA loop) a ete invente
et developpe par le colonel John Boyd de la USAF (U.S. Air Force). La boucle OODA
(Observer-Orienter-Decider-Agir) est utilisee pour decrire le processus de commande
et controle. Une telle boucle OODA constitue de nos jours un standard pour decrire
les cycles de prise de decision. Cette boucle est illustree a la figure 2.7. Elle montre a
quel point le commande et controle est un processus continuel et cyclique. Nous avons
laisse les termes anglais dans la figure afin de ne pas changer la signification de certains
termes avec une traduction inappropriee.
La premiere phase, “observer”, consiste a recolter l’information de l’environnement.
Lors de cette phase, on doit identifier les ennemis et les allies. Lors de la deuxieme phase,
“orienter”, on doit estimer, faire des hypotheses, analyser et porter des jugements afin
de se faire une image de la situation et des menaces possibles. La troisieme phase,
“decider”, determine ce qui doit etre fait, que ce soit sous forme de reaction immediate
ou sous forme de plan d’actions echelonne sur une plus longue periode de temps. Enfin,
la quatrieme phase, “agir”, met a execution les decisions prises a la troisieme phase.
2.4.3 Un probleme de C2 : l’allocation de ressources sur des
menaces
Nous presentons ici un probleme typique des systemes de commande et controle :
l’allocation de ressources sur des menaces (weapon-target assignment). Bien que ce
probleme ne represente pas exactement la problematique du projet NEREUS, les so-
lutions proposees pour ce type de probleme pourraient etre adaptees au probleme du
projet NEREUS. Elles pourraient aussi conduire a des pistes de solutions interessantes
pour la gestion des ressources.
Le but ici n’est pas de faire une etude approfondie du probleme mais bien de montrer
que les problemes se retrouvant dans les systemes de commande et controle ne sont pas
simples. Voici donc la definition du probleme.
Definition du probleme
Le probleme consiste a optimiser l’assignation des ressources sur les menaces dans
le but de minimiser la valeur totale de la survie des menaces. Il y a deux versions de
ce probleme : statique et dynamique. Dans la version statique, chaque ressource engage
Chap
itre2.
Agen
tset
IAdan
sles
system
esC
omm
ande
etC
ontrole
(C2)
22
Feed
ForwardObservations Decision
(Hypothesis)
Action
(Test)
Cultural
Traditions
Genetic
Heritage
New
Information Previous
Experience
Analyses &
SynthesisFeed
ForwardFeed
Forward
Implicit
Guidance
& Control
Implicit
Guidance
& Control
Unfolding
Interaction
With
EnvironmentUnfolding
Interaction
With
Environment Feedback
Feedback
Outside
Information
Unfolding
Circumstances
Observe Orient Decide Act
Fig. 2.7 – La boucle OODA (Boyd, 1987).
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 23
les menaces une seule fois et toutes les actions sont declenchees en meme temps. Dans
la version dynamique, les ressources ne sont pas utilisees simultanement comme dans
le probleme statique. Lorsqu’on utilise une ressource sur une menace, on regarde le
resultat de l’action et on decide par la suite s’il faut utiliser une autre ressource sur la
menace (au cas ou l’action serait un echec).
D’un point de vu plus formel, voici comment se formule un tel probleme. Nous avons
n menaces, numerotees de 1 a n et nous avons m ressources, numerotees de 1 a m. On
pose Vj la valeur de la menace j et Wi le nombre de ressources de type i pouvant etre
assignees aux menaces. On pose aussi pij la probabilite d’une ressource de type i de
detruire la menace j. Ainsi, qij = 1−pij represente la probabilite de survie de la menace
j si une ressource de type i lui est assignee. Notons que si l’on assigne un nombre xij
de ressources de type i sur la menace j, alors la probabilite de survie de la menace j
est de qxij
ij . Le probleme consiste donc a determiner le nombre xij de ressources de type
i a assigner a la menace j afin de minimiser la probabilite de survie totale des menaces.
Le probleme peut donc etre formule comme suit :
Minimiser∑n
j=1Vj(
∏mi=1
qxij
ij )
de sorte que
∑nj=1
xij ≤ Wi, pour tout i = 1, 2, ...,m
xij ≥ 0 et entier, pour tout i = 1, 2, ...,m et pour tout j = 1, 2, ...n.
Ce probleme se rapproche du probleme qu’on a a traiter dans le projet NEREUS.
Cependant, ce probleme ne prend pas en compte les contraintes sur les differentes
ressources (angles morts, portee, ...). C’est pourquoi il ne represente pas exactement
le probleme du projet NEREUS. Il a ete prouve par Lloyd et Witsenhausen (1986)
que ce probleme est NP-complet (voir (Hromkovic, 2001) pour des details sur la NP-
completude). Ainsi, c’est un probleme tres difficile a resoudre et ou il faut parfois
approximer la solution optimale a l’aide d’heuristiques afin de le resoudre.
Differentes solutions proposees
Comme il serait tres long et complique d’elaborer les solutions proposees a ce
probleme, nous ne ferons que donner une idee des solutions proposees. Ce probleme,
bien que tres interessant, n’a pas ete etudie pas beaucoup de chercheurs. Nous citons ici
les chercheurs ayant travaille sur ce probleme ainsi que les solutions qu’ils ont proposees.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 24
Les recherches sur ce probleme ont commence dans les annees 50 avec des travaux
sur la modelisation du probleme (Manne, 1958; Braford, 1961; Day, 1966). Cependant,
il a fallu attendre jusqu’en 1986 pour que Lloyd et Witsenhausen (1986) etablissent la
preuve de la NP-completude de ce probleme.
De son cote, Hosein (1989) du MIT en a fait son sujet de recherches doctorales.
Bien qu’il ait etudie les deux versions du probleme (statique et dynamique), la majeure
partie de son travail fut sur la version dynamique du probleme. Comme le probleme est
NP-complet, il a du faire des simplifications afin de trouver des solutions satisfaisantes
au probleme. Le lecteur peut se referer a (Hosein, 1989) et (Hosein et Athans, 1990)
pour des details sur les solutions proposees.
Plus recemment, Lee et al. (2003) ont propose un algorithme genetique pour resou-
dre le probleme. L’algorithme propose peut utiliser une fonction de choix vorace ou
encore un algorithme de type recuit-simule pour la recherche de solutions approchees.
Enfin, Ahuja et al. (2003) font une revue de litterature des travaux effectues sur ce
probleme. De plus, ils proposent differentes solutions d’approximation pour le probleme.
Parmi ces solutions, on retrouve des algorithmes de type “branch-and-bound”, des
reseaux de neurones et des algorithmes iteratifs de recherche. Certains de ces algorithmes
peuvent resoudre le probleme pour des instances de 200 ressources et 400 menaces en
un temps relativement court (moins de 2 secondes).
Maintenant que sont expliques les systemes de commande et controle ainsi qu’un
probleme typique que l’on retrouve dans de tels systemes, nous pouvons passer aux
divers travaux effectues dans ce domaine. En particulier, nous donnons les divers travaux
sur l’automatisation des systemes de commande et controle.
2.5 Travaux sur l’automatisation des systemes de
commande et controle
Avant de donner les travaux anterieurs du projet NEREUS, nous allons donner un
apercu des travaux effectues dans le domaine de l’automatisation des systemes de com-
mande et controle. Comme les travaux effectues dans ce domaine sont relies au milieu
militaire, ils sont tres souvent confidentiels. La plupart des laboratoires ou entreprises
ne font que donner un survol de leurs projets sans en donner les details. C’est pourquoi,
nous ne pouvons donner les travaux en details. Nous allons plutot donner une liste non
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 25
exhaustive des laboratoires et entreprises travaillant dans ce domaine en enumerant
quelques projets sur lesquels ils travaillent.
2.5.1 TNO Physics and Electronics Laboratory (TNO-FEL)
Le laboratoire de physique et d’electronique5 fait partie de l’organisme sur la re-
cherche scientifique appliquee des Pays-Bas (TNO). Cet organisme independant cherche
a faire le pont entre le savoir-faire fondamental et les pratiques des autorites gouver-
nementales et du milieu des affaires. Les produits et services de TNO-FEL couvrent
entierement la chaıne de l’information. Elle va de la collecte d’informations jusqu’a son
utilisation, en passant par le transport et le traitement de celles-ci.
Nous avons retenu 2 projets plus specifiquement relies aux systemes de commande
et controle qui se rapprochent du projet NEREUS. Le premier projet est IFICS (In-
formation Filtering and Information Control System). Ce projet a pour but de reduire
le flot d’informations que doit gerer le commandant de bord d’un navire. En filtrant
l’information recueillie et en ne gardant que l’information utile, le systeme peut aider
le commandant a prendre de meilleures decisions car il reduit l’information que doit
traiter le commandant, lui facilitant ainsi la tache.
Le second projet est nomme “Command & Control (C2) for the Royal Netherlands
Navy”. Ce projet vise a augmenter la qualite de defense des fregates de la marine des
Pays-Bas tout en reduisant le personnel a bord de ces fregates. Cela est fait en gerant
l’information recueillie et en la classant afin de mieux la presenter au commandant
de bord. Un flot d’informations bien classees et bien presentees facilite la tache au
commandant. Un simulateur a ete developpe afin de permettre aux utilisateurs du
systeme de juger de l’interface presentant l’information et de se familiariser avec cette
derniere.
2.5.2 Defense Advanced Research Projects Agency (DARPA)
DARPA6 est l’organisation responsable de la recherche et du developpement pour le
departement de la defense des Etats-Unis. Elle controle et dirige des projets de base et
des projets appliques en recherche et developpement pour le departement de la defense.
5http ://www.tno.nl/instit/fel/wie-we-zijn/mission.html6http ://www.darpa.mil/
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 26
Elle poursuit des recherches pouvant mener a des avancees majeures pour des missions
militaires traditionnelles.
Deux projets de DARPA ont retenu notre attention. Le premier est FCS (Future
Combat System) de la division TTO (Tactical Technology Office) de DARPA. Ce pro-
jet consiste en l’integration de plusieurs systemes de combat pour diverses missions.
Ces systemes vont incorporer les dernieres technologies sur la mobilite, les senseurs et
la capacite de survie. Le projet est developpe en utilisant de la modelisation, de la
simulation et de l’experimentation.
Le second projet est UCAR (Unmanned Combat Armed Rotorcraft). Le but de ce
projet est de concevoir, developper et integrer les dernieres technologies aux systemes de
l’armee americaine. Les dernieres technologies sont la capacite de survie et les operations
autonomes dans les systemes de commande et controle. Un tel systeme permettra d’avoir
un helicoptere de guerre capable de poursuivre des cibles de grande valeur sans avoir
de pilote aux commandes. Il y a plusieurs objectifs specifiques dans ce projet. Un des
ces objectifs, qui est plus interessant pour nous, est de permettre une cooperation et
une collaboration autonome entre differents navires de guerre.
2.5.3 Stanford Research Institute International (SRI)
SRI International7 est un institut de recherche independant sans but lucratif, situe
aux Etats-Unis. Il fait de la recherche et du developpement pour les agences du gouver-
nement, les fondations, les entreprises et autres organisations. Il est reconnu pour ses
recherches en technologie de l’information, communication, ingenierie, chimie, physique,
sante, developpement economique, etc.
Nous avons retenu deux projets de la division AIC (Artificial Intelligence Center). Le
premier est SUO-PDA (Planning and Decision Aids for Small Unit Operation). Le but
de ce projet est de developper un systeme de planification et d’aide a la decision pour le
programme SUO (Small Unit Operations) de DARPA. Le concept de SUO est d’avoir
une petite unite de soldats disperses dans un tres grand environnement. Cette unite
possede de l’equipement permettant la communication entre les membres de l’unite, le
calcul informatique et la localisation geographique des membres. Le systeme permet
d’etablir une planification afin de permettre une bonne coordination entre les membres
de l’unite. Dans sa version actuelle, le systeme prend en compte les contraintes de temps
et de localisation qui doivent etre respectees afin d’assurer une bonne execution du plan.
7http ://www.sri.com/
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 27
Le second projet est JFACC (Joint Force Air Component Commander). Ce projet a
permis le developpement de CPEF (Continuous Planning and Execution Framework),
une architecture permettant la generation de plans et la replanification pour des agents
situes dans des environnements tres dynamiques. Les plans generes ont la capacite de se
mettre a jour en reponse a de nouvelles informations percues. Ce projet a ete developpe
en collaboration avec la DARPA.
2.5.4 Defence Science and Technology Organisation (DSTO)
DSTO8 est une division du departement de la defense du gouvernement australien.
Son role est d’assurer l’application des sciences et technologies innovatrices pour la
defense de l’Australie dans le meilleur de ses interets. Ce centre de recherche possede
plusieurs laboratoires dont un sur les technologies de l’information. Ce dernier possede
4 divisions :
1. Commande et Controle.
2. Analyse des systemes de defense.
3. Intelligence, Surveillance et Reconnaissance.
4. Reseaux d’information.
Nous n’avons malheureusement pas pu trouver d’informations sur des projets pou-
vant nous interesser. Certains projets du DSTO sont publiques, mais ces projets ne
s’approchent pas de la problematique que nous etudions presentement dans le cadre du
projet NEREUS.
2.5.5 Autres entreprises
Il y a bien entendu d’autres entreprises qui travaillent sur l’automatisation des
systemes de commande et controle. Il serait impossible de donner ici toute la liste
des entreprises avec leurs projets. Cependant, le lecteur peut retrouver les entreprises
ainsi que leurs projets a l’adresse citee en bas de page9. Les projets sont regroupes
selon le type de vehicule de defense. Il y a donc une section specialement sur les projets
concernant les fregates et destroyers.
8http ://www.dsto.defence.gov.au/index.html9http ://www.naval-technology.com
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 28
2.6 Travaux anterieurs sur NEREUS
Les intervenants du projet NEREUS se sont mis d’accord pour n’aborder que la par-
tie “decider” de la boucle OODA presentee a la section 2.4.2. Ainsi, les autres etapes de
la boucle OODA sont considerees comme connues et n’ont pas a etre traitees. Une telle
hypothese s’explique par la trop grande complexite de la boucle OODA entiere. Pour
pouvoir etre efficace dans nos travaux, nous devons nous concentrer sur une partie de la
boucle plutot que sur la boucle entiere. De plus, les champs de recherche du laboratoire
DAMAS touchent cette partie de la boucle et peuvent contribuer a l’ameliorer.
Il convient de noter ici que la fregate possede trois types de planificateur : position-
nement, actions “hardkill” et actions “softkill”. Il a ete decide que l’ordre des plani-
ficateurs etait celui-ci. Le planificateur de position commence par choisir la meilleure
position pour se defendre (selon une certaine heuristique) et ensuite, les planificateurs
“hardkill” et “softkill” construisent un plan de defense selon la position choisie. Cela
dit, nous pouvons maintenant aborder les travaux anterieurs realises dans le cadre du
projet NEREUS.
2.6.1 Division en secteurs de defense et apprentissage
Tel que presente en annexe, la division de l’aire de defense en 12 secteurs a ete pro-
posee par Plamondon (2003). Cette meme division a conduit par la suite a la construc-
tion d’un module d’apprentissage dans le but d’evaluer la qualite de defense de chacun
des secteurs.
Ce module d’apprentissage a permis, a l’aide de simulations, de savoir quel etait
l’efficacite de defense de chacun des secteurs. La qualite de defense etait mesuree selon
le pourcentage de survie de la fregate. Voici comment se deroule une simulation :
1. On fait apparaıtre des menaces dans le secteur a tester.
2. On construit un plan de defense.
3. On execute ce plan.
4. On regarde si la fregate a survecu.
A la fin des simulations, les resultats ont ete compiles pour obtenir l’efficacite de
chacun des secteurs. Les resultats du module d’apprentissage ont ete utilises pour le
positionnement bayesien presente ci-apres.
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 29
2.6.2 Positionnement bayesien
Le positionnement bayesien consiste en une methode permettant de savoir quelle est
la meilleure position que doit prendre la fregate pour augmenter ses chances de survie.
Cette technique utilise un classificateur bayesien naıf afin de calculer les chances de
survie de la fregate selon les secteurs ou se trouvent les menaces qui l’attaquent. Dans
ce calcul, les menaces sont considerees independantes les unes des autres. Le calcul se
fait donc comme suit :
Bayesien =n
∏
i=1
S(si) (2.1)
ou n represente le nombre de menaces et si le secteur ou se retrouve la menace i. La
valeur de S(si) represente la probabilite de survie de la fregate pour le secteur si. Cette
valeur est donnee par le module d’apprentissage.
2.6.3 Planification
Trois types de planificateur ont ete developpes dans le cadre du projet NEREUS :
reactif, deliberatif et deliberatif avec amelioration tabu. Le planificateur reactif est ce-
lui qui represente le mieux le comportement humain. Dans sa planification, il considere
seulement les deux premieres menaces (les plus dangereuses) qui attaquent la fregate.
Le plan de defense pour les deux premieres menaces est construit de la meme facon
que le plan du planificateur deliberatif explique plus bas. La difference est que le pla-
nificateur deliberatif planifie pour l’ensemble complet de menaces alors que le reactif
considere seulement les deux premieres menaces. Lorsque les deux premieres menaces
sont detruites, le planificateur reactif considere les deux suivantes et ainsi de suite. Ce
planificateur a ete implemente comme reference pour comparer les algorithmes de pla-
nification. Cela permet de comparer la qualite d’un plan produit par le systeme d’aide
a la decision (deliberatif et deliberatif avec tabu) par rapport au plan produit par le
commandant de la fregate (reactif).
Le planificateur deliberatif cree un plan pour les armes “softkill” et les armes “hard-
kill”. Lorsque les deux plans sont crees, le planificateur fusionne les deux plans en
enlevant les actions du plan “softkill” qui pourraient nuire a certaines actions du plan
“hardkill”. Le choix des actions considere les ressources disponibles d’apres la position
de la fregate et des menaces. Pour le plan “hardkill”, le planificateur tente d’allouer
un SAM aux menaces les plus dangereuses car le SAM est l’arme la plus efficace. Si
cela n’est pas possible, il tente d’allouer le GUN a ces menaces. Si certaines menaces ne
peuvent etre engagees par une ressource “hardkill”, le planificateur tentera alors d’al-
Chapitre 2. Agents et IA dans les systemes Commande et Controle (C2) 30
louer une ressource “softkill” a ces menaces afin de les faire devier de leur trajectoire.
Enfin, le CIWS adopte un comportement reactif. Il fait simplement tirer sur toute me-
nace qui entre dans son rayon d’action jusqu’a ce que cette menace soit detruite ou ait
atteint la fregate.
Le planificateur deliberatif avec amelioration tabu est base sur celui presente par
Blodgett et al. (1998). Il a ete adapte au projet NEREUS par Soucy (2003). L’idee
de ce planificateur est de prendre le plan propose par le planificateur deliberatif et
de l’ameliorer. Pour ce faire, le planificateur tente d’ajouter ou de retirer des actions
du plan. Lorsqu’un changement est effectue au plan, on evalue le nouveau plan. Si
le nouveau plan est de meilleure qualite, ce dernier est retenu. Il peut arriver que
des changements reduisant la qualite du plan soient effectues afin d’echapper a des
maximum locaux. Cet algorithme est un algorithme “a tout moment” tel que presente
a la section 2.2.3
2.7 Sommaire
Dans ce chapitre, nous avons explique le concept d’agent et d’environnement d’un
agent. Nous avons donne diverses techniques d’intelligence artificielle qui peuvent etre
utilisees par les agents, en particulier la planification et les algorithmes a tout moment.
Nous avons aussi explique en detail les systemes temps-reel et les systemes de com-
mande et controle. Par la suite, nous avons enumere differents laboratoires faisant de
la recherche sur les systemes de commande et controle. Enfin, nous avons explique les
travaux deja realises sur le projet NEREUS. Comme le systeme developpe dans le cadre
du projet NEREUS ne peut etre teste dans le monde reel (en raison des couts), nous
allons expliquer au prochain chapitre comment nous pouvons tester ce systeme a l’aide
de la simulation.
Chapitre 3
Simulation et methode Monte-Carlo
Maintenant que nous avons donne un apercu des systemes de commande et controle,
nous ferons, dans ce chapitre, une introduction a la simulation. Nous commencerons par
donner diverses notions de simulation : definitions, modeles, types de simulation, etc.
Par la suite, nous exposerons une methode permettant de resoudre numeriquement
des problemes tres complexes a l’aide de la simulation : la methode de Monte-Carlo.
Enfin, nous ferons un survol du simulateur (NDS) developpe au DAMAS dans le cadre
du projet NEREUS. Nous ferons un parallele entre le simulateur NDS et la methode
Monte-Carlo.
3.1 Notions de simulation
La simulation a ete depuis toujours un outil privilegie de l’ingenieur. Depuis l’avene-
ment d’ordinateurs de plus en plus puissants, l’importance de la simulation ne cesse de
s’accentuer. A chaque fois qu’il doit concevoir un nouvel engin ou optimiser le fonc-
tionnement d’un systeme deja existant, le concepteur commence par se construire une
maquette. Cette maquette constitue une image plus ou moins fidele permettant de
mieux saisir et comprendre le systeme qu’elle represente. Pour le concepteur, cette ma-
quette peut etre mentale ou physique, statique ou dynamique. Lorsque la maquette est
physique, on peut parler d’un modele de simulation. De nos jours, ces modeles prennent
le plus souvent la forme de realisations informatiques sur ordinateur. Quand elle ne la
precede pas, la simulation vient souvent s’ajouter a l’experimentation sur l’objet etudie,
voire meme la remplacer carrement dans certains cas.
Chapitre 3. Simulation et methode Monte-Carlo 32
3.1.1 Definition de la simulation
Selon Heche et al. (2003), simuler c’est reproduire un processus donne, l’original,
bien souvent encore inexistant, a l’aide d’un deuxieme processus, le modele, dans le but
de tirer des conclusions concernant le premier, basees sur des observations du second.
Cela pourra etre reussi si le modele represente bien l’original dans les aspects cru-
ciaux de ce dernier. En effet, le modele ne pourra jamais representer parfaitement
l’original. Si le modele permet de faire une representation assez fiable de l’original et
permet de reproduire le comportement de ce dernier avec une marge d’erreur tolerable,
l’interet de la simulation prend tout son sens. La simulation permet souvent de faire
des experiences qui seraient impossibles. Selon Heche et al. (2003), l’utilisation de la
simulation est preconisee notamment, lorsque le processus original
1. est trop rapide pour qu’on puisse suivre son evolution avec les instruments a
disposition (reactions chimiques, processus physiques)
2. est trop lent pour qu’on puisse en mesurer le comportement en un temps utile
(croissance des arbres, mouvements migratoires, evolution des especes)
3. est trop dangereux ou occasionnerait trop d’ennuis a l’entourage si on l’experi-
mentait (reaction nucleaire, simulateur de vol, confrontations belliqueuses)
4. n’existe pas encore (processus industriels, systemes de transport)
5. est trop cher pour que l’on puisse effectuer plusieurs tests (politiques de gestion
de la chaıne logistique, commande optimale des systemes asservis)
3.1.2 Processus complet de simulation
La figure 3.1 illustre les etapes par lesquelles nous devons passer lorsque nous faisons
de la simulation. Le processus va de la definition du probleme jusqu’a la validation des
resultats.
3.1.3 Taxonomie des systemes dynamiques
Tout comme dans le chapitre 2 ou nous avons fait une description de l’environnement
dans lequel peut se retrouver un agent, nous allons donner ici les caracteristiques que
peut avoir un systeme dynamique afin de bien choisir le modele pour le representer.
Cette section se base sur la taxonomie exposee par Heche et al. (2003).
Chapitre 3. Simulation et methode Monte-Carlo 33
Définir le problème
Définir le modèle
Devons-nous simuler?
Plus de tests?
Tout est correct?
Utiliser des méthodes
analytiques
Écrire un programme
Valider le modèle
Faire des simulations
Résultats satisfaisants?
Redéfinir le modèle
Vérifier les résultats
Tout est correct?
Non
Non
STOP
Oui
Oui
Non
Oui
Oui
Non
Oui
Non
Fig. 3.1 – Processus complet de simulation
Chapitre 3. Simulation et methode Monte-Carlo 34
Tout d’abord, le systeme peut etre a temps continu ou a temps discret. S’il est a
temps continu, cela veut dire que les valeurs possibles du temps sont puisees dans les
nombres reels. S’il est a temps discret, les valeurs possibles du temps forment une suite
ordonnee et denombrable. Les nombres naturels en sont un exemple. Il arrive souvent
que la suite de valeurs possibles soit vue comme un ensemble de points equiespaces,
plonges dans la droite des reels. A ce moment, le systeme a temps discret est interprete
comme etant obtenu par echantillonnage d’un systeme a temps continu.
Tout comme le temps, l’ensemble des etats dans lequel pourrait se retrouver un
systeme peut lui aussi etre soit continu, soit discret. Lorsque l’on parle d’un systeme
a etats continus, l’ensemble des etats est souvent represente par un ouvert dans Rn.
Nous ne donnerons pas ici la definition d’un ouvert dans Rn ; il faut seulement retenir
que l’ensemble des etats est non denombrable. Lorsque l’ensemble des etats est fini ou
denombrable, le systeme est dit a etats discrets.
Système
Statique Dynamique
Temps continuTemps discret
États continusÉtats discrets
Déterministe Stochastique
Fig. 3.2 – Caracteristiques d’un systeme
Enfin, un systeme peut etre soit deterministe, soit stochastique. Selon Heche et al.
(2003), un systeme est dit deterministe si son evolution future peut etre decrite de
maniere precise a l’aide de sa loi d’evolution, moyennant la connaissance de son etat a
un instant donne. En d’autres mots, lorsque le systeme se trouve dans un etat donne,
nous pouvons determiner la suite des etats dans lequel le systeme se retrouvera dans
le futur. Par contre, un systeme est dit stochastique si son evolution future ne depend
pas seulement de son etat actuel, mais aussi du hasard. Donc, il n’est pas possible de
Chapitre 3. Simulation et methode Monte-Carlo 35
determiner les etats futurs du systeme. Nous pouvons seulement donner des pronostics
probabilistes sur l’evolution du systeme selon l’observation d’un etat a un temps donne.
La figure 3.2 illustre les caracteristiques d’un systeme sous forme de graphe. Ce graphe
est inspire de Holger (2001).
Pour le reste de ce chapitre, afin de ne pas alourdir le contenu, nous allons nous
concentrer sur les systemes ou les modeles pouvant les representer ont les caracteris-
tiques suivantes : temps continu, etats discrets et stochastique. Dans la section suivante,
nous donnons une approche permettant de faire de la simulation sur de tels systemes :
la simulation par evenements discrets.
3.2 Simulation par evenements discrets
Selon Smith (2004), la simulation par evenements discrets fut utilisee pour la pre-
miere fois dans les annees 50 dans le but d’etudier certains problemes relies au com-
merce. Les objectifs etaient d’ameliorer l’efficacite, reduire les couts et augmenter les
profits. Les modeles crees dans les annees 60 et 70 etaient generalement des programmes
informatiques et les sorties de ces programmes etaient donnees sous forme de listes de
chiffres. Dans les annees 80, les modeles furent ameliores avec l’ajout d’animations 2D
qui permettaient d’avoir une representation visuelle du probleme. Enfin, dans les annees
90, les logiciels de simulation ont permis l’ajout d’animations 3D, ce qui aida pour la
representation de certaines contraintes spatiales.
Dans cette section, nous allons expliquer ce qu’est la simulation par evenements
discrets. Cette approche est tres repandue dans la simulation des systemes stochastiques.
La raison pour laquelle nous exposons cette methode est qu’elle est utilisee dans le
projet NEREUS a l’interieur du simulateur que nous allons exposer a la section 3.4.
Nous commencons par donner une breve description de la methode.
Dans un modele de simulation par evenements discrets, le systeme considere se
trouve a tout instant dans un certain etat. Cet etat ne peut changer que lorsque survient
un evenement. Les evenements ne se produisent qu’a des instants discrets, d’ou le nom
de l’approche. La figure 3.3 represente le deroulement d’une simulation par evenements
discrets. Dans ce genre de simulation, un evenement peut :
1. provoquer un changement d’etat du systeme
2. provoquer le declenchement d’autres evenements qui vont se produire dans le futur
3. modifier le cours des evenements prevus
Chapitre 3. Simulation et methode Monte-Carlo 36
Temps0 e e e e e e e1 2 3 4 5 6 7
Fig. 3.3 – Deroulement d’une simulation par evenements discrets
3.2.1 Elements d’un simulateur par evenements discrets
Selon Heche et al. (2003); Ball (1996); iBright Ltd. (2004), un simulateur par evene-
ments discrets devrait comporter les elements suivants :
1. les entites
2. les relations entre les entites
3. un generateur de nombres aleatoires
4. une horloge
5. un gestionnaire de simulation
6. un compilateur de resultats
Tout d’abord, nous devons avoir la liste des entites que contient le modele. Les
entites sont les elements tangibles qui composent le monde reel. Par exemple, dans une
usine ou l’on retrouve une chaıne de montage, les entites pourraient etre toutes les
machines composant la chaıne. Nous retrouvons aussi les relations entre les entites. Ces
relations definissent le comportement du modele. Bien que tres simples, les relations
peuvent se retrouver en tres grande quantite dans le modele ce qui contribue a faire
augmenter la complexite de ce dernier.
Nous retrouvons ensuite le generateur de nombres aleatoires. Ce generateur contri-
bue a reproduire le comportement stochastique du monde reel. Il peut obeir a differentes
lois (uniforme, normale, etc.) afin de reproduire le comportement stochastique le plus
approprie selon la situation. Un autre outil que l’on retrouve est l’horloge. Cette derniere
est utilisee afin de garder la trace du temps dans la simulation. Ainsi, si l’on veut savoir
a quel moment est survenu ou surviendra un evenement, l’horloge est la pour nous le
preciser.
Un autre element est le gestionnaire de simulation. Ce dernier contient l’echeancier
de tous les evenements futurs. Il permet d’inserer ou de supprimer des evenements au
besoin. C’est lui qui fait la recherche du prochain evenement et qui fait avancer la
simulation suite a cet evenement. De plus, il gere les relations entre les entites et ajoute
ou enleve des evenements en consequence.
Chapitre 3. Simulation et methode Monte-Carlo 37
Enfin, le dernier element est le compilateur de resultats. Ce dernier sert a valider
le modele et permet une analyse plus approfondie de ce dernier. Il permet de valider
le modele avec differentes metriques et contribue a produire des graphiques afin de
visualiser les resultats.
3.2.2 Deroulement d’une simulation par evenements discrets
Une simulation par evenements discrets se deroule comme suit. Au depart, le systeme
se trouve dans son etat initial. Le gestionnaire de simulation cree un premier evenement
DEBUT, au temps t = 0, qui initialise le processus, inscrit d’autres evenements a
l’echeancier de simulation et prevoit l’evenement FIN qui marquera la fin de la simu-
lation.
Ensuite, la simulation se retrouve dans une boucle. Le gestionnaire de simulation
traite les evenements successifs selon l’ordre qu’ils ont dans l’echeancier de simulation. Il
avance le temps de simulation jusqu’au prochain evenement dans l’echeancier, retire cet
evenement de l’echeancier et l’execute. Si cet evenement a comme consequence de creer
d’autres evenements ou d’en retirer de l’echeancier, le gestionnaire de simulation fera
l’ajustement de l’echeancier. Il mettra aussi a jour les compteurs pour la compilation
des resultats. Il se deplacera ensuite vers le prochain evenement.
La simulation se termine lorsque le gestionnaire de simulation se retrouve a executer
l’evenement special FIN. Ce dernier peut avoir ete declenche par d’autres evenements
ou il se peut tout simplement que la simulation soit rendue a cet evenement FIN qui a
ete place a l’echeancier des le debut de la simulation.
3.2.3 Analyse des resultats
Lors de la simulation d’un systeme stochastique, le but est tres souvent d’evaluer le
comportement du systeme ou encore ses performances. Il s’agit donc d’estimer un certain
nombre de parametres inconnus qui jouent un role sur le comportement du systeme.
Pour ce faire, il existe plusieurs techniques d’estimation et plusieurs techniques pour
evaluer la precision de l’estimation. Entre autres, on retrouve la methode des moindres
carres, la methode du maximum de vraisemblance, etc. Nous n’exposerons pas en detail
toutes les techniques. Le lecteur peut se referer a (Heche et al., 2003) et (Granger, 2000)
pour une information plus complete.
Chapitre 3. Simulation et methode Monte-Carlo 38
Dans cette section, nous allons exposer comment calculer les intervalles de confiance
et leur signification. Commencons par une definition. Un intervalle de confiance [a, b]
est un intervalle a l’interieur duquel la vraie valeur, Vp, du parametre a estimer peut se
retrouver avec une certaine probabilite. Formellement, on obtient
P (a ≤ Vp ≤ b) = 100(1 − α)% ou 0 ≤ α ≤ 1
Par exemple, si α = 0.05, le niveau de confiance est de 95%. Il y a donc 5% des
chances que la vraie valeur du parametre se retrouve en dehors de l’intervalle [a, b]. La
question ici est comment le calculer cet intervalle de confiance. Nous allons exposer le
calcul de l’intervalle sans toutefois en detailler toute la theorie qui justifie ce calcul. Le
lecteur peut trouver toute l’information sur la justification theorique des intervalles de
confiance dans (Granger, 2000) et (Rice, 1995).
Pour pouvoir calculer un intervalle de confiance, nous devons tout d’abord avoir une
estimation de la valeur du parametre que nous recherchons. Dans notre cas, l’estimation
du parametre est expliquee a la section 3.3. Pour l’instant, nous allons supposer que nous
avons une estimation de la valeur du parametre. Cet estimation vient de resultats de
simulation. Lorsque nous avons une estimation de la valeur du parametre, nous devons
calculer une marge d’erreur, que nous appelons l’intervalle de confiance. Le calcul de
l’intervalle de confiance fait intervenir les parametres suivants :
n : la taille de l’echantillon, ou le nombre de simulations
σ2 : la variance, calculee a partir des resultats de simulation
α : le risque, ou la probabilite que la vraie valeur ne soit pas dans l’intervalle
x : l’estimation de la valeur du parametre
L’intervalle de confiance [a, b] est donc calcule comme suit :
a = x − zα/2
σ√n
b = x + zα/2
σ√n
A noter que la valeur de zα/2 est trouvee dans une table de loi normale (voir Rice,
1995). Ainsi, si nous prenons un risque de α = 5%, nous aurons z0.25 = 1.96 et l’intervalle
de confiance sera
a = x − 1.96σ√n
b = x + 1.96σ√n
Si nous prenons un risque beaucoup plus faible, α = 0.5%, nous aurons z0.025 = 2.81,
ce qui fera grossir l’intervalle.
Chapitre 3. Simulation et methode Monte-Carlo 39
3.2.4 Exemple : simulation d’une file d’attente
L’exemple que nous donnons ici (tire de Heche et al., 2003) est un systeme forme
d’un serveur et d’une file d’attente. Le systeme fonctionne de la facon suivante. Tout
client qui arrive dans le systeme est pris immediatement en charge par le serveur, si ce
dernier est disponible, autrement le client se place dans une file d’attente de longueur
infinie. Le client doit attendre que tous les clients le precedant dans la file aient ete
servis avant de se faire servir.
Les intervalles de temps entre deux arrivees successives de clients forment une suite
αi de variables aleatoires independantes, obeissant toutes a une meme fonction de dis-
tribution Fα(t) (qui est a determiner : uniforme, normale, etc.). Aussi, les temps que
prend le serveur pour servir les clients forment une suite βi de variables aleatoires
independantes, obeissant toutes a une meme fonction de distribution Fβ(t) (qui est
aussi a determiner).
Le but de la simulation est d’estimer le nombre moyen N de clients presents ainsi que
la duree moyenne T de sejour d’un client dans le systeme. La simulation est formee de
4 evenements possibles. Nous decrivons chaque evenement sous forme d’algorithme ou
chaque operation de l’algorithme est detaillee. La simulation commence par l’evenement
DEBUT et se termine lorsque l’on atteint l’evenement FIN, c’est-a-dire lorsque le temps
de la simulation est ecoule. Voici donc la description des 4 evenements :
DEBUT : Initialisation et lancement de la simulation
• Poser n = 0 (nombre de clients dans le systeme)
• Poser ntotal = 0 (total des durees de sejour de tous les clients)
• Poser t = 0 (temps courant)
• Choisir la duree totale Dtotale de la simulation
• Placer a l’echeancier l’evenement FIN pour l’instant tfin = Dtotale
• Generer un α (d’apres la loi Fα(t), pour l’arrivee du premier client)
• Placer a l’echeancier un premier evenement ARRIVEE pour l’instant tarr = α
• Aller chercher dans l’echeancier le prochain evenement
ARRIVEE : Arrivee d’un client au temps tarr
• Enlever cet evenement de l’echeancier
• Poser ∆ = tarr − t ; t = tarr (calcul du temps entre cet evenement et le precedent ;
mise a jour du temps de la simulation au temps de cet evenement)
• Generer un α (d’apres la loi Fα(t), pour l’arrivee du prochain client)
• Placer a l’echeancier un nouvel evenement ARRIVEE pour l’instant tarr = t + α
• Si n = 0 (le serveur est libre), alors
. Generer un β (d’apres la loi Fβ(t), duree de service du client)
Chapitre 3. Simulation et methode Monte-Carlo 40
. Placer a l’echeancier un nouvel evenement DEPART pour l’instant tdep = t+β
• Poser ntotal = ntotal + n × ∆ (mise a jour des statistiques)
• Poser n = n + 1 (mise a jour du nombre de clients dans le systeme)
• Aller chercher dans l’echeancier le prochain evenement
DEPART : Depart d’un client au temps tdep
• Enlever cet evenement de l’echeancier
• Poser ∆ = tdep − t ; t = tdep (calcul du temps entre cet evenement et le precedent ;
mise a jour du temps de la simulation au temps de cet evenement)
• Si n ≥ 1 (il y a au moins un client dans la file), alors
. Generer un β (d’apres la loi Fβ(t), duree de service du client suivant)
. Placer a l’echeancier un nouvel evenement DEPART pour l’instant tdep = t+β
• Poser ntotal = ntotal + n × ∆ (mise a jour des statistiques)
• Poser n = n − 1 (mise a jour du nombre de clients dans le systeme)
• Aller chercher dans l’echeancier le prochain evenement
FIN : Fin de la simulation au temps tfin et calcul des resultats
• Poser N = ntotal/Tfin (nombre moyen de clients presents dans le systeme pour la
duree de la simulation)
• Poser T = N/λ (temps moyen de sejour des clients dans le systeme, d’apres la
formule de Little (voir Heche et al., 2003), ou λ represente le taux moyen d’arrivee
des clients dans le systeme)
• STOP (arret de la simulation)
Voila qui complete cette section sur la simulation par evenements discrets. Dans
la section suivante, nous exposons une methode qui permet d’estimer la valeur du
parametre recherche d’un systeme : la methode de Monte-Carlo.
3.3 Methode Monte-Carlo
Tel que mentionne dans la section 3.1.1, trouver la valeur exacte d’un parametre
n’est pas toujours facile. Dans les cas ou il est pratiquement impossible de trouver la
valeur exacte, nous devons nous tourner vers les methodes d’approximation. Une de
ces methodes est la methode de Monte-Carlo, imaginee par Taub (1963) et reprise par
Metropolis et al. (1953). Cette methode est a l’origine meme de la simulation stochas-
tique et pourtant, elle s’attaque a des problemes qui n’ont souvent rien a voir avec le
hasard.
Chapitre 3. Simulation et methode Monte-Carlo 41
3.3.1 Description de la methode
Selon Bayart (2004), voici la definition d’une methode de Monte-Carlo. On appelle
methode de Monte-Carlo toute methode visant a calculer une valeur numerique en
utilisant des procedes aleatoires, c’est-a-dire des techniques probabilistes.
D’apres Heche et al. (2003), l’approche de la methode Monte-Carlo consiste a for-
muler un deuxieme probleme, celui-ci de calcul de probabilites, dont la solution est
egalement solution du probleme de depart. On determine ensuite une solution approchee
du probleme de probabilites au moyen de la simulation et on en obtient ainsi une pour
le probleme de depart (voir figure 3.4). Pour le reste de cette section, nous allons expo-
ser 2 applications de la methode de Monte-Carlo afin de permettre au lecteur de mieux
comprendre la methode. Les deux exemples sont des exemples classiques pour expliquer
la methode : le calcul de la valeur d’une integrale et l’estimation de la valeur de π.
Problème numériquedonné
Problème du calculdes probabilités
Approximationpar simulation
Solution duproblème donné
parfoistrop
difficile
Fig. 3.4 – Schema qui illustre la methode de Monte-Carlo
3.3.2 Exemple d’application de la methode Monte-Carlo : Cal-
cul d’une integrale
Nous allons illustrer au moyen de ce premier exemple comment calculer l’integrale
d’une fonction quelconque a l’aide de la methode de Monte-Carlo. L’idee est la suivante.
Si l’on tire au hasard sur une cible, la probabilite d’atteindre le centre, par exemple,
est proportionnelle a l’aire du centre par rapport a la cible au complet. Sous certaines
conditions, une integrale simple sur un certain intervalle correspond a l’aire sous la
courbe de la fonction a integrer sur l’intervalle. Ainsi, si l’on emboıte la surface a integrer
a l’interieur d’une surface dont on connaıt l’aire, la probabilite d’atteindre la “cible”
Chapitre 3. Simulation et methode Monte-Carlo 42
(l’aire sous la courbe), sera en fait la proportion de l’aire sous la courbe par rapport a la
surface qui l’emboıte. En simulant plusieurs tirs dans la surface, nous pourrons calculer
la probabilite d’atteindre la cible avec les resultats de simulation (voir figure 3.5). Nous
(0,0)(a,0) (b,0)
(0,c)
f(x)
x
y
Fig. 3.5 – Calcul d’une integrale par la methode de Monte-Carlo
pourrons par la suite evaluer la valeur de l’integrale puisque nous savons la probabilite
d’atteindre la cible et nous savons aussi l’aire de la grande surface. Si on se conforme a
la figure 3.5, voici la formule :
P (atteindre cible) =
∫ b
af(x)dx
(b − a) · c
Nous en deduisons donc la formule suivante pour le calcul de l’integrale :
∫ b
a
f(x)dx = P (atteindre cible) · (b − a) · c (3.1)
Nous illustrons maintenant comment, a l’aide de simulation, trouver la valeur de
l’integrale. Pour ce faire, il s’agit simplement de choisir le nombre de simulations que
nous voulons effectuer, n, et faire l’algorithme suivant :
Algorithme EVALUER INTEGRALE(f, a, b, n)
Retourne valeurint, la valeur de l’integrale que l’on cherche
Entrees : f, la fonction a integrer
a, la borne inferieure de l’intervalle
Chapitre 3. Simulation et methode Monte-Carlo 43
b, la borne superieure de l’intervalle
n, le nombre de simulations a effectuer
Variables locales : c, ordonnee de la surface d’aire connue, plus grand que le max
de la fonction f sur [a, b]
ncible, le nombre de fois que l’on atteint la cible, initialement 0
xi, abscisse de la variable aleatoire generee
yi, ordonnee de la variable aleatoire generee
Pcible, la probabilite de se retrouver sous la courbe a integrer
POUR i = 1 a n FAIRE
xi ← U(a, b), suit une loi uniforme sur [a, b]
yi ← U(0, c), suit une loi uniforme sur [0, c]
SI yi ≤ f(xi) ALORS
ncible ← ncible + 1, le point est sous la courbe
FIN POUR
Pcible ← ncible/n
valeurint ← Pcible · (b − a) · cRETOURNER valeurint
Bien entendu, dans ce genre de probleme, plus le nombre de simulations, n, est
grand, plus l’approximation de la vraie valeur est precise. A l’aide des intervalles de
confiance exposes a la section 3.2.3, il s’agit de choisir le bon n afin de faire le compromis
“qualite-temps de calcul” qui satisfait le mieux a nos besoins.
3.3.3 Autre exemple : Estimation de la valeur de π
Pour ce deuxieme exemple, nous allons illustrer comment evaluer la valeur de π a
l’aide de simulations. Tout comme l’evaluation d’une integrale, l’evaluation de π se base
aussi sur le principe de la “probabilite d’atteindre la cible”. Partons de la situation de
depart suivante (voir figure 3.6). Nous avons un cercle centre a l’origine de rayon egal a
1. Nous avons aussi un carre centre a l’origine de cote egal a 2. L’aire du cercle est donc
de π et l’aire du carre est de 4. Si nous nous limitons seulement au premier quadrant,
ou x ≥ 0 et y ≥ 0, l’aire du quart de cercle sera de π4
et l’aire du carre sera de 1 (voir
figure 3.7). En faisant plusieurs tirs dans le carre du premier quadrant, la probabilite
de tomber dans le quart de cercle sera le rapport des aires. Donc,
P (atteindre quart de cercle) =π
4
Chapitre 3. Simulation et methode Monte-Carlo 44
(0,0) (1,0)
(0,1)
(-1,0)
(0,-1)
x
y
Fig. 3.6 – Construction de la figure pour evaluer π
(0,0) (1,0)
(0,1)
x
y
Fig. 3.7 – Evaluation de la valeur de π
Chapitre 3. Simulation et methode Monte-Carlo 45
Il reste a trouver la probabilite d’atteindre la quart de cercle, a l’aide de simulations,
et de la multiplier par 4 pour obtenir l’estimation de la valeur de π. L’estimation de la
valeur de π se fait a l’aide de l’algorithme suivant :
Algorithme EVALUER π(n)
Retourne valeurπ, l’estimation de la valeur de π
Entrees : n, le nombre de simulations a effectuer
Variables locales : ncible, le nombre de fois que l’on atteint la cible, initialement 0
xi, abscisse de la variable aleatoire generee
yi, ordonnee de la variable aleatoire generee
Pcible, la probabilite de se retrouver dans le quart de cercle
POUR i = 1 a n FAIRE
xi ← U(0, 1), suit une loi uniforme sur [0, 1]
yi ← U(0, 1), suit une loi uniforme sur [0, 1]
SI x2i + y2
i ≤ 1 ALORS
ncible ← ncible + 1, le point est dans le quart de cercle
FIN POUR
Pcible ← ncible/n
valeurπ ← Pcible · 4RETOURNER valeurπ
Voila qui complete l’exemple de l’estimation de la valeur de π et qui complete par
le fait meme la section sur la methode de Monte-Carlo. Dans la section suivante, nous
exposons le simulateur de defense navale developpe au DAMAS.
3.4 Simulateur de defense navale (NDS)
Dans le cadre du projet NEREUS, le groupe DAMAS a developpe un simulateur de
defense navale (NDS). Ce simulateur a ete developpe en JAVA. Il a ete developpe afin de
satisfaire a deux objectifs principaux. Le premier est de pouvoir faire des demonstrations
d’une simulation de guerre navale. Ainsi, il est possible de presenter les travaux faits
au DAMAS a des personnes qui sont moins specialistes en informatique. L’interface
graphique permet de bien visualiser les divers evenements qui surviennent lors d’une
simulation. Elle permet aussi de bien visualiser l’utilisation des differentes ressources
disponibles sur la fregate.
Chapitre 3. Simulation et methode Monte-Carlo 46
Le deuxieme objectif du simulateur NDS est plus important et vise a permettre de
tester l’efficacite des diverses techniques de planification et d’allocation de ressources
employees sur la fregate. Les ressources militaires etant extremement dispendieuses, il
est impossible de faire des milliers de tests avec de vraies ressources. En effet, une
simulation dans un environnement reel pourrait couter des millions de dollars. Le
developpement d’un simulateur est donc essentiel dans le cadre du projet. Ce simula-
teur permet donc aux etudiants du projet NEREUS de developper diverses techniques
de defense et de les tester sans se soucier des couts relatifs a ces tests. De plus, ce simu-
lateur permet de faire des simulations en tres grande quantite afin d’avoir des resultats
d’une precision tres satisfaisante.
3.4.1 Fonctionnalites en mode demonstration
Le premier mode de fonctionnement du simulateur est le mode de demonstration.
Lorsque le simulateur est en mode demonstration, il est plus lent car il y a beaucoup
plus de details dans l’interface graphique. Les figures 3.8 et 3.9 illustrent deux captures
d’ecran du simulateur en mode demonstration. Dans la figure 3.8, le menu de gauche
contient la vitesse de simulation ainsi que le zoom. La vitesse permet de ralentir ou
d’accelerer la vitesse de simulation. Le zoom permet d’approcher la vue afin de faire
varier l’echelle de 60 m a 200 km. Le zoom permet d’avoir une vue d’ensemble de la
simulation ou encore d’avoir une vue rapprochee afin de voir ce qui se passe lorsque
des menaces s’approchent tres pres de la fregate. Le menu de gauche de la figure 3.9
permet de faire afficher des informations dans la fenetre principale. Des informations
sur les objets de la simulation peuvent etre affichees tout comme les rayons d’action des
differentes ressources de la fregate.
Dans le menu du bas des figures 3.8 et 3.9, nous retrouvons toute l’information
sur les differentes ressources de la fregate. L’information va du nombre de ressources
disponibles jusqu’aux actions prevues ou entamees avec ces ressources. Par exemple,
dans la figure 3.8, nous pouvons voir que le STIR avant guide un SAM sur la menace
2 et que le STIR arriere est verrouille sur la menace 3.
Ainsi, l’interface graphique de NDS permet de bien visualiser ce qui se passe lors
d’une simulation. Elle peut permettre a un auditoire qui n’est pas specialiste de bien
comprendre le deroulement d’une simulation et de bien comprendre comment sont uti-
lisees les differentes ressources.
Chapitre 3. Simulation et methode Monte-Carlo 47
Fig. 3.8 – Capture d’ecran du simulateur (1 de 4)
Fig. 3.9 – Capture d’ecran du simulateur (2 de 4)
Chapitre 3. Simulation et methode Monte-Carlo 48
3.4.2 Representation du modele fregate-ressources
Maintenant que nous avons explique le mode demonstration du simulateur, il reste
maintenant a expliquer le cote traitement du simulateur. Tout d’abord, tel que vu a la
figure 3.1, apres avoir programme le simulateur, nous devions nous assurer que ce dernier
represente bien le modele que nous presentons en annexe. Pour ce faire, nous avons
procede a une serie de tests unitaires en vue de valider les differentes caracteristiques des
ressources. Nous avons valide les distances d’interception, les temps d’utilisation, etc.
Par la suite, nous devions nous assurer que pendant les simulations, les rayons d’action
des differentes ressources etaient respectes. La aussi, nous avons teste les limites des
rayons d’action de toutes les ressources presentes sur la fregate.
A titre d’exemple, la figure 3.10 illustre le rayon d’action du Gun et la figure 3.11
illustre le rayon d’action du STIR. Une fois les validations terminees et l’assurance que
notre programme de simulation representait bien le modele presente en annexe, il nous
a fallu passer a l’etape suivante du processus : la simulation. Dans la section ci-apres,
nous faisons etat de la gestion du temps et des evenements dans NDS.
3.4.3 Evolution de la gestion du temps et des evenements
Selon la figure 3.1, l’etape suivante du processus est de faire des simulations. Au
tout debut, le simulateur fonctionnait de la facon suivante. Le temps etait divise en
intervalles de 200 ms afin d’avoir du temps discret plutot que du temps continu. A
chaque intervalle, on faisait avancer et agir les objets presents dans la simulation. Apres
les premiers resultats, nous nous sommes apercus qu’il y avait des problemes dans
certaines simulations. En effet, certains evenements etaient plus rapides que ce que
nous avions juge lors des specifications et il arrivait donc que certaines actions devaient
etre validees dans un intervalle plus petit que 200 ms. Ainsi, il arrivait que des actions
etaient invalidees car les intervalles de temps etaient trop grands. La figure 3.12 illustre
le probleme qui survenait.
Pour pallier a ce probleme, nous avons diminue la longueur des intervalles a 80 ms.
Avec ce nouvel intervalle, les actions ayant les intervalles de validation les plus petits
pouvaient etre validees. Or, un nouveau probleme est survenu avec cette facon de faire.
Il arrivait que 2 evenements se produisent a l’interieur du meme intervalle mais ces
evenements n’etaient pas executes dans le bon ordre. Il y avait donc des evenements
invalides dans le simulateur. La figure 3.13 illustre une situation qui pouvait se pro-
duire. Dans ce cas, il pouvait arriver que l’evenement E2 soit execute avant l’evenement
Chapitre 3. Simulation et methode Monte-Carlo 49
Fig. 3.10 – Capture d’ecran du simulateur (3 de 4)
Fig. 3.11 – Capture d’ecran du simulateur (4 de 4)
Chapitre 3. Simulation et methode Monte-Carlo 50
Intervalle devalidation
t t 200+ ms tempsv v1 2
Fig. 3.12 – Probleme avec un intervalle de 200ms entre les tours
E1 meme si l’evenement E1 devait commencer avant. Si une pre-condition pour que
l’evenement E2 soit valide etait que l’evenement E1 soit declenche, alors l’evenement
E2 etait invalide.
t t 80+ ms temps
E E1 2
Fig. 3.13 – Probleme avec un intervalle de 80ms entre les tours
Nous avons regle ce probleme de la facon suivante. Lorsque plusieurs evenements
survenaient dans le meme tour de simulation (a l’interieur du meme intervalle), le simu-
lateur s’occupait de creer une file d’evenements, ordonnee selon le temps d’execution des
evenements, afin de les executer dans le bon ordre. Ainsi, les evenements demeuraient
toujours valides car ils etaient executes selon l’ordre dans lequel ils se devaient d’etre
executes. Or, cette facon de faire s’approche d’une simulation par evenements discrets.
C’est pourquoi, nous avons par la suite decide de changer le processus de simulation
afin d’avoir un simulateur par evenements discrets, tel qu’explique dans la section 3.2.
3.4.4 Deroulement d’une simulation
Etant donne que nous avions plusieurs types d’algorithme a tester, nous avons decide
de creer deux types de simulation : une simple et une plus complexe. La simulation
simple est utilisee afin de tester les differents planificateurs, de mouvement et de plans
de defense. La simulation plus complexe est utilisee afin de tester les planificateurs
plus complets. Ces planificateurs incluent des strategies de replanification lorsque des
changements surviennent dans l’environnement.
La simulation simple se deroule comme suit. Tout d’abord, l’utilisateur decide du
nombre de menaces qui doivent attaquer la fregate, entre 1 et 8. Nous n’avons pas teste
pour plus de 8 menaces car, tel que vu dans (Soucy, 2003), avec plus de 8 menaces, la
situation se deteriore rapidement et les resultats deviennent moins interessants. Lorsque
Chapitre 3. Simulation et methode Monte-Carlo 51
le nombre de menaces est determine, nous les faisons apparaıtre a l’interieur du radar
de la fregate, simultanement au debut de la simulation. Les menaces apparaissent entre
25 et 80 km de la fregate en suivant une loi de distribution uniforme U(25, 80). L’angle
d’attaque est aussi determine a l’aide d’une distribution uniforme U(0, 360). Dans ce
type de simulation, il n’y a aucune incertitude quant a la detection des menaces par le
radar. Ainsi, toute menace se trouvant dans le rayon d’action du radar est consideree
comme detectee par ce dernier.
Lorsque les menaces apparaissent dans l’environnement, la fregate determine la
meilleure position a adopter et construit un plan de defense. A mesure que les me-
naces avancent, le plan de defense est execute et les resultats recoltes. Ce type de
simulation est simple mais necessaire pour tester les differents algorithmes. En effet,
certains algorithmes ne possedent pas de strategies de replanification. Par consequent,
lorsque l’environnement change, ce type d’algorithme ne peut reagir efficacement face
a la nouvelle situation. Il est donc inutile de faire apparaıtre de nouvelles menaces dans
l’environnement car nous savons a l’avance que les resultats ne seront pas concluants.
Une simulation complexe se deroule comme suit. Nous commencons par faire ap-
paraıtre les menaces dans l’environnement en suivant trois lois normales (voir figure
3.14) : N(40, 5), N(80, 5) et N(120, 5). Le lecteur peut se referer a (Rice, 1995) ou
(Ross, 1996) pour des explications sur les lois normales. Ces lois normales determinent
a quelle distance de la fregate les menaces apparaissent. L’angle d’attaque des menaces
est determine a l’aide d’une loi de distribution uniforme U(0, 360). Lorsque les menaces
sont placees dans l’environnement, la simulation peut commencer.
25 40 55km
Probabilité
65 80 95 105 120 135
Fig. 3.14 – Lois normales gerant l’apparition des menaces.
Dans ce type de simulation, nous avons simule l’incertitude quant a la detection
des menaces qui entrent dans le rayon d’action du radar. Ainsi, lorsqu’une menace
entre dans le rayon d’action du radar, la distance a laquelle cette menace est detectee
est determinee a l’aide d’une loi normale N(60, 13) tel que presentee a la figure 3.15.
Chapitre 3. Simulation et methode Monte-Carlo 52
De cette facon, l’incertitude de detection des menaces est mieux representee. En effet,
20 60 80 100 km
Probabilité
Fig. 3.15 – Loi normale gerant la detection des menaces.
lorsqu’une menace entre dans le rayon du radar, il y a peu de chances qu’elle soit
detectee instantanement. Plus elle avance dans le rayon du radar, plus elle a de chances
de se faire detecter. Dans une telle simulation, la difficulte vient du fait que lorsqu’une
nouvelle menace apparaıt, la fregate doit creer un nouveau plan qui inclut cette nouvelle
menace, ce qui n’est pas toujours evident. Le reste de la simulation complexe se deroule
comme une simulation simple. Nous faisons avancer les menaces tout en executant le
plan de defense pour finalement en recolter les resultats.
3.4.5 Utilitaire de tests et compilation des resultats
Afin de pouvoir faire des tests en grande quantite, dans le but d’avoir des resultats
d’une grande precision, nous avons incorpore au simulateur un utilitaire nous permet-
tant d’effectuer des tests en grande quantite. Dans le simulateur, cet utilitaire se presente
tel que vu dans la figure 3.16. Il permet d’effectuer plusieurs fois le meme scenario avec
des algorithmes differents. Il permet precisement de choisir :
1. la duree des simulations (critere d’arret),
2. le nombre de scenarios differents que nous voulons tester,
3. le nombre de fois que chaque scenario sera repete,
4. le nombre de menaces qui se retrouveront dans les scenarios,
5. le nombre de fregates (1 dans notre cas),
6. les algorithmes de planification et de mouvement,
7. le fichier ou seront sauvegardes les resultats.
Les resultats sont sauvegardes dans un fichier Excel. Pour chaque scenario, nous
conservons les donnees suivantes :
1. le numero du scenario,
Chapitre 3. Simulation et methode Monte-Carlo 53
Fig. 3.16 – Utilitaire pour faire des bancs de tests
2. le nombre de menaces,
3. les algorithmes de planification et de mouvement,
4. le nombre d’impacts sur la fregate,
5. le nombre de fregates detruites (1 ou 0 dans notre cas),
6. le nombre de SAM planifies,
7. le nombre de SAM lances,
8. le nombre de menaces detruites par un SAM,
9. le nombre de Gun planifies,
10. le nombre de Gun lances,
11. le nombre de menaces detruites par un Gun,
12. le nombre de CIWS planifies,
13. le nombre de CIWS lances,
14. le nombre de menaces detruites par un CIWS,
15. le nombre de Jammer planifies,
16. le nombre de Jammer utilises,
17. le nombre de menaces deviees par un Jammer,
18. le nombre de Chaff planifies
Chapitre 3. Simulation et methode Monte-Carlo 54
19. le nombre de Chaff lances,
20. le nombre de menaces deviees par un Chaff,
21. le nombre de combos Jammer-Chaff planifies,
22. le nombre de combos Jammer-Chaff utilises,
23. le nombre de menaces deviees par un combo Jammer-Chaff.
Avec toutes ces informations, il est possible de calculer differentes metriques afin
d’evaluer l’efficacite des differents algorithmes de planification et de mouvement. De
plus, le fait d’avoir ces informations dans un fichier Excel permet de calculer tres faci-
lement les moyennes, ecarts-type, etc. Ainsi, il est possible de verifier si le nombre de
SAM planifies est egal au nombre de SAM lances. Cette facon de faire nous a permis de
valider nos resultats, de cibler certains problemes (par exemple, il arrivait que certaines
actions invalides etaient planifiees) et de les regler.
3.5 Utilisation de la methode Monte-Carlo dans le
simulateur NDS
Nous avons pu voir que le simulateur NDS developpe dans le cadre du projet NE-
REUS repondait aux caracteristiques de simulation par la methode de Monte-Carlo.
Si l’on regarde la definition donnee a la section 3.3.1, le simulateur tente en effet de
calculer une valeur numerique (l’efficacite des differents algorithmes de planification
et de mouvement) a l’aide de procedes aleatoires (la creation de divers scenarios ou
les menaces apparaissent de facon aleatoire dans l’environnement). Comme il n’est pas
possible de calculer theoriquement l’efficacite des algorithmes, le simulateur cree des
scenarios aleatoires dans le but de generer le plus de situations possibles afin de voir
comment se comportent les algorithmes face a ces situations. Par la suite, il est possible
d’approximer l’efficacite des algorithmes. Tel que nous allons voir au chapitre 4, il y a
deux principales metriques utilisees pour l’evaluation de l’efficacite : le taux de survie
de la fregate et le pourcentage de menaces detruites.
Le taux de survie se calcule de la facon suivante. Il suffit simplement de verifier a
la fin de chacune des simulations si la fregate a survecu aux attaques et de suivre le
principe de la “cible” comme explique a la section 3.3.2. Nous aurons donc un graphique
comme la figure 3.17. Il suffit par la suite de calculer le nombre de fois que la fregate a
survecu par rapport au nombre de scenarios executes. Pour calculer le pourcentage de
menaces detruites, nous utilisons encore une fois le principe de la “cible” mais de facon
un peu differente. Lors d’un scenario contenant n menaces, la fregate peut detruire
Chapitre 3. Simulation et methode Monte-Carlo 55
Survécu Pas survécu
Fig. 3.17 – Calcul de la probabilite de survie avec des simulations
un nombre de menaces contenu dans l’ensemble {0, 1, 2, ..., n}. Nous aurons donc une
cible telle qu’illustree a la figure 3.18. A la fin de chaque scenario, nous placons notre
0
1
2
n
...
Fig. 3.18 – Calcul du pourcentage de menaces detruites avec des simulations.
“score” (le nombre de menaces detruites) sur la cible. Ainsi, il est possible de calculer
la probabilite de detruire un certain nombre de menaces en calculant le nombre de fois
que l’on a detruit ce nombre de menaces par rapport au nombre total de simulations.
Si l’on pose S comme etant le nombre de scenario, le pourcentage de menaces detruites
sera la moyenne de notre score sur les S tentatives. Cela se calcule comme suit :
Pourcentage de menaces detruites =
∑Si=1
xi
nS
ou xi est le nombre de menaces detruites pendant le scenario i. A noter que la somme
represente le total de menaces detruites et nS represente le maximum possible du
total de menaces pouvant etre detruites. Ce calcul represente l’esperance du nombre de
menaces qui seront detruites.
Chapitre 3. Simulation et methode Monte-Carlo 56
3.6 Sommaire
Dans ce chapitre, nous avons expose une partie de la theorie sur la simulation, en par-
ticulier la simulation par evenements discrets. Nous avons montre comment fonctionnait
un simulateur par evenements discrets et nous en avons donne quelques exemples. Nous
avons aussi explique la methode de Monte-Carlo et donne deux exemples d’application
de cette methode. Enfin, nous avons explique le simulateur developpe au DAMAS dans
le cadre du projet NEREUS. Nous avons montre comment ce simulateur pouvait valider
les recherches du projet NEREUS dans le but d’atteindre les objectifs fixes. Dans le
prochain chapitre, nous exposons les recherches effectuees pour le positionnement de la
fregate et nous proposons une nouvelle strategie de positionnement.
Chapitre 4
Positionnement de la fregate
4.1 Introduction
Lors d’attaques aeriennes, le but de la fregate est de se defendre le mieux possible
en construisant un plan de defense qui maximisera ses chances de survie. En raison
de certaines restrictions des ressources, il y a certains secteurs de defense ou certaines
ressources ne sont pas disponibles (voir annexe). Des lors, avant de construire un plan
de defense, la fregate doit se positionner afin de pouvoir maximiser l’utilisation de ses
ressources.
Toutefois, plusieurs questions peuvent survenir a ce moment : Quelles sont les posi-
tions possibles ? Comment savoir si une position est meilleure qu’une autre ? Comment
traiter tous les cas possibles de positionnement tout en ayant une charge de calcul rai-
sonnable ? Comment donner une reponse de bonne qualite dans un delai suffisamment
court ?
Comme on l’a vu dans le chapitre 2, lorsque la fregate detecte que des missiles
ennemis l’attaquent, elle doit elaborer un plan de defense. Ce plan de defense comprend
3 etapes :
1. Choix de la position de la fregate
2. Elaboration du plan Hardkill
3. Elaboration du plan Softkill
Ce chapitre traite de la premiere etape alors que le chapitre suivant traitera des
etapes 2 et 3.
Chapitre 4. Positionnement de la fregate 58
Pour traiter la premiere etape, nous presentons une methode pour positionner ef-
ficacement la fregate en cas d’attaque aerienne. Nous commencerons tout d’abord par
exposer un modele permettant de reduire la complexite de calcul lors du choix de la
position. A cet effet, nous proposerons une preuve demontrant que notre modele permet
de traiter tous les cas possibles de rotation. Nous donnerons egalement une heuristique
qui evalue la qualite d’une position en fonction des menaces qui attaquent la fregate. Par
la suite, nous ferons l’analyse de l’algorithme de positionnement propose. Finalement,
nous terminerons ce chapitre en exposant les resultats obtenus et en donnant differentes
idees qui pourraient etre utilisees dans le futur afin d’ameliorer le positionnement de la
fregate.
4.2 Modele pour reduire la complexite de calcul lors
du positionnement
Comme on l’a explique precedemment, l’agent doit commencer par choisir la position
que doit prendre la fregate afin d’ameliorer les chances de survie de celle-ci. Cette section
presente le modele d’allocation de ressources que nous avons cree afin de reduire la
charge de calcul lors du positionnement. Tout d’abord, commencons par donner une
definition qui sera fort utile tout au long de ce chapitre.
4.2.1 Definition
Une combinaison menaces-secteurs est un ensemble de n couples formes de la facon
suivante :
(1, s1), (2, s2), (3, s3), ..., (n, sn) ou 1 ≤ si ≤ 12 pour 1 ≤ i ≤ n
La premiere coordonnee represente l’identifiant unique (ID) de la menace et la deuxieme
coordonnee represente le secteur ou se trouve cette menace.
Les combinaisons menaces-secteurs constituent un bon moyen de faire un lien entre
les menaces attaquant la fregate et les ressources disponibles pour se defendre. En effet,
le fait de jumeler les menaces avec les secteurs de defense revient en fait a jumeler les
menaces avec les ressources disponibles du secteur ou elle se trouve. Par la suite, il
reviendra au planificateur des actions de defense de decider quelle ressource devra etre
utilisee sur cette menace.
Chapitre 4. Positionnement de la fregate 59
4.2.2 Exemple
La figure de gauche de la figure 4.1 presente une situation de depart ou il y a
3 menaces dans l’environnement. En faisant une rotation de la fregate de 50◦, nous
obtenons la situation de la figure de droite. Ces 2 situations donnent les 2 combinaisons
menaces-secteurs suivantes :
ID Menace 1 2 3
ID Secteur 1 6 7
Rotation de 50o
ID Menace 1 2 3
ID Secteur 2 7 9
10
1560
o
120
145
170
190
215
240
300
345
350
14
710
2
3
5
6
89
11
12
40
280
205
1
2
3
10
15
60120o
145
170
190
215
240 300
345
350
1
4
7
10
2
3
5
6
8
9
11
12
90
330
255
1
2
3
Rotation de 50 Situation de départ
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o oo
o
o
o
o
o
o
o
o
o
o
o
o
Fig. 4.1 – Exemple de 2 combinaisons menaces-secteurs
4.2.3 Generateur de combinaisons menaces-secteurs
(GenTSC )
Tout d’abord, precisons que GenTSC est l’acronyme pour “Threats-Sectors Com-
binations Generator” et qu’il sera utilise tout au long de ce chapitre afin de designer le
generateur de combinaisons menaces-secteurs.
La raison qui nous pousse a utiliser GenTSC est la suivante. Supposons que nous
partons de la situation initiale avec un certain nombre de menaces qui attaquent la
fregate. Pour pouvoir traiter tous les cas possibles de rotation, il faudrait considerer
toutes les rotations incluses dans l’intervalle [−180, 180] et regarder toutes les com-
binaisons menaces-secteurs generees. Cependant, il n’est pas possible en pratique de
considerer toutes les rotations dans un intervalle de nombres reels.
Chapitre 4. Positionnement de la fregate 60
Une idee serait donc de parcourir l’intervalle avec de petits increments, 0.5 par
exemple. Or, comment peut-on s’assurer que l’on genere toutes les combinaisons pos-
sibles. En effet, il se pourrait que les 3 rotations suivantes, 31◦, 31.3◦ et 31.5◦, generent
3 combinaisons differentes. Dans ce cas, la combinaison generee par une rotation de
31.3◦ ne serait pas consideree si on ne considere que des increments de 0.5◦.
De plus, avec une telle approche, il y aurait sans doute plusieurs combinaisons
redondantes qui feraient perdre beaucoup de temps de calcul et nous savons que le
temps disponible pour donner une reponse est tres court. GenTSC est un algorithme
permettant de generer toutes les combinaisons menaces-secteurs sans toutefois creer de
la redondance. Nous commencons par donner l’algorithme et nous donnons ensuite la
preuve que cet algorithme genere toutes les combinaisons possibles.
Premierement, nous devons preciser que la vitesse de rotation de la fregate ainsi
que le temps disponible pour la rotation sont connus. Donc, nous savons la rotation
maximale, notee Rmax, que peut effectuer la fregate pour son positionnement. A noter
que cette rotation peut s’effectuer autant dans le sens horaire que dans le sens anti-
horaire. Voici la facon de proceder pour generer les combinaisons.
Pour chaque menace attaquant la fregate, nous regardons dans quel secteur se re-
trouverait cette menace si la fregate faisait une rotation de Rmax. Nous faisons de meme
pour une rotation de −Rmax. Nous obtenons donc, pour chaque menace, l’ensemble Si,
ou i represente l’ID de la menace, des secteurs dans lesquels pourraient se retrouver
cette menace. Pour chaque secteur de l’ensemble Si, nous simulons une rotation de la
fregate qui amenerait la menace i au debut de ce secteur 1.
Le fait d’amener les menaces au debut des secteurs jouera un role important dans
la construction de la preuve qui suit. Cette methode suggere donc un maximum de 12
positions par menaces. Soit n le nombre de menaces, nous aurons donc un maximum de
12n positions suggerees par GenTSC. A noter que 12n positions sont suggerees lorsque
la valeur de Rmax s’approche de 180◦.
Dans la figure 4.2, nous pouvons voir un exemple dans lequel nous amenons la
menace au debut du secteur 2. Pour ce faire, nous simulons une rotation de la fregate
de 60◦. Comme l’angle de la menace est relatif a la position de la fregate, une rotation
positive de la fregate engendre une diminution de l’angle de la menace relativement a
la fregate.
1Le debut d’un secteur est l’angle que nous obtenons lorsque nous entrons dans ce secteur en faisant
une rotation anti-horaire autour de la fregate.
Chapitre 4. Positionnement de la fregate 61
10
15o
60o
120o
145o
170o
190o
215o
240o 300
o
345o
350o
1
4
7
10
2
3
5
68
9
11
12
o
75o
10o
15o
60o
120o
145o
170o
190o
215o
240o
300o
345o
350o
1
4
7
10
2
3
5
6
89
11
12
Rotation de 60 o
Situation de départ
15o
Fig. 4.2 – Rotation pour amener la menace dans le secteur 2.
Proposition 1
La liste des positions suggerees par GenTSC nous donnera l’ensemble de toutes les
combinaisons menaces-secteurs possibles selon la position de depart des menaces et le
temps disponible pour la rotation.
En d’autres mots, peu importe la valeur de la rotation, comprise dans l’intervalle
[−Rmax, Rmax], la combinaison menaces-secteurs obtenue avec cette rotation peut aussi
etre obtenue avec une des rotations suggerees par GenTSC.
Preuve de la Proposition 1
Prenons une combinaison menaces-secteurs quelconque qui peut etre atteinte avec le
temps disponible pour la rotation. Cette combinaison quelconque est representee dans
la table 4.1. Prouvons que cette combinaison peut etre atteinte avec une des rotations
suggerees par GenTSC.
ID menace 1 2 3 ... n
ID secteur s1 s2 s3 ... sn
Tab. 4.1 – Representation de la combinaison menaces-secteurs quelconque a atteindre.
Pour chacune des menaces, definissons les variables suivantes (voir figure 4.3 pour un
exemple) :
si : le secteur ou se trouve la menace i
Chapitre 4. Positionnement de la fregate 62
θi : l’angle du debut du secteur si
di : l’angle d’attaque de la menace i relativement a la fregate
∆i = di − θi
90o
50o1
2
3
∆1
∆2
∆3
Exemple de combinaison
Frontière
Direction menace
Rotation de ∆ 3
1
2
3
1
4
7
10
2 3
5
6
8
9
11
12 1
4
7
10
23
5
6
8
9
11
12
10o
15o
60o120o
145o
170o
190o
215o
240o 300o
345o
350o
205o
120o
60o
15o
10o
350o
345o
300o
240o215o
190o
170o
145o
Fig. 4.3 – Exemple de combinaison a atteindre et rotation de ∆min.
Donc, dans l’exemple de la figure 4.3, les variables prendraient les valeurs suivantes :
ID menace si θi di ∆i
1 1 60 90 30
2 2 15 50 35
3 9 190 205 15
Tab. 4.2 – Valeur des variables pour l’exemple de la figure 4.3.
A partir de la combinaison menaces-secteurs du tableau 4.1, definissons aussi
∆min = min1≤ i≤n
(∆i)
Considerons j = i tel que ∆i = ∆min.
Donc, j represente l’ID de la menace ayant le plus petit ∆i. Dans l’exemple de la figure
4.3, j serait egal a 3 et ∆min serait egal a 15.
En faisant une rotation de la fregate de ∆j, l’angle d’attaque de la menace j deviendra
egal a l’angle du debut de la zone sj. Donc, apres une rotation de ∆j, nous aurons
dj = θj.
Chapitre 4. Positionnement de la fregate 63
De plus, comme ∆j = min1≤ i≤n
(∆i), nous pouvons affirmer qu’avec la rotation ∆j, au-
cune menace ne changera de secteur et que la combinaison menaces-secteurs restera
inchangee.
Finalement, comme dj = θj (qui est la condition pour generer une combinaison avec
GenTSC ) et que la combinaison menaces-secteurs peut etre atteinte avec le temps dis-
ponible, nous pouvons affirmer que cette combinaison est atteinte avec une des positions
suggerees par GenTSC.
C.Q.F.D.
4.3 Heuristique PNH
Maintenant que nous avons genere toutes les combinaisons menaces-secteurs pos-
sibles a l’aide de GenTSC, nous devons savoir quelle combinaison est la moins dange-
reuse. Autrement dit, face a quelle combinaison nos chances de survie sont les meilleu-
res ? Dans cette section, nous proposons une heuristique qui nous permet d’evaluer la
qualite des combinaisons pour pouvoir par la suite les classer. Avant de donner l’heu-
ristique, nous commencons par expliquer le module d’apprentissage que nous avons
construit et qui sera utilise pour le calcul de l’heuristique.
4.3.1 Module d’apprentissage
Comme nous l’avons explique au chapitre 2, nous avons divise la zone de defense de
la fregate en 12 secteurs. Cette division provient des restrictions de certaines ressources.
Ainsi, les 12 secteurs n’ont pas tous les memes ressources disponibles. La figure 4.4 nous
fait un rappel de la division de la zone de defense en 12 secteurs et la table 4.3 nous
enumere les ressources disponibles dans chacun des secteurs.
Comme il est tres difficile de calculer theoriquement l’efficacite de defense de chacun
des secteurs, nous avons cree un module d’apprentissage statistique qui nous donnera
un estime de l’efficacite de chacun des secteurs. Le calcul de l’efficacite des secteurs cor-
respond au pourcentage de menaces qui ont ete detruites par la fregate. La construction
du module d’apprentissage s’est faite comme suit. Nous avons fait des simulations pour
tester l’efficacite de defense de chaque secteur. Pour chaque secteur, nous avons fait
8 000 simulations par nombre de menaces. Le nombre de menaces variait entre 1 et
Chapitre 4. Positionnement de la fregate 64
Stir
CIWS
Jammer
Gun
10o
15o
60o
120o
145o
170o
190o
215o
240o 300
o
345o
350o
1
4
7
10
2
3
5
6
8
9
11
12
Fig. 4.4 – Secteurs engendres par la restriction des ressources.
Secteurs Ressources disponibles
1, 7 SAM, Gun, CIWS, 1 Jammer, 2 STIRs
2, 6, 8, 12 SAM, Gun, CIWS, 1 Jammer, 1 STIR
3, 5 SAM, Gun, 1 Jammer, 1 STIR
4 SAM, Gun, 2 Jammers, 1 STIR
9, 11 SAM, CIWS, 1 Jammer, 1 STIR
10 SAM, CIWS, 2 Jammers, 1 STIR
Tab. 4.3 – Ressources disponibles dans chacun des secteurs.
8. La raison pour laquelle nous n’avons pas teste pour plus de 8 menaces est que les
simulations effectuees afin de tester les planificateurs contiennent de 1 a 8 menaces. Il
n’etait donc pas necessaire de connaıtre l’efficacite des secteurs pour plus de 8 menaces.
Donc, nous avons fait un total de 64 000 simulations par secteur. Comme certains
secteurs ont les memes ressources, nous n’avons pas teste tous les secteurs. Par exemple,
l’efficacite du secteur 7 est la meme que celle du secteur 1 car ils ont les memes res-
sources. Nous avons donc pris les resultats du secteur 1 pour le secteur 7.
Une simulation se deroulait comme suit. Les menaces apparaissaient dans le secteur
a tester et elles apparaissaient aleatoirement entre 25 et 75 km de la fregate. La fregate
ne bougeait pas puisque le but etait de tester l’efficacite d’un secteur en particulier.
Chapitre 4. Positionnement de la fregate 65
La fregate se defendait donc avec les ressources disponibles dans le secteur a tester. Le
plan de defense etait construit avec le planificateur deliberatif explique dans le chapitre
2. Il n’y avait aucune menace dans les autres secteurs. A la fin de la simulation, nous
calculions le pourcentage de menaces detruites. Ainsi, les resultats du module d’appren-
tissage correspondent a la moyenne de menaces detruites dans les 8 000 simulations. La
table 4.4 presente les resultats du module d’apprentissage et la figure 4.5 presente les
resultats sous forme graphique.
Secteurs \ Nb menaces 1 2 3 4 5 6 7 8
1, 7 95.52 95.64 94.95 94.30 93.04 91.75 90.82 89.57
2, 6 ,8 ,12 95.46 94.58 93.12 91.37 90.52 88.60 87.60 86.31
10 94.75 93.33 92.52 91.53 90.70 89.66 88.57 87.82
9, 11 94.36 93.11 92.53 91.17 89.59 88.39 87.05 85.97
4 91.19 88.17 85.69 82.92 80.85 78.23 76.65 74.56
3, 5 91.56 87.99 85.29 81.84 78.85 75.71 73.17 70.59
Tab. 4.4 – Resultats du module d’apprentissage.
70
75
80
85
90
95
1 2 3 4 5 6 7 8
Nombre de menaces
Men
aces d
étr
uit
es (
%)
Secteurs 1, 7
Secteurs 2, 6, 8, 12
Secteur 10
Secteurs 9, 11
Secteur 4
Secteurs 3, 5
Fig. 4.5 – Graphique des resultats du module d’apprentissage.
4.3.2 Discussion sur les resultats du module d’apprentissage
Nous allons maintenant tenter de justifier que certains secteurs sont meilleurs que
d’autres. Tout d’abord, il convient d’observer une tendance generale pour les secteurs
3, 4 et 5. En raison de l’absence de l’arme a courte portee (CIWS), ces secteurs sont
Chapitre 4. Positionnement de la fregate 66
toujours moins efficaces que les autres peu importe le nombre de menaces. En effet, le
CIWS est l’arme utilisee en dernier recours et permet souvent de detruire des menaces
qui n’ont pas ete detruites, par le SAM ou le GUN, ou qui n’ont pu etre deviees par le
Chaff ou le Jammer. Il convient egalement de remarquer qu’a partir de 4 menaces, la
difference entre le secteur 4 et les secteur 3 et 5 devient plus significative. Cela est cause
par la presence de 2 Jammers dans le secteur 4 qui permettent de devier 4 menaces
simultanement. Un raisonnement semblable explique pourquoi, a partir de 4 menaces,
le secteur 10 devient plus efficace que les secteurs 2, 6, 8, 9, 11 et 12.
Une autre tendance qu’il convient de noter est la suivante. Les secteurs 2, 6, 8 et
12 sont toujours un peu plus efficaces que les secteurs 9 et 11. Cela est du au fait que
le Gun n’est pas disponible dans les secteurs 9 et 11 et diminue donc la qualite de la
defense. Finalement, on peut facilement voir que les meilleurs secteurs sont les secteurs
1 et 7, et ce en raison de la presence de 2 STIRs, ce qui peut les amener a utiliser 2
SAMs simultanement. Comme les SAMs sont les armes hardkill les plus efficaces, ces
secteurs profitent d’une qualite de defense accrue. Cependant, nous devons remarquer
que plus le nombre de menaces augmente, plus la qualite de defense des secteurs 1 et 7
s’approche de la qualite de defense du secteur 10.
Ces resultats montrent tres bien que le nombre de menaces dans un secteur fait
varier la qualite de defense de ce secteur par rapport aux autres secteurs. Ainsi, le choix
du meilleur secteur de defense est dependant du nombre de menaces se trouvant dans
ce secteur.
4.3.3 Choix de la metrique pour l’efficacite des secteurs
Cette section vise a justifier le choix de la metrique qui est utilisee pour calculer
l’efficacite du module d’apprentissage. Une telle metrique calcule le pourcentage de
menaces detruites. Toutefois, on pourrait se demander pourquoi calculer le pourcentage
de menaces detruites plutot que de calculer le taux de survie de la fregate. Nous donnons
ci-apres les raisons qui nous ont pousses a utiliser une telle metrique.
Supposons que nous aurions pris la survie de la fregate comme metrique. Ainsi, nous
aurions verifie a la fin de chaque simulation si la fregate a survecu aux menaces qui l’ont
attaquee. Le resultat de la simulation serait donc une variable booleenne : la fregate a
survecu ou la fregate n’a pas survecu. Donc, pour un scenario tres evolue, le resultat
est un variable booleenne et l’efficacite d’un secteur serait le nombre de scenario ou la
fregate a survecu divise par le nombre de scenario total.
Chapitre 4. Positionnement de la fregate 67
Regardons maintenant les avantages de calculer le nombre de menaces detruites
plutot que la survie de la fregate. Donnons un exemple pour montrer les avantages
(voir table 4.5).
Scenario Metrique des
menaces detruites
Metrique
de survie
A 1/4 = 0, 25 0
B 3/4 = 0, 75 0
Tab. 4.5 – Exemple pour comparer 2 metriques d’evaluation.
Supposons que nous avons 2 scenarios contenant 4 menaces. Dans le premier scena-
rio, la fregate est detruite par la premiere menace alors que dans le 2e scenario, la
fregate detruit les trois premieres menaces mais est detruite par la quatrieme menace.
En regardant la table 4.5, nous voyons qu’un tel scenario donne le meme resultat pour
la metrique de survie de la fregate. Or, il est evident que dans le deuxieme scenario,
la defense de la fregate etait de meilleure qualite. La metrique du nombre de menaces
detruites nous donne donc une evaluation plus precise de la qualite. De plus, l’intervalle
de confiance (voir section 3.2.3) est beaucoup plus petit avec la metrique du nombre
de menaces detruites. A titre d’indicatif, l’intervalle de confiance (avec un niveau de
confiance de 95%) pour le secteur 2 contenant 4 menaces est de 0.3% pour la metrique
du nombre de menaces detruites et de 0.8% pour la metrique de la survie de la fregate.
4.3.4 Calcul de l’heuristique PNH
Tout d’abord, precisons que l’acronyme PNH vient de l’anglais “Potential Number of
Hits”. En d’autres mots, cette heuristique represente l’esperance du nombre de menaces
qui risquent de frapper la fregate. Nous disons qu’elle represente l’esperance puisque, tel
que nous avons vu a la section 2.1.3, dans un environnement stochastique, on ne peut
calculer exactement ce qui va arriver. On calcule plutot l’esperance de ce qui pourrait
arriver. Cette heuristique permet de classer les combinaisons menaces-secteurs pour
savoir quelle est la combinaison qui nous donne le plus de chance de survivre.
Pour evaluer le nombre de menaces qui risquent de frapper la fregate, nous utilisons
les resultats du module d’apprentissage. Pour ce faire, nous devons regarder le nombre
de menaces se trouvant dans chacun des secteurs de defense. Le calcul de l’heuristique
se fait a l’aide de l’equation suivante :
PNH =12
∑
i=1
ni · (1 − H(i|ni)) (4.1)
Chapitre 4. Positionnement de la fregate 68
ou ni represente le nombre de menaces se trouvant dans le secteur i et (1 − H(i|ni))
represente le pourcentage de menaces qui ont frappe la fregate lorsque ni menaces se
trouvaient dans le secteur i. La table 4.3 nous donne les differentes valeurs de H(i|ni)).
Par exemple, s’il y a 4 menaces dans le secteur 9, nous devons aller chercher la valeur de
H(9|4)) qui correspond a 91.17. Comme H(i|ni)) represente le pourcentage de menaces
detruites, nous devons calculer (1 − H(i|ni)) pour obtenir le pourcentage de menaces
qui ont frappe la fregate.
Voici un exemple qui montre comment calculer l’heuristique PNH. Prenons la com-
binaison menaces-secteurs suivante :
ID menace 1 2 3 4 5 6 7
ID secteur 3 9 7 9 4 9 3
ou nous avons :
1 menace dans le secteur 7 ;
2 menaces dans le secteur 3 ;
3 menaces dans le secteur 9 ;
1 menace dans le secteur 4.
Pour cette combinaison, le nombre d’impacts potentiel est :
PNH = (1 ·(1−0.95525))+(2 ·(1−0.87994))+(3 ·(1−0.92525))+(1 ·(1−0.91188))
PNH = (1 · (0.04475)) + (2 · (0.12006)) + (3 · (0.07475)) + (1 · (0.08812))
PNH = 0.59724
4.4 Choix final de la position
Maintenant que nous avons classe les combinaisons menaces-secteurs a l’aide de
l’heuristique PNH, nous devons finalement choisir la position que devra prendre la
fregate afin d’atteindre la meilleure combinaison. Pour ce faire, nous devons nous assurer
que la combinaison est atteignable (une combinaison n’est pas atteignable si le temps
disponible pour la rotation ne permet pas d’atteindre cette combinaison). Si la meilleure
combinaison n’est pas atteignable, nous devons verifier la suivante et ainsi de suite
jusqu’a ce qu’une combinaison puisse etre atteinte.
Chapitre 4. Positionnement de la fregate 69
4.4.1 Methode “Final Positioning” (PosFin)
Partant de la combinaison menaces-secteurs visee, nous savons dans quel secteur
doit se retrouver chaque menace. Ainsi, pour chaque menace, il est possible de calculer
un intervalle de rotation qui amenerait la menace dans son secteur vise. Les bornes de
l’intervalle correspondent aux rotations pour amener la menace au debut et a la fin de
son secteur vise. Cet intervalle sera note [xi, yi] pour la menace i (voir table 4.6).
ID menace 1 2 ... n
ID secteur s1 s2 ... sn
Intervalle [x1, y1] [x2, y2] ... [xn, yn]
Tab. 4.6 – Intervalle de rotation pour chaque menace.
Une fois les intervalles de rotation de toutes les menaces calcules, nous pouvons
evaluer l’intervalle de rotation de la fregate, note [Rstart, Rend]. Une telle evaluation se
fait comme suit :
[Rstart, Rend] = [ max1≤ i≤n
(xi), min1≤ j ≤n
(yj) ] (4.2)
Pour la borne inferieure, nous utilisons max car cela correspond a la rotation mini-
male pour amener chaque menace dans son secteur vise. En effet, si nous n’utilisions
pas max mais plutot une rotation plus petite, il y aurait au moins une menace qui
ne serait pas dans son secteur vise. Par le meme raisonnement, nous pouvons justifier
l’utilisation de min pour le calcul de la borne superieure.
Si la fregate n’a pas le temps de faire la rotation Rstart avec le temps disponible, cela
signifie que la combinaison menaces-secteurs visee ne peut etre atteinte avec le temps
disponible. Dans ce cas, nous devons viser la prochaine combinaison.
Remarque : Comme les combinaisons menaces-secteurs sont generees en simulant une
rotation de la fregate, nous pouvons affirmer que toutes les combinaisons generees
peuvent etre atteintes (sans considerer le temps disponible pour la rotation).
4.4.2 Exemple
Reprenons l’exemple de la figure 4.1. La situation initiale est representee par la
combinaison menaces-secteurs suivante :
Chapitre 4. Positionnement de la fregate 70
ID menace 1 2 3
ID secteur 1 6 7
Voici la combinaison que nous voulons atteindre (la meilleure selon l’heuristique PNH) :
ID menace 1 2 3
ID secteur 2 7 9
Calculons maintenant les intervalles de rotation pour amener chaque menace dans son
secteur vise :
ID menace 1 2 3
ID secteur 2 7 9
Intervalle [30, 75] [30, 90] [40, 65]
Enfin, nous calculons l’intervalle de rotation de la fregate a l’aide de la formule 4.2 :
[Rstart, Rend] = [max(30, 30, 40), min(75, 90, 65)]
[Rstart, Rend] = [ 40, 65 ]
A noter que chaque rotation de la fregate, incluse dans l’intervalle [40, 65], donnera
la combinaison menaces-secteurs visee. La figure 4.6 nous montre la situation initiale,
une rotation de 40◦ et une rotation de 65◦ de la fregate. Nous pouvons voir que c’est la
menace 3 qui a le plus de restrictions et c’est cette menace qui determine les bornes de
l’intervalle.
4.4.3 Avantages de la methode PosFin
Un gros avantage de la methode PosFin est qu’elle retourne un intervalle de rotation
plutot qu’une simple rotation. Cet intervalle permet plus de latitude quant a la rotation
a effectuer. Nous allons illustrer a l’aide d’un exemple comment la methode PosFin peut
permettre d’accroıtre la qualite de la defense de la fregate.
Supposons que la fregate fait face a 2 vagues de menaces qui l’attaquent (un al-
gorithme complet pour traiter plusieurs vagues est propose au chapitre suivant). La
Chapitre 4. Positionnement de la fregate 71
fregate voudrait se positionner pour se defendre face a la premiere vague et se reposi-
tionner par la suite pour se defendre face a la deuxieme vague. Supposons aussi que le
fregate a le temps de faire une rotation de 50◦ avec le temps qui lui est disponible pour
la premiere vague et une rotation de 10◦ avec le temps qui lui est disponible pour la
deuxieme vague. Finalement, supposons que la methode PosFin retourne un intervalle
de rotation de [20, 40] pour se positionner pour la premiere vague et un intervalle de
rotation de [45, 60] pour se positionner pour la deuxieme vague. Voici en quoi le fait
d’avoir un intervalle de rotation peut devenir tres efficace pour la defense.
La fregate pourrait effectuer une rotation de 20◦ pour atteindre sa position afin de
se defendre contre la premiere vague. Cependant, comme la fregate ne peut effectuer
qu’une rotation maximale de 10◦ pour se positionner pour la deuxieme vague, elle ne
pourra pas atteindre la position souhaitee car il faudrait qu’elle effectue une rotation
de 25◦, ce qui n’est pas possible. Or, comme la fregate possede plus de temps pour
se positionner face a la premiere vague, elle pourrait effectuer plutot une rotation de
35◦, ce qui ne changerait en rien la combinaison menaces-secteurs. Cela lui permettrait
par la suite de pouvoir se positionner pour faire face a la deuxieme vague car avec une
rotation de 10◦, cela donnerait une rotation de 45◦ par rapport a la position de depart.
Ainsi, le fait d’avoir un intervalle de rotation permet de pouvoir voir plus loin dans
le temps et de planifier une defense de qualite a plus long terme. Dans le prochain
chapitre, nous allons voir en quoi la methode PosFin combinee avec la methode de
planification proposee permet d’accroıtre la qualite de la defense de la fregate.
Chap
itre4.
Position
nem
ent
de
lafregate
72
10o
15o
60o
120o
145o
170o
190o
215o 240
o
300o
345o
350o
1 4
710
2
3
5
6
89
11
12
1
2
3
Rotation de 65Rotation de 40
10o15
o
60o
120o
145o
170o
190o
215o
240o
300o
345o
350o
1
4
7
10
2
3
5
6
89
11
12
1
2
3
ooSituation initiale
10o
15o
60o120
o
145o
170o
190o
215o
240o 300
o
345o
350o
1
4
7
10
2
3
5
6
8
9
11
12
90o
330o
255o
1
2
3
Fig. 4.6 – Intervalle des rotations possibles pour la fregate.
Chapitre 4. Positionnement de la fregate 73
4.5 Synthese de la methode de positionnement
Dans cette section, nous allons faire un recapitulatif de toutes les methodes qui
ont ete presentees jusqu’a maintenant dans ce chapitre. Ce recapitulatif sera fait en
donnant l’algorithme complet pour le positionnement de la fregate. Par la suite, nous
ferons l’analyse de cet algorithme.
4.5.1 Algorithme complet
Algorithme FRIGATE POSITIONING(listeMenaces, tempsRotation)
Retourne Rstart et Rend les rotations minimum et maximum pour placer la fregate
dans la meilleure position de defense
Entrees : listeMenaces, la liste des menaces attaquant la fregate
tempsRotation, le temps disponible pour la rotation
Variables locales : positionsSuggerees, vecteur contenant la liste des positions
suggerees par GenTSC, vide au depart
Rmax, la rotation maximale que la fregate peut faire en
considerant tempsRotation
positionsSuggerees ← GenTSC (listeMenaces)
POUR TOUT position dans positionsSuggerees FAIRE
Calculer le nombre de menaces dans chaque secteur si la fregate prenait la position
position
Calculer l’efficacite de position avec l’heuristique PNH
FIN POUR
Trier positionsSuggerees selon l’efficacite
REPETER
position ← prochaine position dans positionsSuggerees
[Rstart, Rend] ← PosFin(listeMenaces, position)
JUSQU’A Rstart ≤ Rmax
Retourner Rstart et Rend
4.5.2 Analyse de l’algorithme
La table 4.7 presente l’analyse de l’algorithme FRIGATE POSITIONING. Notons
que le “Nombre d’operations” peut etre multiplie par une constante qui ne sera pas
Chapitre 4. Positionnement de la fregate 74
consideree ici puisqu’elle ne change rien au resultat de l’analyse. En effet, selon le prin-
cipe d’invariance (voir Brassard et Bratley, 1996), deux implantations differentes d’un
meme algorithme ne differeront pas (en efficacite) de plus qu’une constante multiplica-
tive. Ainsi, en considerant que chaque operation elementaire de l’algorithme prend un
temps constant, nous ne changeons pas le resultat de l’analyse.
Pour realiser l’analyse de l’algorithme, nous devons considerer la constante s, qui
represente le nombre de secteurs de defense, ainsi que les variables suivantes :
n : le nombre de menaces au total
T (n) : le temps que prend l’algorithme en fonction de n
Etape Description Nombre
operations
Cout
1 positionsSuggerees ← GenTSC(listeMenaces) ≤ sn ≤ sn
2a POUR TOUT position dans positionsSuggerees ≤ sn
2b Calculer nombre menaces dans chaque secteur n
2c Calculer l’efficacite avec l’heuristique PNH s
≤ sn(n + s)
3 Trier selon l’efficacite (quicksort) sn log (sn) sn log (sn)
4a REPETER ... JUSQU’A ≤ sn
4b [Rstart, Rend] ← PosFin(listeMenaces, position) n≤ sn2
Tab. 4.7 – Analyse de l’algorithme FRIGATE POSITIONING.
Le temps que prend l’algorithme correspond a la somme de ce qui se retrouve dans la
colonne “Cout” de la table 4.7.
T (n) ≤ sn + sn2 + s2n + sn log sn + sn2
T (n) ≤ s(n+n2 + sn + n log sn + n2)
Selon Brassard et Bratley (1996), il existe 2 constantes k et n0 telles que :
T (n) ≤ k(s(n2)) ∀n ≥ n0
Etant donne que, dans notre probleme, le nombre de secteurs de defense est une
constante, nous pouvons redefinir la constante k afin d’inclure la constante s. Ainsi,
nous obtenons :
T (n) ≤ k(n2) ∀n ≥ n0
Donc,
T (n) ∈ O(n2)
Chapitre 4. Positionnement de la fregate 75
4.6 Experimentations
Tel que vu au chapitre 1, les environnements navaux modernes sont tres complexes
du aux technologies de plus en plus sophistiquees. Ainsi, il est tres difficile en pratique
de prouver des concepts dans de tels environnements. Dans notre cas, il est tres difficile
egalement de prouver en pratique les concepts que nous avons developpes. En effet,
chaque simulation couterait plusieurs millions de dollars si elle etait faite reellement.
Dans le projet NEREUS, les idees sont testees sur le simulateur NDS que nous avons
presente au chapitre 3. Cette section donne les resultats obtenus pour les algorithmes
de positionnement de la fregate.
4.6.1 Banc de tests
Plusieurs tests ont ete effectues avec plusieurs metriques d’evaluation. Tout d’abord,
nous avons teste la qualite de la defense de la fregate en mesurant le pourcentage de
menaces qui ont ete detruites lors des simulations. Les tests ont ete effectues avec 3 types
de mouvement : aucun mouvement, mouvement bayesien et mouvement PNH. Lorsqu’il
n’y a aucun mouvement, la fregate garde toujours la meme position et ne bouge pas
du tout. Une telle position immobile a servi de point de comparaison pour voir a quel
point nos algorithmes de mouvement pouvaient ameliorer la defense de la fregate. Le
mouvement bayesien correspond au mouvement bayesien presente au chapitre 2. Le
mouvement PNH correspond a l’algorithme FRIGATE POSITIONING presente dans
ce chapitre.
Pour chaque algorithme de mouvement, nous avons fait des tests avec les 3 planifica-
teurs expliques au chapitre 2 : reactif, deliberatif et deliberatif avec amelioration tabu.
Enfin, nous avons fait des simulations ou il y avait de 1 a 8 menaces qui attaquaient la
fregate. Comme nous avons 3 types de mouvement, 3 types de planificateur et de 1 a 8
menaces, nous avons donc un total de 72 situations differentes. Pour chaque situation,
nous avons fait 5 000 simulations. Nous avons donc fait un total de 360 000 tests pour
mesurer l’efficacite des algorithmes de positionnement.
Nous avons aussi teste le temps que prenait chaque algorithme pour retourner une
reponse. Ces tests ont ete effectues avec le mouvement bayesien et le mouvement PNH.
Il n’etait evidemment pas necessaire de faire ces tests lorsque la fregate ne bougeait pas
puisque dans ce cas, aucun calcul n’est effectue. Les algorithmes ont ete implemente en
Java dans le simulateur NDS.
Chapitre 4. Positionnement de la fregate 76
Les tests ont ete effectues sur un processeur Intel Centrino 1.5 GHz avec 512 Mb de
memoire vive DDR333. Nous avons fait des tests pour 1 a 8 menaces encore une fois.
Pour chaque nombre de menaces, nous avons fait 200 simulations. A chaque simulation,
l’algorithme etait appele 1 000 fois dans le but de diminuer le bruit. A chacune des
200 simulations, nous avons fait la moyenne des 1 000 appels de l’algorithme. Nous
avons fait ensuite la moyenne des 200 simulations. Les resultats correspondent donc a
la moyenne d’un appel a l’algorithme.
4.6.2 Resultats
Les figures 4.7, 4.8 et 4.9 presentent les resultats detailles de l’efficacite de defense des
algorithmes de positionnement. La figure 4.10 presente les memes resultats mais nous
avons fait, pour chaque algorithme de positionnement, la moyenne des 3 planificateurs.
Les resultats correspondent au pourcentage de menaces qui ont ete detruites lors des
simulations. Notons que, dans les graphiques, nous pouvons voir une barre au-dessus
des resultats indiquant l’intervalle de confiance (voir section 3.3.3). Les intervalles de
confiance ont ete calcule pour un niveau de confiance de 99%. La marge d’erreur varie
entre 0,2% et 0,3% selon les resultats.
La figure 4.11 presente les temps moyens pour le mouvement bayesien et le mou-
vement PNH pour retourner une reponse. Les resultats correspondent au temps que
prend un appel a l’algorithme et ce temps est calcule en millisecondes.
4.6.3 Analyse des resultats
Commencons par analyser les resultats regroupes par planificateur. Tout d’abord,
pour le planificateur reactif (figure 4.7), nous pouvons voir que l’algorithme de mouve-
ment n’a pas beaucoup d’influence sur la qualite de la solution. Cela est du au fait que
le planificateur reactif ne produit un plan que pour les 2 menaces les plus proches. Or,
les algorithmes de mouvement tiennent compte de toutes les menaces presentes dans
l’environnement. Ainsi, avec le planificateur reactif, un positionnement de bonne qualite
ne fait pas augmenter la qualite de defense. Nous verrons plus en detail le planificateur
reactif au chapitre suivant et nous expliquerons pourquoi nous avons implemente un tel
planificateur.
Les resultats du planificateur deliberatif et du planificateur deliberatif avec amelio-
ration tabu (figures 4.8 et 4.9) sont tres semblables et c’est pourquoi nous les analyserons
Chapitre 4. Positionnement de la fregate 77
Planificateur réactif
76
80
84
88
92
96
100
1 2 3 4 5 6 7 8
Nombre de menaces
Men
aces d
étr
uit
es (
%)
PNH
Bayésien
Aucun
Fig. 4.7 – Efficacite des algorithmes de mouvement avec le planificateur reactif.
Planificateur délibératif
90
92
94
96
98
100
1 2 3 4 5 6 7 8
Nombre de menaces
Men
aces d
étr
uit
es (
%)
PNH
Bayésien
Aucun
Fig. 4.8 – Efficacite des algorithmes de mouvement avec le planificateur deliberatif.
ensemble. Nous pouvons remarquer une tendance generale ou le mouvement PNH donne
de meilleurs resultats que le mouvement bayesien et que ces 2 algorithmes de mouvement
donnent de meilleurs resultats que lorsque la fregate ne bouge pas du tout. Ces resultats
s’explique de la facon suivante.
Comme on a vu au chapitre 2, le mouvement bayesien evalue les menaces indepen-
Chapitre 4. Positionnement de la fregate 78
Planificateur délibératif avec amélioration tabu
90
92
94
96
98
100
1 2 3 4 5 6 7 8
Nombre de menaces
Men
aces d
étr
uit
es (
%)
PNH
Bayésien
Aucun
Fig. 4.9 – Efficacite des algorithmes de mouvement avec le planificateur deliberatif avec
amelioration tabu.
Efficacité par algorithme de mouvement
(moyenne des 3 planificateurs)
86
88
90
92 94
96
98
100
1 2 3 4 5 6 7 8
Nombre de menaces
Men
aces d
étr
uit
es (
%)
PNH
Bayésien
Aucun
Fig. 4.10 – Efficacite des algorithmes de mouvement (moyenne des trois planificateurs).
damment les unes des autres. En effet, il evalue la probabilite de survie de la fregate
en evaluant la probabilite de detruire les menaces une a une. Or, il est evident que
la probabilite de detruire une menace depend des autres menaces se trouvant dans
l’environnement. Le mouvement PNH donne de meilleurs resultats puisqu’il considere
la dependance des menaces se trouvant dans le meme secteur. En effet, lorsque plusieurs
Chapitre 4. Positionnement de la fregate 79
0
2
4
6
8
1 2 3 4 5 6 7 8
Nombre de menaces
Tem
ps e
n m
illiseco
nd
es
PNH
Bayésien
Fig. 4.11 – Temps utilise par les algorithmes de mouvement pour retourner une reponse.
menaces se trouvent dans le meme secteur, l’evaluation de la qualite de defense se verra
diminuee. Le mouvement PNH traite donc la dependance entre les menaces mais il y a
encore place a l’amelioration. Nous en discuterons dans la section suivante.
Passons maintenant a l’analyse de la moyenne des algorithmes de planification
presentes dans la figure 4.10. Encore une fois, nous pouvons observer une tendance
generale ou le mouvement bayesien donne de meilleurs resultats que lorsque la fregate
ne bouge pas et le mouvement PNH donne de meilleurs resultats que le mouvement
bayesien. Nous pouvons voir que pour 1 et 2 menaces, les mouvements bayesien et
PNH sont semblables. Cela est du au fait que lorsqu’il y a 1 ou 2 menaces, les res-
sources sont beaucoup moins limitees et il y a une moins grosse dependance entre les
menaces. Lorsque le nombre de menaces augmente, nous pouvons voir que le mouvement
PNH donne de meilleurs resultats.
En faisant une comparaison des efficacites de chaque algorithme, voici ce que nous
obtenons. En faisant une moyenne sur 1 a 8 menaces, les pourcentages de menaces
detruites sont les suivants : 92,92% si la fregate ne bouge pas, 93,3% pour le mouvement
bayesien et 93,45% pour le mouvement PNH. Ainsi, relativement a l’efficacite lorsque
le fregate ne bouge pas, le mouvement bayesien ameliore le pourcentage de menaces
detruites de 5,37%. De son cote, le mouvement PNH donne une amelioration de 7,49%.
L’amelioration des algorithmes de mouvement pourrait sembler faible, mais en fait, ce
n’est pas le cas. En effet, plus nous nous approchons de la solution optimale, plus il
Chapitre 4. Positionnement de la fregate 80
est difficile d’ameliorer la solution existante sans tomber dans des charges de calcul
enormes. Donc, lorsqu’il y a peu de place a l’amelioration, une amelioration telle que
nous avons ici est tres satisfaisante.
Enfin, nous terminons l’analyse des resultats en faisant l’analyse des temps de
reponse pour les algorithmes de mouvement presentes dans la figure 4.11. Tout d’abord,
nous pouvons remarquer que le mouvement bayesien donne une reponse plus rapide que
le mouvement PNH. Cependant, en terme d’analyse algorithmique, les 2 algorithmes
ont un temps de reponse qui suivent une courbe de type n2. Cela est logique car, tel que
nous avons vu a la section 4.5.2, l’analyse de l’algorithme PNH donne un algorithme
de l’ordre de n2.
Nous pouvons constater que les temps de reponse sont en dessous de 10 millise-
condes. Ainsi, les reponses sont donnees extremement rapidement. Donc, l’utilisation
de l’algorithme PNH constitue un bon compromis “efficacite-temps de reponse”. L’al-
gorithme est plus efficace sans toutefois etre beaucoup plus lent que le mouvement
bayesien. Dans la section suivante, nous allons discuter de certaines ameliorations que
l’on pourrait apporter au mouvement PNH. Le temps de calcul serait probablement
plus grand mais cela en vaudra surement la peine pour ameliorer l’efficacite.
4.7 Travaux futurs pour le positionnement
Dans cette section, nous allons exposer une limitation des algorithmes expliques
dans ce chapitre. Par la suite, nous donnerons quelques pistes de solution pour pallier
a cette limitation. Ces pistes de solution pourraient contribuer a poursuivre le travail
effectue sur le projet NEREUS depuis plusieurs annees et continuer ainsi a ameliorer
l’efficacite de la defense de la fregate.
4.7.1 Limitation des algorithmes de positionnement
Comme nous l’avons deja esquisse dans ce chapitre, le mouvement bayesien considere
les menaces independamment des autres menaces se trouvant dans l’environnement.
Avec le mouvement PNH, nous avons propose une solution ou la dependance des me-
naces etait traitee. Toutefois, cela n’est pas toujours optimal et il y a encore place a
l’amelioration.
Chapitre 4. Positionnement de la fregate 81
Nous pouvons voir en annexe que les contraintes sur l’armement disponible nous ont
amenes a diviser l’aire de defense en 12 secteurs. Dans cette division, un changement
de secteur correspondait a la limitation d’une ressource. Ainsi, lorsque l’on est dans un
secteur et que l’on change de secteur, nous savons qu’une ressource vient de s’ajouter ou
de s’enlever. Or, plusieurs ressources demeurent inchangees pour des secteurs voisins.
Par exemple, si l’on regarde la figure 4.12, en passant du secteur 8 au secteur 9, on
perd le Gun. Ce changement de secteur est du aux limitations du Gun. Or, les secteurs
8 et 9 auront encore en commun le STIR arriere et le Jammer droit. Ce que nous
voulons montrer en donnant cet exemple, c’est que les secteurs sont dependants car ils
partagent, en general, les memes ressources.
10o
15o
60o
120o
145o
170o
190o
215o
240o
300o
345o
350o
1
4
7
10
23
5
6
8
9
11
12
10
15
60120o
145
170
190
215
240o
300
345
350
1
4
7
10
2
3
5
6
8
9
11
12
Rotation que pourrait proposer PNH Situation initiale
o
o
o
o
o
o
o
o
o
o
Fig. 4.12 – Exemple de cas ou le mouvement PNH ne serait pas optimal.
Le mouvement PNH traite la dependance entre les menaces se trouvant dans le
meme secteur. Donc, la limitation des ressources est consideree mais seulement pour un
secteur a la fois. En prenant l’exemple de la figure 4.12, le mouvement PNH pourrait,
par exemple, avoir tendance a placer une menace dans le secteur 8 et une dans le secteur
9 puisque placer 2 menaces dans le secteur 8 diminuerait la qualite car le mouvement
PNH considere la dependance des menaces se trouvant dans le meme secteur. Or, les
secteurs 8 et 9 utilisent les memes ressources. La seule difference est que le secteur 9
n’a pas de Gun. Ainsi, dans cette situation, il serait preferable d’avoir 2 menaces dans
le secteur 8 plutot qu’une menace dans le secteur 8 et une dans le secteur 9.
Cet exemple nous montre qu’il y a une dependance entre les secteurs en raison
des ressources partagees par ces secteurs. Cette dependance n’est pas traitee dans le
mouvement PNH et cela constitue une lacune de l’algorithme. Dans la prochaine section,
nous allons proposer des pistes de solution pour pallier a ces lacunes.
Chapitre 4. Positionnement de la fregate 82
4.7.2 Ameliorations possibles
Tel que vu dans la section precedente, les secteurs sont dependants les uns des
autres en raison du partage des ressources. Dans cette section, nous allons proposer des
solutions qui pourraient aider a traiter cette dependance entre les secteurs.
Une premiere solution serait de modifier le module d’apprentissage presente a la
section 4.3.1. Au lieu de faire des simulations en placant des menaces seulement dans le
secteur a tester, nous pourrions faire des simulations en placant des menaces dans les
secteurs voisins et voir comment se comporte la qualite de la defense. Dans le mouve-
ment PNH, l’efficacite constitue une probabilite conditionnelle qui considere le nombre
de menaces dans le meme secteur. Cette nouvelle methode donnerait une probabilite
conditionnelle qui considererait le nombre de menaces se trouvant dans le meme secteur
et le nombre de menaces se trouvant dans les secteurs voisins. Bien sur, avec une telle
strategie, il faudrait explorer pour voir combien de menaces placer dans les secteurs
voisins et voir aussi s’il faut placer des menaces seulement dans le voisin de gauche et
le voisin de droite ou encore placer des menaces dans des voisins plus eloignes.
Une autre solution serait de faire des simulations avec le module d’apprentissage
et d’enlever une ressource dans le secteur a tester. En enlevant cette ressource et en
comparant avec les resultats lorsque toutes les ressources sont disponibles, nous pour-
rions evaluer l’effet qu’a cette ressource sur la qualite de la defense. Ainsi, nous pour-
rions probablement voir que certains secteurs auraient une dependance plus forte avec
d’autres secteurs etant donne qu’ils partagent une ressource ayant un gros impact sur
la qualite de la defense. Par exemple, supposons que le STIR aurait un gros impact sur
la qualite de la defense, nous pourrions affirmer que les secteurs 12 et 2 ne sont pas
tres dependants l’un de l’autre puisqu’ils ne partagent pas le meme STIR. D’un autre
cote, la dependance entre le secteur 2 et le secteur 6 serait beaucoup plus forte que la
dependance entre le secteur 2 et le secteur 12, meme si le secteur 6 est plus loin du
secteur 2 que le secteur 12, car le secteur 2 et le secteur 6 partagent le meme STIR.
Cette methode est une piste qui pourrait mener a un nouvel algorithme qui permettrait
de traiter la dependance entre les secteurs.
4.8 Sommaire
Dans ce chapitre, nous avons presente une facon de modeliser le probleme de posi-
tionnement de la fregate qui a permis de diminuer considerablement la charge de calcul
Chapitre 4. Positionnement de la fregate 83
pour le positionnement. Ce modele nous a permis de traiter tous les cas possibles sans
toutefois tomber dans une charge de calcul demesuree. Nous avons aussi propose une
heuristique qui nous permet d’evaluer la qualite d’une position en considerant les me-
naces se trouvant dans l’environnement. Par la suite, nous avons donne une methode
permettant de trouver un intervalle de rotation pour le positionnement qui donne plus
de latitude lors du positionnement. Nous avons fait une synthese de la methode proposee
en donnant l’algorithme complet et en faisant l’analyse de cet algorithme.
Enfin, nous avons expose les resultats de nos experimentations. Ces resultats ont
permis de demontrer que la methode proposee ameliore la defense de la fregate tout
en ayant un temps de reponse en dessous de 10 millisecondes. Nous avons conclu ce
chapitre en donnant des pistes qui pourraient permettre, dans le futur, d’ameliorer la
methode proposee et de pallier aux lacunes de la methode.
Chapitre 5
Planification des actions de defense
Nous avons presente au chapitre precedent un algorithme pour positionner la fregate
lors d’attaques aeriennes. Lorsque la fregate est bien positionnee, on se doit de construire
un plan de defense qui maximisera nos chances de survie. Soucy (2003) a propose deux
algorithmes de planification : deliberatif et deliberatif avec amelioration tabu. Dans
ce chapitre, nous presentons une approche de planification pouvant utiliser ces deux
algorithmes. Tout d’abord, nous commencons par donner ci-dessous les motivations qui
nous ont conduit a developper une telle approche.
5.1 Objectifs specifiques a atteindre
Les algorithmes deliberatif et deliberatif avec amelioration tabu sont des algorithmes
tres efficaces pour la planification des actions de defense. Cependant, ce sont des algo-
rithmes qui prennent en entree une liste de menaces et produisent un plan de defense
pour cette liste de menaces. Donc, avec une approche de resolution standard, les algo-
rithmes prennent l’ensemble complet de menaces qui se trouvent dans l’environnement
et construisent un plan pour cet ensemble de menaces.
Cette approche de resolution cree certains desavantages pour la defense de la fregate.
Tout d’abord, avec une telle approche, une seule position est trouvee au depart et le plan
de defense est construit en fonction de cette position. Il serait bon, lors d’une simulation,
de pouvoir repositionner la fregate afin de maximiser l’utilisation des ressources. Un tel
repositionnement aurait un impact direct sur la qualite de defense. Or, cela n’est pas
possible avec une approche standard.
Chapitre 5. Planification des actions de defense 85
Ensuite, lorsque des changements surviennent dans l’environnement, ces algorithmes
se voient dans l’obligation de construire un nouveau plan en considerant les change-
ments survenus dans l’environnement. Ainsi, l’ancien plan de defense est abandonne au
complet pour en construire un nouveau. Ces algorithmes ne permettent donc pas une
replanification efficace des actions puisqu’ils replanifient toutes les actions du plan. Il
serait donc bon de pouvoir conserver les actions du plan qui sont considerees comme
“urgentes”.
Enfin, lorsque certaines menaces sont tres proches de la fregate, le plan se doit
d’etre produit tres rapidement. En fait, dans de telles situations d’urgence, il faudrait
que la fregate construise un plan de defense en ne considerant que les menaces tres
dangereuses. Un plan pour les menaces se trouvant plus loin pourrait etre construit par
la suite. En ne considerant que les menaces tres proches, le plan serait produit et mis
a execution plus rapidement. L’efficacite de defense serait donc accrue par une reponse
plus rapide. Or, les deux algorithmes de planification donnes ci-haut planifient pour
l’ensemble complet de menaces. Ainsi, il pourrait arriver que le delai pour retourner
une reponse soit trop grand. L’efficacite de defense serait alors reduite.
En resume, il y a donc trois objectifs specifiques que l’on cherche a atteindre :
1. Repositionnement de la fregate lors de l’execution du plan de defense.
2. Replanification plus efficace (eviter de replanifier au complet).
3. Temps de reponse tres court lorsque des menaces sont proches de la fregate.
On peut voir facilement que l’atteinte de ces trois objectifs specifiques, pour la
planification des actions de defense, pourraient contribuer a ameliorer l’efficacite de la
defense de la fregate. Dans ce chapitre, nous proposons donc une approche permettant
d’atteindre ces objectifs : l’approche diviser pour regner.
5.2 Approche Diviser Pour Regner (DPR)
Lors de la resolution d’un probleme quelconque, il existe plusieurs approches que
nous pouvons utiliser afin de concevoir un algorithme resolvant le probleme. L’approche
vorace et la programmation dynamique en sont deux exemples. L’approche que nous
presentons ici est une approche Diviser Pour Regner (DPR). Nous commencons par
definir l’approche en general pour donner par la suite un exemple d’algorithme utilisant
cette approche. Dans la section suivante, nous expliquons comment nous avons applique
cette approche au projet NEREUS.
Chapitre 5. Planification des actions de defense 86
5.2.1 Definition de l’approche DPR
Plusieurs algorithmes de resolution sont de structure recursive. Pour resoudre un
probleme, ils s’appellent eux-memes une ou plusieurs fois sur des sous-problemes tres
similaires au probleme de depart. Cette facon de resoudre est en fait l’approche DPR.
Voici comment se decompose l’approche DPR :
1. Diviser : on divise le probleme en un certain nombre de sous-problemes. On doit
determiner un seuil (ou critere de division) qui permettra de mesurer lorsqu’il est
necessaire de diviser le probleme ou le sous-probleme.
2. Regner : resoudre le sous-probleme. Lorsque le sous-probleme ne peut etre redivise
(seuil atteint), on le resout a l’aide d’un algorithme ad hoc (algorithme de base
servant a resoudre les sous-problemes).
3. Combiner : on combine les solutions des sous-problemes pour obtenir une solution
complete au probleme initial.
5.2.2 Structure d’un algorithme DPR
Algorithme DPR(x)
Retourne y la solution au probleme x
Entrees : x, le probleme a resoudre
Variables locales : seuil, le seuil pour determiner la division du probleme
SI x assez petit (seuil) ALORS
Retourner ADHOC(x)
SINON
Decomposer x en sous-exemplaires x1, x2, ..., xk
POUR i = 1 a k FAIRE
yi = DPR(xi)
FIN POUR
Combiner les yi pour obtenir la solution y du probleme x
Retourner y
5.2.3 Analyse d’un algorithme DPR general
Lorsqu’un algorithme contient un appel recursif a lui-meme, il est possible d’analyser
cet algorithme a l’aide d’une equation de recurrence decrivant le comportement de
Chapitre 5. Planification des actions de defense 87
l’algorithme. Cette equation de recurrence peut ensuite etre resolue a l’aide d’outils
mathematiques (voir Cormen et al., 2002). Lorsque cette recurrence peut se resoudre,
il est alors possible d’avoir l’ordre exact de l’algorithme. Il peut cependant arriver que
l’on puisse seulement trouver une borne pour les performances de l’algorithme. Dans
une telle situation, nous nous retrouvons a faire une analyse en pire cas ou en meilleur
cas (voir Brassard et Bratley, 1996).
Pour faire l’analyse de l’algorithme, il faut trouver l’equation de recurrence qui decrit
le comportement de l’algorithme. Cette equation prend en compte le temps d’execution
des trois etapes d’un algorithme DPR soit : diviser, regner et combiner. Pour construire
l’equation de recurrence, nous avons besoin de definir les variables suivantes :
1. n : la taille du probleme a resoudre,
2. T (n) : le temps que prend l’algorithme pour resoudre le probleme,
3. F (n) : fonction qui represente le temps que prend la fonction ad hoc pour resoudre
les petites instances (lorsque l’on ne peut rediviser le probleme).
4. D(n) : fonction qui represente le temps que prend l’algorithme pour diviser le
probleme en sous-problemes.
5. C(n) : fonction qui represente le temps que prend l’algorithme pour combiner les
sous-solutions afin d’obtenir la solution finale.
Supposons que lors d’une division, on divise le probleme en a sous-problemes de taillenb, on obtient alors la recurrence suivante pour calculer le temps que prend l’algorithme :
T (n) =
{
F (n) si n est suffisamment petit
aT (nb) + D(n) + C(n) sinon
5.2.4 Exemple d’algorithme DPR : Tri par fusion
Nous donnons ici un exemple classique d’algorithme DPR. Il s’agit d’un algorithme
de tri : le tri par fusion (mergesort). Nous donnons ici l’algorithme ainsi que la fonction
“Fusion” qui est utilisee par l’algorithme. Des explications seront donnees par la suite.
Chapitre 5. Planification des actions de defense 88
Algorithme TriFusion(T [1..n])
Retourne T le tableau trie (retourne en parametre)
Entrees : T [1..n], un tableau de n elements non tries
Variables locales : U [1..1 + bn2c], tableau temporaire qui contiendra la premiere
moitie de T
V [1..1 + dn2e], tableau temporaire qui contiendra la seconde
moitie de T
SI n assez petit ALORS
TriInsertion(T ) // algorithme de tri efficace pour de petites instances
SINON
U [1..bn2c] ← T [1..bn
2c]
V [1..dn2e] ← T [1 + bn
2c..n]
TriFusion(U)
TriFusion(V )
Fusion(T , U , V )
Fonction Fusion(T [1..m + n], U [1..m + 1], V [1..n + 1])
Retourne T le tableau trie compose de la fusion de U et V (retourne en parametre)
Entrees : T [1..m + n], un tableau qui contiendra les elements tries
U [1..m + 1], un tableau trie de m elements
V [1..n + 1], un tableau trie de n elements
( U [m + 1] et V [n + 1] serviront de marqueur de fin de tableau )
Variables locales : i, un compteur pour le tableau U
j, un compteur pour le tableau V
U [m + 1] ← ∞V [n + 1] ← ∞i, j ← 0
POUR k = 1 a m + n FAIRE
SI U [i] < V [j] ALORS
T [k] ← U [i]
i ← i + 1
SINON
T [k] ← V [j]
j ← j + 1
FIN POUR
Cet algorithme prend en entree un tableau de taille n contenant des valeurs a
trier. Il divise le tableau en 2 jusqu’a ce que les sous-tableaux soient assez petits
(voir (Brassard et Bratley, 1996) pour des informations sur le choix d’un seuil optimal).
Chapitre 5. Planification des actions de defense 89
Lorsque le seuil est atteint, on tri les sous-tableaux obtenus a l’aide d’un algorithme
de tri efficace sur de petites instances : le tri par insertion (algorithme ad hoc). Par
la suite, on combine les sous-tableaux tries, avec la fonction “Fusion”, pour obtenir
le tableau de depart trie. L’analyse de l’algorithme TriFusion peut etre trouvee dans
(Brassard et Bratley, 1996) ou (Cormen et al., 2002).
Le schema illustre a la figure 5.1 montre un exemple du fonctionnement de l’algo-
rithme de tri par fusion. Dans cet exemple, nous considerons que les instances doivent
avoir une taille (le seuil) plus petite ou egale a 2 pour etre resolues avec l’algorithme
ad hoc.
3 2 7 4 5 1 6 4
3 2 7 4 5 1 6 4
3 2 6 45 17 4
2 3 4 7 1 5 4 6
Division
Division Division
Séquence initiale
Tri insertion Tri insertion
2 3 4 7 1 4 5 6
Fusion Fusion
1 2 3 4 4 5 6 7
Fusion
Séquence triée
Tri insertion Tri insertion
Fig. 5.1 – Exemple de fonctionnement du tri par fusion.
5.3 Application de DPR a NEREUS
Maintenant qu’est expliquee l’approche diviser pour regner, nous pouvons passer a
son application dans le projet NEREUS. Nous proposons d’appliquer cette approche a la
Chapitre 5. Planification des actions de defense 90
planification des actions de defense. Tout d’abord, pour pouvoir utiliser cette approche,
nous devons determiner :
1. Le critere de division (seuil).
2. L’algorithme ad hoc pour resoudre les petites instances.
3. La fonction pour fusionner les sous-solutions.
5.3.1 Determination du seuil et des sous-ensembles
Pour pouvoir appliquer l’approche DPR au projet NEREUS, nous devons trouver
une facon de diviser le probleme de planification en plusieurs sous-problemes. Voici ce
que nous proposons pour diviser ce probleme.
Tout d’abord, nous considerons le moment d’impact de chacune des menaces. Nous
pouvons donc classer les menaces par ordre de moment d’impact. On parcoure la liste des
menaces en regardant le moment d’impact de deux menaces successives. Si la difference
du moment d’impact entre deux menaces qui se succedent est plus grande qu’une cer-
taine constante, on cree un nouveau sous-ensemble. Bien entendu, plus la constante est
petite, plus il y aura de sous-groupes formes.
Formellement, si on pose hi le moment d’impact de la menace i, le critere pour
diviser en 2 sous-groupes est le suivant :
SI hi - hi−1 > C ALORS diviser en 2 sous-groupes. La menace i − 1 ne sera pas
dans le meme sous-groupe que la menace i.
SINON les 2 menaces sont dans le meme sous-groupe.
Exemple
Supposons que nous avons 8 menaces avec les temps d’impact suivants :
ID menace 1 2 3 4 5 6 7 8
Temps d’impact(s) 5 18 32 56 60 86 94 109
Si la constante pour diviser en sous-groupes est egale a 23 sec, nous aurons les sous-
groupes suivants :
Sous-groupe 1 = { 1, 2, 3 }
Chapitre 5. Planification des actions de defense 91
Sous-groupe 2 = { 4, 5 }Sous-groupe 3 = { 6, 7, 8 }
Dans cet exemple, nous avons choisi une constante egale a 23 sec puisque c’est la
constante qui a ete choisie pour le projet NEREUS. Cette constante represente la duree
de l’action de defense la plus longue a executer, soit le Jammer. En choisissant cette
constante, nous evitons de creer des conflits d’allocation de ressources entre les sous-
groupes. En effet, si on commence une action de Jammer sur la premiere menace du
deuxieme groupe, nous sommes assures que les actions de Jammer du premier sous-
groupe sont terminees. Nous sommes donc assures qu’il n’y a pas de Jammer (ou toute
autre ressource) d’alloue sur une menace du groupe precedent.
5.3.2 Planification pour les sous-groupes
Lorsque la division en sous-groupes est realisee, il convient d’avoir un algorithme ad
hoc qui resout le probleme pour les sous-groupes. Dans notre cas, il y a deux algorithmes
possibles pour resoudre le probleme : deliberatif et deliberatif avec amelioration tabu.
Ces deux algorithmes ont ete developpes par Soucy (2003) et sont expliques au chapitre
2. Comme nous l’avons indique precedemment, le choix de la constante permet d’utiliser
ces deux planificateurs sans se soucier des autres sous-groupes car les planificateurs sont
certains d’avoir toutes les ressources disponibles pour le groupe sur lequel ils planifient.
De plus, avant de construire le plan de defense, il se peut que la fregate ait le temps
de se repositionner. Par exemple, si le delai entre 2 sous-groupes est de 30 secondes, la
fregate possede donc 7 secondes pour se repositionner. Le positionnement peut etre fait
avec le mouvement bayesien explique au chapitre 2 ou encore avec le mouvement PNH
propose au chapitre 4. Donc, avec l’approche DPR, les algorithmes de mouvement et
de planification ne changent pas. Ils sont simplement appliques a des sous-groupes de
menaces plus petits plutot qu’a l’ensemble complet de menaces.
5.3.3 Solution globale
Sachant qu’il n’y aura pas de conflits d’allocation de ressources entre les sous-
groupes, nous pouvons affirmer que tous les sous-plans pourront etre appliques succes-
sivement sans probleme de disponibilite des ressources. Le plan global est donc forme
du choix de la position et du plan de defense pour chacun des sous-groupes. Il est donc
tres facile de fusionner les sous-solutions pour en faire une solution globale.
Chapitre 5. Planification des actions de defense 92
Plus formellement, supposons que nous avons 3 sous-groupes de menaces : S1, S2
et S3. Avec notre approche, il y aura donc un choix de position pour chacun des sous-
groupes, appelons ces positions p1, p2 et p3. Il y aura aussi un sous-plan de defense pour
chaque sous-groupe que nous appelons respectivement D1, D2 et D3. Le plan global est
donc forme comme ceci :
Plan global = p1 ∪ D1 ∪ p2 ∪ D2 ∪ p3 ∪ D3
5.3.4 Algorithme DPR complet
Nous donnons ici l’algorithme DPR complet pour le projet NEREUS. Nous donnons
la version utilisant le planificateur deliberatif. L’algorithme DPR utilisant le planifica-
teur deliberatif avec tabu est le meme, il ne faut que changer l’appel au planificateur
deliberatif par un appel au planificateur deliberatif avec tabu. Il en va de meme pour le
choix de la position, nous pouvons utiliser le bayesien ou le PNH. Voici l’algorithme :
Algorithme DeliberatifDPR(listeMenaces, position)
Retourne planGlobal le plan de defense
Entrees : listeMenaces, la liste des menaces attaquant la fregate
position, la position qu’occupera la fregate au moment d’executer le plan
de defense pour listeMenaces
Variables locales : positionTemp, contiendra la position suggeree par l’algorithme
de positionnement
planTemp, contiendra le plan de defense retourne par l’appel
a l’algorithme deliberatif
listeTemp1, contiendra la premiere sous-liste de menaces
listeTemp2, contiendra la deuxieme sous-liste de menaces
planGlobalTemp, contiendra le plan global retourne par un
appel a DeliberatifDPR
planGlobal, le plan global qui sera retourne
SI aucune division possible pour listeMenaces ALORS
{Algorithme ad hoc}positionTemp ← FRIGATE POSITIONING(listeMenaces)
planTemp ← DELIBERATIF(positionTemp)
Ajouter positionTemp a planGlobal
Ajouter planTemp a planGlobal
Retourner planGlobal
SINON
Chapitre 5. Planification des actions de defense 93
{Diviser}Parcourir listeMenaces et faire une division lorsque possible pour obtenir les sous-
listes listeTemp1 et listeTemp2. {on sait ici que listeTemp1 ne peut etre redivisee}{Algorithme ad hoc}positionTemp ← FRIGATE POSITIONING(listeTemp1 )
planTemp ← DELIBERATIF(positionTemp)
{Appel recursif}planGlobalTemp ← DeliberatifDPR(listeTemp2, positionTemp)
{Fusionner}Ajouter positionTemp a planGlobal
Ajouter planTemp a planGlobal
Ajouter planGlobalTemp a planGlobal
Retourner PlanGlobal
5.3.5 Analyse de l’algorithme DeliberatifDPR
Etant donne que le temps que prend l’algorithme depend de l’entree qu’on lui donne,
nous ferons l’analyse de cet algorithme en faisant une analyse en pire cas et une analyse
en cas moyen.
Analyse en pire cas
Le pire cas survient lorsqu’aucune division de la liste des menaces n’est possible.
Dans ce cas, les temps utilises par chacune des etapes sont ceux-ci :
1. Diviser : on parcoure la liste de menaces au complet, donc Θ(n).
2. Algorithme ad hoc : le positionnement prend Θ(n2) et la planification prend Θ(n),
donc Θ(n2).
3. Appel recursif : aucun appel recursif.
4. Fusionner : aucune fusion.
Donc, en pire cas, le temps pris par l’algorithme est :
T (n) = Θ(n + n2 + n) = Θ(n2)
qui est le meme temps que pour l’algorithme standard.
Chapitre 5. Planification des actions de defense 94
Analyse en cas moyen
Prenons un exemple de cas moyen, le cas ou il y a n menaces qui se divise en 3
sous-groupes de n3
menaces. Dans ce cas, le temps pris par l’algorithme est :
T (n) =
{
F (n) si n est suffisamment petit
3T (n3) + D(n) + C(n) sinon
Dans un tel cas, la fonction D(n) aura le meme cout qu’en pire cas car il faudra
encore une fois parcourir toute la liste de menaces afin d’en faire les divisions, donc Θ(n).
D’autre part, la fonction C(n) prend un temps constant car elle ne fait qu’ajouter la
solution a la liste d’actions a executer, donc Θ(1).
Le gain en temps se trouve dans la fonction F (n) puisque cette derniere est d’ordre
2. Nous justifions ici pourquoi le fait de diviser apporte un gain en temps de calcul.
Nous avons tout d’abord n menaces divisees en 3 sous-groupes contenant respec-
tivement n1, n2 et n3 menaces. Nous savons que :
n = n1 + n2 + n3
Le cout de la fonction F (n) etant de n2, nous aurons, dans notre cas moyen, un
cout de n12 + n2
2 + n32. Nous cherchons donc a prouver que :
n2 ≥ n12 + n2
2 + n32
Si l’on revient a l’equation n = n1 + n2 + n3, on peut elever au carre les deux
cotes de l’egalite. On obtient donc :
n2 = (n1 + n2 + n3)2
En developpant la partie de droite, on obtient :
n2 = n12 + n2
2 + n32 + 2n1n2 + 2n1n3 + 2n2n3
Comme n1, n2 et n3 representent le nombre de menaces dans les sous-groupes,
nous sommes assures qu’ils sont positifs. Donc, les termes n1n2, n1n3 et n2n3 sont
positifs. Cela nous assure que :
n2 > n12 + n2
2 + n32
C.Q.F.D.
Chapitre 5. Planification des actions de defense 95
En faisant des divisions, nous aurons donc un gain lors du calcul de la fonction
ad hoc. Cependant, il est difficile de generaliser (ou calculer) ce gain pour l’analyse
de l’algorithme en general. Nous nous contenterons donc ici de dire que lorsqu’il y a
separations en sous-groupes, il y a un gain en temps de calcul en raison de l’algorithme
ad hoc qui est de l’ordre de n2.
5.3.6 Avantages d’une telle approche
Nous faisons ici un retour sur les objectifs specifiques qui ont ete fixes a la section
5.1. Nous redonnons ici les objectifs en expliquant comment l’algorithme DPR repond
a ces objectifs.
Repositionnement de la fregate
L’approche diviser pour regner permet d’avoir plus de flexibilite lors de la planifica-
tion. Cette approche permet un repositionnement de la fregate entre deux sous-groupes
de menaces qui l’attaquent. Ce repositionnement permet d’avoir un plan qui est en
general plus efficace. De plus, comme nous l’avons vu a la section 4.4.3, l’algorithme
de positionnement presente retourne un intervalle de rotation ou aucune menace ne
changera de secteur. Or, la rotation choisie dans cet intervalle pourrait ne pas etre
la rotation minimale. En effet, la rotation choisie dans cet intervalle pourrait servir a
atteindre plus facilement la position desiree pour le prochain sous-groupe.
Par exemple, supposons que nous avons 2 sous-groupes et que les temps disponibles
pour se positionner sont respectivement de 15 secondes et 5 secondes. Nous savons aussi
que la vitesse de rotation de la fregate est de 3◦/sec. Supposons que l’algorithme de
positionnement suggere un intervalle de rotation de [25, 40] pour se defendre face au
premier groupe et un intervalle de rotation de [50, 60] pour se defendre face au deuxieme
groupe. Dans ce cas, si nous effectuons une rotation de seulement 25◦ pour se positionner
pour le premier groupe, il restera une rotation de 25◦ a faire pour se positionner pour
le deuxieme groupe. Or, le temps disponible pour la deuxieme rotation ne permet pas
de faire une rotation de 25◦. Cependant, si la fregate fait une rotation de 40◦ pour se
positionner face au premier groupe, alors dans ce cas, elle aura le temps de se positionner
pour le deuxieme groupe. La table 5.1 illustre cet exemple.
Cet exemple illustre bien que nous pouvons planifier en considerant les prochaines
etapes de planification. Ainsi, sans changer la planification pour un groupe, on peut
contribuer a faciliter la planification pour le groupe suivant.
Chapitre 5. Planification des actions de defense 96
Sous-groupe 1 Sous-groupe 2
Temps disponible 15 5
Rotation maximale 45 15
Intervalle suggere [25, 40] [50, 60]
Rotation choisie 40 10
Tab. 5.1 – Exemple de rotation choisie en fonction de la prochaine rotation.
Replanification plus efficace
Un autre avantage de cette approche est du point de vue de la replanification.
Lorsque l’algorithme de planification planifie pour le groupe complet de menaces, il
devient difficile de modifier le plan de defense lorsque des changements surviennent.
Avec une approche DPR, il est possible de savoir dans quel sous-groupe un changement
est survenu. Sachant que le plan global est compose de l’union des sous-plans, il devient
donc plus facile de modifier le plan global en modifiant seulement le sous-plan ou un
changement est survenu. D’ailleurs, nous proposons a la section suivante une strategie
de replanification que nous avons applique au projet NEREUS.
Temps de reponse tres court lorsque des menaces sont proches
Nous avons vu a la section 5.3.5, lors de l’analyse en cas moyen, que l’approche DPR
reduisait la charge de calcul en raison d’un algorithme ad hoc de l’ordre de n2. Ainsi,
une telle approche permet un temps de reponse plus court.
Il serait aussi possible de construire un plan de meilleure qualite que celui produit
par une approche standard. En effet, si l’algorithme DPR etait un algorithme a tout
moment, il serait possible d’utiliser les premieres secondes pour planifier seulement pour
le sous-groupe le plus urgent. Des lors, un algorithme ad hoc du type deliberatif avec
tabu pourrait utiliser son temps a optimiser le plan pour les menaces les plus urgentes
plutot que de tenter d’optimiser le plan global. Dans un tel cas, la qualite de la solution
pour les menaces urgentes se verrait donc accrue. Par la suite, lorsque ce plan serait
construit, la fregate pourrait s’occuper de construire un plan pour les autres menaces
tout en mettant a execution le plan pour les menaces urgentes. La figure 5.2 illustre ce
principe.
Cette facon de faire permettrait donc de maximiser l’utilisation du temps pour
ameliorer la qualite de la solution. Cela aurait donc comme consequence d’ameliorer la
qualite globale de la defense. Nous discutons, dans la section 5.7, de la possibilite d’un
algorithme DPR a tout moment.
Chapitre 5. Planification des actions de defense 97
Planification standard
Planification DPR à tout moment
Planification
Exécution
Toutes les menaces
Toutes les menaces
t
t
t
t
ss-ens 1 ss-ens 2 ss-ens 3
ss-ens 1 ss-ens 2 ss-ens 3
Planification
Exécution
Fig. 5.2 – Comparaison des planifications standard et DPR a tout moment.
5.4 Proposition d’une strategie de replanification
Dans un environnement tres dynamique comme celui du projet NEREUS, il faut
savoir s’adapter aux changements survenant dans l’environnement. Ayant developpe
une approche de planification permettant de faire de la replanification, nous proposons
ici une strategie de replanification. Cette strategie de replanification supporte les deux
changements suivants dans l’environnement : apparition d’une menace et disparition
d’une menace.
Nous commencons tout d’abord par expliquer les changements possibles dans la
formation des sous-groupes. Ensuite, nous enumerons les divers cas possibles de chan-
gements qui seront a traiter. Enfin, nous expliquons comment traiter chacun de ces cas.
Nous verrons tres bien le lien entre cette strategie de replanification et la representation
lineaire des contingences presentee a la section 2.2.1.
5.4.1 Modifications possibles des sous-groupes
Afin de bien comprendre les divers cas possibles de replanification, nous nous devons
ici d’expliquer les effets crees par l’apparition ou la disparition d’une menace dans
l’environnement. Voici les consequences possibles sur la formation des sous-groupes de
menaces :
1. Fusion de deux sous-groupes.
2. Defusion d’un groupe.
3. Ajout d’un sous-groupe.
4. Aucun changement sur les sous-groupes.
Chapitre 5. Planification des actions de defense 98
La fusion de deux sous-groupes survient lorsqu’une menace apparaıt entre deux sous-
groupes et qu’il n’est plus possible de separer ces deux sous-groupes. Par exemple,
supposons que nous avons la situation suivante, avec un seuil de 5 sec, qui forme les
deux sous-groupes {1, 2, 3} et {4, 5} :
ID menace 1 2 3 4 5
Temps d’impact(s) 5 7 11 17 20
Si une sixieme menace s’ajoute entre les deux sous-groupes, nous pourrions obtenir
la situation suivante :
ID menace 1 2 3 6 4 5
Temps d’impact(s) 5 7 11 14 17 20
Dans ce cas, il n’est plus possible de diviser en deux sous-groupes. Nous dirons donc
qu’il y a eu fusion des deux sous-groupes de menaces.
La defusion d’un sous-groupe survient lorsqu’une menace du sous-groupe disparaıt
de l’environnement et qu’il devient possible de former deux sous-groupes. Prenons
l’exemple suivant, toujours avec un seuil de 5 sec, qui forme le sous-groupe {1, 2, 3, 4,
5} :
ID menace 1 2 3 4 5
Temps d’impact(s) 5 7 11 14 17
Si la menace 3 disparaıt, il devient possible de separer le sous-groupe pour former
les deux sous-groupes {1, 2} et {4, 5}. Dans ce cas, nous dirons qu’il y a eu defusion
du sous-groupe.
L’ajout d’un sous-groupe survient lorsqu’une menace apparaıt dans l’environnement
mais qu’elle ne peut etre ajoutee a aucun sous-groupe. Par exemple, supposons que nous
avons la situation suivante, avec un seuil de 5 sec, qui forme les deux sous-groupes {1,
2, 3} et {4, 5} :
ID menace 1 2 3 4 5
Temps d’impact(s) 5 7 11 23 25
Chapitre 5. Planification des actions de defense 99
Si une sixieme menace s’ajoute entre les deux sous-groupes, nous pourrions obtenir
la situation suivante :
ID menace 1 2 3 6 4 5
Temps d’impact(s) 5 7 11 17 23 25
Dans ce cas, nous obtenons donc les sous-groupes {1, 2, 3}, {6} et {4, 5}. Nous
dirons donc qu’il y a eu ajout d’un sous-groupe.
Le quatrieme et dernier cas s’explique rapidement. Ce cas survient lorsqu’il y a
apparition ou disparition d’une menace a l’interieur d’un sous-groupe et qu’il n’y a pas
de fusion ou de defusion possible. Dans ce cas, nous dirons donc qu’il n’y a eu aucun
changement dans les sous-groupes.
5.4.2 Divers cas possibles a traiter
Tel que specifie precedemment, les modifications possibles aux sous-groupes sont
classees en quatre categories. Dans cette section, nous enumerons les divers cas pos-
sibles qui devront etre traites par la replanification. Nous verrons par la suite, dans la
section suivante, comment traiter ces divers cas. Les cas sont regroupes par modification
possible sur les sous-groupes. A noter que le premier sous-groupe est toujours un cas
different et nous verrons pourquoi dans la section qui suit. Voici donc les cas possibles :
1. Fusion de sous-groupes
(a) Fusion du premier et du deuxieme sous-groupe.
(b) Fusion de deux sous-groupes n’incluant pas le premier.
2. Defusion d’un sous-groupe
(a) Defusion du premier sous-groupe.
(b) Defusion d’un sous-groupe qui n’est pas le premier.
3. Ajout d’un sous-groupe
(a) Ajout d’un sous-groupe qui devient le premier sous-groupe.
(b) Ajout d’un sous-groupe apres le premier.
4. Aucun changement dans les sous-groupes
(a) Ajout d’une menace dans le premier sous-groupe.
(b) Ajout d’une menace dans un sous-groupe qui n’est pas le premier.
(c) Retrait d’une menace dans le premier sous-groupe.
(d) Retrait d’une menace dans un sous-groupe qui n’est pas le premier.
Chapitre 5. Planification des actions de defense 100
5.4.3 Traitement des divers cas possibles
Maintenant que nous avons enumere les divers cas qui peuvent survenir, nous ex-
pliquons ici la strategie qui nous permet de traiter chacun de ces cas. Bien entendu ici,
certains cas sont traites de la meme facon, c’est pourquoi nous allons les regrouper pour
les explications.
Les cas n’impliquant pas le premier sous-groupe se traitent assez facilement. Ainsi,
les cas 1.(b), 2.(b), 3.(b), 4.(b) et 4.(d) se traitent de la facon suivante. On replanifie
pour tous les sous-groupes en cause ainsi que les sous-groupes suivants. On trouve donc
une nouvelle position et un nouveau plan pour chacun des sous-groupes en cause ainsi
que pour les sous-groupes suivants. Par exemple, s’il y a 4 sous-groupes et qu’il y a
fusion du deuxieme et du troisieme groupe, on replanifie pour le deuxieme sous-groupe
(forme des sous-groupes 2 et 3) et pour le troisieme sous-groupe (qui etait le quatrieme
sous-groupe avant la fusion).
Les cas impliquant le premier sous-groupe, 1.(a), 2.(a), 3.(a), 4.(a) et 4.(c), peuvent
se diviser en deux cas de traitement. Ces deux cas sont les suivants :
1. Le plan pour le premier sous-groupe est entame.
2. Le plan n’est pas entame.
Le deuxieme cas est traite comme les cas n’impliquant pas le premier sous-groupe,
c’est-a-dire que l’on replanifie au complet pour tous les sous-groupes. On peut se per-
mettre de replanifier au complet puisqu’aucune action n’est commencee.
Lorsque le plan est entame, il est tres difficile de modifier des actions dans le plan
sans creer des problemes d’allocation de ressources. De plus, comme la menace est dans
le premier sous-groupe, elle a de bonnes chances d’etre tres proche de la fregate (donc
delai de reponse court). La solution que nous proposons donc est une solution reactive.
S’il s’agit d’un ajout de menace, nous assignons le CIWS (arme courte portee) a cette
menace. De plus, si le temps le permet, on tente de lui assigner un Jammer. Puisque
c’est la ressource la plus abondante (4 canaux), il y a de bonnes chances qu’un canal
soit disponible. S’il s’agit d’un retrait de menace, nous annulons les actions qui etaient
assignees a cette menace. Meme si nous ne l’avons pas implemente, il serait possible
de reassigner a d’autres menaces les ressources qui etaient allouees a la menace qui a
disparue.
Comme on peut le constater, il n’est pas toujours simple de replanifier puisqu’il y a
de nombreux cas a traiter. Nous avons propose ici une strategie qui est simple tout en
etant assez efficace. Cette strategie ne replanifie pas le plan au complet mais bien les
Chapitre 5. Planification des actions de defense 101
sous-plans ou il y a des changements lorsque ces changements surviennent suffisamment
loin de la fregate. Lorsque les changements surviennent tres pres de la fregate, nous
parlons donc de solution reactive ou l’efficacite n’est certes pas optimale. Cependant,
le delai de reponse est tres court ce qui nous assure tout de meme une efficacite non
nulle (ce qui est le but d’une solution reactive). Dans la section qui suit, nous faisons
un parallele entre cette strategie de replanification et la classification des contingences
presentees au chapitre 2.
5.4.4 Retour sur la classification des contingences
Rappelons que dans le chapitre 2, nous avons presente une classification lineaire des
contingences. La figure 5.3 illustre cette classification.
Très urgentPeu important
Rien faire Replanifier Réagir Plan conditionnel
Fig. 5.3 – Classification des contingences.
Nous devons rappeler aussi qu’un plan de contingences ne peut contenir toutes les
contingences possibles. Dans le cadre du projet NEREUS, les contingences qui sont
incluses dans un plan de contingence sont en fait les echecs possibles d’une action de
defense. Ainsi, l’apparition et la disparition de menaces dans l’environnement ne sont
pas traitees dans un plan de contingences.
Pour traiter l’apparition ou la disparition d’une menace, nous devons donc utiliser
d’autres strategies. La strategie de replanification que nous proposons inclut une so-
lution reactive dans le cas d’une contingence tres urgente (une menace apparaissant
proche de la fregate) et une replanification dans le cas d’une contingence moins urgente
(une menace apparaissant suffisamment loin pour nous donner le temps de replanifier).
Donc, nous pouvons voir facilement que l’approche DPR (incluant la strategie de
replanification) traite les contingences selon l’echelle lineaire presentee dans la figure
5.3. Nous exposons dans la prochaine section comment nous avons teste l’approche DPR
et la strategie de replanification que nous venons de proposer.
Chapitre 5. Planification des actions de defense 102
5.5 Experimentations
Nous presentons ici les resultats des simulations realisees. Ces simulations ont ete
realisees afin d’evaluer les differents algorithmes selon plusieurs metriques. Pour obte-
nir certains resultats, nous avons du faire certaines hypotheses simplificatrices sur le
modele.
5.5.1 Hypotheses sur le modele
Pour tester l’efficacite de defense (pourcentage de menaces detruites) des differents
planificateurs (deliberatif, deliberatif avec tabu, deliberatif DPR et deliberatif avec tabu
DPR), nous avons utilise le modele de simulation complexe presente a la section 3.4.4.
En temps normal, dans le modele de simulation complexe, le radar a une portee de 80
km et il detecte les menaces qui entrent dans son rayon d’action selon une loi normale
(tel que presente au chap 3). Or, ce genre de simulation cree beaucoup de changements
(apparition de menaces) dans l’environnement et entraıne donc beaucoup de replanifi-
cation. Comme les planificateurs deliberatif et deliberatif avec tabu ne sont pas efficaces
en replanification, il est difficile de tester ces planificateurs avec le modele de simulation
complexe.
Pour pouvoir comparer l’approche DPR avec une approche standard, nous avons
donc du supposer que toutes les menaces presentes dans l’environnement etaient detec-
tees au debut de la simulation. Cela veut donc dire que nous avons agrandi le rayon
d’action du radar afin d’avoir une vue sur toutes les menaces. En faisant cette sim-
plification, chaque planificateur pouvait creer son plan au debut de la simulation et le
mettre a execution. Ainsi, il devenait plus facile de comparer l’efficacite des differents
planificateurs puisque les planificateurs deliberatif et deliberatif avec tabu n’etaient pas
handicapes par leurs lacunes en replanification.
De plus, comme la constante pour diviser en sous-groupe est grande, il devient
difficile de former des sous-groupes si la densite des menaces est trop grande. En faisant
apparaıtre les menaces sur une plus longue distance, la densite est plus faible et nous
pouvons donc plus facilement les diviser en sous-groupe. Une technique pour reduire la
constante de separation en sous-groupes est proposee a la section 5.7.1.
Chapitre 5. Planification des actions de defense 103
5.5.2 Banc de tests
Nous avons effectue plusieurs types de tests afin d’evaluer nos algorithmes. Tout
d’abord, nous avons teste l’efficacite des algorithmes de planification : deliberatif, deli-
beratif avec tabu, deliberatif DPR et deliberatif avec tabu DPR. L’efficacite etait
mesuree selon le pourcentage de menaces detruites. Ces tests ont ete effectues avec
le modele de simulation complexe explique a la section 3.4.4 en prenant l’hypothese
presentee a la section precedente. Les tests ont ete effectues pour 6, 8, 10, 12, 14 et 16
menaces. Pour chaque algorithme, nous avons fait 3 000 simulations (1 000 par algo-
rithme de positionnement) par nombre de menaces. Les resultats des figures qui suivent
representent la moyenne des trois algorithmes de positionnement.
Nous avons aussi teste la qualite de la replanification. Dans ce cas, nous avons utilise
le modele de simulation complexe sans toutefois utiliser l’hypothese de simplification.
Donc, au debut des simulations, les menaces n’etaient pas toutes visibles. La metrique
utilisee pour la qualite de la replanification correspond au pourcentage d’actions qui
sont conservees dans le plan lors d’une replanification. Nous avons fait des tests pour
6, 8, 10, 12, 14 et 16 menaces. Le planificateur etait le deliberatif DPR. Nous avons
fait 3 000 tests (1 000 par algorithme de positionnement) par nombre de menaces. Les
resultats representent la moyenne pour les trois algorithmes de positionnement.
D’autre part, nous avons effectue des tests sur les planificateurs deliberatif et delibe-
ratif avec tabu afin d’enrichir les resultats obtenus prealablement sur le projet. Nous
avons tout d’abord teste l’amelioration qu’apportait la recherche tabu sur la qualite
de la solution. Cette amelioration est en fonction du nombre d’iterations de la re-
cherche tabu. Elle represente l’amelioration apportee au plan. Une iteration correspond
a un changement effectue sur le plan (ajout ou retrait d’une action). Nous avons teste
l’amelioration tabu pour 1 a 8 menaces et nous avons fait 2 000 simulations par nombre
de menaces.
Enfin, nous avons teste le temps que prenait chaque algorithme pour retourner une
reponse. Nous avons teste le planificateur deliberatif et le planificateur deliberatif avec
tabu. Comme le planificateur deliberatif avec tabu est un algorithme a tout moment,
on ne peut evaluer le temps que prend l’algorithme pour retourner une reponse. Nous
avons donc fixe le nombre d’iterations pour la recherche tabu. Nous avons fait des tests
pour une recherche tabu de 10 iterations et de 25 iterations.
Les tests pour le temps de reponse ont ete effectues sur un processeur Intel Centrino
1.5 GHz avec 512 Mb de memoire vive DDR333. Nous avons fait des tests pour 1 a 8
menaces. Pour chaque nombre de menaces, nous avons fait 200 simulations. A chaque
Chapitre 5. Planification des actions de defense 104
simulation, l’algorithme etait appele 1 000 fois dans le but de diminuer le bruit. A
chacune des 200 simulations, nous avons fait la moyenne des 1 000 appels a l’algorithme.
Nous avons fait ensuite la moyenne des 200 simulations. Les resultats correspondent
donc a la moyenne d’un appel a l’algorithme.
5.5.3 Resultats
La figure 5.4 presente les resultats detailles de l’efficacite de defense des algorithmes
de planification. Les resultats correspondent au pourcentage de menaces qui ont ete
detruites lors des simulations. Notons que dans le graphique, nous pouvons voir une
barre au-dessus des resultats indiquant l’intervalle de confiance (voir chapitre 3.3.3).
Les intervalles de confiance ont ete calcules pour un niveau de confiance de 99%. La
marge d’erreur tourne autour de 0,25%.
Ensuite, la qualite de la replanification est presentee dans la figure 5.5. Cette qualite
represente le pourcentage d’actions conservees dans le plan lorsqu’une replanification
est effectuee.
D’autre part, la figure 5.6 presente l’amelioration de la recherche tabu sur la qualite
du plan en fonction du nombre d’iterations de la recherche.
Enfin, la figure 5.7 presente les temps moyens pour le planificateur deliberatif et le
planificateur deliberatif avec tabu (10 et 25 iterations) pour retourner une reponse. Les
resultats correspondent au temps que prend un appel a l’algorithme et ce temps est
calcule en millisecondes.
5.5.4 Analyse des resultats
Commencons tout d’abord avec la comparaison des algorithmes de planification (fi-
gure 5.4). Nous pouvons voir que le planificateur deliberatif et le planificateur deliberatif
DPR ont un comportement semblable. Nous pouvons aussi remarquer que le planifica-
teur tabu DPR apporte une legere amelioration au planificateur tabu. Bien entendu,
cette amelioration n’est pas tres grande (soit environ 0,25% en absolu). Cependant, il
faut se souvenir que la constante pour diviser en sous-groupe est relativement grande.
Le fait que cette constante soit grande laisse moins de temps pour un repositionnement
entre les sous-groupes. Il est facile de voir que plus le temps pour le repositionnement
sera grand, plus la qualite du plan produit sera amelioree. Donc, en reduisant cette
Chapitre 5. Planification des actions de defense 105
Efficacité par planificateur
(moyenne des 3 mouvements)
80 82
84 86 88 90
92 94
6 8 10 12 14 16
Nombre de menaces
Men
aces
détr
uit
es (
%)
Tabu DPR
Tabu
Délib. DPR
Délibératif
Fig. 5.4 – Comparaison des algorithmes standard avec les algorithmes DPR.
34
36
38
40
42
44
46
48
6 8 10 12 14 16
Nombre de menaces
Ac
tio
ns
co
ns
erv
ée
s (
%)
Fig. 5.5 – Efficacite de la replanification.
constante, l’amelioration de l’approche DPR sera encore plus considerable.
La qualite de la replanification est illustree a la figure 5.5. Nous pouvons voir que
cette qualite s’ameliore lorsque le nombre de menaces augmentent. On peut aussi obser-
ver une tendance qui nous laisse croire que cette courbe pourrait suivre une asymptote
lorsque le nombre de menaces serait tres grand. Le pourcentage d’actions conservees
Chapitre 5. Planification des actions de defense 106
0
1
2
3
4
0 5 10 15
Nombre d'itérations
Am
éli
ora
tio
n
de
la
qu
ali
té
8 menaces
7 menaces
6 menaces
5 menaces
4 menaces
3 menaces
2 menaces
Fig. 5.6 – Amelioration de la recherche tabu.
0
10
20
30
40
50
60
1 2 3 4 5 6 7 8
Nombre de menaces
Te
mp
s e
n m
illi
se
co
nd
es
Tabu25
Tabu10
Délibératif
Fig. 5.7 – Temps utilise par les algorithmes de planification pour retourner une reponse.
est tres considerable. Pour 16 menaces, c’est presque la moitie du plan qui est conserve
lors d’une replanification. Bien entendu, ces resultats sont tres dependants du modele
de simulation, mais ils n’en demeurent pas moins interessants.
Chapitre 5. Planification des actions de defense 107
Ensuite, a la figure 5.6, on peut voir que la recherche tabu plafonne assez rapidement.
En effet, la majorite de l’amelioration se fait lors des 5 premieres iterations. Ces resultats
nous permettent donc de voir qu’il n’est pas necessaire de faire une recherche tabu tres
longue pour obtenir une bonne amelioration. En fait, si l’algorithme a le temps de faire
10 iterations, l’amelioration sera tres considerable.
Enfin, les temps de reponse sont illustres a la figure 5.7. Nous pouvons voir que
le temps de reponse du planificateur deliberatif est lineaire en fonction du nombre de
menaces. De son cote, le planificateur deliberatif avec tabu ne semble pas parfaitement
lineaire. Cela est du a une implementation non optimale de l’algorithme dans le NDS.
On peut aussi observer que la recherche tabu est particulierement longue. Cependant,
comme nous venons de le specifier, 10 iterations de la recherche tabu pourraient suffire
a ameliorer la qualite du plan. Ainsi, nous pouvons affirmer que, pour 8 menaces, un
plan tabu bien ameliore prend environ 32 ms pour etre construit.
5.6 Ameliorations possibles
Tout au long de ce chapitre, nous avons presente une approche pouvant nous ai-
der a resoudre la problematique sur le projet NEREUS. Bien entendu, cette approche
n’est pas parfaite et il y a place a l’amelioration. Nous donnons ici quelques idees
d’ameliorations qui pourraient contribuer a rendre la defense de la fregate encore plus
efficace.
5.6.1 Eliminer l’hypothese simplificatrice
Nous avons vu a la section precedente qu’il a fallu faire des simplifications sur le
modele afin de pouvoir tester notre approche. Nous pensons entre autre au fait que le
radar de la fregate a un rayon d’action plus grand que ce que le modele propose. Cette
hypothese sur le modele a ete faite car nous voulions comparer l’efficacite des planifi-
cateurs standards avec les planificateurs utilisant l’approche DPR. Cette hypothese a
aussi ete faite car nous voulions une plus petite densite de menaces afin de permettre
la division des menaces en plusieurs sous-groupes.
Pour pouvoir eliminer cette hypothese, il faudrait pouvoir diminuer le seuil pour
separer les menaces en sous-groupes. En diminuant ce seuil, il serait possible d’utiliser
l’approche DPR meme si la densite des menaces est plus grande. Dans la section 5.7.1,
Chapitre 5. Planification des actions de defense 108
nous proposons une piste qui pourrait contribuer a eliminer cette hypothese.
5.6.2 Agir tout en positionnant
Nous avons egalement base notre approche sur le fait que lors d’un positionnement,
aucune action n’est executee. Autrement dit, la fregate ne se defend pas en tournant.
Elle tourne puis se defend par la suite, mais ne fait pas les deux en meme temps.
Il serait bien de pouvoir executer des actions de defense tout en tournant. Cela
permettrait d’avoir plus de temps pour se positionner et plus de temps pour agir. En
effet, si le positionnement et la defense etaient faits en parallele, le gain pourrait etre
tres considerable. Encore une fois, dans la section 5.7.1, nous proposons une piste de
solution qui pourrait contribuer a resoudre ce probleme.
5.6.3 Ameliorer la replanification
La strategie de replanification proposee a la section 5.4 pourrait etre amelioree.
Lors de la replanification, cette strategie replanifie pour le sous-groupe ou il y a un
changement et les sous-groupes suivants. Donc, s’il y a un changement dans le sous-
groupe Si, on replanifie pour les sous-groupes Si, Si+1, Si+2, etc. On replanifie pour les
sous-groupes Si+1, Si+2,... au cas ou la position du sous-groupe Si changerait et que la
position planifiee pour le sous-groupe Si+1 deviendrait inatteignable.
Cependant, il pourrait y avoir un critere qui verifie si, selon la nouvelle position du
sous-groupe Si, les positions des sous-groupes suivants demeurent atteignables. S’il est
encore possible d’atteindre ces positions, une replanification ne serait pas necessaire et
les sous-plans pourraient etre conserves.
5.7 Travaux futurs sur la planification
Nous terminons ce chapitre en donnant quelques avenues qui pourraient etre interes-
santes a explorer pour la planification sur le projet NEREUS. Nous donnons quelques
pistes qui pourraient servir a pallier aux problemes dictes a la section precedente.
Chapitre 5. Planification des actions de defense 109
5.7.1 Diminution du seuil pour l’approche DPR
La diminution du seuil pour la separation des menaces n’est pas une tache facile.
La constante que nous avons proposee a la section 5.3.1 correspond a la duree de
l’action la plus longue (Jammer) qui est de 23 sec. Cette constante assure la validite de
toutes les actions et assure la disponibilite de toutes les ressources pour un sous-groupe.
Or, s’il etait possible de diminuer cette constante pour qu’elle prenne la valeur de la
deuxieme action la plus longue (SAM), la constante deviendrait egale a 10,2 sec. Cela
representerait une amelioration considerable.
Le probleme serait de s’assurer que les actions de Jammer ne soient pas invalidees par
un repositionnement de la fregate. Il faudrait aussi verifier la disponibilite du Jammer
lorsque l’on planifie pour un sous-groupe. En effet, il se pourrait que le Jammer soit
alloue pour une menace du sous-groupe precedent.
La diminution de la constante pourrait etre fait de la facon suivante. La planificateur
“softkill” pourrait creer un plan et donner un intervalle de rotation a l’interieur duquel
aucune action de son plan ne serait invalidee. Cet intervalle pourrait etre construit
tout comme l’intervalle de rotation explique a la section 4.4.1. Il suffirait de considerer
toutes les actions du plan et de donner, pour chaque action, un intervalle de validite.
L’intervalle final de validite serait l’intersection de tous les intervalles de validite.
Par la suite, comme le mouvement PNH explique au chapitre 4 retourne un intervalle
de rotation, il serait alors possible de faire l’intersection de l’intervalle de rotation avec
l’intervalle de validite du plan softkill. Ainsi, il serait possible d’executer les actions du
plan softkill tout en tournant la fregate. Il resterait a traiter la dependance entre les
sous-groupes pour ce qui est de la disponibilite du Jammer.
5.7.2 Rendre l’approche DPR a tout moment (anytime)
Nous avons discute a la section 5.3.6 de la possibilite de rendre l’approche DPR a
tout moment. Une telle amelioration serait en effet possible. Il suffirait de retourner la
solution obtenue lorsque l’echeance (deadline) survient. En commencant par planifier
pour les sous-groupes plus proches de la fregate, nous pourrions utiliser tout le temps
qui est a notre disposition afin de planifier pour le sous-groupe le plus urgent. Par la
suite, lorsque le plan le plus urgent serait construit, nous pourrions construire un plan
pour les autres menaces presentes dans l’environnement.
Chapitre 5. Planification des actions de defense 110
Ce principe rejoint encore une fois la classification lineaire des contingences. En effet,
lorsqu’il y a plusieurs menaces dans l’environnement, le fait de planifier seulement pour
les menaces urgentes revient a dire que nous ignorons les menaces moins importantes.
Cela correspond a ignorer les contingences moins importantes (loin de la fregate) pour
le moment pour y revenir plus tard.
5.7.3 Interaction entre les 3 planificateurs
L’idee presentee dans la section precedente est une tres bonne piste pour executer
des actions de defense tout en tournant. En effet, les planificateurs de defense (“hardkill”
et “softkill”) pourraient creer leurs plans et donner les contraintes au planificateur de
position afin que leurs plans demeurent valides. Cette idee permettrait une interaction
plus riche entre les planificateurs.
Il pourrait en effet y avoir des aller-retours entre les planificateurs pour en venir
a un consensus sur le choix de la position. Le probleme pourrait etre ramene a un
probleme de satisfaction de contraintes distribuees ou chaque planificateur tenterait de
satisfaire ses contraintes. Dans un tel cas, chaque planificateur serait un agent et il se
devrait d’y avoir une negociation entre les differents planificateurs pour en arriver a une
solution. Des lors, on aurait a faire a un systeme multi-agents compose de trois agents
(“hardkill”, “softkill” et positionnement) ayant comme but commun de maximiser la
survie de la fregate.
5.7.4 Planificateur de haut niveau
Comme nous avons plusieurs types de planificateurs (reactif, deliberatif, deliberatif
DPR, deliberatif avec tabu, deliberatif avec tabu DPR) ayant chacun leurs forces et
leurs faiblesses, il serait interessant d’avoir un planificateur de haut niveau qui, selon
la situation, choisirait le type de planification requise. Un tel planificateur pourrait
analyser la situation et demander un plan au planificateur qu’il considere le meilleur
pour cette situation. Cela pourrait contribuer a ameliorer la qualite de la defense car
les planificateurs ayant des lacunes face a certaines situations ne seraient pas utilises.
Nous pourrions profiter des qualites de chaque planificateur.
Chapitre 5. Planification des actions de defense 111
5.7.5 Trouver la solution optimale
Il pourrait aussi etre interessant de trouver un moyen de calculer la solution optimale
face a une certaine situation. Ainsi, nous pourrions savoir si nous sommes proches de
cette solution optimale et nous pourrions comparer les temps de calcul pour trouver la
solution optimale avec les temps de calcul pour trouver une approximation.
L’idee de combinaisons menaces-secteurs proposees au chapitre 4 pourrait servir ici.
En effet, nous avons prouve que GenTSC generait toutes les combinaisons possibles.
Ainsi, si nous avions un moyen de trouver le plan optimal pour chacune de ces com-
binaisons menaces-secteurs, nous pourrions par la suite trouver le plan optimal face a
une certaine situation.
5.8 Sommaire
Nous avons presente dans ce chapitre une approche permettant d’ameliorer la qualite
de la planification sur le projet NEREUS : l’approche diviser pour regner. Nous avons
vu que cette approche apporte de l’amelioration a la qualite de la defense mais qu’il
y a encore place a l’amelioration. Cette approche permet une mise a execution plus
rapide du plan de defense. Elle permet aussi de repositionner la fregate et de faire de la
replanification efficace. Nous avons par la suite expose les resultats obtenus a l’aide de
simulations. Enfin, nous avons propose quelques avenues possibles avec cette approche.
Une de ces avenues qui semble la plus interessante est celle qui permettrait d’agir tout
en se positionnant. Pour terminer, le chapitre qui suit conclut ce memoire en presentant
un sommaire global des travaux presentes dans ce memoire et des travaux qui pourraient
s’averer interessants pour l’avenir du projet NEREUS.
Chapitre 6
Conclusion
Dans ce memoire, nous avons expose differentes techniques d’intelligence artificielle
pouvant etre utilisees par les agents afin de resoudre notre probleme. Pour ce faire, nous
avons tout d’abord decrit la problematique du projet NEREUS. Cette problematique
tourne autour de la specification, le developpement et la validation d’un systeme d’aide
a la decision pour la gestion des ressources a bord d’une fregate.
Dans le chapitre 2, nous avons decrit les agents et les differentes architectures
d’agents pour ensuite expliquer ce qu’etait la planification. Nous avons aussi explique les
systemes temps-reel, en particulier les systemes de commande et controle. Au chapitre
3, nous avons expose la theorie sous tendant notre simulation et qui permet de justifier
et valider les resultats obtenus a l’aide du NDS (Naval Defense Simulator). Nous avons
expose en particulier la methode de Monte-Carlo.
Par la suite, nous avons propose, aux chapitres 4 et 5, une methode pour positionner
la fregate et une approche permettant de faire de la planification et replanification des
actions de defense. Au chapitre 4, nous avons donne un modele formel d’interaction
entre les differentes ressources disponibles et les menaces presentes dans l’environne-
ment. En particulier, nous avons expose une technique permettant de traiter tous les
cas possibles d’interactions (preuve a l’appui). L’approche presentee au chapitre 5 est
nouvelle dans le cadre de notre projet. Cette approche apporte un gros avantage du
cote du repositionnement de la fregate et de la replanification des actions de defense.
Bien entendu, ce que nous avons propose dans les chapitres 4 et 5 n’est pas parfait.
C’est pourquoi, dans ces deux chapitres, nous avons fait des sections “Ameliorations
possibles” et “Travaux futurs”. Cela a permis de critiquer les methodes proposees et
d’apporter des pistes de solution pour pallier aux lacunes de ces methodes.
Chapitre 6. Conclusion 113
6.1 Retour sur les objectifs
Maintenant que nous avons resume le contenu de ce memoire, nous pouvons faire
un retour sur les objectifs presentes au chapitre 1 et voir comment ces objectifs ont ete
remplis.
1. Etudier les differentes architectures d’agents. Ce point a ete discute au
chapitre 2. Il a permis au lecteur de se familiariser avec les agents et les differentes
architectures d’agents.
2. Etudier les systemes temps-reel, en particulier les systemes de com-
mande et controle (C2). Ce point a aussi ete discute au chapitre 2. Il a permis
d’expliquer les differentes caracteristiques des systemes temps-reel et des systemes
de commande et controle.
3. Valider la plate-forme de simulation (NDS), developpee prealablement
sur le projet NEREUS, afin de s’assurer qu’elle respecte bien le modele
de simulation presente en annexe. Ce point a ete legerement discute au
chapitre 3. Cependant, la majeure partie de ce travail a consiste en la validation
des methodes utilisees dans le simulateur NDS au moyen de tests unitaires.
4. Etudier la theorie de la simulation afin de valider les resultats obtenus
via le NDS. Le chapitre 3 a presente la theorie de la simulation. Il a egalement
presente l’analyse des resultats obtenus au moyen de la simulation.
5. Developper un modele formel d’interaction entre les ressources dispo-
nibles et les menaces presentes dans l’environnement. Le chapitre 4 a
presente le modele propose. L’interaction entre les ressources disponibles et les
menaces presentes dans l’environnement a egalement ete representee au moyen
des combinaisons menaces-secteurs.
6. Developper une technique de positionnement de la fregate afin de maxi-
miser l’utilisation des ressources. Nous avons propose au chapitre 4 une
methode de positionnement de la fregate. Nous avons aussi propose une nouvelle
heuristique, PNH, permettant d’evaluer la qualite d’une position.
7. Developper une approche de planification qui permet une gestion effi-
cace des ressources afin de maximiser les chances de survie de la fregate.
Une approche diviser pour regner a ete proposee au chapitre 5. Cette approche
comporte beaucoup d’avantages pour la planification. Cependant, etant une nou-
velle approche, il y a encore place a l’amelioration afin de la rendre tres efficace.
Chapitre 6. Conclusion 114
6.2 Travaux futurs
Dans les chapitres 4 et 5, nous avons presente une section “Travaux futurs”. Ces tra-
vaux representent en fait des solutions proposees pour pallier aux lacunes des methodes.
Ici, nous donnons plutot quelques avenues qui pourraient etre interessantes pour la
continuite du projet.
6.2.1 Rendre le modele plus realiste
Le modele de simulation presente en annexe est en fait un modele simplifie de la
realite. Il pourrait etre interessant d’enlever certaines hypotheses simplificatrices faites
dans ce modele. Tout d’abord, les menaces pourraient etre plus realistes. Voici quelques
exemples qui permettraient aux menaces d’etre plus realistes :
1. Vitesses differentes.
2. Menaces plus dangereuses que d’autres (probabilites de destruction differentes).
3. Menaces ayant des probabilites de detection differentes.
Nous pourrions aussi introduire, dans nos simulations, une probabilite de defaillance
de l’equipement. Par exemple, il pourrait arriver qu’un SAM devant etre lance ne soit
pas lance en raison d’un probleme technique. Cela rendrait les scenarios plus interessants
en raison de certaines contingences imprevues.
Enfin, nous pourrions introduire un module permettant de mieux modeliser le mou-
vement de la fregate. Dans notre modele, la fregate est consideree comme un point fixe
et elle tourne sur elle-meme. Un tel module permettrait de raffiner les techniques de
defense “softkill” et rendrait la simulation encore plus realiste.
6.2.2 Probleme d’assignation de ressources sur des menaces
Nous avons vu au chapitre 2 un probleme typique des systemes de commande
et controle : l’assignation de ressources sur des menaces. Il pourrait etre interessant
d’etudier ce probleme et de voir s’il cadre dans la problematique du projet NEREUS.
Comme plusieurs solutions ont ete proposees pour ce probleme, il serait interessant de
voir comment elles pourraient etre adaptees a un tel projet.
Chapitre 6. Conclusion 115
De plus, il serait possible de complexifier le probleme d’assignation de ressources sur
des menaces en ajoutant des contraintes sur les ressources (angles morts, disponibilite
reduite, etc.). Le probleme deviendrait plus interessant et pourrait constituer un tres
bon sujet de recherche. Les solutions proposees pourraient alors etre testees sur le projet
NEREUS.
6.2.3 Interaction avec le commandant
Le but du projet NEREUS etant de developper un systeme d’aide a la decision, il
serait interessant de mieux representer l’interaction entre le systeme et le commandant
utilisant le systeme. Les interactions pourraient prendre differentes formes. Voici des
exemples d’interactions qui pourraient survenir :
1. Le commandant pourrait rejeter le plan qui lui est propose et demander un nou-
veau plan.
2. Le commandant pourrait rejeter une partie du plan propose et demander une
replanification pour la partie du plan qui a ete rejetee.
3. Le commandant pourrait exiger qu’une action precise se retrouve dans le plan.
Une telle interaction permettrait de se rapprocher encore plus de la realite. De plus,
elle rendrait la planification plus interessante en raison des contraintes externes qui
seraient imposees par le commandant.
Bibliographie
Ahuja, R., Kumar, A., Jha, K., et Orlin, J. (2003). Exact and heuristic al-
gorithms for the weapon target assignment problem. Non publie. Disponible a
http ://web.mit.edu/sloan-msa/Papers/1.5.pdf.
Ash, D. W. et Dabija, V. G. (2000). Planning for Real Time Event Response Mana-
gement. Prentice-Hall.
Ball, P. (1996). Introduction to discrete event simulation. In 2nd DYCOMANS work-
shop on Management and Control : Tools in Action, pp. 367–376, Algarve, Portugal.
Bayart, F. (2004). La bibm@th. [Online]. Disponible a http ://www.bibmath.net/
dico/index.php3 ?action=affiche&quoi=./m/montecarlo.html.
Blodgett, D., Gendreau, M., Guertin, F., Potvin, J.-Y., et Seguin, R. (1998). A tabu
search heuristic for resource management in naval warfare. Publication du Centre de
Recherche en Transport, CRT-98-63, Montreal.
Boddy, M. et T.Dean (1989). Solving time-dependent planning problems. In Procee-
dings of the 11th International Joint Conference on Artificial Intelligence (IJCAI-89),
pp. 979–984.
Boyd, J. R. (1987). Organic design for command and control. Briefing slides.
Braford, J. (1961). Determination of optimal assignment of a weapon system to
several targets. Technical Report AER-EITM-9, Vought Aeronautics, Dallas, Texas.
Brassard, G. et Bratley, P. (1996). Fundamentals of Algorithmics. Prentice-Hall, Inc.
Chlique, P. (2004). [Online]. Disponible a http ://www.supelecrennes.fr/ren/
perso/pchlique/tpsreel/acctr.htm.
Cormen, T., Lieserson, C., Rivest, R., et Stein, C. (2002). Introduction a l’algorith-
mique. 2e edition.
Day, R. (1966). Allocating weapons to target complexes by means of nonlinear pro-
gramming. Operations Research, 14, pp. 992–1013.
BIBLIOGRAPHIE 117
Dean, T. (1988). Intractability and time-dependant planning. In Proceedings of
Workshop on Reasoning about Actions and Plans.
Dean, T. et Boddy, M. (1988). An analysis of time-dependant planning. In Proceedings
of the 7th National Conference on Artificial Intelligence (AAAI-88), pp. 49–54, Menlo
Park, California. AAAI Press.
Gillies, D. (2004). [Online]. Disponible a http ://www.faqs.org/faqs/realtime-
computing/faq/.
Granger, L. (2000). If505 simulation par evenements discrets. chapitre 9 : Analyse
des resultats. Disponible a http ://www.cours.polymtl.ca/if505/.
Heche, J.-F., Liebling, T. M., et de Werra, D. (2003). Recherche operationnelle pour
ingenieur II.
Holger, K. (2001). A brief introduction to discrete event simulation.
Presentation PDF. Presentation disponible a http ://www-tkn.ee.tu-
berlin.de/˜karl/teaching/SimulationPrimer.pdf.
Horvitz, E. (1987). Reasoning about beliefs and actions under computational resource
constraints. In Proceedings of Workshop on Uncertainty in Artificial Intelligence,
Seattle, WA.
Hosein, P. et Athans, M. (1990). Some analytical results for the dynamic weapon-
target allocation problem. Technical report, Massachusetts Institute of Technology.
Laboratory for Information and Decision Systems. Appears in Collections : LIDS
Technical Reports.
Hosein, P. A. (1989). A Class of Dynamic Nonlinear Resource Allocation Problems.
These de doctorat, Massachusetts Institute of Technology (MIT), Cambridge.
Hromkovic, J. (2001). Algorithmics for Hard Problems. Springer-Verlag.
iBright Ltd. (2004). [Online]. Disponible a http ://www.ibrightsolutions.com/
support/simulation/simulation.htm.
Jennings, N., Sycara, K., et Wooldridge, M. (1998). A roadmap of agent research and
development. Autonomous Agents and Multi-Agent Systems (AAMAS), 1(1), pp. 7
– 38.
Krishna, C. et Shin, K. (1997). Real-Time Systems. McGraw-Hill Companies, Inc.
Lee, Z., Su, S., et Lee, C. (2003). Efficiently eolving general weapon-target assign-
ment problem by genetic algorithms with greedy eugenics. In IEEE Transactions on
Systems, Man, and Cybernetics, Part B : Cybernetics, volume 33.
BIBLIOGRAPHIE 118
Lloyd, S. et Witsenhausen, H. (1986). Weapons allocation is np-complete. In Pro-
ceedings of the 1986 Summer Conference on Simulation. Reno, NV.
Manne, A. (1958). A target-assignment problem. Operations research, 6, pp. 346–351.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., et Teller, E. (1953). Equa-
tions of state calculations by fast computing machines. Journal of Chemical Physics,
21, pp. 1087–1092.
Plamondon, P. (2003). A Frigate Survival Approach based on Real-time Multiagent
Planning. Memoire de maıtrise, Departement d’informatique et de genie logiciel,
Universite Laval.
Rice, J. A. (1995). Mathematical Statistics and Data Analysis. Wadsworth Inc., 2nd
edition.
Ross, S. M. (1996). Initiation aux probabilites. Macmillan, 4e edition.
Russel, S. et Zilberstein, S. (1991). Composing real-time systems. In J. Mylopoulos et
R. Reiter, editors, Proceedings of the 12th International Joint Conference on Artificial
Intelligence (IJCAI-91), pp. 212–217. Morgan Kaufmann publishers Inc. : San Mateo,
CA, USA.
Russell, S. J. et Norvig, P. (2003). Artificial Intelligence : A Modern Approach (second
edition). Prentice-Hall, Englewood Cliffs, NJ.
Smith, N. (2004). [Online]. Disponible a http ://www.twi.co.uk/j32k/protected/
band 3/ksngs002.html.
Soucy, M. (2003). Planification deliberative en temps reel. Memoire de maıtrise,
Departement d’informatique et de genie logiciel, Universite Laval.
Suermondt, H. (1989). Flexible inference for decision under scare resources. In
Proceedings of the 1989 Workshop on Uncertainty in Artificial Intelligence.
Taub, A., editor (1963). John von Neumann : Collected Works, volume V : Design
of computers, Theory of Automata and Numerical Analysis. Pergamon Press, New
York.
Wooldridge, M. (2002). An Introduction to MultiAgent Systems. John wiley & sons
ltd edition.
Zilberstein, S. (1993). Operational rationality through compilation of anytime algo-
rithms. These de doctorat, University of California at Berkeley.
Zilberstein, S. et Russel, S. (1996). Optimal composition of real-time systems. Arti-
ficial Intelligence, 82, pp. 181–213.
Annexe A
Modele de simulation pour le projet
NEREUS
Etant donne la complexite des ressources disponibles sur une fregate et de l’envi-
ronnement naval qui l’entoure, nous devions avoir un modele simplifie qui reduirait une
telle complexite afin de pouvoir effectuer des recherches sans tomber dans des calculs
trop complexes. Pour ce faire, un modele simplifie de la fregate et de l’environnement a
ete propose afin de permettre aux etudiants du projet NEREUS de faire de la recherche
sur un tel projet.
Comme les specifications des ressources a bord d’une fregate constituent des donnees
classifiees (i.e confidentielles), les specifications du modele ne concordent pas exactement
avec la realite. Cependant, ces specifications permettent de faire de la recherche dans
le domaine tout en ayant des resultats significatifs. Il convient de dire que le modele
presente ici est un modele qui date d’avril 2001. Un modele plus complexe, et plus
realiste, sera propose au cours de l’automne 2004 afin de contribuer a faire avancer les
recherches avec un modele plus proche de la realite.
A.1 Explications des differentes ressources a gerer
A bord de la fregate, nous pouvons distinguer trois types de ressources : hardkill,
softkill et radar. Il y a 3 ressources de type hardkill, 2 de type softkill et 3 de type
radar. Chacune des ressources possedent ses propres specifications. Ces specifications
se retrouvent dans la table A.1.
Annexe A. Modele de simulation pour le projet NEREUS 120
Les ressources hardkill sont utilisees afin de detruire une menace qui attaque la
fregate. Elles sont dirigees directement sur la menace. Elles peuvent la detruire au
moyen d’un impact direct ou a l’aide d’une explosion a proximite de celle-ci. La fregate
possede trois ressources de type hardkill :
1. SAM (Surface-to-Air Missile) : missile surface-air a longue portee qui fait exploser
la menace.
2. GUN : un canon de moyenne portee qui permet de detruire la menace en la
bombardant de projectiles a une cadence elevee.
3. CIWS (Close-In Weapons System) : mitraillette a courte portee qui detruit la
menace en la bombardant de petits projectiles a une cadence tres elevee. C’est la
derniere ressource utilisee avant que la menace ne frappe la fregate.
Les ressources softkill sont utilisees dans le but de desorienter une menace qui at-
taque la fregate. De tels systemes brouillent les systemes de guidance de la menace
afin de la faire devier de sa trajectoire. Lorsque cela fonctionne, la menace peut s’auto-
detruire ou encore, terminer sa course loin de son objectif. Notre modele comporte deux
ressources de type softkill :
1. Chaff : le chaff est un nuage de particules metalliques qui sert de leurre afin
d’attirer la menace. Il peut arriver que la menace croit que la chaff est une cible
(une fregate) et, dans ce cas, la menace se dirige directement sur le chaff.
2. Jammer : le jammer est un systeme de brouillage d’ondes qui permet de desorienter
la menace et la faire changer de trajectoire. La fregate possede 2 canaux de jammer
de chaque cote, donc 4 au total.
Lorsque la fregate a deja lance un chaff, le jammer est souvent utilise pour faire
devier la menace dans le chaff. L’utilisation de ces 2 ressources ensemble maximise la
probabilite de succes (voir table A.1).
Enfin, les differents radars presents sur la fregate composent le troisieme type de
ressources. Trois ressources de ce type sont presentes sur la fregate :
1. Radar : le radar est la ressource avec la plus grande portee. Il sert a detecter les
menaces qui attaquent la fregate. Il patrouille l’environnement et rapporte a la
fregate tout changement qui survient.
2. STIR (Separate Tracking and Illuminating Radar) : c’est un illuminateur qui
permet de verrouiller une cible afin de guider un SAM ou pointer le GUN sur
cette cible. Il peut guider une seule ressource hardkill a la fois. La fregate possede
deux STIRs : un a l’avant et un a l’arriere.
3. CIWS Radar : c’est l’illuminateur qui permet de pointer le CIWS sur la cible
desiree.
Annexe A. Modele de simulation pour le projet NEREUS 121
A.2 Doctrines a respecter
Bien entendu, les ressources enumerees precedemment ne peuvent etre utilisees
comme bon nous semble. Les ressources sont regies par diverses contraintes physiques
et logiques. Voici les doctrines qui doivent etre respectees :
1. On ne peut assigner simultanement les 2 STIRs sur une meme cible.
2. Le STIR ne peut controler qu’une seule ressource a la fois.
3. On ne peut engager ou reengager un SAM ou le GUN tant qu’il n’y a pas eu
confirmation que le cible n’a pas ete detruite.
4. On ne peut engager un SAM ou le GUN sur une cible engagee par le CIWS.
5. Le CIWS peut etre engage sur une cible meme si cette derniere est engagee par
un SAM ou le GUN.
6. On ne peut engager un SAM ou le GUN sur une cible s’il y a un chaff dans la
trajectoire de tir.
A.3 Specifications des ressources
La table A.1 contient toutes les specifications en detail des ressources enumerees
ci-haut. Entre autres, elle contient la portee de chacune des ressources ainsi que les
conditions d’utilisation. Notons qu’un angle de 0◦correspond au devant de la fregate
et que les angles autour de la fregate suivent un sens anti-horaire. Ainsi, un angle de
90◦est a la gauche, 180◦a l’arriere et 270◦a la droite de la fregate.
Ressource Angles
couverts (◦)
Particularites
SAM 0 a 360 - Quantite maximale : 16
- Vitesse : 306 m/s
- Probabilite de succes : 75%
- Doit etre guidee par un STIR
- Portee maximale : 20 km
- Portee minimale : 2,2 km
Gun 215 a 145 - Quantite maximale : 750 balles
- Vitesse : 850 m/s
- Cadence de tir : 200 balles/min
- Probabilite de succes : 4% par balle
Annexe A. Modele de simulation pour le projet NEREUS 122
- Doit etre guidee par un STIR
- Portee maximale : 5 km
- Portee minimale : 0,9 km
CIWS 15 a 345 - Quantite maximale : 1500 balles
- Vitesse : 1200 m/s
- Cadence de tir : 55 balles/sec
- Probabilite de succes : 0,6% par balle
- Doit etre guidee par le CIWS Radar
- Portee maximale : 2,5 km
- Pas de portee minimale
Jammer gauche 350 a 190 - Quantite maximale : 2 canaux
- Delai pour brouiller les ondes d’une cible : 20
sec
- Delai pour feinter une nouvelle position de la
fregate : 3 sec
- Probabilite de succes : 40% seul, 80% avec
chaff
- Portee maximale : 24 km
- Pas de portee minimale
Jammer droit 170 a 10 - idem jammer gauche
Chaff 0 a 360 - Duree maximale : 10 min
- Probabilite de succes : 30% seul, 80% avec
jammer
- Portee maximale : 0,2 km
STIR avant 240 a 120 - Delai pour verrouiller une cible : 3 sec
- Delai pour valider une destruction avec un
SAM : 2,5 sec
- Delai pour valider une destruction avec un
GUN : 1 sec
- Portee maximale : 50 km
- Pas de portee minimale
STIR arriere 60 a 300 - idem STIR avant
CIWS Radar 15 a 345 - Delai pour verrouiller une cible : 1 sec
- Aucun delai pour valider une destruction
- Portee maximale : 5,5 km
- Pas de portee minimale
Radar 0 a 360 - Portee maximale : 80 km
- Pas de portee minimale
Tab. A.1: Specifications des ressources de la fregate.
Annexe A. Modele de simulation pour le projet NEREUS 123
A.4 Secteurs engendres par les limitations des res-
sources
En regardant la zone de couverture de chacune des ressources, il est possible de
diviser l’aire de defense de la fregate en 12 differents secteurs. Cette idee fut proposee par
(Plamondon, 2003). Chaque secteur possede des ressources differentes de ses voisins. La
figure A.1 illustre la division en secteur et la table A.2 donne les ressources disponibles
dans chacun des secteurs. Cette division en secteur est utilisee au chapitre 4.
Stir
CIWS
Jammer
Gun
10o
15o
60o
120o
145o
170o
190o
215o
240o 300
o
345o
350o
1
4
7
10
2
3
5
6
8
9
11
12
Fig. A.1 – Secteurs engendres par la restriction des ressources.
Secteurs Ressources disponibles
1, 7 SAM, Gun, CIWS, 1 Jammer, 2 STIRs
2, 6, 8, 12 SAM, Gun, CIWS, 1 Jammer, 1 STIR
3, 5 SAM, Gun, 1 Jammer, 1 STIR
4 SAM, Gun, 2 Jammers, 1 STIR
9, 11 SAM, CIWS, 1 Jammer, 1 STIR
10 SAM, CIWS, 2 Jammers, 1 STIR
Tab. A.2 – Ressources disponibles dans chacun des secteurs.
Annexe A. Modele de simulation pour le projet NEREUS 124
A.5 Specifications de la fregate
Dans notre modele, la fregate est consideree comme un point fixe dans l’environne-
ment. C’est le point central de la simulation. Il n’y a qu’une seule fregate dans l’en-
vironnement. Lorsque cette derniere effectue une rotation, elle tourne sur elle-meme a
une vitesse de 3◦/sec. Rappelons que l’angle de 0◦est situe a l’avant de la fregate et les
angles tournent dans le sens anti-horaire autour de la fregate.
A.6 Specifications des menaces ennemies
Notre modele contient des menaces ennemies relativement simplifiees. Toutes les
menaces ont les memes specifications, ces specifications sont les suivantes :
1. Les menaces vont a une vitesse constante de 850 m/s.
2. Elles se dirigent directement sur la fregate en ligne droite.
3. Chaque menace a une probabilite de 50% de detruire la fregate en cas d’impact
avec cette derniere.
Nous avons cree 2 types de scenario. Dependamment du type de scenario, le lieu
et le moment d’apparition des menaces peuvent varier. Les 2 types de scenario sont
expliques en details au chapitre 3.