Ordonnancement de ressources en temps réel avec

OLIVIER GAGNÉ ORDONNANCEMENT DE RESSOURCES EN TEMPS RÉEL AVEC CONTRAINTES DYNAMIQUES DANS

UN ENVIRONNEMENT NON DÉTERMINISTE

Mémoire présenté à la Faculté des études supérieures de l’Université Laval dans le cadre du programme de maîtrise en informatique pour l’obtention du grade de Maître ès sciences (M.Sc)

FACULTÉ DES SCIENCES ET DE GÉNIE

UNIVERSITÉ LAVAL QUÉBEC

2007 © Olivier Gagné, 2007

Resume

Les problemes militaires sont tres complexes et plusieurs d’entre eux ne peuvent

etre resolues en utilisant les techniques d’optimisation classiques. Le probleme vise

par ce travail de maıtrise, est celui de la gestion en temps reel des ressources d’une

fregate. Ces ressources doivent etre assignees convenablement et dans les delais requis

de maniere a contrer les menaces et augmenter ainsi la probabilite de survie de la

fregate. Pour contribuer a resoudre un tel probleme, nous avons convenu tout d’abord,

d’analyser les menaces une a une et de determiner lesquelles sont les plus importantes

et quel plan d’attaque il convient d’elaborer pour les contrer. Nous avons introduit a

cet effet, l’evaluation de “l’engageabilite” qui permet de considerer differents facteurs

determinants dans l’allocation des ressources. Nous avons ensuite formalise le probleme

en question, en utilisant un modele formel emprunte a la satisfaction des contraintes

(CSP=constraint Satisfaction problem). Finalement, nous avons montre dans quelles

circonstances il est avantageux d’utiliser cette evaluation de l’engageabilite dans un

processus d’allocation de ressources en temps reel et dans un environnement stochas-

tique, le tout relativement a la survie de la fregate.

Abstract

Military problems are very complex and they can be solved by different artificial

intelligence techniques. In this thesis, we address the problem of weapon-targets as-

signment for a frigate. To defend efficiently the ship, we have to analyze each threat

and determine which resource assigns against it. For that purpose, we utilize the enga-

geability assessment to consider different characteristics ; useful in the resources assign-

ment. To this end, a mathematical model named Constraint Satisfaction Problem (CSP)

is employed. This framework allows formalizing the problem to ensure the constraint

consistency and to sort threats in importance order. We tried this algorithm on different

types of weapon-target assignment problems. Finally, we demonstrate the advantage of

engageability assessment on the weapon-target assignment problem in real time and

stochastic environment.

Avant-propos

D’abord, ce fut un plaisir de cotoyer tous les gens du DAMAS. Travailler en equipe

permet de se depasser et de voir les choses sous un autre angle. De plus, il est im-

portant de souligner l’excellent travail, l’ethique et la perseverance de mon directeur

de recherche Brahim Chaib-draa aupres de ces etudiants. Un gros merci, j’ai apprecie.

Mention speciale aussi a Abder R. Benaskeur, pour son appui et ses opinions sur mon

travail tout au long de ma maıtrise.

Sur le plan personnel, merci de tout mon coeur a Marie, qui est aupres de moi tous

les jours et m’encourage dans ce que j’accomplis. Sans oublier mes parents, qui m’ont

soutenu sans cesse, de pres ou de loin, depuis le debut de mes etudes.

Table des matieres

1 Introduction generale 1

1.1 Problematique d’etude . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Les motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Les objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 L’organisation du memoire . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Problematique de la gestion des ressources en milieu militaire 5

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Environnement militaire . . . . . . . . . . . . . . . . . . . . . . 5

2.1.2 L’evaluation de l’engageabilite . . . . . . . . . . . . . . . . . . . 8

2.2 Description de la fregate . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2.1 Les Hardkill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.2 Les illuminateurs . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.3 Les Softkill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.4 Les secteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Les scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.1 Les menaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.2 Les types de scenarios . . . . . . . . . . . . . . . . . . . . . . . 13

2.4 L’apport au projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5 Sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Probleme de l’evaluation de l’engageabilite 18

3.1 La modelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.1 Les variables et les domaines . . . . . . . . . . . . . . . . . . . . 19

3.1.2 Les contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Niveau d’Engageabilite (NE) . . . . . . . . . . . . . . . . . . . . . . . . 21

3.3 Pourquoi utiliser l’engageabilite ? . . . . . . . . . . . . . . . . . . . . . 22

3.4 ILOG Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.5 Les domaines dynamiques . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.6 Presentation de l’engageabilite . . . . . . . . . . . . . . . . . . . . . . . 27

3.6.1 L’espace de faisabilite . . . . . . . . . . . . . . . . . . . . . . . . 27

3.6.2 Les diagrammes de Gantt . . . . . . . . . . . . . . . . . . . . . 29

vi

4 Satisfaction des contraintes 30

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.1.1 La definition du CSP . . . . . . . . . . . . . . . . . . . . . . . . 30

4.1.2 Les problemes combinatoires . . . . . . . . . . . . . . . . . . . . 31

4.1.3 La complexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1.4 Les types de contraintes . . . . . . . . . . . . . . . . . . . . . . 34

4.2 Resoudre un CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.2.1 Les conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.2.2 La recherche systematique . . . . . . . . . . . . . . . . . . . . . 38

4.2.3 Les techniques de consistance . . . . . . . . . . . . . . . . . . . 43

4.2.4 La propagation de contraintes . . . . . . . . . . . . . . . . . . . 49

4.2.5 L’ordre et reduction de recherche . . . . . . . . . . . . . . . . . 53

4.2.6 L’optimisation des CSP . . . . . . . . . . . . . . . . . . . . . . 54

4.3 Les modeles de CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.3.1 Satisfaction de contraintes stochastiques . . . . . . . . . . . . . 60

4.3.2 Satisfaction de contraintes ouvertes . . . . . . . . . . . . . . . . 62

4.3.3 Satisfaction de contraintes dynamiques . . . . . . . . . . . . . . 64

4.3.4 Les CSP distribue . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.3.5 Le probleme de satisfaction des contraintes hierarchiquement dis-

tribuees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.3.6 Satisfaction de contraintes distribuees et optimisees . . . . . . . 68

4.3.7 Satisfaction de contraintes temporelles . . . . . . . . . . . . . . 69

4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5 L’evaluation de l’engageabilite 71

5.1 L’allocation des ressources . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.1.1 Le niveau d’engageabilite et niveau de menace (NENM) . . . . . 73

5.1.2 Le niveau d’engageabilite et le niveau de menace pondere . . . . 78

5.2 Validite du plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6 La simulation et les resultats 82

6.1 La simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.1.1 SADM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.1.2 Les types de simulations . . . . . . . . . . . . . . . . . . . . . . 85

6.1.3 Les metriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.2 Les resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.2.1 Niveau d’engageabilite et niveau de menace . . . . . . . . . . . 89

6.2.2 Le nombre d’options disponibles . . . . . . . . . . . . . . . . . . 93

6.2.3 Le temps d’execution . . . . . . . . . . . . . . . . . . . . . . . . 93

6.3 Recommandations futures . . . . . . . . . . . . . . . . . . . . . . . . . 95

6.4 Sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

vii

7 Conclusion 97

7.1 Retour sur les objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7.2 Les travaux futurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Liste des tables

4.1 Convex Point Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.2 Tableau des conventions . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.3 Complexite des algorithmes d’arc-consistence . . . . . . . . . . . . . . . 46

4.4 Bucket Initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.5 Bucket Final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.1 Moyenne de survie globale . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.1 Metriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.2 Abreviation des approches . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.3 Moyenne de survie sur scenario uniforme . . . . . . . . . . . . . . . . 89

6.4 Moyenne de survie sur scenario uniforme-D . . . . . . . . . . . . . . . 90

6.5 Moyenne de PK sur scenario Contraint . . . . . . . . . . . . . . . . . . 91

6.6 Moyenne des couts pour tous les scenarios . . . . . . . . . . . . . . . . 93

Liste des figures

2.1 Probabilite de destruction du SAM par rapport a la distance . . . . . . 10

2.2 Secteurs de la fregate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Scenario Unifome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.4 Scenario Contraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5 Scenario Gaussien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.1 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.3 Espace de Faisabilite T=10 . . . . . . . . . . . . . . . . . . . . . . . . 28

3.4 Espace de Faisabilite T=32 . . . . . . . . . . . . . . . . . . . . . . . . 28

3.5 Diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1 Graphe de contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2 Solution au 8-Queen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.3 Relations d’Allen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.4 Arc-consistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.5 Graphe des contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.6 Graphe des contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.7 Cycle-Cutset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.8 Taxonomie CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.9 CSP Ouvert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.10 TCSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.1 Processus Global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.2 Assignation Partielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.3 Allocation Finale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.4 Plusieurs poids de NENM pondere . . . . . . . . . . . . . . . . . . . . 80

5.5 Meilleurs Poids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.1 Fenetre Principale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.2 Fenetre de configuration des armes . . . . . . . . . . . . . . . . . . . . 84

6.3 Fenetre des resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.4 Fenetre de gestion des ressources . . . . . . . . . . . . . . . . . . . . . 85

6.5 Scenario uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

x

6.6 Scenario uniforme-D . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.7 Scenario Contraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.8 Nombre moyen de menaces detruites . . . . . . . . . . . . . . . . . . . 92

6.9 Nombre d’options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6.10 Temps de planification . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6.11 Temps d’assignation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Chapitre 1

Introduction generale

A l’heure actuelle, la gestion de ressources en temps reel est un probleme des plus

complexe. Pour expliquer cette difficulte, nous devons considerer plusieurs facteurs.

D’une part, il faut tenir compte de l’abondance des donnees et de la complexite a les

utiliser. D’autre part, les limites imposees par le temps peuvent avoir un reel impact sur

la prise de decision. Toutefois, plusieurs techniques en intelligence artificielle (IA) sont

presentes pour resoudre ce type de probleme. Plus particulierement, il existe un modele

qui se concentre sur la satisfaction des contraintes. Le “Constraint Satisfaction Problem

(CSP)” est utilise dans plusieurs domaines, tels que la planification, l’ordonnancement,

le commerce electronique et la comprehension du langage. Tout comme le probleme de

la gestion de ressources, la majorite des problemes reels sont soumis a des contraintes

qui limitent la recherche d’une solution.

Ce memoire traite avant tout du probleme de la gestion de ressources en temps

reel dans un contexte militaire. Pour cela, nous avons convenu d’utiliser la technologie

des CSP afin d’eliminer les actions qui ne respectent pas les contraintes du probleme

etudie. Cette technique a permis de conserver seulement les actions envisageables et

ainsi faciliter le choix des ressources a assigner. De plus, dans le but de repondre a la

problematique du temps reel, le CSP a du etre resolu a plusieurs reprises et a divers

endroits strategiques durant la simulation. Par ailleurs, des contraintes dynamiques ont

du etre integrees au modele, afin de pouvoir gerer tout type de changements dans l’en-

vironnement. Dans ce projet, les CSP sont utilises dans l’evaluation de l’engageabilite,

qui est un processus avant la planification. Ce processus permet de reduire l’espace de

recherche, de trouver le domaine de faisabilite des actions et de faciliter la planification.

Afin d’evoluer dans ce type d’environnement, il faut detenir une entite capable

d’interagir avec celui-ci. Dans le domaine de l’intelligence artificielle, ce concept porte

Chapitre 1. Introduction generale 2

le nom d’agent. Il s’agit d’un systeme informatique qui est en mesure d’executer des

actions rationnelles dans un environnement, et ce, de maniere autonome [56]. Pour

y arriver, l’agent doit, dans un premier temps analyser de quelle facon se comporte

l’environnement, pour ensuite resoudre le CSP et executer les actions qu’il a planifiees

suite a la resolution du CSP. Pour executer les actions, il devra prealablement les

ordonner afin qu’elles soient realisees convenablement.

1.1 Problematique d’etude

Tel qu’enonce precedemment, le probleme sur lequel nous nous sommes penches est

du domaine militaire et concerne la gestion des ressources tactiques. Le but du projet est

de gerer efficacement toutes les ressources disponibles sur un navire de guerre de type

fregate, de maniere a augmenter ses chances de survie lors d’une attaque. Dans le cadre

du projet, nous avons utilise une fregate de type HALIFAX. Toutefois, il faut specifier

que l’approche presentee ici peut s’appliquer a n’importe quel type de plateforme. Il

suffirait seulement de modifier les ressources et de s’adapter a la nouvelle plateforme

pour que l’approche demeure effective.

Pour sa part, la fregate HALIFAX est un navire qui detient plusieurs types d’armes.

Ces armes possedent differentes proprietes, telles qu’une portee minimale et maximale,

des angles aveugles, une efficacite pour contrer les menaces, un certain nombre de muni-

tions, etc. Ces caracteristiques doivent etre considerees a chaque etape de la gestion des

ressources. Il peut donc etre difficile d’en faire l’assignation s’il y a plusieurs ressources,

menaces ou contraintes a respecter. D’autant plus, la tache est souvent compliquee

lorsqu’il faut assurer une certaine efficacite contre les possibles agressions. Dans ce

probleme, il faut que les actions choisies dans le processus de defense augmentent les

chances de survie de la plateforme.

Devant une situation d’attaque, le temps de reponse doit etre tres court. 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.


1.2 Les motivations

Les principales motivations qui nous ont incites a effectuer ce travail sont les sui-

vantes :

– L’absence d’une methode qui simplifie les choix pour l’operateur de la plateforme.

– La presence d’un probleme complexe en temps reel ou l’utilisation de techniques

d’intelligence artificielle semble prometteuse.

– L’absence d’un processus, precedent la planification, qui simplifierait le reste du

probleme.

– Utiliser les CSP dans un contexte temps reel, dans le but de faciliter la defense

d’une plateforme militaire.

– Coordonner deux types d’armes differentes (“softkill” et “hardkill”) qui peuvent

avoir des interactions positives, neutres ou negatives.

1.3 Les objectifs

L’objectif de la presente maıtrise est d’etudier les impacts de l’evaluation de l’enga-

geabilite dans un systeme de Commandes et Controle (C2). Il sera aussi important de

trouver et de valider une methode pour resoudre le probleme de la defense d’une plate-

forme dans un environnement temps-reel, stochastique et contraint. Les autres objectifs

sont les suivants :

– Modeliser le probleme en utilisant le formaliste CSP ;

– Etudier et appliquer les problemes de satisfaction de contraintes (CSP) ;

– Etudier et appliquer une methode d’optimisation de satisfaction de contraintes

(“Constraint Optimization Problem” [COP]) ;

– Etudier les problemes de satisfaction de contraintes distribuees sur des agents

(“Distributed Constraint Satisfaction Problem” [DCSP]) ;

– Definir ce qu’est le domaine de faisabilite ;

– Definir comment effectuer la propagation dynamique des contraintes ;

– Comparer diverses methodes pour utiliser l’engageabilite dans la planification ;

– Implementer et valider l’approche de planification sur un simulateur de la defense

du Canada ;

– Implementer une approche qui coordonne les “softkill” et les “hardkill” ;


1.4 L’organisation du memoire

Ce memoire est organise comme suit. Le chapitre 2 traite de la problematique de la

gestion de ressources. Puis, le chapitre 3 introduit, definit et explique ce qu’est le pro-

cessus de l’engageabilite. Le chapitre 4 presente une revue de litterature sur les modeles

de CSP, ainsi que les techniques pour les resoudre. Le chapitre 5 decrit de quelle facon

le probleme de planification et de gestion des ressources est resolu. Ensuite, le chapitre

6 contient l’explication et la presentation des resultats obtenus lors des simulations.

Enfin, le chapitre 7 conclut ce memoire et propose quelques avenues possibles pour la

suite du projet.

Chapitre 2

Problematique de la gestion des

ressources en milieu militaire

2.1 Introduction

Le present travail a ete realise dans le cadre du projet NEREUS (Naval Environment

for Resource Engagement in Unpredictable Situations)1. NEREUS est un projet de

gestion de ressources pour une plateforme militaire, dans le but de contrer des attaques.

Une telle plateforme comporte differents types d’armements qui sont consideres, ici,

comme les ressources a gerer. Elles doivent donc etre jumelees a des menaces afin de

proteger la fregate. Plusieurs difficultes sont inherentes a ce type de probleme. Les

sections qui suivent enumerent les principales.

2.1.1 Environnement militaire

D’entree de jeu, dans le cas d’un probleme temps reel, il est souvent inconcevable

d’utiliser de longues periodes de temps afin de trouver la meilleure solution possible. En

effet, il est essentiel de restreindre la duree du calcul et de parvenir a trouver une solution

efficace malgre les limites de temps. Pour ce faire, il est obligatoire que les contraintes

temporelles soient respectees. Ceci permet notamment de choisir les actions realisables

dans la periode de temps visee. De plus, un processus en temps reel, necessite une

approche capable de s’adapter aux changements (solution adaptative) [53] et d’operer

1http ://damas.ift.ulaval.ca/projets/TeamWork/index.fr.html

Chapitre 2. Problematique de la gestion des ressources en milieu militaire 6

malgre les contingences possibles. Si le systeme ne peut gerer les contingences, l’efficacite

de la defense sera diminuee.

Deuxiemement, en plus d’avoir une solution adaptative, il serait avantageux pour

le systeme d’etre en mesure de prevoir les prochains evenements. Pour y parvenir, il

peut construire un plan, en y introduisant des plans de contingences et les cas les plus

probable [44]. Le but de ce plan, est de pouvoir prevoir les ressources disponibles dans

le futur, selon differentes circonstances, et ainsi, faciliter le respect des contraintes de

ressources et de temps [41].

Troisiemement, les algorithmes doivent etre en mesure de retourner une solution a

tout moment (anytime) [16], [17],[10]. Avoir un algorithme “anytime”, dans un systeme

temps reel, comporte deux avantages. Premierement, cela permet d’avoir une solution

adequate rapidement, meme avec une periode de temps limite. Deuxiemement, la qualite

de la solution s’ameliore, plus le temps d’execution augmente[21]. Malheureusement,

modifier des algorithmes pour qu’ils soient “anytime” demande plusieurs changements.

Il faut les modifier afin de reduire le temps de calcul et rendre une solution disponible

a n’importe quelle etape de l’algorithme.

Bien entendu, une facette importante des systemes temps reels est qu’ils soient bien

adaptes a leurs environnements. Le comportement du systeme varie en fonction des

periodes de temps consacrees a la prise de decision. Selon les environnements et le type

de systeme fabrique, cette periode de temps peut etre tres flexible. Par contre, dans le

projet NEREUS, les attaques contre la plateforme durent en moyenne 120 secondes.

Comme des decisions sont prises a chaque 20 millisecondes, le temps de decision est

relativement limite.

En resume, les systemes temps reels peuvent etre ameliores de differentes facons

selon leurs contextes. Dans le domaine militaire, il est important d’avoir une solution

rapidement. De plus, comme nous l’expliquons dans la section suivante, il faut aussi

etre capable de planifier malgre des informations manquantes et imprecises.

L’incertitude et la planification

Tel que mentionne precedemment, planifier avec des informations imparfaites est

rarement une tache facile dans des environnements complexes [37]. En fait, il arrive

souvent que certaines informations soient imparfaites, voire stochastiques, mais qu’elles

doivent tout de meme etre considerees dans l’elaboration de la solution. Dans le cadre

du projet NEREUS, l’incertitude se presente sous de multiples facettes, par exemple :


sur les trajectoires des menaces ou sur l’efficacite des ressources tactiques.

De plus, il faut savoir que les actions executees dans l’environnement ne sont pas

toujours efficaces. Une action contre une menace peut parfois echouer, si les informa-

tions recueilles sur la menace sont eronnees. En effet, les outils (capteurs, appareils

d’ecoute) ne sont pas toujours precis et une certaine marge d’erreur doit etre prise en

consideration. Cela implique qu’il peut y avoir des erreurs sur la position, l’angle, le

type ou la vitesse de la menace.

Par ailleurs, certaines armes ont de meilleures probabilites de detruire une menace

que d’autres. Ceci s’explique par les caracteristiques et l’utilisation du systeme d’ar-

mement. Certaines armes sont designees pour contrer des menaces situees pres de la

fregate, d’autres le sont pour des menaces plus eloignees. Cet aspect n’est pas a negliger

lors de la planification, puisqu’il determine la reussite des actions.

Puis, en plus des consequences des actions probabilistes, le temps d’execution des

actions peut varier. La difficulte du probleme est alors augmentee, car la duree variable

des actions doit maintenant etre consideree. Il est donc frequent que deux ressources,

identiques, ne necessitent pas la meme duree d’action dans differentes circonstances.

Toute cette incertitude dans le probleme rend la planification ardue [37].

Commande et Controle (C2)

Le C2 est le systeme permettant de commander et de controler une plateforme

militaire. La construction d’un systeme de commandes et controle se divise en plusieurs

facettes complexes. Il requiert beaucoup d’analyse, de conception et de modelisation. De

plus, il faut s’assurer que l’architecture du systeme soit conforme aux attentes initiales.

Pour ce faire, il est necessaire d’executer de nombreuses simulations et experimentations,

permettant d’analyser le fonctionnement du C2.

En ce qui nous concerne, nous avons construit qu’une composante d’un C2, en nous

concentrant sur le probleme d’assignation d’armes contre les menaces. Il a ete demontre

que ce probleme est NP-Complet [38] [51], c’est-a-dire qu’il n’y a pas d’algorithme qui

peut resoudre le probleme en temps polynomial. En fait, un algorithme est dit en temps

polynomial si, pour toute entree de taille n, l’algorithme s’execute en moins de C.nk

operations elementaires ou C et k sont deux constantes independantes de n [13].

Le probleme d’assignation est connu dans la litterature comme le “Weapon Target

Assignment (WTA)”. Le WTA peut etre divise en deux classes distinctes, soit le WTA


statique et le WTA dynamique. D’abord, le WTA statique est compose d’un nombre x

de menaces et d’un nombre y de ressources. Le but est d’assigner en une seule etape les

x menaces avec les y ressources disponibles. La seconde classe, le WTA dynamique, est

celle qui nous interesse. Elle est une succession de WTA statique. L’assignation se fait

sur plusieurs etapes rendant le probleme delicat. Ces etapes representent des pas dans le

temps. Il devient alors moins facile de faire les assignations, car de nouvelles contraintes

font leurs apparitions. Par exemple, la disponibilite des ressources et le temps restant

pour completer l’assignation doivent desormais etre consideres.

2.1.2 L’evaluation de l’engageabilite

L’evaluation de l’engageabilite est un processus dans la planification militaire. Il

permet de supporter le module d’assignation d’armes contre les menaces. Pour ce faire,

plusieurs facteurs sont consideres lors de l’evaluation de l’engageabilite tel que :

– les regles d’engagements ;

– la disponibilite des effectifs et leurs efficacites ;

– les interactions entre les ressources ;

– les angles aveugles des ressources ;

– les munitions ;

Ces facteurs seront utilises afin de filtrer l’ensemble des solutions pour ne garder que

celles possibles. Avoir un espace restreint de solution facilitera le processus de la plani-

fication puisque l’espace de recherche sera diminue.

Ainsi, l’evaluation de l’engageabilite est le processus qui a le role d’analyser et de

traiter tous ces facteurs. De plus, il donne la possibilite de regrouper les menaces selon

leurs ressources disponibles et les associer a un niveau d’engageabilite. Ce niveau sera

ensuite utilise pour choisir les menaces a contrer et les ressources a utiliser. Pour ac-

complir cette tache, l’engageabilite est en grande partie resolue a l’aide d’un CSP ayant

la capacite de s’adapter a l’environnement. L’engageabilite sera entierement decrite au

chapitre 3.

2.2 Description de la fregate

La fregate canadienne, de type Halifax, est un navire de guerre muni de differentes

ressources permettant de se defendre en milieu hostile. Pour se faire, deux types d’ar-

mements distincts permettent de contrer les menaces, soit les armes lourdes, appelees


“Hardkill” (HK), et les contre-mesures, nommees “Softkill” (SK).

D’une part, les “Hardkill” interceptent directement les cibles adverses. Dans le

cadre de notre projet, l’utilisation des “Hardkill” se fait en choisissant une cible et

en determinant un temps de lancement. Pour evaluer si l’action a reussi, il faut regar-

der si, au temps d’interception prevue, la menace est encore presente. En somme, il

existe trois categories “Hardkill” avec differentes proprietes.

D’autre part, les “Softkill’ sont des effectifs ayant l’objectif de devier les menaces de

la plateforme. Une contre-mesure, peut affecter les trajectoires de plusieurs menaces. De

plus, leur fonctionnement est plus complexe que les “Hardkill”. Ce qui rend l’utilisation

des “Softkill’ difficile, c’est de detecter avec certitude si l’action a fonctionne. Pour le

decouvrir, il faut analyser la trajectoire des missiles et determiner si les menaces ont

change de cible. Malheureusement, cette analyse se termine souvent au moment ou le

missile est tres pres de la plateforme. Dans le modele d’armement utilise dans le projet,

les probabilites de reussite des “Softkill’ sont beaucoup moins elevees que celles des

“Hardkill”.

2.2.1 Les Hardkill

Les “Hardkill” sont composes de trois types d’armes, soit les “Surface-Air-Missile”

(SAMs), le Gun et le “Close-In Weapon System” (CIWS). Ils visent a detruire la menace

a une distance donnee de la plateforme. Ces armes possedent differentes probabilites

de detruire les menaces, qui augmentent lorsque les cibles ennemies s’approchent de la

fregate. Chaque type d’arme a des proprietes distinctes qui permettent d’engager les

menaces selon leur type, leur distance, leur altitude, leur vitesse et leur azimut. Ces

differentes proprietes sont importantes, car elles seront traitees comme des contraintes

dans notre problematique. Ces proprietes sont issues d’un modele generique, adopte

aux fins du travail.

Les SAMs sont des missiles de longue portee. Ils peuvent atteindre une menace

qui se situe entre 2.2 et 20 kilometres. Ils sont repartis dans deux lanceurs, situes de

chaque cote de la plateforme. Il y a 16 SAMs au total, soit 8 dans chaque lanceur. Ils

peuvent etre tires sur n’importe quelle menace peut importe son azimut. Ces missiles

peuvent aller jusqu’a une vitesse de 800 metres/seconde et leurs chances d’interception

varient en fonction de la distance de la menace. La figure 2.1 represente les courbes

de probabilite pour intercepter une cible par rapport a sa distance et son acceleration

laterale (en g). En fait, les menaces n’ayant aucune acceleration laterale ont toujours

95% de chances d’etre detruites lorsqu’elles sont entre 2.2 et 20 kilometres.


Fig. 2.1 – Probabilite de destruction du SAM par rapport a la distance

Le seul Gun sur la fregate est de portee moyenne. Il peut detruire une menace situee

entre 0.9 et 5 kilometres. Dans le cadre de ce projet, chaque fois qu’il est assigne sur

une menace, il tire 5 fois, 5 salves. Le Gun est situe a l’avant de la plateforme, ce qui

limite un peu son rayon d’action. En realite, il possede un angle mort qui l’empeche de

tirer a ±35◦ vers l’arriere.

Pour sa part, le CIWS cible les menaces proches de la plateforme. C’est une ressource

unique en terme de portee courte. De plus, aucune autre alternative n’existe si le CIWS

ne parvient pas a detruire la cible, puisqu’elle est la seule armee de courte portee. Il est

donc preferable de detruire la menace avant qu’elle penetre dans la portee du CIWS. A

ce propos, aussitot qu’une menace entre dans la limite des 2.5 kilometres et qu’elle n’est

pas engagee, le CIWS l’engage automatiquement. Il tire 1200 coups/secondes, mais a

de tres faibles chances de detruire la menace. En revanche, le fait de tirer autant,

augmente les chances d’intercepter la cible. Dans le projet, le CIWS est situe a l’arriere

de la fregate, ce qui l’empeche d’engager les menaces situees a ±15◦ vers l’avant.


2.2.2 Les illuminateurs

Ces trois types d’armement ne peuvent agir seuls. Ils doivent etre guides par des

systemes de radar, nommes illuminateurs ou STIR (Separate Track and Illumination

Radar). Ces STIR permettent de detecter une menace et d’indiquer aux SAMs et au

Gun vers ou ils doivent se diriger. Cette ressource est donc extremement importante,

mais restraint les actions possibles. Il n’y a que deux STIRs sur la fregate, limitant a

2, le nombre de menaces engageables simultanement. Aussi, les STIRs possedent des

angles morts. Le premier STIR couvre autour de la fregate de 120 a 240 degres et le

deuxieme de 60 a 300 degres. Le STIR est donc une ressource limitee et primordiale

a l’utilisation des “Hardkill”. Le choix du STIR a utiliser se revele donc important

lors de l’assignation des armes contre les menaces. De plus, le STIR prend un certain

temps, non fixe, a reperer les cibles pour bien les situer dans l’espace. Ce temps doit

etre considere lors de la planification. Le CIWS possede son propre systeme de radar et

peut agir des que la menace est engagee.

2.2.3 Les Softkill

Dans le present projet, les “softkill” sont divises en deux types, le chaff et le jammer.

Il s’agit de deux systemes distincts qui servent a contrer les menaces sans les detruire. Ils

agissent comme une diversion sur les menaces afin de changer leurs trajectoires initiales

et de leur faire rater la plateforme.

Le chaff est un nuage de petites particules metalliques qui sont envoyees a quelques

metres du navire. Cela a pour effet d’attirer le missile vers le chaff puisque ce dernier

emet plus d’energie que la fregate. La menace a donc l’impression que ce nuage est la

cible la plus importante et change sa trajectoire. Selon la disposition des lanceurs, il

est possible de lancer un chaff a 4 endroits distincts, soit au nord-ouest, au nord-est, au

sud-ouest et au sud-est de la fregate. Meme s’il est lance pour une menace en particulier,

il peut en influencer plusieurs a la fois. Nous considerons deux modes d’utilisation qui

sont les modes de seduction ou de distraction. Lance en seduction, le nuage de particule

metallique se situe a 250 metres du navire et a 125 metres d’altitude. D’autre part,

le chaff utilise en distraction est lance a 125 metres de la fregate et a 75 metres de

hauteur. Toutefois, comme le chaff est compose de petites particules metalliques, celui-

ci est sensible au vent. Ainsi, il faut prevoir ou lancer le chaff, car sa trajectoire et sa

position peuvent etre changees.

Il existe aussi une arme qui permet de tromper le radar guidant le missile ennemi.


Il s’agit du jammer. Il induit le radar de la menace en erreur, en retenant son signal

afin de lui donner l’impression que la plateforme est ailleurs. Dependant du systeme de

defense utilise, un chaff peut etre envoye directement a l’endroit ou le radar croit que

la plateforme est situee. En deplacement le navire par la suite, la menace a tres peu de

chance de retrouver sa cible principale.

2.2.4 Les secteurs

En outre, une notion importante a considerer dans la problematique est celle des

secteurs se situant autour de la fregate et representant des zones precises. En tout, il

y a 12 secteurs et ils sont divises en fonction des angles morts (blind zone) des armes

HK et SK. La figure 2.2 presente les secteurs definis par Morissette [40] et represente la

disponibilite des ressources selon le modele decrit precedament. Dans Morissette [40], il

utilise les secteurs pour faire la rotation de la fregate dans le but de rendre un plus grand

nombre de ressources disponibles. En effectuant une rotation, il permet de changer les

menaces de secteurs et ainsi profiter d’un nouveau groupe de ressource pour les contrer.

Il est aussi possible de classer les secteurs par le nombre de ressources disponibles dans

chaque secteur : (S1 = S7) > (S2 = S6 = S8 = S12) > (S9 = S11) > (S3 = S5) >

S10 > S4

10

145

350345

240

60

120

300

S1

S8

S7

S6

S5 S4 S3

S2

015

170190

215 S9

S10

S11

S12

Gun

CIWSJammerSTIR

Secteurs de la frégate

Fig. 2.2 – Secteurs de la fregate


2.3 Les scenarios

Les scenarios sont utilises lors des simulations afin d’analyser le comportement du

systeme de defense. Les scenarios ont ete construits dans le cadre de NEREUS, pour

representer des attaques contre la fregate.

2.3.1 Les menaces

Les menaces ont de multiples caracteristiques qu’il faut considerer. Durant une si-

mulation, on peut choisir de retrouver de 1 a 13 missiles. Bien entendu, la tache est plus

compliquee lorsqu’il y a plusieurs menaces. Aussi, une autre caracteristique a considerer

est l’angle duquel arrive le missile. Comme nous l’avons vu, les secteurs sont importants

et dependent directement des ressources disponibles.

De plus, la vitesse de la menace influence son niveau de dangerosite et fait varier le

nombre de re-engagement possible pour la contrer. Les vitesses couramment utilisees

dans nos scenarios sont 310 metres/seconde (subsonique), 510 metres/seconde et 810

metres/seconde (supersonique). La trajectoire d’un missile peut varier pendant qu’il

est en vol. Par exemple, il peut ne pas se diriger directement sur la plateforme et

changer tranquillement de trajectoire. Un missile peut aussi manoeuvrer, c’est-a-dire se

deplacer de droite a gauche, ou encore faire des tourbillons. Ceci rend le missile plus dur

a intercepter et entre en ligne de compte sur la probabilite de le detruire. La menace

la plus facile a contrer est donc celle qui suit une trajectoire en ligne droite avec une

vitesse subsonique.

2.3.2 Les types de scenarios

Plusieurs types de scenarios sont possibles dans la gestion des ressources en temps

reel. Nos scenarios ont tous des caracteristiques qui leurs sont propres et qui permettent

d’observer de quelle facon les systemes de defense se comportent dans diverses situa-

tions. Par contre, certaines caracteristiques reviennent d’un scenario a l’autre. Notam-

ment, c’est le cas pour la vitesse des missiles. Dans chaque scenario, on essaie de garder

une distribution uniforme des trois vitesses possibles. Ceci est important, car certaines

menaces deviennent plus prioritaires a contrer que d’autres. De plus, dans chacun des

scenarios, le nombre de menaces ainsi que leurs positions initiales ne sont pas par-

tages au C2. Evidemment, ces informations sont decouvertes au fil du temps lorsqu’une


certaine quantite d’information a ete accumulee.

Le scenario uniforme

Un premier type de scenario possible est celui d’une fregate attaquee par plusieurs

menaces (2 a 13 missiles). Ces menaces peuvent arriver de n’importe quel cote et les

vitesses sont constantes et subsoniques. La figure 2.3 represente un scenario de type

uniforme a 8 menaces. Il est facile de voir que chacune des menaces est assez dispersee

les unes des autres autour de la fregate. Une variante de ce scenario existe ou les

vitesses des menaces changent. Il s’agit du scenario Uniforme-D qui consiste a utiliser

des menaces supersoniques et subsoniques seulement afin de faire varier leur niveau de

danger.

10

145

350345

240

60

120

300

S1

S8

S7

S6

S5 S4 S3

S2

015

170190

215 S9

S10

S11

S12

Gun

CIWSJammerSTIR

Scénario Uniforme

Fig. 2.3 – Scenario Unifome

Le scenario contraint

Le scenario contraint utilise le scenario Uniforme-D, mais des changements sont

apportes a la fregate. Les angles morts ont ete augmentes, dans le but de creer un

scenario avec des contraintes plus importantes. Cette demarche sera utile pour observer


l’apport d’une approche utilisant l’evaluation de l’engageabilite. La figure 2.4 montre

le scenario type ou les zones aveugles sont augmentees. Cela a pour effet de rendre des

armes moins disponibles sur une surface plus grande. Dans la simulation, les portees

des armes ont legerement ete modifiees pour rendre le scenario plus contraignant.

Gun

CIWSJammerSTIR

Scénario Uniforme-Contraint

Fig. 2.4 – Scenario Contraint

Scenario Gaussien

Le scenario Gaussien recoit de 1 a 8 missiles concentres sur quelques secteurs

connexes. Pour choisir l’emplacement des menaces, il suit une distribution gausienne sur

les angles. On s’en sert pour simuler une attaque qui viendrait d’une direction donnee.

Il est donc plus difficile de se defendre dans une situation ou les memes ressources sont

constamment utilisees. C’est a ce moment que le choix de la menace a attaquer est tres

important, car la marge d’erreur est tres faible. Ainsi, utiliser une ressource pendant

une longue periode sur une mauvaise cible peut-etre fatale. La figure 2.5 presente un

scenario de type gaussien, dont les menaces ont ete regroupees dans les secteurs S1-S2

et S12.


10

145

350345

240

60

120

300

S1

S8

S7

S6

S5 S4 S3

S2

015

170190

215 S9

S10

S11

S12

Gun

CIWSJammerSTIR

Scénario Gaussien

Fig. 2.5 – Scenario Gaussien

2.4 L’apport au projet

Ce memoire se concentre pricipalement sur l’evaluation de l’engageabilite. Ce pro-

cessus se situe avant la planification et permet de savoir quelles actions sont admissibles

dans l’environnement. L’engageabilite est souvent negligee dans la creation de systeme

C2, mais demeure tres importante, car elle permet de reduire le facteur de branchement

pendant la planification. Plus ce facteur est eleve, plus il aura de possibilites a explorer

afin de trouver une solution. Le temps de recherche dans l’arbre des solutions sera alors

plus eleve. De plus, elle donne une nouvelle information sur les cibles, utilisee lorsque

vient le temps de choisir quelle menace attaquee.

Le paradigme des CSP est explique et developpe. Ainsi, les differents modeles sont

presentes et leurs avantages sont enumeres. Les algorithmes connus sont ensuite detailles

et illustres par des exemples. De plus, les CSP sont appliques a un domaine reel. Pa-

rallelement, des outils puissants ont ete utilises. Le simulateur SADM permet de tester

nos approches par une simulation tres pres de la realite. Pour sa part, ILOG Solver2

permet de modeliser et de resoudre l’evaluation de l’engageabilite de facon efficace.

Le tout permet d’avoir une approche complete qui reussit assez bien dans differentes

situations.

2http ://www.ilog.com


2.5 Sommaire

Le probleme etudie est inclus dans un processus complexe. Il demande de construire

une approche sur un systeme en temps reel dans un milieu incertain. Pour tester cette

approche, une fregate de type HALIFAX est utilisee dans divers scenarios. Ces scenarios

permettent de comprendre de quelle facon se comporte l’approche a l’etude devant

differentes situations. Ils contiennent differents types de menaces ayant une influence

directe sur le deroulement des simulations. La problematique etant maintenant definie,

les prochains chapitres demontreront de qu’elle facon il est possible de resoudre ce

probleme.

Chapitre 3

Probleme de l’evaluation de

l’engageabilite

La premiere partie de ce travail se situe au niveau de l’evaluation de l’engageabilite.

C’est dans cette partie que les informations fournies par l’environnement sont filtrees.

Ces informations sont divisees en variables et en contraintes qui interagissent ensembles.

Comme il y a un grand nombre de contraintes, il est impossible de toutes les considerer.

Il faut donc se concentrer sur les plus importantes, les plus critiques, et les inserer

dans le “Constraint Satisfaction Problem” (CSP). Le but premier de l’estimation de

l’engeagabilite est de fournir, selon un etat de l’environnement, les actions possibles

contre les cibles. Un etat comprend les informations sur les menaces et sur la plateforme.

Pour que toutes les actions soient admissibles, il faut etre en mesure de resoudre un CSP.

Ce chapitre presente comment le CSP est modelise et decrit le probleme de l’evaluation

de l’engageabilite.

3.1 La modelisation

Ce qui est interessant avec les CSP, c’est que celui qui s’en sert est entierement

libre et responsable de modeliser le probleme. Dans la plupart des cas, des centaines

d’algorithmes sont disponibles pour resoudre le probleme. Toutefois, il n’est pas tou-

jours facile de modeliser un probleme pour construire un CSP repondant a la definition

du probleme. Il faut choisir judicieusement les variables, bien limiter leurs domaines

et surtout bien definir les contraintes. Ensuite, s’il faut optimiser le tout, une fonction

d’objectivite doit etre choisie. De meme, s’il y a des variables stochastiques, il est indis-

Chapitre 3. Probleme de l’evaluation de l’engageabilite 19

pensable d’introduire une fonction de distribution sur les variables afin de representer

cette incertitude. Ces choix sont importants, car ils vont intervenir dans la resolution

du CSP et directement influencer la solution.

3.1.1 Les variables et les domaines

La definition du “Weapon Target Allocation (WTA)” en CSP se fait en trois etapes,

soit la definition des variables, des domaines et le choix des contraintes. Comme les deux

ensembles les plus importants sont les informations sur les menaces et sur les ressources,

elles se retrouvent au centre de la definition du CSP. Les variables sont definies dans

l’engageabilite, comme les ressources de la fregate, c’est a dire : SAM1, SAM2, Gun,

Ciws, STIR A, STIR B, Chaff, Jammer. Ces 8 ressources representent les variables

de notre CSP. S’il y a deux SAMs, c’est que la fregate possede deux lanceurs qui

sont en mesure de projeter leurs SAMs simultanement. Chacune de ces variables doit

avoir un domaine precis. Dans l’engageabilite, ce qui nous interesse est de savoir quelles

ressources peuvent etre assignees a une menace donnee. Pour y parvenir, le domaine des

variables doit etre compose des menaces presentes dans l’environnement. Cela signifie

qu’au debut d’un scenario, si toutes les ressources sont disponibles et qu’il y 4 menaces

de detectees, l’ensemble variable/domaine sera le suivant :

– SAM1 = {1,2,3,4}

– SAM2 = {1,2,3,4}

– Gun = {1,2,3,4}

– Ciws = {1,2,3,4}

– STIR A = {1,2,3,4}

– STIR B = {1,2,3,4}

– Chaff = {1,2,3,4}

– Jammer = {1,2,3,4}

La modelisation de la sorte est un choix de design. Elle aurait pu etre inversee en

considerant les menaces comme les variables et les armes comme les domaines. Par

contre, apres avoir essaye de modeliser les contraintes et les interactions entre les res-

sources, il est beaucoup plus facile de modeliser le probleme tel que presente. Les

contraintes sont principalement exprimees sur les ressources et non sur les menaces.

Ces restrictions ont des repercussions sur les variables et non pas sur les valeurs du

domaine des variables. Par exemple, si on veut modeliser le cas ou les deux SAMs ne

peuvent pas assigner la meme menace, il suffit de mettre la contrainte “SAM1 6= SAM2”.

Par contre, si nous voulions utiliser la modelisation inverse, en se servant des menaces

comme variables, il serait tres dur de s’assurer que deux menaces distinctes n’ont pas

le meme SAM d’assigne. Il faudrait alors traiter particulierement chaque domaine des

variables. Ceci s’explique par le fait que mettre une contrainte de type “Menace1 6=


Menace2”, signifierait que les deux menaces n’ont aucune ressource identique. Cette

contrainte est beaucoup plus severe que “SAM1 6= SAM2”. De plus, il n’y a pas de

moyens efficaces de faire cette restriction sur la modelisation des menaces en tant que

variables. Le choix de mettre les ressources en variables facilite ainsi la modelisation

des contraintes.

3.1.2 Les contraintes

Sur une plateforme militaire, les contraintes sont nombreuses et se divisent en deux

groupes. Elles sont d’ordre local ou global. D’une part, les contraintes locales ne touchent

qu’une seule ressource. Par exemple, la contrainte de portee est locale et propre a chaque

arme. L’epuration est executee seulement sur une variable. Les contraintes globales,

pour leur part, englobent plusieurs variables. Elles affectent donc le domaine de deux

variables ou plus. En effet, deux SAMs ne pouvant engager la meme ressource est une

restriction globale (SAM1 6= SAM2). La liste ci-dessus regroupe quelques contraintes

traitees et implementees pour la fregate du probleme. Cette liste est composee de plu-

Contraintes Types

Zone aveugle Locale

Portee maximale Locale

Portee minimale Locale

Munitions Locale

Deux SAMs ne peuvent assignes la meme menace Globale

Maximun de deux chaffs actifs simultanement Globale

Uniquement un STIR par menace Globale

Peut assigner un SAM ou le Gun seulement Globale

si un STIR est sur la menace

sieurs contraintes, comme celle de la zone aveugle, des portees maximales et minimales,

des munitions et des contraintes de type globales. Effectivement, pour chaque menace

et chaque ressource, la contrainte s’assure que la menace n’est pas situee dans l’angle

aveugle de la ressource. Dans le cas echeant, la menace est effacee du domaine ou la

contrainte a ete violee. Pour sa part, la limitation sur les portees sert a definir si la

ressource peut atteindre la cible. En analysant les portees minimales et maximales,

elles permettent de determiner sur quelle periode de temps la cible est accessible. Dans

le meme ordre d’idees, le nombre de munitions permet de valider si la ressource peut

encore engager une cible. Subsequemment, les contraintes globales servent a modeliser

les regles suivantes :


– Un SAM detient la priorite sur un Gun pour engager une menace.

– Un CIWS doit engager une menace des qu’il le peut.

– Un SAM ou un Gun peuvent etre assignes sur une menace seulement si un STIR

est sur la cible.

3.2 Niveau d’Engageabilite (NE)

Le niveau d’engageabilite (NE) fournit de l’information supplementaire sur la me-

nace et definit l’espace de faisabilite de la menace. Pour toutes les solutions possibles,

l’union des actions admissibles sur les menaces est faite. L’union permet de savoir quelles

ressources sont disponibles pour chaque menace. A l’aide de ces ressources, un calcul

permet de trouver le NE pour chaque cible. Plus le NE est eleve, plus il y a d’actions

possible contre la menace, et moins nous sommes contraints dans l’assignation d’une

ressource.

Il est indispensable de calculer le NE pour etre en mesure de bien analyser les

menaces. Pour se faire, il faut commencer par assigner un niveau d’efficacite aux armes.

Initialement, nous avons donne des valeurs d’efficacite fixe aux armes par rapport a

leurs types. La solution etait peu precise et on obtenait souvent plusieurs menaces

avec le meme niveau d’engageabilite. Cette situation n’etait pas ideale, car une seconde

distinction devait etre faite par rapport au nombre de ressources disponibles pour chaque

menace. La formule 3.1 represente la premiere equation utilisee :

NETi=

|Rti|∑

x=0

CST (rx) (3.1)

ou Ti est la menace pour laquelle le NE est calcule et CST (rx) represente la constante

d’efficacite pour la ressource rx. Puis, |Rti| represente le nombre de ressources dispo-

nibles dans Ti. Pour avoir une meilleure evaluation du NE, le calcul a ete modifie afin

de considerer le PK (Probability of Kill) de l’arme multiplie par le temps ou cette res-

source est disponible. La formule 3.2 represente l’equation considerant le PK de l’arme

multiplie par le temps :

NETi=

|Rti|∑

x=0

PK(rx) ∗ Temps(rx, Ti) (3.2)

ou PK(rx) est la probabilite de detruire une menace avec la ressource rx, et Temps(rx, Ti)

est la duree pendant laquelle la ressource rx peut-etre utilisee sur la menace Ti. Par

contre, comme les PK ne sont pas constants, cette methode est une approximation du


NE. Pour avoir encore une meilleure estimation du NE, il faut considerer que les PK

peuvent varier en fonction de la distance de la menace. Plus la menace est proche,

plus les chances de la detruire sont bonnes. C’est pourquoi le calcul de l’integrale du

PK selon la distance de la menace donne une meilleure evaluation du NE, comme le

represente la formule 3.3 :

NETi=

|Rti|∑

x=0

∫ DistMax(rx,ti)

DistMin(rx,ti)

(Pk(rx))drx (3.3)

ou DistMin(rx, ti) et DistMax(rx, ti) sont les distances, selon le temps ou la ressource

rx est utilisee sur la menace ti. La fonction Pk(rx) donne la distribution de probabilite

de detruire une menace rx, en fonction de la distance de celle-ci.

Le resultat est considere comme le NE de la menace au moment present. Il sera

utilise par les algorithmes d’assignations.

3.3 Pourquoi utiliser l’engageabilite ?

Meme si les CSP peuvent etre NP-complet, ils demeurent tres utiles pour resoudre

des problemes complexes. En fait, les CSP ont l’avantage de pouvoir diminuer la duree

du calcul pour trouver une solution lorsque les contraintes sont bien utilisees. Ils per-

mettent de reduire les domaines des variables en plus de detecter des inconsistantes dans

ces dernieres. En reduisant les domaines, l’espace de recherche est necessairement reduit

dans le CSP, ce qui accelere de beaucoup le processus d’assignation d’une valeur a une

variable. De plus, si un domaine d’une variable est vide, il ne sera jamais possible de

trouver une valeur avec cet ensemble. Il faudra donc revenir en arriere (backtracking).

Aussi, l’evaluation de l’engageabilite est un concept qui nous permet d’avoir un

ensemble d’action valide en tout temps. C’est important, car a tout moment il est

possible de savoir si une action peut etre executee. Ces actions ne sont pas toujours

faciles a trouver. Par exemple, certaines approches procedent par regles (reactif) [32],

tandis que d’autres font une analyse sur toutes les actions possibles sur une periode de

temps [6] [9]. Il est donc tres couteux pour les approches deliberatives de ne pas utiliser

l’engageabilite, car cela augmente le temps de calcul. Les plans deviennent plus grands

et la recherche de la solution est plus longue. L’engageabilite restreint ce probleme

de facon efficace, en ne donnant qu’un ensemble d’action faisable. En plus, evaluer

l’engageabilite, permet de donner aux menaces un niveau d’engageabilite. Ce niveau

est ensuite utilise comme une donnee primordiale dans le choix des menaces a assigner.


Par ailleurs, les approches de planification ne considerent pas l’aspect d’evaluation

de l’engageabilite, puisqu’il est inexistante. Pour combler ce manque, ils doivent utiliser

des methodes probabilistes, ou d’apprentissage afin de realiser qu’un choix d’assignation

est mauvais. Il est souvent difficile de constater qu’une decision est mauvaise dans le

feu de l’action. Les effets se traduisent sur le long terme, car un mauvais choix d’ac-

tion elimine des ressources de l’ensemble de faisabilite. L’evaluation de l’engageabilite

decouvre l’ensemble de faisabilite et permet a la menace qui a le moins d’options d’avoir

plus de chance d’etre assignee en premier.

Par exemple, suivant la figure 3.1, suspposons que nous avons deux menaces a

detruire, la plus dangereuse (menace A) est dans un secteur ou les deux STIRs sont dis-

ponibles et la seconde (menace B) est dans celui ou que le STIR A est disponible. Avec

l’engageabilite, il est clair que le NE est plus eleve sur la premiere menace, puisqu’il y

a plus de ressources disponibles. Il faut donc d’abord assigner la deuxieme menace avec

le STIR A. Il sera par la suite facile d’assigner la menace plus dangereuse avec le STIR

B. Bref, tout ceci se fait extremement facilement, puisque nous connaissons l’ensemble

des actions possibles, le NE pour chaque menace et un choix d’assignation intelligent.

Sans une approche utilisant le principe de l’engageabilite, il faudrait tenter les deux

actions pour observer laquelle fournit le meilleur resultat. Par exemple, pour la menace

A, qui est la plus dangereuse, il y a un risque d’utiliser le STIR A et de ne plus etre

en mesure d’assigner la menace B par la suite. Evidemment, les approches intelligentes

trouveront qu’il faut utiliser le STIR A sur la menace B et le STIR B sur la menace A.

Cependant, plusieurs simulations ou periodes d’apprentissage seront necessaires pour

comprendre le bon choix. Cette option peut s’averer une lourde perte de temps dans

des cas plus complexes.

Niveau d’Engageabilité

Menace A = 10Menace B = 5

Niveau de Menace

1. Menace A2. Menace B

a

b

Fig. 3.1 – Exemple 1


De plus, connaıtre le niveau de menace est fort utile pour decider des etapes logiques

de la defense. Cependant, il peut arriver qu’un groupe de menaces avec des proprietes

semblables soient autant dangereuses, mais dispersees autour de la plateforme. Dans ce

cas, utiliser uniquement le critere de la dangerosite reduit les chances d’assigner toutes

les menaces. Ainsi, en considerant l’engageabilite, il est fort probable d’augmenter le

nombre d’assignation faite sur le groupe de menaces.

La figure 3.2 propose un exemple ou 3 menaces, de niveaux de menace presque

identiques sont ordonnees comme suit : {C,A,B}. Les menaces A et B sont dans des

secteurs ou le STIR A est le seul disponible pour la menace A, et le STIR B est le seul

possible pour la menace A. La menace C peut cependant utiliser l’un des deux STIRs.

Il ne serait pas tres intelligent de commencer par assigner la menace C, et ensuite d’y

aller avec A ou B, sous pretexte qu’elle est la plus dangereuse. Dans ce cas, si la menace

C n’a pas ete detruite, mais que la menace A l’a ete, il est rendu impossible de prendre

le STIR disponible pour assigner B, car il est utilise par C. Il est donc plus logique de

considerer l’engageabilite, d’assigner A et B avec leurs STIRs et d’attendre de detruire

n’importe laquelle des deux menaces, pour utiliser le premier STIR disponible sur C.

Niveau d’Engageabilité

Menace A = 5Menace B = 5

Niveau de Menace

2. Menace A3. Menace B

a

b

Menace C = 10

1. Menace C

c

Fig. 3.2 – Exemple 2

Dans notre cas, pour resoudre l’evaluation de l’engageabilite, nous avons utilise les

CSP. En modelisant le probleme en variables et contraintes, l’ensemble de faisabilite

des actions se trouve avec l’union des solutions possibles au CSP. Par la suite, le NE

est calcule pour chaque menace et le tout est donne a l’algorithme charge de planifier

et de faire le choix des actions. Pour trouver les solutions du CSP, nous utilisons ILOG

Solver, discute dans la prochaine section.


3.4 ILOG Solver

Un des outils les plus performants pour resoudre les “Constraint Satisfaction Pro-

blem” (CSP) est le ILOG SOLVER1. Plusieurs outils pour les CSP sont tres interessants,

mais les proprietes de ILOG lui permettent d’etre tres souple et flexible. Il offre des

librairies C++, ce qui nous permet de lier notre systeme avec ILOG et le simulateur

SADM. Dans le cadre du projet, nous avons choisi de l’utiliser, car il est repute pour

etre extremement rapide. Pour resoudre le probleme de l’engageabilite, il faut donc

modeliser le CSP avec ILOG.

Par contre, pour l’utiliser adequatement, plusieurs classes ont du etre ajoutees afin

de mieux repondre a nos besoins. Il etait necessaire de rentre l’approche generique, c’est-

a-dire applicable a n’importe quel probleme de “Weapon Target Assignment”(WTA).

C’est pourquoi une couche supplementaire de classe de contraintes a ete ajoutee afin

d’encapsuler les classes ILOG. Ces classes representent des contraintes plus complexes,

formees a partir des contraintes de base fournies par ILOG. De plus, dans le but

d’accelerer la recherche de la solution, il est possible de donner a ILOG une solution

partielle (i.e. : la derniere utilisee).

De meme, il est possible de faire de l’ordonnancement avec ILOG. Dans le cadre de ce

memoire, il a ete fait et implemente a l’aide de contraintes temporelles. Ces contraintes

sont des predicats qui indiquent la preseance des taches. Par exemple, il est important

que le STIR soit assigne a une cible avant de lancer un SAM. Le temps pour assigner

le STIR a une menace est donc calcule et le SAM est lance par la suite. Apres quelques

experimentations, il a ete remarque qu’il n’y a pas beaucoup d’actions (moins de 10)

a planifier en meme temps. Pour le moment, l’ordonnancement necessite que quelques

regles simples, ce qui permet de sauver de l’espace memoire. Par contre, si l’agent devait

faire face a plusieurs actions (10 et plus), il serait preferable d’utiliser ILOG pour en

faire l’ordonnancement.

L’engageabilite est donc evaluee a l’aide d’un CSP inclus dans ILOG Solver. Ce

dernier permet en outre de trouver toutes les solutions possibles aux CSP. C’est tres

interessant puisque c’est avec celles-ci que le NE est calcule. De plus, une jonction

sur tous les ensembles de ressources est faite afin de trouver quelles ressources sont

disponibles.

1http ://www.ilog.com/products/solver/


3.5 Les domaines dynamiques

L’engageabilite consiste aussi a garder les domaines des variables a jour. Les do-

maines sont constamment en changement, principalement parce que des actions sont

prises dans l’environnement et qu’il y a une progression dans le temps. Par exemple,

une arme qui etait disponible au temps T, ne l’est peut-etre plus au temps T’. A tout

moment, nous devons donc nous assurer que ces informations sont propagees dans notre

modele. Pour accomplir cette tache, des evenements particuliers sont necessaires pour

enclencher les mises a jour sur les variables.

Le premier type d’evenement concerne les menaces. Celles-ci sont constamment en

mouvement et le but est de les detruire. Il faut donc constamment les surveiller durant

la simulation, car elles sont responsables de plusieurs mises a jour des domaines. Les

evenements de mises a jour sont les suivants :

1. De nouvelles menaces apparaissent ;

2. Une menace est detruite ;

3. Une menace change de secteur ;

4. Une menace entre ou sort de la portee d’une arme.

Quand un de ces quatre evenements survient, il faut alors reevaluer l’engageabilite,

resoudre le CSP et mettre les domaines a jour.

Le second type d’evenement survient par rapport a la fregate. Il faut en surveiller

les ressources et ajuster les domaines en consequence. Si une ressource est assignee sur

une cible et qu’elle est aussi disponible pour d’autres menaces, il faut la supprimer

du domaine des autres variables. Une ressource peut devenir non disponible si elle est

assignee sur une autre menace, mais egalement si elle n’est plus operationnelle. Cela se

manifeste par un manque de munition ou un bris.

En gardant constamment a jour les domaines et en considerant les changements

sur les menaces et sur les ressources, nous sommes assures que l’ensemble de solutions

suggerees par l’engageabilite sera toujours valide. Bref, detenir un ensemble valide a

tout moment est un element tres important, car il assure que les actions pourront etre

effectuees.


3.6 Presentation de l’engageabilite

Le but premier de l’engageabilite est d’aider l’operateur tactique a prendre des

bonnes decisions rapidement dans des situations de stress. Afin d’y arriver, il faut etre

capable de presenter les informations de facon simple et concise. Evaluer l’engageabilite

permet ainsi d’obtenir une information supplementaire sur les menaces, laquelle aidera

l’operateur a faire son choix sur les cibles a considerer prioritairement.

3.6.1 L’espace de faisabilite

L’operateur a besoin de connaıtre l’espace de faisabilite des actions contre les me-

naces. Pour y parvenir, il faut etre en mesure de representer graphiquement les domaines

dynamiques. Il est possible de construire un graphique a plusieurs axes representant les

informations fournies par l’environnement. Chacun des axes represente une information

qui permet de definir l’espace de faisabilite. Plus l’espace de faisabilite est faible, plus

la menace sera critique. La figure 3.3 illustre comment il est possible de representer

cet espace. Les axes principaux sont souples et peuvent etre conserves ou elimines de

l’espace de faisabilite. L’important est que l’echelle debute par une valeur quantifiable

et que la valeur la plus eloignee de l’origine soit la valeur la moins critique. Dans le

cas de l’axe de la vitesse, une menace tres rapide est situee tout pres de l’origine. Ceci

s’explique par le fait que plus une menace est rapide, moins elle peut etre reengagee,

donc moins il y a d’options pour la contrer. L’axe des secteurs se rapporte a l’ordre des

secteurs introduit a la section 2.2.4. La region qui offre le moins d’options, representera

donc le point le plus proche de l’origine. Pour determiner quelle menace a le plus pe-

tit espace de faisabilite, il faut calculer l’aire. Dans ce but, la sommation des aires de

tous les triangles formes entre les arcs doit etre calculee. Plus l’aire sera petite, plus la

menace sera importante pour l’operateur.

Comme c’est un processus dynamique, la figure 3.4 montre de quelle facon les do-

maines ont evolue durant 22 secondes. L’espace de faisabilite a change et aucune menace

n’a ete detruite pendant ce temps.

L’operateur est alors a meme d’evaluer les menaces, d’observer les changements et

de prendre une decision par rapport a ces informations. Il est aussi possible d’ajouter

des axes pour augmenter l’information de l’espace de faisabilite.


Niveau de Menace

NE

Distance

Vitesse

Secteurs

Menace 1 (201.01u2)

Menace 2 (154.56u2)

Fig. 3.3 – Espace de Faisabilite T=10

Niveau de Menace

NE

Distance

Vitesse

Secteurs

Menace 1 (62.65u2)

Menace 2 (54.55u2)

Fig. 3.4 – Espace de Faisabilite T=32


3.6.2 Les diagrammes de Gantt

L’evaluation de l’engageabilite apporte plus que le niveau d’engageabilite et l’espace

de faisabilite. Elle est aussi en mesure de donner la periode de temps pour laquelle

les ressources sont disponibles. Il est important que l’operateur puisse juger quelles

ressources sont admissibles presentement, mais aussi pour quelle duree. Ainsi, chaque

fois qu’une ressource peut etre assignee contre une menace, il faut evaluer le temps

ou cette ressource ne pourra plus etre utilisee. Comme l’engageabilite est un processus

qui evalue le moment present, le temps qui nous interesse est seulement celui ou la

ressource ne sera plus disponible. Une bonne technique pour le representer est d’utiliser

un diagramme de GANTT. La figure 3.5 illustre comment il est possible de presenter

les options disponibles a l’operateur. Evidemment, tout comme pour la presentation de

l’espace de faisabilite, le tout est dynamique et les boıtes se modifient avec le temps.

Menace 1

Menace 2 Jammer

CIWS

GUN

SAM

STIR1

Temps 10 20 30 40 50

Fig. 3.5 – Diagramme de Gantt

Chapitre 4

Satisfaction des contraintes

4.1 Introduction

Depuis plusieurs annees, des recherches ont ete effectuees au sujet des problemes de

satisfaction de contraintes. De ces etudes, un modele mathematique a emerge et il s’agit

du CSP [34], [20], [46], [22], [23], [35]. Le modele CSP initial, restreint aux contraintes

binaires entre deux variables, a ete introduit par Montaranari [52]. Les avantages des

CSP sont multiples puisque les contraintes surviennent naturellement dans plusieurs

problemes courants. Ainsi, les contraintes permettent de reduire l’espace des domaines

ce qui a pour effet de reduire l’espace de recherche. Le CSP permet en outre de bien

representer les problemes de planification et de gestion des ressources.

Ce chapitre presente les “Constraint Satisfaction Problem” (CSP), les differents

types de contraintes composant le modele, les classes de CSP ainsi que les moyens

pour les resoudre. Pour commencer, nous allons definir le CSP et introduire quelques

problemes combinatoires afin de bien illustrer l’utilisation de ceux-ci.

4.1.1 La definition du CSP

Le terme CSP vient des mots anglais “Constraint Satisfaction Problem”. En francais

il pourrait etre defini par “probleme de satisfaction de contraintes”. On peut definir un

CSP de facon formelle par un ensemble de variables {X1, X2, ..., XN} ou chaque variable

Xi a un domaine Di non vide. Lorsque les domaines des variables sont discrets et finis,

il est possible d’enumerer tous les cas. Il devient donc plus facile de traiter le CSP. Pour

Chapitre 4. Satisfaction des contraintes 31

les domaines discrets et infinis, il n’est pas possible de tous les enumerer et c’est alors

que les contraintes deviennent tres utiles. Celles-ci sont presentees comme un ensemble

{C1, C2, ..., CN} ou chaque contrainte Ci sert a creer un ensemble de variables non

permises. Un CSP est represente par un tuple < X,D,C > ou une solution est une

assignation a toutes les variables (Xi = vi, Xj = vj, ..., XN = vn). De plus, une solution

dite consistante est un ensemble de valeurs associees aux variables qui ne viole pas les

contraintes.

Pour representer visuellement un probleme de satisfaction de contraintes, il est pos-

sible de le faire a l’aide d’un graphe de contraintes. Ce type de graphe est represente

a la figure 4.1 et il illustre les relations entre les variables. Un arc entre deux noeuds

definit la portee d’une contrainte. S’il n’y a pas d’arc entre deux noeuds, c’est qu’il n’y

a pas de contrainte directe.

x1 x2

x3 x4

=>

Fig. 4.1 – Graphe de contraintes

4.1.2 Les problemes combinatoires

La satisfiabilite (SAT)

SAT est un probleme de decision tres difficile dans lequel le but est de trouver si une

formule logique est satisfiable. Dans ce cadre, une formule logique est composee d’une

conjonction de clauses. Une clause est formee de plusieurs disjonctions de litteraux.

Ainsi, une formule est SAT s’il est possible d’assigner des valeurs, vraies ou fausses,

aux variables afin d’evaluer la formule logique a vrai. Le probleme de la “Satisfiabilite”

(SAT) est le probleme utilise dans le theoreme de Cook [11] qui montre que SAT est

un probleme NP-Complet. La classe de probleme NP-Complet signifie qu’il n’existe

pas d’algorithme connu pouvant resoudre toutes les instances du probleme en temps

polynomial.

Subsequemment, la forme 3-SAT est une restriction du probleme SAT, elle consiste

a avoir 3 litteraux par clause. Ce probleme reste tout meme NP-Complet [11]. Voici a


quoi ressemble une formule logique dans 3-SAT :

φ = (l1 ∨ l2 ∨ l3) ∧ (l1 ∨ ¬l2 ∨ l4) ∧ (¬l2 ∨ ¬l3 ∨ l5) (4.1)

Pour savoir si la formule φ est SAT, il faut trouver la valeur des variables qui montre

que la formule peut etre vrai. Il existe plusieurs techniques qui permettent d’evaluer

une formule de type 3-SAT. Parmi celles-ci, il y a la methode de reduction de formule

ou le DPLL [15] qui applique une certaine forme de backtracking. Par contre, ce qui

nous interesse ici, c’est d’utiliser les CSP pour resoudre 3-SAT.

Pour commencer, il faut prendre chaque litteral de SAT et le transformer en une

variable du CSP. Comme les seules valeurs permises sont vrai ou faux, le domaine des

variables sera {vrai, faux}. Puis, pour formaliser les contraintes, nous devons transfor-

mer chaque clause en contrainte. Pour se faire, les litteraux qui rendent la clause fausse

doivent etre enleves. Cela devient possible si on sort les negations et que l’on inverse les

valeurs. Dans cette optique, la clause (l4 ∨ ¬l2 ∨ l1) serait mise en contrainte de cette

facon : ¬(l4 = faux ∨ l2 = vrai ∨ l1 = faux). De cette maniere, la clause est assuree

d’etre evaluee “vrai” si les contraintes sont respectees. Ainsi, si pour chaque clause,

ce type de contraintes est ajoute, la formule sera SAT (si possible) puisque toutes les

clauses seront vraies.

Coloration d’un graphe

Un probleme de coloration de graphe, comme 3-COL, consiste a colorer les noeuds

d’un graphe dans le cas ou deux noeuds voisins ne peuvent etre colores de la meme cou-

leur. La plupart du temps, ce probleme est illustre par une carte geographique ou deux

pays voisins ne peuvent etre colores identiquement. Le chiffre 3 devant COL designe

le nombre de couleurs possibles pour colorer un noeud. Ce probleme se transforme

naturellement en CSP, il suffit de considerer chaque noeud comme une variable et le

domaine comme les 3 couleurs permises. Etant donne qu’il existe seulement un type de

contraintes dans le probleme : deux noeuds voisins ne peuvent avoir la meme couleur.

Il faut donc ajouter une contrainte entre chaque noeud adjacent du graphe, specifiant

que deux voisins ne peuvent avoir la meme valeur (i.e. France 6= Espagne ).

Les Q-Reines

Le probleme des Q-Reines consiste a les placer sur un echiquier de QxQ, Q reines,

de sorte qu’aucune reine ne s’attaque. Considerant les memes regles que pour les echecs,


une reine peut attaquer n’importe quelle piece se trouvant sur ses deux diagonales, sur

sa rangee ou sa colonne. Resoudre le probleme des Q-Reines en CSP demande un peu

plus d’attention dans la definition des contraintes. D’abord, les variables sont definies

comme chacune des rangees (Q) de l’echiquier. Les valeurs possibles du domaine sont

equivalentes a toutes les positions possibles de la reine sur cette rangee. Il faut donc

comprendre que le domaine est compose des Q positions sur les colonnes. Il y a donc 3

types de contraintes a respecter sur l’echiquier :

1. Aucune reine sur la meme colonne [Xi 6= Xj].

2. Aucune reine sur la meme diagonal Nord-Ouest [ Xi −Xj 6= i− j ].

3. Aucune reine sur la meme diagonal Sud-Est [ Xj −Xi 6= i− j ].

Etant donne que chaque variable represente une rangee, nous savons par defaut qu’il

n’y aura pas deux reines sur une meme rangee. Nous n’avons donc pas besoin d’ajouter

de contraintes pour celles-ci. Le probleme le plus utilise et le plus conventionnel est

celui des 8-Reines. La figure 4.2 represente une solution a ce probleme.

Fig. 4.2 – Solution au 8-Queen

4.1.3 La complexite

Pour resoudre un CSP, il est possible d’utiliser une approche simple, qui consiste

a parcourir tous les ensembles de valeurs possibles et de voir si elles satisfont les


contraintes. En general, cette methode ne peut pas etre appliquee, car elle est exponen-

tielle sur le nombre de variables (n). De plus, les CSPs sont generalement NP-Complet

[43], c’est pourquoi il est important de prendre des approches differentes ( heuristique

de recherche, approximation, etc) pour contourner la completude. Il faut noter, cer-

taines structures de graphe dans les CSP peuvent faciliter la resolution du probleme.

Une structure en forme d’arbre a l’avantage d’etre resolue en temps lineaire. Les tech-

niques de decomposition de graphe en arbre peuvent s’averer tres utiles pour reduire la

complexite des problemes. L’absence de cycle dans les arbres est aussi un avantage tres

important a considerer. Il facilite la propagation des contraintes et la verification de la

consistance de celles-ci.

4.1.4 Les types de contraintes

Les contraintes d’un probleme peuvent etre definies de differentes facons. Il peut y

avoir des contraintes sous forme logique, algebrique ou mathematique. Il est possible

egalement de les regrouper en types de contraintes, soient temporelles, de ressources,

locales et globales.

Les contraintes temporelles

Les contraintes temporelles sont tres utiles pour definir les relations entre les evenements.

Elles sont generalement utilisees pour ordonnancer les activites dans le temps afin

qu’elles soient assignees avec les bonnes ressources au bon moment. Il existe differents

types de contraintes temporelles qui aident a definir les relations entre les evenements.

L’algebre d’intervalle d’Allen (IA)[3] permet de representer de facon formelle les

relations entre deux intervalles temporels. Le modele d’Allen aide a presenter des

imprecisions, ce qui n’est pas possible lorsque les relations temporelles sont relatives

a une date ou un temps precis.

En consequence, l’algebre d’Allen introduit treize relations possibles entre des ac-

tivites : before, after, during, contains, overlaps, over-lapped-by, meets, met-by, starts,

started by, finishes et finished-by. En fait, elles pourraient etre restreintes a sept, car

la forme inverse des relations y est aussi exprimee. Ces relations sont presentees a la

figure 4.3. Ainsi, il est possible d’exprimer que le missile 1 est lance avant le missile 2 par

la relation suivante : missile1 < missile2. Cette technique permet donc de modeliser

les contraintes temporelles de facon claire, precise et dans un cadre mathematique. De


plus, ces relations de contraintes sont facilement representables sur un graphe ou chaque

activite est un noeud et ou les arcs sont augmentes par l’algebre d’intervalle Allen.

Relation Symbole Symbole

inverse

Exemple

Pictogramme

Terme

anglais

X avant Y < > XXX YYY before

X égal à Y = = XXX

YYY

equal

X rencontre Y m mi XXXYYY meets

X chevauche Y o oi

XXX

YYY

overlaps

X durant Yd di

XXXYYYYYY

during

X début Ys si

XXXXYYYYYY

starts

X fini Yf fi

XXXYYYYYY

finishes

Fig. 4.3 – Relations d’Allen

Cependant, l’algebre IA demande beaucoup de temps calcul par son nombre de

possibilites (213 * 213 relations). C’est pourquoi la methodologie “Qualitative Point

Constraint (QPA)” a ete introduite. Elle permet de representer les contraintes par des

points precis dans le temps. Les relations sont exprimees en “Basic Temporal Relation

(BTR)”. Une relation BTR est une relation qui est soumise a deux conditions :

1. Tous les elements sont mutuellement exclusif.

2. L’union des elements est la contrainte universelle, c’est-a-dire, permet toutes les

valeurs.

Par exemple, une relation Cij = {r1, ..., rn} peut aussi etre exprimees par : (Xir1Xj)∧

... ∧ (XirnXj). De cette facon, Cij est une contrainte entre deux variables Xi et Xj et

ou ri ∈ BTR.

Subsequemment, le “Qualitative Point Constraint” permet de d’utiliser que les rela-

tions BTR suivantes : {=, <,>}. Pour travailler avec ces relations, il existe trois types

d’algebre, le Basic Point Algebra (BPA), le Point Algebra (PA) et le Convex Point

Algebra (CPA). Le BPA (basic point algebra) a pour but d’utiliser les relations afin

de creer un ordre dans les evenements. Pour que les contraintes temporelles soient res-

pectees, il faut trier les elements de facon topologique [12], ce qui permet par la suite

de les ordonnancer correctement.


Pour sa part, PA transforme les relations BTR en un graphe-≤- 6=. Seules les re-

lations ≤ et 6= y sont utilisees. Ce type de graphe assure la consistance, seulement si

aucune paire de noeuds n’est connectee par une arrete 6= et qu’il n’existe pas une boucle

comprenant une arrete ≤ [31].

Le CPA est represente dans un graphe dirige et pondere. Il utilise les memes relations

que le BPA, mais transforme ces relations en arcs tels qu’exprimes a la table 4.1. Une fois

la transformation effectuee, l’utilisation d’un algorithme de plus court chemin, tel que

Dijkstra, ou Floyd-Warshall [12], doit etre applique. Ce chemin donnera une solution

au probleme satisfaisant les contraintes temporelles.

xi = xj transforme en arcs xi ≤ xj et xi ≥ xj

xi ≤ xj transforme en arcs xi+∞→ xj et xi

0→ xj

xi < xj transforme en arcs xi+∞→ xj et xi

−ǫ→ xj

Tab. 4.1 – Convex Point Algebra

Les contraintes de ressources

Dans plusieurs problemes d’allocation de ressources, certaines contraintes peuvent

survenir. Il est possible d’en degager quatre groupes couvrant les diverses restrictions

sur les ressources :

A) La ressource unitaire est une ressource pouvant etre utilisee que par une activite

a la fois. Ceci cree un probleme, car elle devient alors une ressource critique

lorsque plusieurs taches veulent utiliser la meme ressource en meme temps. Dans

ce cas, il faut bien faire la gestion afin de favoriser certaines taches par rapport

aux autres. Malheureusement, cela entraıne de nombreux delais et demande une

gestion adequate des taches.

B) La ressource de volume est un type de ressource limite par son nombre d’unite,

qui ne peut etre excede. Cela peut etre genant, car la planification demande de

tenir compte de l’utilisation futur des ressources. Ne pas savoir le nombre d’unite

disponible dans l’avenir, demande plus de calcul pour gerer adequatement les

ressources. Lorsqu’il est possible de savoir le nombre d’unites qui sera utilise, il

suffit de bien planifier et de tout partager de facon efficace. Par contre, lorsque les

taches qui suivent a moyen terme sont inconnues, il peut arriver que des unites

soient gardees en reserve mais qu’elles ne soient jamais utilisees par la suite. Il est

egalement envisageable de les utiliser maintenant et d’avoir une penurie a moyen

terme. Il faut donc etre vigilant avec ce type de ressources et les utiliser de facon

intelligente et moderee.


C) La ressource d’etat peut etre utilisee par une activite seulement lorsque le

systeme est dans un etat precis. Ce type de ressource apporte parfois des difficultes

puisque la methode pour arriver a l’etat permettant d’utiliser la ressource est

souvent inconnue. Evidement, selon les systemes, obtenir le bon etat peut-etre

tres facile, comme tres difficile.

D) La ressource non renouvelable est un effectif ne pouvant etre renouvelles. Il

faut donc etre conscient qu’il n’y aura pas moyen de profiter a nouveau de cette

ressource.

Chaque type de ressources presente ci-haut peut se retrouver dans un probleme

d’allocation de ressource. Considerant une instance de notre probleme de gestion de

ressources ou nous sommes limitees a 3 SAMs et a deux STIR et dont le but est d’allouer

les bons SAMs afin de contrer les menaces les plus dangereuses. Par consequent, dans cet

exemple, chaque type de contrainte sur les ressources s’y trouve. La ressource unitaire

est presente par le fait qu’il est impossible d’allouer le meme SAM a plusieurs menaces.

En effet, un SAM peut etre assigne a une seule menace. La ressource de volume, pour sa

part, se presente sous le nombre limite de SAMs disponibles sur la plateforme. De plus,

une ressource non renouvelable dans ce type de probleme est necessairement le temps.

Chaque seconde perdue, peut etre critique pour contrer une menace et ne pourra etre

renouvelee. Le dernier type de ressource presente est celui d’etat qui limite l’utilisation

de ressource tant que le systeme n’a pas atteint l’etat precis. Lancer un missile necessite

d’illuminer la cible avec le STIR afin de guider le missile sur la menace. Il est donc

possible de lancer un SAM seulement au moment ou la menace est illuminee par un de

nos deux STIRs.

Les contraintes locales et globales

Bien que toutes les contraintes influencent le domaine des variables, certains types

de contraintes y sont mieux adaptes. Les contraintes unaires sont definies par rapport

a une constante (i.e. nbMissiles < 16 ). Ce type de contrainte limite le domaine

d’admissibilite des le depart, avant l’application des contraintes.

Les contraintes globales (AllDif, k-Dif, AllEqual, etc), pour leur part, se retrouvent

sur deux ou plusieurs variables. Elles sont habituellement presentees par un ensemble de

contraintes binaires, ou chaque contrainte restreint deux variables. Ces deux variables

sont liees par une relation, (i.e. X1 6= X2). Il existe d’autres types de contraintes que

celles-ci, mais il est important de savoir que tous les types de contraintes peuvent se

transformer en contraintes binaires. Ainsi, si nous prenons une contrainte ternaire tel

que X1 6= X2 = X3, il est facile de la transformer en deux contraintes binaires soit


X1 6= X2 et X2 = X3, ou les deux contraintes doivent etre consistantes. Les domaines

sont consistants lorsque toutes les valeurs respectent les contraintes. C’est un concept

tres important, car la consistance des contraintes assure qu’une solution au probleme

existe.

Dans le meme ordre d’idees, la consistance dans les contraintes locales (consistance

de noeud) peut facilement etre prise en compte, car il suffit d’eliminer du domaine,

les valeurs qui ne respectent pas la contrainte. Pour les contraintes globales (consis-

tance d’arcs), il faut s’assurer de la consistance entre les domaines des variables. Cette

operation est plus complexe et c’est ce que nous allons explorer dans les prochaines

sections.

4.2 Resoudre un CSP

Les techniques pour resoudre un “Constraint Satisfaction Problem” (CSP) sont

nombreuses [4] et regroupees en diverses familles telles que la recherche systematique,

les techniques de consistances, la propagation de contraintes, l’ordonnancement des

variables et des valeurs ainsi que les techniques pour reduire l’espace de recherche. Cer-

taines de ces techniques sont evidemment plus performantes que d’autres dans certaines

situations, mais chacun des algorithmes tente de contourner les calculs intraitables.

4.2.1 Les conventions

Pour la prochaine section nous allons utiliser certains notations pour decrire les

algorithmes et les exemples. Ces conventions sont presentees au tableau 4.2.

4.2.2 La recherche systematique

La methode la moins efficace pour resoudre un CSP est la methode d’essai-erreur,

c’est a dire generer et tester (GT). La methode GT tire une solution au hasard et

la teste. Elle peut prendre beaucoup de temps, car elle peut parcourir un ensemble

tres grand de solutions la rendant inefficace. De plus, il est possible de conclure que le

CSP est inconsistant seulement une fois que toutes les solutions ont ete essayees. C’est

pourquoi le retour arriere (BT) [8] a ete introduit. Il est d’ailleurs souvent utilise pour


CSP Variable qui defini un CSP

X Variable qui signifie un ensemble de variable du CSP

D Variable qui definie le domaine des variables

C Variable qui signifie l’ensemble des contraintes du CSP

Cij Contraintes entre les variables i et j

N Cardinalite de l’ensemble X

sol Solution final a un CSP

BT Back-Tracking - Retour-Arriere

av Valeur d’une variable

ai Vecteur qui contient i elements de l’assignation

BM BackMarking - Retour-Marquant

consitant Variable booleen qui indique la consistance d’une assignation

Mi,v Tableau de 2 dimensions pour la variable i a la valeur v

lowi Tableau qui contient la derniere variable

changee depuis l’instanciation de xi

Tab. 4.2 – Tableau des conventions

effectuer la recherche dans les arbres et peut etre applique facilement au CSP. Lorsqu’il

trouve une assignation inconsistante, il effectue un retour arriere afin d’essayer une

nouvelle assignation.

L’algorithme 4.1, decrit la methode de recherche BT. Il commence avec la premiere

variable et copie son domaine dans D′i. Pour toutes les variables, BT appelle la fonc-

tion Selection-Valeur, laquelle retourne une valeur av du domaine D′i consistante avec

l’assignation courante ai−1. Si la valeur retournee par Selection-Valeur est nulle, c’est

qu’il n’y a pas de valeur consistante pour la variable. Il est donc necessaire de revenir en

arriere, ce qui est exprime par la ligne 8. Si la valeur est differente de nulle, l’algorithme

recommence avec la variable suivante. Si l’algorithme trouve une valeur pour toutes les

variables, il retourne l’assignation consistante.

L’algorithme BT appelle constamment la procedure Selection-Valeur, l’algorithme

4.2, qui permet de retourner une valeur du domaine Di consistante avec l’assignation

partielle ai−1. Il essaie au hasard les valeurs du domaine et retourne seulement une valeur

si elle est consistante avec l’assignation. Pour verifier si la valeur av est consistante avec

l’assignation partielle ai−1, un teste est effectue avec la fonction Consistant(ai−1, xi =

av). Lorsqu’une contrainte est violee, Consistant(...) retourne faux. Ceci engendre un

nouveau choix pour la variable av. Si le domaine de la variable est vide, la valeur nulle

est retournee et un retour arriere dans l’arbre est effectue.

Le BT peut s’executer de deux facons, en profondeur ou en largeur. La recherche


en profondeur va descendre dans l’arbre tant qu’elle le peut. Lorsqu’elle detecte une

solution inconsistante, elle revient au noeud precedent. S’il y a un voisin non visite,

elle le visite et explore cette nouvelle branche. L’algorithme s’arrete lorsqu’il arrive a la

fin d’une branche (feuille), signifiant que la solution est consistante. Pour la recherche

en largeur, l’exploration s’execute toujours en se deplacant de cote et en descendant

pour valider si la branche est valide. Dans les deux cas, la consistance de l’assignation

partielle est verifiee pour savoir s’il est necessaire d’executer un retour arriere.

Algorithm 4.1 Retour-Arriere (BackTracking [BT])

1: Entree : CSP =< X,D,C >

2: Sortie : Solution ou avertissement

3: i← 1

4: D′i ← Di

5: tant que 1 ≤ i ≤ n faire

6: xi ← Selection-Valeur(ai−1, xi, D′i)

7: si xi est nulle alors

8: i← i− 1

9: sinon

10: i← i− 1

11: D′i ← Di

12: si i = 0 alors

13: retourne inconsistant

14: sinon

15: retourne Valeur instanciee x1, ..., xn

Algorithm 4.2 Selection-Valeur (ValueSelection)

1: Entree : Assignation Courante ai−1 ; Variable xi ; Domaine D′i.

2: Sortie : retourne une valeur de D′i consistante avec l’assignation partielle ai−1

3: tant que D′i non vide faire

4: Choisir une valeur arbitraire av et l’eliminer de D′i

5: si Consistant(ai−1,xi = av) alors

6: retourne av

7: retourne nulle

Malheureusement, le BT peut etre affecte par le “trashing”, c’est-a-dire qu’il doit

redecouvrir a chaque fois des inconsistances deja connues grace aux recherches precedentes.

Il se retrouve donc a effectuer le meme travail plusieurs fois. De plus, le BT n’a pas la

capacite de trouver un conflit avant d’arriver directement dessus. Tous ces defauts sont

heureusement contres par d’autres approches. Une de celle-ci est le saut arriere (Back-

Jumping) [29], il permet d’eliminer le “trashing”. L’algorithme de saut arriere utilise


la meme technique de la rechercher dans l’arbre que le retour arriere, a l’exception de

lorsqu’il rencontre un ensemble inconsistant. Dans ce cas, au lieu d’executer un retour

arriere, il analyse la situation pour detecter la source de l’inconsistance. Cette analyse

est effectuee sur les contraintes violees. Une fois la cause detectee, il la sauvegarde et

tente de l’eviter le prochain coup.

Dans la recherche systematique, l’algorithme le plus performant pour le moment

est le retour marquant (BackMarking) [28]. Il a l’avantage d’eliminer completement le

travail redondant, en gardant des traces des anciens tests de consistance qui ont echoue.

Tout comme pour le retour et le saut arriere, le retour marquant fonctionne de facon

similaire, sauf qu’il possede deux tables pour garder en memoire les tests de consistances

echouees. La table Mi,v contient pour chaque variable, ainsi que ses valeurs possibles,

la premiere assignation inconsistante avec la valeur v. Donc, si Mi,v = i, il considere

que la valeur v est consistante. La table lowi contient la derniere variable qui a changee

depuis que xi a ete instancie.

Le BM est decrit entierement a l’algorithme 4.3 et 4.4. Il se comporte de facon

semblable a l’algorithme 4.1 sauf qu’il doit s’occuper de gerer ses deux tables. Il com-

mence par initialiser les deux tables Mi,v et lowi a 0 (ligne 3 ). Par la suite, si la valeur

retournee par Selection-Valeur-BM est nulle, il met la valeur courante de i dans low

pour toutes les variables entre i et N (ligne 8-13 ). La variable low indique la derniere

variable du CSP instanciee avant le retour arriere.

La grande difference entre le BT et BM se situe au niveau de la fonction de selection

de valeur. Selection-Valeur-BM, l’algorithme 4.4, a pour role de gerer la table Mi,v, de

trouver une valeur av et d’eliminer de nombreuses valeurs inconsistantes du domaine de

la variable. Pour commencer, il efface du domaine D′i toutes les valeurs av pour lesquelles

la table Mi,v indique une valeur plus petite que celle dans la table lowi. Ces valeurs

sont eliminees, car elles sont inconsistantes avec l’assignation courante et qu’elles ont

deja ete testees precedemment. Il n’est pas necessaire de les tester a nouveau puisque

s’ils ont echoue dans le passe, ils vont encore d’echouer. Lorsqu’une valeur av est jugee

consistante, il met a jour la table Mi,v avec la valeur courante de la variable. Lorsqu’elle

ne l’est pas, il doit mettre a jour toutes les valeurs de Mi,v a partir de la derniere variable

qui a change depuis l’instaciation de xi, c’est-a-dire lowi, jusqu’a i. Cette mise a jour

est exprimee par les lignes 7 a 13 de l’algorithme 4.4.

Ces trois techniques n’utilisent pas les contraintes de facon judicieuse. Les prochaines

methodes de recherche permettent de mieux utiliser les contraintes afin de reduire plus

efficacement l’espace de recherche. Le fait de chercher dans tout l’espace comme le fait

la recherche systematique est rarement avantageux, sauf si une bonne assignation est


Algorithm 4.3 Retour-Marquant (BackMarking [BM])

1: Entree : CSP =< X,D,C >

2: Sortie : Solution ou Inconsistant

3: Mi,v ← 0, lowi ← pour tout i et v

4: i← 1

5: D′i ← Di {Copie le domaine}

6: tant que 1 ≤ i ≤ N faire

7: xi ←Selection-Valeur-BM(ai−1, xi, D′i)


9: pour tout j, i ≤ j ≤ N faire

10: si i < lowj alors

11: lowj ← i

12: lowi ← i− 1

13: i← i− 1

14: sinon

15: i← i− 1

16: D′i ← Di

17: si i = 0 alors

18: retourne inconsistant

19: sinon

20: retourne Valeur instanciee x1, ..., xn


Algorithm 4.4 Selection-Valeur-BM

1: Entree : Assignation Courante ai−1 ; Variable Xi ; Domaine D′i.

2: Sortie : Retourne av une valeur de D′i consistante.

3: Efface de D′i tout av pour lequel Mi,j < lowi


5: Choisir une valeur arbitraire av et l’eliminer de D′i

6: consitant← vrai

7: k ← lowi

8: tant que k < i et consitant faire

9: si non-Consistant(ak, xi = av) alors

10: Mi,v ← k

11: consitant← false

12: sinon

13: k ← k + 1

14: si consistant alors

15: Mi,v ← i

16: retourne av

17: retourne nulle

trouvee des le depart. Dans le cas contraire, la recherche peut s’averer tres lente, surtout

dans de tres grands arbres.

4.2.3 Les techniques de consistance

Il existe deux techniques de consitance soit l’arc-consistance et le chemin-consistance.

Elles sont tres profitables, car elles permettent d’utiliser la propagation de contraintes.

Il est alors possible d’inferer sur les contraintes, ce qui facilite la recherche d’une solu-

tion consistante. Deux types de consistances sont possibles. Le premier s’effectue sur

les arcs et permet de trouver les assignations possibles entre deux variables. Le second

s’execute sur les chemins et est une extension d’arc consistance. Dans les techniques

presentees par la suite, nous allons uniquement considerer les contraintes binaires.

L’arc-consistance

Le Arc-Consistance-1 (AC-1) consiste a trouver toutes les assignations entre toutes

les variables du CSP. La figure 4.4 exprime les diverses assignations possibles ou une


contrainte de non-egalite est presente entre deux variables X et Y. Les arcs entre les

variables representent les assignations consistantes avec la contrainte. Les algorithmes

d’arc-consistance utilise ce principe mais sur toutes les variables du CSP. AC-1 a une

complexite de O(k2) ou k represente la borne de la cardinalite maximale des domaines.

1

3

22

1

Contrainte :X != Y

X Y

Fig. 4.4 – Arc-consistance

L’algorithme 4.5 appele Revise, s’execute sur deux variables xi et xj et a pour but

de retourner le plus grand domaine de xi, arc-consistant avec xj. Le plus grand domaine

consistant possible ne signifie pas que n’importe quelle valeur de Di sera consistante

avec xj, mais bien qu’il en existe au moins une. Il essaie toutes les valeurs i de Di (ligne

4) afin de verifier que i est consistante avec au moins une valeur du domaine Dj. Si

aucune valeur n’est trouvee, il supprime la valeur i du domaine (ligne 6). La variable

efface est un booleen signifiant qu’une valeur du domaine a ete effacee. L’algorithme

4.5 retourne cette valeur afin de savoir si une modification du domaine a eu lieu.

L’utilisation seule de l’algorithme Revise sur chacun des arcs n’est pas assez puis-

sante. Il faut l’inserer dans l’algorithme AC-1 ou pour chaque pair de variables presentes

dans une contrainte, Revise sera applique. Ce processus est repete jusqu’a ce qu’un cycle

complet des contraintes aient ete executees et que les domaines restent inchanges.

AC-1 est donnee par l’algorithme 4.6. Il traite chaque paire de variables xi et xj liees

ensemble par une contrainte. Il applique pour celles-ci l’algorithme Revise deux fois

(ligne 5 et 6 ). L’algorithme parcourt toutes les paires de la sorte, et se termine lorsqu’il

n’y a plus de changement dans les domaines des variables et qu’un tour complet des

contraintes a ete fait.

L’inconvenient majeur d’AC-1 c’est qu’il refait une boucle, sur toutes les variables,

chaque fois qu’un changement mineur survient, ce qui rend l’algorithme moins efficace.

Une variation de l’algorithme se nomme AC-3 [1]. Elle elimine completement les retours

inutiles en effectuant une revision seulement pour les arcs possiblement affectes.


Algorithm 4.5 Revise

1: Entree : Deux variables du CSP xi et xj.

2: Sortie : Le domaine Di rattache a la variable xi

3: efface← faux

4: pour tout i ∈ Di faire

5: si (¬∃j ∈ Dj : Consistant(xi, j) ) alors

6: Supprimer i de Di

7: efface← vrai

8: retourne efface

Algorithm 4.6 Arc-Consistance-1 (Arc-Consistency-1 [AC-1])

1: Entree : Un reseau CSP = (X,D,C)

2: Sortie : Reseau CSP ′ le plus faiblement arc-consistant a CSP

3: repeter

4: pour chaque paire(xi, xj) qui participe a une contrainte faire

5: Revise(xi, xj)

6: Revise(xj, xi)

7: jusqu’a Pas de changement dans le domaine

L’algorithme 4.7 presente le AC-3. Il debute en construisant une queue de paires

de variables. Cette queue est construite avec toutes les variables en relation dans une

contrainte (ligne 3 et 4). Par la suite, tant que la queue n’est pas vide il applique

l’algorithme Revise sur les paires de variables. Lorsqu’un changement dans le domaine

survient (ligne 7), toutes les paires de variables en relation avec la variable dont le

domaine est change sont ajoutees a la queue (ligne 8). C’est a cet endroit que AC-3 a

l’avantage sur AC-1, car il refait l’arc-consistance seulement sur les variables susceptibles

d’etre influencees par le changement de domaine.

Algorithm 4.7 Arc-Consistance-3 (Arc-Consistency-3 [AC-3])


2: Sortie : Toutes les assignations possibles

3: pour tout paire(xi, xj) qui participe a une contrainte Cij ∈ C faire

4: queue = queue ∪ (xi, xj)(xj, xi)

5: tant que queue non vide faire

6: Choisir et effacer (xi, xj) de queue

7: si Revise(xi, xj) alors

8: queue← queue ∪ ((xk, xi), k 6= i et k 6= j)

Il y a beaucoup d’algorithmes dans la famille des AC et chaque version d’AC corrige

des problemes, ou ameliore la rapidite de calcul. Par exemple, AC-1 s’execute en O(enk3)


ou e est le nombre de contraintes binaires, n le nombre de variables et k represente la

borne superieur de la grandeur des domaines. AC-3 s’execute en O(ek3) et est ameliore

par AC-4, qui lui est en O(ek2).

Algorithme Complexite

AC-1 O(enk3)

AC-3 O(ek3)

AC-4 O(ek2)

Tab. 4.3 – Complexite des algorithmes d’arc-consistence

Arc-Consistance directionnelle

Une technique pour diminuer la duree du calcul est l’arc-consistance directionnel

(DAC). Le DAC fait un arc-consistance dans une seule direction, tandis que le AC le

fait dans les deux directions (sur les arcs < x, y > et < y, x >). Il est certain que le

DAC est moins efficace, car il assure la consistance seulement d’un cote. Cependant, il

demande moins d’espace memoire et surtout moins de calcul que le AC-1 ou le AC-3.

L’algorithme 4.8 represente le DAC qui utilise lui aussi la methode Revise. Il prend

en entree un ordre d, qui indique l’ordre dans lequel les variables doivent etre as-

signees. L’algorithme parcourt donc les variables dans l’ordre inverse afin d’executer

l’arc-consistance (ligne 3). Comme il veut seulement le faire dans une direction, il ne

prend que les paires de variables les plus petites dans l’ordre inverse de d par rapport

a la variable actuelle (ligne 4). Par la suite, lorsqu’il assigne des valeurs aux variables,

il suit l’ordre de d ce qui assure une consistance complete lors du choix des valeurs, et

ce, sans effectuer de retour arriere.

Algorithm 4.8 Arc-Consistance Directionnelle (Directional Arc Consistency [DAC])

1: Entree : Un reseau CSP = (X,D,C) et un ordre d = (x1, ...xn)

2: Sortie : CSP Arc-Consistant directionnel

3: pour i = n jusqu’a 1 par -1 faire

4: pour chaque j < i tel que Cji ∈ C faire

5: Revise(xj, xi)

La figure 4.5 montre un graphe de contraintes ou il y a quatre variables, A,B,C et D.

Chacune d’elle est soumise a des contraintes exprimees sur les liens entre les variables.

Si nous supposons que l’ordre choisi pour executer le DAC est : d = {A,B,C,D}. Il

faut d’abord que l’algorithme commence par analyser la variable D. Ensuite, il doit

considerer toutes les variables liees a D par une contrainte et situees avant lui dans


l’ordre d. Dans ce cas, il y a seulement la variable C qui repond a tous ces criteres. Il

execute donc un arc-consistence de C vers D. Ceci a pour effet d’epurer le domaine de

C contenant alors que les valeurs 8 et 10. Par la suite, il evalue la variable C et applique

des arc-consistances sur les variables A et B. A restera identique car toutes les valeurs

de A sont differentes a celles de C. Par contre, la seule valeur de B qui peut etre egale

aux valeurs de C est 8. Ceci engendre une reduction notable du domaine de B. Selon

l’ordre d, il ne reste plus qu’a s’assurer que la variable A soit arc consistant avec B.

Ceci etant fait, le nouveau graphe de contrainte est presente a la figure 4.6. Pour

conclure, il ne reste plus qu’a assigner en suivant l’ordre d. La seule valeur de A possible

est 12 et la seule valeur possible pour B est 8. L’assignation est completee, car les

contraintes sont respectees. Lorsque vient le temps d’assigner une valeur a C, la seule

qui satisfait la contrainte entre B et C est 8. De plus, comme nous avons fait un arc-

consistance dans l’autre direction, nous pouvons constater que la contrainte entre A

et C est aussi respectee. Il ne reste plus qu’a assigner D, par n’importe quelle valeur

satisfaisante C < D, soit 9.

A={1-2-4-12}

C = {8-9-10-11} D={5-6-7-8-9}

B={1-6-8}(A>B)

(A B)

(C<D)

(C=D)

Fig. 4.5 – Graphe des contraintes

La consistance de chemin

Utiliser uniquement le AC pour detecter l’inconsistance n’est pas toujours inefficace.

Le AC detecte une inconsistance en tombant sur une variable avec un domaine vide.

Par contre, cette detection est limitee, car elle s’applique seulement sur deux variables.

Utiliser une consistance de chemin aide fortement a eliminer ce probleme en considerant

plusieurs variables simultanement.


A={12}

C = {8-9} D={5-6-7-8-9}

B={8}(A>B)

(A B)

(C<D)

(C=D)

Fig. 4.6 – Graphe des contraintes

Prenons en exemple un reseau de contraintes CSP = (X,D,C) et un ensemble de

deux variables {xi et xj}. Ces variables ont un chemin consistant relatif a la variable

xk, si et seulement si, pour toutes les assignations {xi = ai, xj = aj} il existe une

valeur ak ∈ Dk, de sorte que {xi = ai, xk = ak} et {xk = ak, xj = aj} sont eux aussi

consistants.

De plus, Montaranari [52] a demontre que si tous les chemins de longueur deux sont

consistants, le graphe l’est aussi. Cela est donc tres interessant, car il suffit de verifier

la consistance des chemins de longueur deux afin de nous garantir que le graphe est

chemin-consistant.

L’algorithme 4.9 presente la consistance de chemin. L’idee est la suivante : il applique

la procedure Revise-3 pour chaque paire de variables avec toutes les autres variables

(ligne 4 a 7 ). Le processus est repete tant qu’il n’y a plus de changement dans l’ensemble

des domaines.

La procedure Revise-3 (l’algorithme 4.10) fait la meme elimination que Revise mais

pour un couple de variable par rapport a une troisieme variable (ligne 4) ou a et b

sont les valeurs des variables xi et xj. Dans ce cas, au lieu d’eliminer les valeurs d’un

domaine, il le fait dans les deux domaines du couple des variables.

Pareillement au AC-1, le Path-Consistency-1 (PC-1) a le meme defaut de refaire l’al-

gorithme chaque fois qu’un changement mineur a lieu. L’algorithme PC-2 vient corriger

le probleme de la meme facon qu’AC-3.


Algorithm 4.9 Consistance de Chemin (Path-Consistency [PC-1])


2: Sortie : Un graphe CSP consistant

3: repeter

4: pour k = 1 to n faire

5: pour i = 1 to n faire

6: pour j = 1 to n faire

7: Revise-3((xi, xj), xk)

8: jusqu’a Pas de domaine de change

Algorithm 4.10 Revise-3

1: Entree : Trois variables du CSP xi, xj et xk.

2: Sortie : Les domaines Di et Dj rattaches respectivement aux variable xi et xj

3: pour chaque paire(a, b) de Cij ∈ C faire

4: si (¬∃c ∈ Dk : Consistant(a, c) et Consistant(b, c) ) alors

5: Supprimer a de Di et b de Dj

4.2.4 La propagation de contraintes

La propagation de contraintes permet d’utiliser les contraintes plus efficacement

dans la construction de la solution, de reduire l’espace de recherche et de faciliter la

recherche. Dans ce but, des techniques de consistance sont jumelees avec des techniques

de propagation de contraintes. En effet, il faut savoir qu’une propagation de contraintes

s’execute toujours a partir de variables deja assignees.

Le retour-arriere et le arc-consistance

Un algorithme de propagation de contraintes consiste a jumeler le retour-arriere

avec le arc-consistance. Chaque fois que le retour-arriere assigne une valeur, il execute

le arc-consistance sur cette variable. Si aucune valeur du domaine n’est consistante, il

effectue alors un retour arriere.

Toutefois, le retour-arriere a toujours le meme defaut. Il detecte une inconsistance

seulement au moment ou il est rendu a l’assignation partielle de cette variable. Par

contre, jumele avec le arc-consistance, le retour arriere est plus rapide, car il est en

mesure d’eliminer plusieurs branches qu’il devait absolument parcourir auparavant.


L’algorithme 4.11, est appele chaque fois qu’une nouvelle valeur est assignee. Il

prend en entree une liste de variables deja instanciee et ordonnee, av, afin de retourner

un ensemble consistant avec le reste du CSP. La variable booleen consistant sert a

conserver si av est consistant ou non. De plus, il forme une queue de pairs d’elements

ou le premier est une variable non assignee et le second est une variable assignee.

Cependant, cette paire doit etre liee par une contrainte de l’ensemble C (ligne 3 ). Tant

que la queue n’est pas vide, ou qu’il n’y a pas d’ensemble vide (ligne 5 ), Revise est

applique sur les paires (ligne 7).

Algorithm 4.11 Arc-Consistance et Retour arriere (Arc-Consistency and

BackTracking[AC-BT])

1: Entree : av, liste de variables assignees

2: Sortie : si av est consistant ou non.

3: queue← {(xi, xv) de Cij ∈ C tel que i < v}

4: consistant← vrai

5: tant que queue non vide et consistant faire

6: Selectionne et Effacer une paire(xi, xj) ∈ queue

7: consistant← ¬Revise(xi, xj)

8: retourne consistant

La verification vers l’avant et l’arc-consistance

La verification vers l’avant (Foward-Checking) avec l’Arc-consistance(AC-FC) consiste

a faire un arc-consistance entre une variable deja assignee et une autre qui ne l’est pas.

Chaque fois qu’une valeur est assignee, le AC-FC propage la valeur et enleve des do-

maines voisins toutes les valeurs qui ne sont plus consistantes avec les contraintes et

les variables assignees. Les domaines des variables voisines seront alors necessairement

consistants avec l’assignation partielle. Le Foward Checking (FC) est la technique la

plus facile pour prevenir de futurs conflits. Cela permet aussi d’eliminer des branches

avant meme d’avoir detecte le conflit.

L’algorithme 4.12, est un FC applique a un arc-consistance. Il prend en entree une

liste de variables deja assignee av et applique un Revise sur les arcs de la queue (ligne

7 ). Si le domaine est vide par la procedure Revise, alors il retourne faux et arrete le

AC-FC. L’assignation av est donc inconsistante et devra etre modifiee. Considerant que

le temps pour verifier si une contrainte est satisfaite coute O(1), la complexite de FC

est de O(ek2) ou k est la cardinalite du plus grand domaine et e est le nombre de

contraintes.


Algorithm 4.12 Arc-Consistance et Regarder vers l’avant (Arc-Consistency pour Fo-

ward Checking [AC-FC])

1: Entree : av, liste de variables deja assignee



4: consistant← true


6: Selectionne et Detecte un par (xi, xj) dans queue


8: consistant← non vide Dk


Le partial look ahead

Le “Partial Look Ahead” propose une consistance d’arc plus en profondeur. Au

lieu d’analyser uniquement les variables directement liees a celle-ci, il verifie la consis-

tance des futures variables qui ne sont pas directement connectees a la variable initiale.

L’avantage des approches “Look Ahead” c’est qu’il n’est pas necessaire de s’occuper

de la consistance des variables assignees puisqu’elle a deja ete assuree avant par l’algo-

rithme.

Le “Partial Look Ahead” est plus performant que le AC-FC, car il trouve un plus

grand nombre d’ensembles inconsistants. De plus, il execute moins de travail que l’arc-

consistance, puisqu’il verifie seulement la consistance avec les variables futures.

L’algorithme 4.13 commence par faire une boucle sur toutes les variables qui ne

sont pas encore instanciees (ligne 3 ). Il epure les domaines de chacune des variables,

jusqu’a ce que tous les arcs soient parcourus (ligne 4-5 ). Si un domaine se retrouve

vide, l’algorithme retourne faux, et s’il complete la boucle, il retourne vrai.

Algorithm 4.13 (Directional Arc-Consistency Look Ahead [DAC-LA])

1: Entree : av, liste de variables deja assigne.


3: pour i = v + 1 to n faire

4: pour chaque paire (xi, xj) de Cij ∈ C tel que i > j et j <= v faire


6: si Di est vide alors

7: retourne FAUX

8: retourne VRAI


Le full look ahead

Le “Full Look Ahead” (FLA), est comme le “Partial Look Ahead”. La difference

se situe seulement au niveau de la consistance. Au lieu de verifier seulement dans une

direction, il le fait dans les deux sens. Donc, il verifie les contraintes entre les anciennes

variables, entre les futures variables et sur la variable courante. Ceci permet au “Full

Look Ahead” d’eliminer des branches beaucoup plus rapidement que le FC et le “Partial

Look Ahead”.

Selon l’algorithme 4.14, le FLA commence avec un ensemble queue de paire de

variables correspondant a tous les arcs des futures variables non assignees (ligne 3 ).

Une boucle est effectuee sur ces arcs jusqu’a ce que la queue soit vide ou encore que

l’assignation ne soit plus consistante (ligne 5 ). Il selectionne chaque paire de variables

desquelles il epure les domaines avec la procedure Revise. Si le domaine de de xi est

modifie, il doit remettre dans la queue toutes les paires de variables en relation avec la

variable dont le domaine a change et dont la variable n’est pas assignee (ligne 8 ).

Algorithm 4.14 Arc-Consistance-LookAhead [AC3-LA]

1: Entree : av, liste de variables deja assignee



4: consistant← vrai


6: Selectionne et Effacer la paire (xi, xj) de queue

7: si Revise((xi, xj) alors

8: queue← queue∪ {xi, xj tel que xk, xi ∈ C, i 6= k, i 6= j, i > v}

9: consistant← Di non vide


Differentes techniques pour resoudre les CSP ont ete presentees. La recherche systematique

(backtracking, backmarking) permet d’explorer l’arbre de solution et d’eliminer celles

qui ne sont pas consistantes avec les contraintes. Par contre, dans la recherche systematique,

les contraintes ne guident pas la recherche, mais permettent de valider la solution

trouvee. D’autres methodes de recherche, comme les techniques de consistance (AC-

1,AC-2,AC-3, etc) utilisent les contraintes dans le processus de recherche afin d’eliminer

les valeurs inconsistantes du domaine des variables. Aussi, les algorithmes de propaga-

tion de contraintes comme le “Partial Look Ahead” et le “Full Look Ahead” ont ete

presentes, et ou l’utilisation des contraintes permet d’eliminer rapidement plusieurs

branches dans l’arbre. Ces differentes techniques de recherches n’ont pas les memes

proprietes et ne trouvent pas la solution a la meme vitesse. Par contre, d’autres fac-


teurs peuvent intervenir pour aider a ameliorer la recherche comme l’ordre des valeurs

ou des variables.

4.2.5 L’ordre et reduction de recherche

Le fait de mettre un certain ordre dans les variables ou dans les domaines est parfois

tres utile pour trouver une solution plus rapidement. Par exemple, si dans un probleme,

toutes les variables sont ordonnees parfaitement, la solution sera trouvee automatique-

ment sans avoir besoin d’executer un retour arriere. Ce cas arrive tres rarement, mais il

est possible d’ordonner les variables de facon a augmenter les probabilites de reussite.

L’ordre des variables

Il existe deux types d’ordre dans les variables, le statique et le dynamique. L’ordre

statique consiste a ordonner les variables avant la recherche et a ne plus jamais changer

cet ordre. A l’oppose, l’ordre dynamique permet de choisir la prochaine variable a

evaluer selon l’etat courant de la recherche. L’ordre n’est donc pas predefini et peut

changer a tout moment. Or, comment choisir l’ordre des variables ?

Il existe diverses heuristiques permettant de faciliter ce choix. La premiere est de

commencer avec les variables possedant les plus grandes chances d’echouer. Pour le

determiner, il suffit de prioriser la variable non assignee avec le plus petit domaine.

Cette methode a l’avantage d’eliminer rapidement des branches inconsistantes ayant

tendance a revenir plusieurs fois dans la recherche. De plus, il est aussi possible de

considerer le nombre de contraintes sur la variable. Plus une variable est contrainte,

plus cette variable doit etre instanciee rapidement. Intuitivement, une variable avec

beaucoup de contraintes est difficile a satisfaire. Si elle est satisfaite des le depart, il y

aura plusieurs valeurs a eliminer dans les autres domaines, ce qui aidera a reduire la

duree du calcul.

L’ordre des valeurs

L’ordre des valeurs dans le domaine peut aider a reduire les calculs dans le cas ou

nous cherchons une solution faisable. Si nous cherchons toutes les solutions possibles

ou s’il n’y a pas de solution, l’ordre des valeurs n’aidera pas a aller plus vite. Dans ces

deux cas, il faudra parcourir l’ensemble complet des valeurs. Une heuristique possible


pour l’ordonnancement des valeurs est de prendre celle donnant le plus d’options dans

le futur, de sorte a eliminer les chances de retour en arriere.

L’effet Cycle-Cutset

Il existe un autre moyen de reduire le temps de recherche. Il s’agit de rechercher

des attributs particuliers au graphe. En fait, certains graphes, comme les arbres, sont

plus faciles a resoudre que les graphes cycliques. Le theoreme suivant est la base du

“Cycle-Cutset” [18] :

L’effet Cycle-Cutset Soit un graphe non-dirige G, un sous ensemble de noeuds du

graphe est “Cycle-Cutset” si en enlevant ce sous ensemble, le graph G est sans cycles.

Une des methodes utilisee pour accelerer la recherche de solution est donc de reperer

un ensemble de noeuds “Cycle-Cutset” et d’assigner ces variables en premier. Une

fois le ‘Cycle-Cutset” resolu, les variables sont instanciees et leurs valeurs propagees.

Les noeuds peuvent alors etre supprimes du graphe et ne plus etre consideres dans

la recherche. Le reste du graphe sera alors un graphe sans cycle connexe, donc, un

arbre. Il est reconnu que la recherche d’une solution dans un arbre peut-etre effectuee

efficacement avec un “Directional Arc-Consistence”. La recherche de solution est alors

plus rapide, car la structure du graphe a ete exploitee.

La figure 4.7 represente un ensemble de noeuds, qui, une fois enleve, elimine tous

les cycles dans le graphe de contraintes. On peut constater qu’une fois les noeuds B et

C enleves du graphe, il n’y a plus de cycle.

F

C

D E

A B

F

D E

A

Fig. 4.7 – Cycle-Cutset

4.2.6 L’optimisation des CSP

L’optimisation dans les CSP est connue sous le nom “Constraint Optimization Pro-

blem” (COP). Il contient une fonction d’objectivite sur la valeur des variables qui


doit etre maximisee ou minimisee. Le COP est donc un reseau de contraintes augmente

d’une fonction d’objectivite. Le COP se defini comme suit :

1. X = {x1, ..., xn} qui sont les variables.

2. C = {C1, ..., Ck} sont les contraintes.

3. D = {D1, ..., Dl} ou Dj ∈ X est le domaine des variables.

4. F = {F1, ..., Fl} sont des fonctions d’objectivites retournant des valeurs reels.

5. Q = {Q1, ..., Ql} sont des sous ensembles de X et definie la portee des fonctions

d’objectivite.

6. a = {a1, ..., an} ou ai ∈ Di et ai est une assignation aux i premieres variables.

7. Ou la fonction objective est definie par : F (a) =∑l

j=i Fj(a) ou Fj(a) = Fj(a[Qj])

Le COP peut etre vu comme un “cost network” definie par un Γ = (X,D,C) ou

(X,D,Ch) est le reseau de contraintes ou C = {FQ1, ..., FQl

} et ou Qi = {xi1, ..., xil}

est un sous-ensemble de X. L’assignation optimale dans un COP est a∗ = {a1, ..., an},

tel que F (a∗) = maxaF (a) ou F (a∗) = minaF (a). L’objectif est donc de maximiser ou

de minimiser la fonction de cout utilisee dans les “cost network”.

Le COP comme une succession de CSP

Il est possible de resoudre un COP comme une succession de CSP, dans laquelle

a chaque iteration, une variable est ajoutee dans le CSP. Chaque CSP Ri, est une

partie du COP augmente d’un contrainte∑l

j=1 Fj ≥ Ci ou C1 ≥ C2 ≥ ... ≥ Cj et Ci

represente la fonction globale de cout. Fj represente alors la fonction de cout a optimiser.

Au depart, la borne de la fonction de cout est initialisee avec la premiere assignation

optimisant et satisfaisant les contraintes. La valeur de la fonction d’objectivite sera

tres faible, puisque peu de variables seront considerees. Par contre, a chaque iteration,

en ajoutant une variable au CSP, la valeur de la fonction sera augmentee. Lorsque la

valeur de la fonction d’objectivite sera tres eleve, il deviendra impossible de trouver une

solution meilleur que celle trouve. La derniere solution sera l’optimale.

La separation et l’evaluation

La methode la plus connue de recherche dans un arbre est la “separation et l’evaluation”,

ou, Branch-and-Bound. Elle est represente par l’algorithme 4.15 qui doit parcourir

l’arbre de solution (les branches) et toujours garder la solution avec la meilleure va-

leur de fonction de cout (borne) [49] [55]. Il commence d’abord par copier le domaine

de la premiere variable dans D′i (ligne 4 ). Ensuite, pour toutes les variables (ligne 5 ), il


appelle la procedure 4.16, Selection-Valeur-BNB, retournant une valeur de xi. Si cette

valeur est nulle, c’est que l’algorithme n’a pas ete en mesure de trouver une valeur

consistante avant l’assignation presente. Il doit donc changer de branche (ligne 8 ) pour

choisir une nouvelle assignation. A l’oppose, s’il y a une valeur dans xi, l’algorithme

continu a explorer la branche avec une nouvelle variable (ligne 10 et 11 ). Si i tombe a

0, ceci signifie qu’il a ete impossible de trouver une valeur pour la variable xi consis-

tante avec toutes les autres variables. Il retourne donc, que le CSP est inconsistant.

S’il complete la boucle, c’est que toutes les variables ont ete assignees correctement.

L’algorithme calcule alors le total de la fonction de cout sur les valeurs des variables

(ligne 15 ) et il met a jour la borne inferieure L (ligne 16 ).

L’algorithme Selection-Valeur-BNB permet de choisir une valeur pour une variable.

Il essaie toutes les variables du domaine jusqu’a ce qu’il soit vide (ligne 5 ). Son but est

de trouver la valeur a de xi maximisant la fonction de cout avec l’assignation courante

ai−1 (ligne 6 ). Si la valeur est consistante dans le CSP et que la fonction f de cout sur

la nouvelle assignation est plus grande que la borne inferieure, il retourne cette valeur

(ligne 8-9 ).

Algorithm 4.15 Separation et Evaluation (Branch and Bound [BnB])

1: Entree : Un CSPc = (X,D,C), une borne inferieur L, une fonction de borne

superieur f pour toutes les solutions partielles.

2: Sortie : Solution optimale (maximal) ou une inconsistance

3: i ← 1

4: D′i ← Di

5: tant que 1 ≤ i ≤ n faire

6: xi ← Selection-Valeur-BNB(Xi)


8: i← i-1

9: sinon

10: i← i+1

11: D′i ← Di

12: si i = 0 alors

13: retourne inconsistance

14: sinon

15: C = C(x1, ..., xn)

16: L← max(C,L)

17: i← n− 1

Il est egalement possible d’optimiser en decoupant le probleme en sous-problemes.

Cela permet de resoudre chaque plus petit probleme avec un “Branch and Bound”, pour


Algorithm 4.16 Selection-Valeur-BNB

1: Entree : Sous procedure qui a acces a toutes les variables de BnB et Xi

2: Sortie : Valeur de xi

3: si i = 0 alors

4: retourne L


6: Choisir a ∈ D′i tel que max F (ai−1, a)

7: Effacer a de D′i

8: si Consistant(ai−1, ai = a) et f > L alors

9: f = L

10: retourne a

11: retourne nulle

ensuite effectuer une synthese des solutions optimales [5]. Chacun des sous problemes

se resout identiquement. Pour commencer, l’algorithme trouve, de facon exhaustive,

toutes les combinaisons possibles des valeurs pour le sous probleme. Ensuite, il utilise

la satisfaction des contraintes pour eliminer les combinaisons impossibles. Finalement,

il trouve la valeur optimale pour chaque variable a l’aide des valeurs restantes.

La recherche Russian Doll

Il existe une autre methode de recherche pour trouver une solution optimale. C’est

celle de Russian Doll [36] qui fait n recherches successives sur des problemes de differentes

instances. L’algorithme ordonne premierement les variables et commence une premiere

recherche avec la derniere variable. Par la suite, il injecte l’avant-derniere variable et

recommence une autre recherche en utilisant ce qui a deja ete fait lors de la recherche

precedente. De cette facon, il commence a faire une recherche seulement sur une variable

et il complete lorsque l’algorithme a effectuee une recherche avec toutes les variables

(n).

Chaque sous probleme est sauvegarde ainsi que sa qualite de solution partielle opti-

male. Les recherches sont une suite de Branch and Bound (BnB), mais le fait de reutiliser

les calculs precedents a l’avantage de donner une meilleure borne en plus d’eliminer plu-

sieurs branches dans la recherche. Les bornes d’un Branch and Bound seul ont tendance

a explorer des sous-arbres trop larges. Ce probleme est elimine avec le Russian Doll car

il ajoute une variable a la fois, selon l’ordre de recherche, reduisant ainsi les ecarts entre

les bornes. Les resultats pratiques montrent que la recherche Russian Doll est plus

rapide pour trouver une assignation optimale qu’un Branch and Bound traditionnel.


Le bucket elimination

Le “Bucket Elimination” est un algorithme qui permet un compromis entre l’inference

et la recherche. Il utilise la programmation dynamique afin de resoudre et d’optimiser

un reseau de couts avec contraintes. Cet algorithme a l’inconvenient de prendre un es-

pace memoire exponentiel. Par contre, jumele a l’heuristique de recherche mini-bucket

[45], il est possible de reduire l’espace necessaire en remplacent l’inference complete par

la propagation de contraintes bornees (consistance locale).

Le “Bucket Elimination” utilise quelques manipulations mathematiques pour en-

capsuler des variables dans des fonctions reutilisables afin d’accelerer le calcul de la

solution maximale. Le probleme suivant est tire du livre de Rina Dechter [18] et aide a

mieux comprendre le principe des Buckets :

M = maxa,c,b,f,d,g

F0(a) + F1(a, b) + F2(a, c) + F3(b, c, f) + F4(a, b, d) + F5(f, g) (4.2)

Dans ce cas, Fi est une fonction a valeur reelle sur les domaines des variables A,B,C,D,F

et G. Le “Bucket Elimination” doit suivre un certain ordre d = {A,C,B, F,D,G} pour

trouver les valeurs maximisant M . Avant de commencer, il faut distribuer les max sur

les fonctions de M .

M = maxa,c

F0(a)+F2(a, c)+maxb

F2(a, b)+maxf

F3(b, c, f)+maxd

F4(a, b, d)+maxg

F5(f, g)

(4.3)

Pour se faire, il est necessaire de commencer par l’ordre inverse de d et de generer des

fonctions, qui pourront etre resolues et reutilisees dans les calculs futurs. Il faut donc

commencer avec l’element a l’extreme droite, soit maxd F5(f, g) et generer la fonction

hG(f) = maxg F5(f, g). G est donc la variable a maximiser selon la valeur de f. Par la

suite, la nouvelle fonction doit etre inseree a l’extreme gauche dans l’equation M .

M = maxa,c

F0(a)+F2(a, c)+maxb

F2(a, b)+maxf

F3(b, c, f)+hG(f)+maxd

F4(a, b, d) (4.4)

La fonction est par le fait meme placee avant la maximisation de f , car il faut que f

soit utilisee dans hG(f) pour etre en mesure de maximiser g. A cet egard, d doit etre

maximiser pour generer la fonction hD(a, b) et placer cette fonction a gauche dans M :

M = maxa,c

F0(a) + F2(a, c) + maxb

F2(a, b) + hD(a, b) + maxf

F3(b, c, f) + hG(f) (4.5)

Le meme principe algebrique est repete, suivant l’ordre de d, pour finalement arriver a :

M = maxa

F0(a) + hC(a) (4.6)

C’est ce principe qui est utilise dans le Bucket Elimination afin de fabriquer les

buckets contenant un ensemble de fonctions. Il faut partitionner la fonction de cout en


bucket suivant l’ordre d. Il y aura donc 6 buckets contenant les fonctions a maximiser.

Une fois le bucket initial construit, il suffit d’inclure les buckets aux bons endroits

Bucket G F5(g, f)

Bucket D F4(a, b, d)

Bucket F F3(f, b, c)

Bucket B F1(b, a)

Bucket C F2(c, a)

Bucket A F0(a)

Tab. 4.4 – Bucket Initial

suivant les manipulations algebriques expliquees auparavant. Dans cette optique, la

valeur optimale de a doit etre trouvee dans le bucket A afin de maximiser maxa F0(a)+

hC(a). Par la suite, la valeur de a maximisant la fonction doit etre utilisee dans le bucket

C. Le processus est complete et les calculs sont reutilises jusqu’a ce que le dernier bucket

soit resolu.

4.3 Les modeles de CSP

Les problemes en temps reels sont nombreux et ont differentes caracteristiques (dy-

namique, partiellement observable, stochastique, etc) qui ne peuvent pas toujours etre

exprimees avec le modele CSP traditionnel presente a la section 4.1.1. C’est pourquoi

au fil des annees, plusieurs nouveaux modeles ont ete introduits, afin d’etre en mesure

de repondre adequatement a ces caracteristiques. Les modeles de CSP sont nombreux et

la figure 4.8 represente une taxonomie des differentes familles de CSP connues. Chaque

famille a des distinctions et comporte des avantages, tout comme des desavantages. Les

grandes familles des modeles sont divisees en quatre grands groupes. Le premier groupe

est les CSP/COP deja presentes. Le second est les reseaux de contraintes temporelles

brievement introduits a la section 4.1.4. Suivit des reseaux de contraintes distribuees

Bucket G F5(g, f)

Bucket D F4(a, b, d)

Bucket F F3(f, b, c) + Bucket G

Bucket B F1(b, a) + Bucket D + Bucket D

Bucket C F2(c, a) + Bucket B

Bucket A F0(a) + Bucket C

Tab. 4.5 – Bucket Final


et des reseaux de contraintes dynamiques. Dans la prochaine section, nous regarderons

la difference entre ces modeles et analyserons a quel type de problemes ils peuvent

s’appliquer.

Dynamic CSP[DCSP]

Conditional CSP[CCSP]

Mixed CSP[MCSP]

Stochasitc CSP[SCSP]

Open CSP[OCSP]

Branching CSP[BCSP]

Probabilitic CSP[PCSP]

CSP

ConstraintOptimization Problem

[COP]Distributed CSP

[DisCSP]

Distributed COP[DCOP]

Distributed Partial CSP[DPCSP]

DistributedMaximal CSP

[DMCSP]

DistributedHierarchial CSP

[DHCSP]

Fig. 4.8 – Taxonomie CSP

4.3.1 Satisfaction de contraintes stochastiques

Certains modeles de CSP sont concus pour tenir compte des problemes stochas-

tiques. Un probleme est stochastique lorsque nous n’avons pas entierement le controle

sur le modele. Pour modeliser cet aspect, une fonction de distribution de probabilite est

ajoutee sur les variables afin de specifier les probabilite pour que les variables prennent

certaines valeurs. Quand le CSP est enrichi d’une telle fonction de distribution de

probabilite, il appartient a la famille des “Stochastic Constraint Satisfaction Problem

(SCSP)” [54] [27]. Un SCSP est un 6-tuple < X,S,D, P, C, θ > ou

– X est la liste de variables.

– S sous ensemble de variables de X stochastiques.

– D domaine des variables X.

– P est une distribution de probabilite sur les variables S.

– C est l’ensemble des contraintes sur X.

– θ est le seuil de probabilite dans l’intervalle [0,1].

Dans les SCSPs, il faut diviser nos variables en deux types. Il y a les variables de

decisions (X − S) et les variables stochastiques S, dont nous ne connaissons pas leurs

valeurs avant la resolution du CSP. Les contraintes peuvent cependant etre appliquees

sur les deux types de variables. L’objectif dans un SCSP est de trouver une valeur

aux variables de decision consistante avec une certaine probabilite θ par rapport aux

variables stochastiques S. Cette probabilite θ est donc la probabilite que toutes les

contraintes soient satisfaites selon le choix des variables des decisions. Pour representer


ces problemes dans le temps, la notion d’etape est introduite. Nous nous retrouvons

donc avec le meme SCSP, mais a des etapes succinctes. Ainsi, le but sera de satisfaire

pour un θ donnee, les contraintes dans toutes les etapes du probleme. Les variables

stochastiques suivront alors leurs distributions de probabilite et changeront a chaque

etape du SCSP. Pour resoudre ce type de probleme, il faut adapter les algorithmes d’un

CSP normal. Pour utiliser le retour arriere ou le FC dans les SCSP, il suffit d’injecter

un θ comme seuil de probabilite.

A titre d’exemple, supposons 3 plateformes militaires definies dans X et etant at-

taquees par Y menaces. Chaque plateforme doit prevoir a l’avance combien de missiles

elles lanceront pour detruire les menaces Y . Le domaine de X est un entier de 1 a

15 definissant le nombre de missiles lancees. Dans ce scenario, le nombre de menaces

presentes est defini par une distribution normale P . Certains contraintes sont presentes

dans C, tel que 2 plateformes ne peuvent pas attaquer la meme menace et qu’une meme

plateforme ne peut pas tirer deux fois sur la meme menace.

Ce type de probleme ne se resout pas que par un CSP de base. Nous ne savons

pas combien de menaces attaqueront les plateformes, mais celles-ci doivent preparer un

certain nombre de munitions pour assurer leur defense. En faire trop est couteux pour

les plateformes qui doivent limiter l’utilisation des ressources, mais trop se limiter peut

engendrer la perte d’une plateforme. L’objectif est alors de faire un bon compromis

entre les deux et de predire adequatement S.

Pour y parvenir, le SCSP peut etre defini de la facon suivante :

⋆ X = {x1, ..., x3, y1} est la liste de variables des plateformes militiaires et y1 le

nombre de menace.

⋆ S = {y1} est le nombre de missiles considere comme la variable stochastique.

⋆ D = {1, .., 15} domaine des variables X.

⋆ P est une distribution normal sur S.

⋆ C =

– TousDifferents(X − S) ; contrainte specifiant que toutes les plateforme doivent

attaquer differentes menaces.

– NePeutReengager(X − S) ; contrainte indiquant qu’une plateforme ne peut at-

taquer deux fois la meme menace.

– (∑3

i=1 xi) = y1 ; contrainte specifiant que le nombre de missiles total soit egal

au nombre de menaces.

⋆ θ = 0.8 est le seuil de probabilite avec lequel il cherche a satisfaire les contraintes.


Le retour-arriere

Le SCSP etudier peut se resoudre de la meme maniere qu’un CSP en utilisant un

algorithme de retour arriere. Par contre, quelques modifications doivent etre effectuees

pour repondre adequatement au SCSP. L’algorithme 4.17 presente comment il est pos-

sible d’adapter le retour arriere pour le SCSP. D’abord, il prend en entree l’indice de la

variable a assigner i, une borne superieure et une borne inferieure, respectivement θl et

θh. Pour la variable xi (ligne 5 ) il evalue si elle fait partie de S ou non. Si elle fait partie

de S (ligne 6 ), il juge la probabilite que la valeur av soit egale a la variable stochastique

xi a l’aide la fonction proba (ligne 7 ). Il sauvegarde alors dans p cette valeur tandis

que q contient la probabilite que xi ne soit pas egale a av (ligne 8). Par la suite, si

l’assignation est consistante avec les contraintes, il peut changer de variable. Pour se

faire, il va appeler de nouveau l’algorithme avec i+1. Il doit aussi donner des nouvelles

bornes pour guider les recherches. La borne inferieure devient alors θl+θ+q

pspecifiant la

probabilite de ne pas satisfaire les contraintes. La borne superieure definit la probabilite

avec laquelle les contraintes peuvent etre satisfaites et est donnee par θh−θ

p. Si l’appel

recursif donne un nouveau θ, plus grand que la borne superieure actuelle (ligne 11 ), il

retourne cette valeur. Si le nouveau θ augmente de la valeur de q est plus petit que la

borne inferieure, il retourne aussi le nouveau θ. Le deuxieme bloc (ligne 16-19 ) corres-

pond au traitement des variables de decision. Puis, l’algorithme verifie la consistance de

l’assignation, si elle est consistante il met a jour θ. Par la suite, il prend le θ maximum

entre celui actuel et celui retourne par recursif l’appel de l’algorithme (ligne 19). Dans

tous les cas, s’il ne satisfait pas les contraintes, il retourne θ = 0. Si toutes les variables

assignees satisfont toutes les contraintes, il retourne 1.

Etant donne qu’il est impossible de connaıtre d’avance, la valeur d’une variable

stochastique, l’utilisation du SCSP est de mise. Il arrive cependant des situations ou

les valeurs du domaine sont inconnues des le depart. Cette classe de CSP est la“Open

Constraint Satisfaction Problem (OCSP)”.

4.3.2 Satisfaction de contraintes ouvertes

Le modele “Open Constraint Satisfaction Problem (OCSP)” [24] suppose que le

domaine des variables et les contraintes du probleme sont inconnus au depart. Les

OCSP ont l’avantage d’evoluer dans des mondes ouverts ou les variables et contraintes

sont a decouvrir. Par contre, la plupart des problemes se situent dans des mondes fermes,

car les variables, les contraintes et les domaines sont souvent connus. Il est cependant

important de pouvoir repondre aux problemes ouverts et c’est ce qu’offrent les OCSP.


Algorithm 4.17 Retour-Arriere-SCSP ([BT-SCSP])

1: Entree : CSP =< X,D,C >, i= indice de la variable, θl = borne inferieur, θh =

borne superieur.

2: Sortie : θ qui est le taux de satisfaction des contraintes.

3: si i < n alors

4: retourne 1

5: θ ← 0

6: q ← 1

7: pour chaque av ∈ Di faire

8: si xi ∈ S alors

9: p = proba(xi = av)

10: q = q − p

11: si consistant(ai−1, ai = av) alors

12: θ = θ + p * BT-SCSP(i + 1,θl+θ+q

p, θh−θ

p)

13: si θ > θh alors

14: retourne θ

15: si θ + q < θl alors

16: retourne θ

17: sinon

18: si consistant(ai−1, ai = av) alors

19: θ =max(θ, BT-SCSP(i + 1,max(θ, θl), θh))

20: si θ > θh alors

21: retourne θ

22: retourne θ


Pour decouvrir les domaines ou les contraintes, les variables sont transformees en

agent. Un agent est une entite capable de communiquer avec d’autres agents et de

prendre des decisions de facon rationnelle. Chaque agent s’occupe d’une variable et

c’est par lui que les informations manquantes (domaines et contraintes) du CSP seront

decouvertes. Pour coordonner le tout, un agent mediateur est utilise pour partager

les informations sur les variables connues et les contraintes decouvertes. La figure 4.9

montre une vue globale d’un OCSP ou le mediateur prend un CSP(i) et le modifie selon

les informations recues de l’environnement pour former un nouveau CSP(i+1).

Un OCSP est un ensemble ordonne, sans limite, de CSP tel que {CSP (0), CSP (1),

..., CSP (N), ....} et ou un CSP(i) est defini par un tulpe < X,C,D(i), R(i) > :

– X = {x1, x2, ..., xn} est l’ensemble de variables.

– C = {(xi, xj, ...), (xk, xl, ...), ...} est l’ensemble de m contraintes dans l’ordre quelles

sont decouvertes.

– D(i) = {d1(i), d2(i), ..., dn(i)} est l’ensemble des domaines pour les variables X

dans le CSP(i).

– R(i) = {r1(i), r2(i), ..., rm(i)} est l’ensemble des relations dans le CSP(i) definissant

les valeurs possibles entres les variables.

Au depart, aucune information sur les domaines et sur les contraintes sont connues, de

sorte que dk(0) et rk(0) est vide pour tous les k. Une solution a ce type de CSP est une

valeur a chaque variable qui est dans le domaine de X. Par contre, il est plus difficile

d’optimiser le OCSP, car l’information est incomplete au depart, ce qui ne permet pas de

garantir que nous avons trouve la solution. Toutefois, il a ete demontre[25] que si l’agent

mediateur donne toujours l’information sur les variables en suivant un certain ordre, il

sera en mesure de s’assurer que la solution optimale et que l’algorithme terminera en

tout cas (complet).

Meme s’il est possible de decouvrir le domaine et les contraintes regissant un environ-

nement ouvert, il arrive que les environnements ouverts soient egalement dynamiques.

Dans un environnement dynamique, il peut survenir des changements a tout moment

lors de la recherche d’une solution. Ces modifications peuvent s’effectuer a differents

niveaux, tels que sur les variables, les contraintes et les domaines. Ce type de modele

se nomme “Dynamic Constraint Satisfaction Problem (DCSP)”.

4.3.3 Satisfaction de contraintes dynamiques

De leurs cotes, Verfaillie [53] et Bessiere [7], proposent une approche pour resoudre

les problemes de satisfaction sous l’incertain dans des environnement dynamique. Un

environnement est dynamique si les variables, domaines ou contraintes peuvent changer


f

d

a

b

e c

CSP(i)

Environnement

Médiateur

f

d

a

b

e c

CSP(i+1)

Fig. 4.9 – CSP Ouvert

pendant la recherche de solution. Il faut donc utiliser diverses techniques pour conserver

la solution ou encore en trouver une nouvelle. Le “Dynamic Constraint Satisfaction

Problem” (DCSP) est le modele supportant les problemes dynamiques [19]. Un DCSP

est une sequence de CSP subissant des changements par rapport au precedent. Ces

changements affectent la definition du CSP, c’est-a-dire qu’il peut y avoir l’ajout ou le

retrait d’une variable, la modification des domaines, l’ajout ou le retrait de contraintes,

ou encore, le changement de la portee des contraintes.

Differents modeles sont presents pour supporter les environnements dynamiques et

incertains dans les problemes de satisfaction de contraintes. Il existe quatre principes

de construction de solution sous l’incertain. On peut limiter au maximum le besoin

de resoudre des problemes successifs en ligne, limiter drastiquement le changement de

solution (stabilite), limiter au maximum la duree du calcul, ainsi qu’essayer sans cesse de

produire des solutions consistantes et optimales [53]. Dans cette optique, une methode

est dit reactive si elle permet de reutiliser les solutions et le raisonnement deja effectue

dans les instances precedentes.

L’approches reactives

Les methodes de reutilisation de solutions sont seulement utilisees dans des cas

particuliers. L’action de reutiliser une solution est possible lorsqu’elle est consistante

dans le CSP precedent. De plus, elle pourra etre reutilisee lorsqu’un changement dans


la definition du probleme survient et que la solution precedente n’est plus valide. Il

est avantageux de reutiliser une solution, car le probleme precedent est souvent simi-

laire au probleme actuel. Le fait d’apporter peu de changements dans la definition du

probleme, peut apporter tres peu de changement dans la solution, voire meme aucun.

Pour y parvenir, il faut conserver l’information consistante du CSP. Il est aussi possible

de reutiliser le raisonnement effectue sur les problemes precedents, en conservant les

donnees rendant le CSP inconsistant. D’ailleurs, ces techniques utilisent des methodes

d’explication et de justification sur les valeurs pour exprimer par quelles contraintes

ces valeurs ont ete exclues. Il devient alors plus facile de savoir pourquoi une valeur a

ete supprimee du domaine. Pour ce faire, il suffit de reintegrer la contrainte ayant ete

relachee lorsqu’un changement dans la definition est survenu. Les approches reactives

sont donc tres habiles pour reagir a tout changement, mais elles manquent de robustesse.

En fait, une solution est robuste si elle est en mesure de resister aux changements.

Les approches pro-actives

Les approches pro-actives utilisent l’ensemble des informations connues pour construire

les solutions. Le but est de construire une solution capable de s’adapter rapidement aux

changements. Elles sont divisees en deux groupes, soient les methodes ou les solutions

sont dites robustes ou les methodes ou les solutions sont dites flexibles. Une solution

robuste est difficile a construire, car elle est construite pour repondre a n’importe quel

changement dans la definition du probleme. Une approche qui construit une solution

flexible a pour avantage de construire une solution pouvant s’adapter facilement lors-

qu’un changement survient dans la definition. Elle s’applique a un ensemble de solutions,

que ce soit une solution complete ou meme une solution partielle.

Toutes les approches etudiees jusqu’a maintenant sont concentrees sur les CSP ou les

variables sont considerees comme dynamique, ouvertes ou meme incertaines. Par contre,

il y a certains problemes ou les variables sont distribuees sur des agents controlant celles-

ci.

4.3.4 Les CSP distribue

Les CSP distribues [57] partagent les variables sur plusieurs agents. Les motifs pour

distribuer un CSP sont diverses. Premierement, certains systemes ont deja une archi-

tecture en reseau ou la distribution est omnipresente. Il est alors couteux d’operer un

agent central pour gerer le tout. Deuxiemement, le cout du transfert de la connais-


sance (communication) peut etre eleve si chaque agent est touche seulement par sa

variable et les contraintes lui etant propres. Il y a alors un gain en cout de transfert

de connaissance. De plus, une architecture peut etre axee sur la securite. Dans ce cas,

aucun agent n’est centralise, et donc, ne contient pas toute l’information importante. Il

est aussi evidemment qu’un systeme multi-agents est plus robuste, car si un agent fait

defaut, les autres peuvent prendre la releve [48].

Plusieurs modeles de “Distributed Constraint Statisfaction Problem” (DisCSP) existent,

mais la majorite de ces modeles sont formules en distribuant sur les agents, les va-

riables et les contraintes. Chaque agent possede une variable et connaıt seulement les

contraintes rattachees a sa variable. Un second formaliste existe. Il consiste a donner

un CSP par agent, ou le CSP peut contenir plusieurs variables et plusieurs contraintes.

La definition formelle d’un DisCSP est la suivante :

– Ensemble d’agents A = {1, 2, ...,m}

– Ensemble de variables X = {x1, ...xn}

– Ensemble de contraintes C = {c1, ...ck}.

Dans ce cas, pour chaque variable xj, un agent i est defini tel que xj appartient a i.

Cette situation est definie par le predicat : (xj : i). De plus, une contraintes Cr qui

touche l’agent i est aussi presentee par un predicat (Cr : i). Les contraintes inter-agents

sont definies comme etant connues par un agent et incluant des variables d’un autre

agent. Le probleme est resolu lorsque toutes les conditions sont satisfaites par tous les

agents.

Plusieurs algorithmes existent pour resoudre les DisCSP. Un de ceux-ci est la methode

centralisee, ou un mediateur recolte toutes les informations des autres agents et resout le

CSP. Cependant, ce type de methode est loin d’etre performant, car tout repose sur un

agent central pouvant etre surcharge et devant attendre l’information de tous les agents

avant de completer son raisonnement. A l’oppose, il existe les methodes decentralisees,

ou chaque agent doit agir en fonction de ses connaissances et celles acquises par com-

munication entre les autres agents. Chaque agent s’assure alors de la consistance de

leurs variables, par rapport a leurs contraintes, et communique avec les autres agents

s’ils ne sont pas capables d’accomplir leurs taches.

Toutefois, dans les approches distribuees, deux moyens de communication sont pos-

sibles. La premiere est la methode synchrone et elle est la plus facile a mettre en oeuvre.

Chaque agent essaie d’assigner une valeur a ses variables et une fois que tous les agents

ont complete leurs assignations, ils envoient leurs valeurs en meme temps. Cela a pour

effet de conserver une periode uniquement a l’echange d’information. Cependant, cette

methode peut ralentir le processus d’assignation, car certains agents plus rapides doivent

attendre que d’autres agents plus lents aient envoye leurs messages. C’est pourquoi les


methodes asynchrones ont fait surface et permettent aux agents de s’envoyer des mes-

sages a tout moment pour corriger les inconsistances. De cette maniere, aucun agent

n’est prisonnier de la lenteur du calcul d’un autre agent.

4.3.5 Le probleme de satisfaction des contraintes hierarchique-

ment distribuees

De nombreux DisCSP possedent trop de contraintes. Cela cause des difficultes, car

il peut etre impossible de trouver une solution consistante sans violer des contraintes.

Le Distributed Hierarchical Constraint Satisfaction (DHCSP) permet de trouver une

solution en considerant les contraintes violees [33]. Il assigne donc aux contraintes une

valeur selon un ordre d’importance. Cette valeur sera prise en compte lors de l’assi-

gnation des variables et lorsqu’une contrainte est violee. Le but est donc de trouver

une solution minimisant la valeur des contraintes violees par rapport a l’ordre d’im-

portance. Les contraintes les plus importantes sont alors consistantes et celles qui sont

jugees moins importantes seront peut-etre violees.

S’il est difficile de juger quelles contraintes sont plus importantes que d’autres, ou

si encore toutes les contraintes ont la meme importance, il est possible de reduire le

nombre de contraintes violees. Ce type de modele se nomme le “Distributed Maximal

CSP” (DMCSP). Ces deux modeles sont classes dans la famille de “Distributed Partial

CSP” (DPCSP), la classe des problemes sur contraints.

4.3.6 Satisfaction de contraintes distribuees et optimisees

Tout comme dans le CSP, les DisCSP possedent aussi des techniques pour optimiser

la solution recherchee. L’algorithme le plus recent et qui a fait ses preuves en “Distri-

buted Constraint Optimization Problem” (DisCOP) est ADOPT [42]. Sa principale

force est qu’il est le premier algorithme asynchrone pour les DisCOP, c’est-a-dire que

c’est le premier algorithme distribue avec lequel les agents sont libres de communiquer

lorsqu’ils le veulent et qui a pour but la recherche d’une solution optimale. De plus, il

est aussi possible d’accelerer l’algorithme ADOPT en faisait des pre-manipulations sur

les donnees avant d’executer ADOPT afin de lui fournir les donnees sous la forme ou il

est le plus performant [2].

Une autre methode d’optimisation est d’adopter l’approche cooperative par mediation.

Cette approche est en fait un protocole asynchrone defini entre les agents. Il permet


0

1

2

[10,20][30,40]

[5,12]

Fig. 4.10 – TCSP

de designer un mediateur pour resoudre une partie de la solution [39]. Elle reduit le

nombre de communication entre les agents par rapport a ADOPT, mais demeure tout

de meme un peu plus lente [14].

4.3.7 Satisfaction de contraintes temporelles

Les reseaux temporels qualitatifs ont ete introduits dans la section 4.1.4, ou l’in-

tervalle d’Allen et le “Point Algebra” sont presentes. Ces reseaux sont concus afin de

permettre de specifier la position relative dans le temps entre deux evenements. Par

contre, si l’objectif est de borner de maniere absolue des evenements, il faut utiliser

les reseaux temporels quantitatifs. Ces reseaux sont definis par des problemes de sa-

tisfaction de contraintes temporelles “Temporal CSP (TCSP)”[30] et ont l’avantage de

restreindre la distance temporelle entre deux points. Un point dans le temps est defini

soit par le debut ou la fin d’une activite. Le modele de TCSP est defini comme suit :

– X = {x1, ..., xn} variables continues representant un point dans le temps.

– D = {di, ..., di} domaine des variables, constitue de reel, representant un instant

precis.

– T = {I1, ..., Ik} = {[a1, b1], ..., [ak, bk]} contraintes representees par des intervalles.

Une contraintes unaire Ti dans ce type de modele s’exprime sur la variable xi par la

disjonction suivante : (a1 ≤ xi ≤ b1)∨ ...∨(ak ≤ xi ≤ bk). Pour leur part, les contraintes

binaires Tij concernent deux variables, xi et xj par (a1 ≤ xj − xi ≤ b1) ∨ ... ∨ (ak ≤

xj − xi ≤ bk).

La figure 4.10 represente une petite instance de probleme de satisfaction de contraintes

temporelles, qui pourrait etre defini comme suit :

– X = {0, 1, 2}

– T = {T01 = [10 ≤ x1 − x0 ≤ 20], T12 = [5 ≤ x2 − x1 ≤ 12] ∨ [30 ≤ x2 − x1 ≤ 40]}

Il est donc compose de trois variables continues qui doivent s’executer dans les in-

tervalles permis par l’ensemble de contraintes T . Il est donc plus facile de representer


les activites dans le temps, a des moments precis, tout en considerant les contraintes, ce

qui n’est pas possible lorsque les approches qualitatives sont privilegiees. Evidemment,

il faut s’adapter a la situation. Par exemple, si la preseance des activites est plus im-

portante que de determiner le moment precis ou executer l’action, il faut alors utiliser

les methodes quantitatives.

Pour resoudre les TCSP, il y a quelques avenues possibles. Premierement, il est

possible de simplifier les TCSP en problemes temporels simples (“Simple Temporal

Problem (STP)”) [47]. Un STP est un reseau quantitatif compose uniquement d’un

intervalle par arc. Il existe des algorithmes polynomiaux pour resoudre les STP, tels

que les arc-consistances (AC) et les chemins-consistance (PC) etudies precedemment.

Pour resoudre un TCSP, il est possible de le decomposer en plusieurs STP, de les

resoudre de maniere independante et de combiner les solutions. De plus, comme le STP

est un graphe pondere dirige, il est aussi possible d’utiliser l’algorithme Floyd-Warshall

[26], pour trouver le plus court chemin.

4.4 Discussion

Nous avons presente differents types d’algorithmes permettant de resoudre les CSP.

Ces algorithmes peuvent etre adaptes pour repondre aux differents modeles de satisfac-

tion de contraintes. Les CSP seront principalement utilises pour resoudre le probleme

d’evaluation de l’engageabilite. Comme nous avons pu le constater, les differents modeles

de CSP permettent de bien s’adapter a n’importe quelles circonstances. Etant donne

que l’estimation de l’engageabilite est un processus dynamique, ouvert et stochastique ;

les CSP semblent etre un modele adequat pour resoudre le probleme.

Chapitre 5

L’evaluation de l’engageabilite

La resolution complete du probleme d’allocation de ressource pour un C2 est un pro-

cessus plutot complexe. Chaque etape est importante et permet d’ameliorer les resultats

finaux. Les differents processus et les relations entre eux sont presentes a la figure 5.1.

Parmi ceux-ci, on retrouve la surveillance qui consiste a garder a jour les informations

sur l’environnement. C’est-a-dire la detection, l’identification et le suivi des menaces.

C’est a partir des informations recueillies lors de la surveillance que les decisions seront

prises.

L’evaluation des menaces permet d’evaluer et de classer les menaces en ordre d’im-

portance. Dans le projet en cours, nous utilisons une formule qui considere la vitesse

des menaces, leurs trajectoires et leurs distances par rapport a la plateforme. Ces in-

formations sont utilisees pour determiner le niveau de dangerosite des menaces, aussi

appele niveau de menace (NM). Evidemment, plus une menace est dangereuse, plus

elle sera a considerer. Il existe d’autres methodes pour evaluer le niveau de danger des

menaces. Au besoin, elle pourra etre modifiee ou ajustee.

L’evaluation de l’engageabilite decrite dans le chapitre 3, appartient au processus

global. Tout comme pour l’evaluation des menaces, il existe d’autres methodes que les

CSPs pour estimer l’engageabilite. Parmi celles-ci, il serait possible d’utiliser le Gen-

Cue [9], qui liste tous les engagements possibles pour toutes les menaces, a partir du

temps d’engagement le plus tard. Par contre, cette etape est longue et plus il est pos-

sible d’engager une menace, plus la liste d’engagements devient importante. Le dernier

processus qui nous interesse est celui de l’engagement et de l’execution du plan. Suite

aux actions trouvees grace a l’engageabilite, il faut executer un plan dans l’environ-

nement afin de contrer les menaces qui nous attaquent. L’ordonnancement des actions

et le choix du temps d’execution du plan se fait dans cette etape. Tous ces processus

Chapitre 5. L’evaluation de l’engageabilite 72

Surveillance

Évaluation des menaces

Évaluation de nos propres capacités

Évaluation de l’Engageabilité

Planification & Exécution

Évaluation des menaces détruites

Évaluation de nos domages

Fig. 5.1 – Processus Global

sont donc constamment utilises pendant toute la duree de l’attaque de la plateforme.

Ainsi, la defense efficace d’une plateforme militaire devrait etre constituee d’approches

adequates dans chacun des processus.

Les processus presentes ci-haut sont souvent composes de sous-processus. D’ailleurs,

dans la partie reservee a la planification, un travail important doit etre effectue. Il

s’agit de l’allocation des ressources. Tout comme il est bien d’estimer l’engageabilite, il

faut aussi etre en mesure de l’utiliser afin de construire un plan et de l’executer dans

l’environnement.

5.1 L’allocation des ressources

L’allocation des ressources permet d’assigner des ressources aux menaces prioritaire,

dans le but de les contrer. Toutefois, le choix des ressources depend de plusieurs criteres,

dont le niveau de survie globale de plateforme, la chance de detruire la menace avec la

ressource donnee, le niveau de menace, ainsi que les contraintes empechant d’executer


certaines actions. Par consequent, trois methodes sont utilisees afin de comprendre a

quel moment il est avantageux d’utiliser l’engageabilite, ou encore, le niveau de menace.

Les trois methodes utilisees sont le niveau de menace (NM), le niveau d’engageabilite

(NE) et le niveau de menace (NM), et le NENM pondere.

5.1.1 Le niveau d’engageabilite et niveau de menace (NENM)

Dans le cadre de ce projet, nous avons divise l’allocation des ressources en deux par-

ties qui permettent de considerer les niveaux d’engageabilite et de menaces. La premiere

partie utilise l’engageabilite et nous procure qu’une allocation partielle. La seconde par-

tie traite le niveau de menace et permet de completer l’allocation. L’allocation partielle

n’est pas obligatoirement, car l’allocation avec le niveau de menace peut etre effective

meme employee seule. D’ailleurs, plusieurs approches reactives l’utilisent pour choisir

les menaces a attaquer en priorite.

Assignation par niveau d’engageabilite

L’evaluation de l’engageabilite indique quelles actions il est possible d’executer pour

contrer les menaces. En plus, elle permet de classifier les menaces par rapport a leurs

NE. Plus une menace peut etre assignee par des ressources, plus son NE est eleve.

Par exemple, pour une simulation, on suppose que la plateforme est attaquee par

six menaces : A,B,C,D,E et F et que ces menaces se trouvent a differentes distances,

avance a differentes vitesses et ont des azimuts differents. Chaque menace dispose donc

de diverses ressources servant a la detruire. Suite a l’evaluation de l’engageabilite, un

tri est effectue afin d’obtenir la liste des menaces ordonnees selon le NE : B(10), A(5),

E(5), D(4), C(3), F(0). La menace B est donc celle qui peut etre engagee par le plus

grand nombre de nos ressources, tandis que la menace F ne peut pas etre attaquee.

Avec cette liste, il est possible de commencer a operer une assignation partielle sur

les menaces. Dans ce but, l’algorithme d’assignation commence par la menace ayant le

plus bas NE, car c’est elle qui possede le plus de contraintes. Ce processus se repete

jusqu’a ce qu’il ne soit plus possible d’assigner une ressource a chaque menace.

Il est a prevoir que le choix des ressources ait un impact sur la probabilite de survie de

la plateforme. Il peut egalement arriver qu’a l’assignation, plusieurs ressources soient

disponibles pour une menace. Dans ce cas, un choix judicieux est necessaire afin de


favoriser une meilleure allocation. Premierement, il est possible de choisir la ressource

maximisant la probabilite de detruire la menace. Ce choix nous assure une plus grande

chance de destruction sur cette menace, mais il peut nuire aussi aux nombres options

envisageables pour les autres menaces. Par exemple, si cette ressource peut etre utilisee

par plusieurs menaces, nos options sont reduites et certaines menaces ne peuvent pas

etre assignees. Il faut donc trouver le moyen d’augmenter la probabilite de survie globale

de la plateforme, tout en utilisant des ressources efficaces contre les menaces. A cet

effet, le fait d’opter pour une methode prenant la ressource la moins presente dans les

domaines des autres menaces peut etre une solution.

La figure 5.2 montre une assignation par l’engageabilite qui se termine avec une solu-

tion partielle. Le choix des ressources par menace y est presente et le NE y est souligne.

La menace B a un NE de 10 et est donc celle qui est la moins contrainte. L’algorithme

commence par faire une assignation a C, ou il est seulement possible d’assigner le GUN.

Il doit ensuite propager ce choix dans les autres domaines des menaces ou le GUN est

disponible. Les domaines des menaces A,B,C et D sont donc touches. Ensuite, comme

il y a seulement un choix dans les domaines de D et E, l’assignation est effectuee et

propagee. Ce choix d’assignation nous laisse donc un A sans ressource possible et un B

avec un Chaff.

A

F

E

D

C

B 10 = {SAM1,Chaff,Jammer }

5 = {SAM1,GUN }

5 = {SAM1,GUN }

4 = {GUN,CIWS }

3 = {GUN }

0 = {noOP }

Engageabilité

A

F

E

D

C


5 = {SAM1,GUN }

5 = {SAM1,GUN }

4 = {GUN,CIWS }

= GUN

0 = {noOP }

Première Assignation (C)

A

F

E

D

C


5 = {SAM1,GUN }

= SAM1

= CIWS

= GUN

0 = {noOP }

Assignations 2-3 (D-E)

A

F

E

D

C

B = Chaff

5 = {SAM1,GUN }

= SAM1

= CIWS

= GUN

0 = {noOP }

Assignation Partielle

Fig. 5.2 – Assignation Partielle


L’algorithme 5.1 represente la methode dont l’assignation partielle est effectuee.

Il prend en entree la liste des menaces et leurs domaines, c’est-a-dire les ressources

disponibles. Il retourne en sortie une assignation partielle, mais valide, qui considere

seulement le niveau d’engageabilite. La methode “Engageabilite” donne toutes les ac-

tions admissibles contre les menaces et ordonne celles-ci en ordre de NE. Une fois les

menaces ordonnees, il construit la solution partielle en bouclant sur les menaces. La

methode “ChoisirRessource” prend en entree une menace et les ressources disponibles

afin de choisir quelles ressources doivent etre selectionnees. Pour finir, il faut propa-

ger ce choix parmi les autres menaces qui n’ont pas encore ete assignees. Ces actions

sont effectuees par la methode “PropagerChoix”, responsable d’eliminer la ressource

des autres domaines.

Algorithm 5.1 Assignation-Engageabilite

1: Entree menaces : liste des menaces avec comme domaine les ressources.

2: Sortie solPart : solution partielle ; ressources assignees aux menaces.

3: solPart← ∅

4: menaces = Engageabilite(menaces)

5: pour each m dans menaces faire

6: si m est non vide alors

7: solPart[m]← ChoisirRessource(m)

8: menaces← PropagerChoix(solPart[m])

9: retourne solPart

Bien que le NE soit essentiel pour effectuer l’allocation des ressources, il faut aussi

s’interesser au niveau de menace. C’est pourquoi l’assignation par engageabilite nous

donne qu’une solution partielle, puisqu’elle ne considere pas le niveau de menace.

Assignation par niveau de menace

Le niveau de menace est une facette du probleme dont il est primordial de considerer

l’importance. Il indique a quel point une menace est dangereuse par rapport aux autres.

Le niveau de menace est utilise pour redistribuer les ressources utilisees par des menaces

a faible NE qui pourraient etre utilisees par une menace de dangerosite superieure, mais

avec un NE eleve. C’est pourquoi l’evaluation des menaces est importante et doit etre

incluse dans l’allocation des ressources.

Le niveau de menace peut etre utilise sans le NE. D’ailleurs, la plupart des approches

utilisent uniquement la dangerosite pour evaluer quelle menace doit etre assignee. Il est

donc possible d’utiliser uniquement l’assignation par niveau de menace. Par contre, il


est favorable de jumeler le niveau de menace avec la solution partielle trouvee par l’en-

gageabilite. Dans ce cas, il conservera la solution partielle et fera des modifications en

fonction des niveaux de menace. Comme l’algorithme d’allocation n’a pas tenu compte

du classement du niveau de menace dans la premiere phase de l’allocation, il doit main-

tenant le faire. Pour cela, il parcourt la liste des menaces en ordre de dangerosite et

s’assurer que la menace a une ressource qui lui est assignee. S’il rencontre une menace

avec aucune assignation, il est tres probable qu’une menace ayant un plus bas niveau

d’engageabilite utilise des ressources pouvant etre plus utiles a une menace plus dan-

gereuse. Il faut alors detecter les conflits entre la menace sans assignation et celles qui

sont assignees mais moins dangereuses. Une fois les conflits detectes, il est necessaire

de prendre les ressources de la menace la moins dangereuse et les laisser a celle qui est

la plus dangereuse.

Certes, il est avantageux d’effectuer une assignation partielle qui considere le NE

et complete l’assignation en tenant compte du niveau des menaces. Effectivement, il

aurait ete possible d’allouer les menaces en favorisant, des le depart, les menaces les

plus dangereuses. Or, cela a pour effet de concentrer les ressources sur les menaces plus

dangereuses. Les interactions entre les ressources ne seraient alors pas considerees et

cela couperait par le fait meme des possibilites pour les autres menaces. Ainsi, moins

nous avons de choix, plus il est difficile d’engager les menaces, ce qui a pour effet de

diminuer la probabilite de survie. En partant d’une solution partielle, favorisant les

menaces les plus contraintes, le nombre de menaces engagees sera maximise.

Par la suite, la deuxieme partie s’assure que les menaces les plus dangereuses sont

assignees. Si elles ne le sont pas, il est possible de faire un changement dans l’allocation

en favorisant la menace la plus dangereuse au detriment d’une menace qui l’est moins.

Le nombre de menaces allouees sera donc toujours egal ou superieur a une methode

utilisant seulement le niveau de menace.

La figure 5.3 nous montre, dans les deux premiers encadres, l’assignation partielle

donnee par l’engageabilite et ou la menace C est la plus dangereuse et la menace F est

la moins menacante. La menace A arrive au 3iem rang au niveau de menace et aucune

ressource ne lui est assignee. Il faut donc detecter les conflits entre la menace A et les

autres menaces, moins dangereuses. Un conflit entre deux menaces existe s’il y a une

ressource commune dans l’ensemble des actions donnees par l’engageabilite. La menace

A entre en conflit avec le GUN de la menace D et avec le SAM et le GUN de la menace

E. Suite a une analyse de l’assignation partielle, il est clair que la menace D n’a pas

le GUN comme assignation, mais bien le CIWS. Il n’y a donc pas de conflit puisque

la menace A ne peut etre assignee par le CIWS. Il reste donc que la menace E, qui

est moins dangereuse, et qui utilise une ressource qui peut etre prise par A. Le SAM


est donc alloue a la menace A et il est deassigne de E. Le processus continu jusqu’a la

derniere menace, la nouvelle assignation etant l’assignation finale qui considere le NE

et le NM.

A

F

E

D

C

B = Chaff

= {SAM1,GUN }

= SAM1

= CIWS

= GUN

= noOP

Assignation Partielle

A

F

E

D

C

B

Niveau de Menace

= GUN

= Chaff

Conflit : {E,D}

= SAM1

= CIWS

A

F

E

D

C

B

Nouvelle Assignation

= GUN

= Chaff

= SAM1

= noOP

= CIWS

= noOP = noOP

Fig. 5.3 – Allocation Finale

Puis, il se peut qu’apres l’allocation par niveau de menace, il reste des ressources

non utilisees qui pourraient l’etre afin d’augmenter la probabilite de survie. Deux choix

sont alors offerts. On peut maximiser la probabilite de survie ou minimiser l’utilisation

des ressources. Il est alors possible d’assigner de nouveau les ressources, en partant de

la plus dangereuse et en assignant les ressources jusqu’a epuisement. On peut aussi ne

rien faire et conserver le plan intact afin de reserver nos ressources pour l’avenir.

L’algorithme 5.2 presente de quelle facon on peut faire l’assignation finale a par-

tir de l’assignation partielle. Dans ce cas, l’algorithme 5.2 prend en entree la liste des

menaces et une solution partielle donnee par l’algorithme 5.1. Il retourne une solution

complete qui utilise le NE et le NM, en commencant par l’ordonner en fonction de

la dangerosite, pour ensuite parcourir les menaces, de la plus dangereuse a celle qui

l’est moins. Quand il rencontre une menace qui n’a pas d’assignation partielle, il de-

mande a detecter les conflits. La fonction “DetecterConlift” s’occupe de faire la liste des

menaces moins dangereuses que la menace courante m, qui sont susceptibles d’engen-

drer des conflits. Celles-ci sont representees par la variable listConf . Cette variable est

ensuite utilisee dans “ConflitMinimal” pour trouver la menace qui est la moins dange-

reuse et qui possede une assignation conflictuelle avec la menace courante. La variable

menaceLow contient la menace en conflit. L’assignation de la menace conflictuelle est

ensuite transferee a la menace courante dans la solution partielle solPart. Ce processus

est repete pour toutes les menaces, jusqu’a ce qu’une assignation finale, solF inale, soit

trouvee. Si le niveau de menace doit etre utilise seul, il suffit de donner une solution

partielle vide, de sorte que l’unique facteur que l’algorithme considere soit le niveau de


menace.

Algorithm 5.2 Assignation-Menace


2: solPart : solution partielle ; ressources assignees aux menaces.

3: Sortie solF inale : solution finale ; ressources assignees aux menaces.

4: menaces = EvaluerDangerosite(menaces)


6: si solPart[m] est vide alors

7: listConf ← DetecterConflit(m,menaces)

8: menaceLow ← ConflitMinimal(listConf)

9: solPart[m]← solPart[menaceLow])

10: solPart[menaceLow]← ∅

11: solF inale← solPart

12: retourne solF inale

5.1.2 Le niveau d’engageabilite et le niveau de menace pondere

Pour tester l’importance du NE et du NM, nous avons pense utiliser une formule

ponderee. A cette fin, nous avons teste differents poids pour ne garder que celui qui

donne le meilleur resultat. La formule NE∗w1+NM ∗w2 a ete utilisee pour determiner

le NENM pondere. Les poids w1 et w2 representent l’importance du NE et du NM.

Bien que la methode pour calculer le NE ait deja ete presentee dans le chapitre sur

l’engageabilite, le niveau de menace (NM) n’est pas utilise de la meme facon que dans

le NENM. Pour le NENM pondere, il faut utiliser une autre valeur que le rang, afin

d’avoir un calcul precis. Pour l’instant, comme les menaces ne se deplace qu’en ligne

droite, nous avons considere le niveau de menace comme la distance de la menace par

rapport a la plateforme, divisee par la vitesse de la menace. Cela nous donne un certain

delai avant que la menace ne touche la plateforme. Ainsi, plus la duree est courte, plus

la menace est dangereuse.

L’algorithme 5.3 montre de quelle facon l’assignation est faite. D’abord, il prend

en entree la liste des menaces, les poids w1 et w2 et il retourne une solution finale.

Il commence par calculer le niveau de menace pour chaque ressource et conserve le

resultat dans TLmenaces. Il fait de meme pour le NE et le conserve dans ESmenaces.

Une fois ces informations trouvees, il trie la liste de menaces selon la fonction NE ∗

w1 + NM ∗ w2 decrite plus haut. Une fois ce travail effectue, l’algorithme a besoin de

choisir les ressources pour la menace qui a la plus haute valeur NENM ponderee et de


propager son choix. Le tout se termine une fois que l’algorithme a parcouru toutes les

menaces.

Algorithm 5.3 NENM pondere


2: w1 et w2 : Poids respectif pour le niveau de menace et le ES.

3: Sortie solF inale : solution finale ; ressources assignees aux menaces.

4: TLmenaces = calculerDangerosite(menaces)

5: ESmenaces = calculerEngageabilite-Score(menaces)

6: menaces = Ordonner(TLmenaces, w1, ESmenaces, w2)


8: solF inale[m]← ChoisirRessource(m)

9: menaces← PropagerChoix(solF inale[m])

10: retourne solF inale

Le choix des poids

Afin de choisir les meilleurs poids a considerer, nous avons experimente quelques

poids possibles, representes a la figure 5.4. Les noms NENMXXYY signifient que nous

avons utilise le niveau d’engageabilite avec le poids XX et le niveau de menace avec le

poids YY. Les approches ont ete testees 25 fois, sur des scenarios comportant de 1 a 12

missiles. Les deux meilleurs resultats ont ete ensuite integres a des scenarios fixes. Un

scenario fixe consiste a rouler en Monte Carlo la meme simulation en eliminant le plus

de variations possible. Les menaces partent donc toujours a partir de la meme distance,

du meme azimut et sans variation d’un scenario a l’autre. Les deux meilleurs resultats

sont presentes a la figure 5.5.

Pour departager les approches, nous avons calcule la moyenne de survie globale

des scenarios dans le tableau 5.1. Le NENM pondere final est celui qui a un poids

d’engageabilite de 0.7 et un poids de menace de 0.3. Le compromis est interessant, car

il montre qu’il est mieux de donner un poids un peu plus important a l’engageabilite

qu’a la dangerosite. Ceci s’explique par le fait que l’evaluation de l’engageabilite permet

d’assigner les menaces les plus contraintes en premier afin d’avoir toujours plus d’options

pour le future.


Scénario Uniforme

0

10

20

30

40

50

60

70

80

90

100

1 2 3 4 5 6 7 8 9 10 11 12

Nombre de Menaces

Ps

NENM0307

NENM0406

NENM0604

NENM0703

NENM0109

NENM0901

Fig. 5.4 – Plusieurs poids de NENM pondere

Scénario Contraint

0

20

40

60

80

100

120

1 2 3 4 5 6 7 8

Nombre de Meances

Ps NENM0406

NENM0703

Fig. 5.5 – Meilleurs Poids

5.2 Validite du plan

La validite d’un plan est la periode de temps ou les actions planifiees restent va-

lides. C’est tres important, car le fait de construire un plan avec des erreurs reduit

considerablement les probabilites de survie. Depuis le debut du processus, notre ob-

jectif premier est de satisfaire les contraintes des ressources afin de trouver la liste

des actions qu’il est possible d’executer. Dans ce cadre, il faut aussi s’assurer que les


Poids (NE-NM) Moyenne scenario uniforme Moyenne scenario fixe

0.1 - 0.9 82.66% –

0.3 - 0.7 81.66% –

0.4 - 0.6 84.33% 82.25%

0.6 - 0.4 83% –

0.7 - 0.3 85% 82.75%

0.9 - 0.1 83% –

Tab. 5.1 – Moyenne de survie globale

contraintes de temps sont satisfaites pour que ces actions restent valides.

En effet, ces contraintes de temps sont en partie respectees. Il est logique, qu’au

moment present, les actions donnees par l’engageabilite soient valides tant au niveau

des contraintes de ressources qu’au niveau des contraintes de temps. Cependant, ces

actions restent valides pendant une certaine periode et c’est cette periode qu’il faut

considerer. Plus un plan est valide sur une longue duree, plus il est permis d’attendre

avant d’envoyer les ordres de tire et esperer augmenter la probabilite de destruction des

menaces. Malheureusement, cette logique peut avoir des inconvenients. Il est possible

que de nouvelles menaces surviennent, obligeant a tout replanifier. De plus, le fait

d’attendre avant d’envoyer les ordres, reduit le nombre de reengagement possible, car

il reste moins de temps par la suite pour effectuer d’autres actions. A cet egard, nous

avons decide d’executer nos action le plus tot possible.

Le plan commence avec les premieres actions disponibles au temps initial. La duree

complete du plan est cependant plus difficile a decouvrir. Pour le trouver, il faut calculer

le temps de lancement au plus tard de chaque action. La fin du plan est definie par

le moment le plus precoce parmis tous les temps au plus tard. Le temps au plus tard

pour executer une action est la limite de temps juste avant de voir une contrainte etre

violee. Ceci nous permettra de limiter l’execution du plan. Par exemple, une menace

quittant la portee d’une arme marquera la fin d’un engagement. Ce temps de fin permet

de s’assurer que toutes les actions peuvent etre executees avant que le plan devienne

invalide.

Chapitre 6

La simulation et les resultats

6.1 La simulation

6.1.1 SADM

Le simulateur utilise dans notre laboratoire est SADM (Ship Air Defence Model)

2.1.2.22.11. C’est un simulateur developpe par BEA System2. Il permet de modeliser une

plateforme en detail, en partant des caracteristiques des senseurs, jusqu’aux radars et

differents types d’armements. Les modeles definis pour chaque composante (senseurs,

radars, armes) sont tres fideles ce qui ajoute un niveau de precision important aux

simulations. SADM est divise en trois grandes parties :

1. Configuration de la simulation ;

2. Visualisation des resultats ;

3. Analyse des resultats.

La partie pour configurer la simulation permet de definir l’environnement, la pla-

teforme militaire et les menaces qui attaquent la plateforme. Des modeles predefinis

existent et facilitent la configuration de la simulation. Ces modeles ont ete modifies

pour correspondre aux caracteristiques de la fregate de classe HALIFAX.

Pour visualiser les resultats, deux interfaces sont disponibles. La simulation en 2D

peut etre utilisee pour observer le deroulement du processus de defense et analyser

1https ://www.sadm.biz/2http ://www.baesystems.com/

Chapitre 6. La simulation et les resultats 83

la gestion des ressources. Le deuxieme module, SIMDIS3, offre une visualisation 3D

ou il est plus aise de suivre chaque element de l’environnement individuellement afin

d’evaluer son comportement.

Afin de pousser plus loin l’analyse des resultats, SADM offre un outil qui permet

de lire les traces de la simulation. Il offre la possibilite de voir le diagramme de Gantt

pour reperer le moment precis ou les ressources sont utilisees. Les traces en mode textes

peuvent servir a isoler une partie de la simulation (i.e. les menaces, les STIRs, etc).

SADM est donc un simulateur complexe, mais qui offre un haut niveau de fidelite

s’il est bien configure. Par contre, sa configuration est compliquee et il possede sou-

vent un comportement non previsible. Plusieurs problemes ont du etre contournes pour

obtenir un systeme qui fonctionne adequatement. Les principales causes du probleme

sont l’absence totale de messages, responsables d’envoyer les informations a l’agent. Par

exemple, il arrive souvent que les informations sur les senseurs, les informations sur la

destruction de la menace ou autres, ne soient pas envoyees par le simulateur. Le meme

probleme se produit lorsque le message est recu a plusieurs fois. Un agent qui pense

recevoir un message et qui ne le recoit pas, peut avoir un comportement imprevu.

Fig. 6.1 – Fenetre Principale

3https ://simdis.nrl.navy.mil/


Fig. 6.2 – Fenetre de configuration des armes

Fig. 6.3 – Fenetre des resultats


Fig. 6.4 – Fenetre de gestion des ressources

6.1.2 Les types de simulations

SADM offre la possibilite de faire differents types de simulation. Premierement, une

simulation simple est composee d’un scenario preetabli execute avec l’agent choisi. Par

exemple, un scenario simple est une plateforme attaquee par 5 menaces provenant du

sud. Par contre, une seule simulation ne permet pas de definir si l’agent est efficace.

Il est donc preferable d’executer une suite de simulation Monte-Carlo [50] pour obte-

nir des resultats plus valides statistiquement. Dans les resultats presentes ci-dessus, un

Monte-Carlo de 100 simulations par nombre de menaces a ete utilise. En plus, il est

possible d’executer des lots de simulations Monte-Carlo. Ces lots permettent de faire

varier plusieurs parametres des simulations comme le nombre de missiles et leurs po-

sitions initiales. C’est d’ailleurs une partie importante des perturbations stochastiques

incluses dans les simulations. A l’aide de ces lots et des simulations Monte-Carlo, il

est possible de faire varier plusieurs attributs dans les scenarios, et il est tres rare que

deux simulations soient identiques. Les attributs facilement variables sont l’azimut des

menaces, la distance de la menace par rapport a la fregate, le temps de depart des

menaces et le nombre de menaces.


6.1.3 Les metriques

Les informations recoltees durant l’execution et qui servent a evaluer le compor-

tement des approches sont tres importantes. Ces informations servent a calculer des

metriques et elles sont ensuite utilisees pour evaluer les performances des algorithmes.

Elles permettent de constater empiriquement dans quelles circonstances les approches

evoluent adequatement. Les informations resumees plus bas ont ete collectees durant

les simulations. On les retrouve egalement dans le tableau 6.1.

La probabilite de survie

La probabilite de survie permet d’evaluer les chances de survie de la plateforme

militaire contre une attaque. Elle est fortement liee aux nombres de menaces qu’elle doit

detruire. Pour evaluer la probabilite de survie d’une approche, plusieurs simulations sont

effectuees avec certains nombres de menaces. La probabilite de survie est un pourcentage

exprimant le nombre de fois que la plateforme a detruit toutes les menaces.

Les couts des ressources

Le simulateur nous permet de mettre un cout sur les ressources utilisees pendant

la simulation. L’evaluation des couts des ressources en dollars permet de savoir si le

systeme de defense utilise un grand nombre de ressources ou si il les economise.

Le nombre moyen de menaces detruites

Au cours de plusieurs simulations, il se peut qu’une approche soit en mesure de

detruire toutes les menaces sauf une. Cela a pour effet de lui donner une probabilite

de survie tres faible. Par contre, il ne faut pas la sous-evaluer, si elle est en mesure de

detruire la grande majorite des missiles. Le nombre moyen de menaces detruites permet

de constater si l’approche a un comportement constant dans toutes les situations.


La moyenne du nombre d’actions

Selon les decisions prises durant la simulation, le nombre d’actions moyen peut

varier d’une approche a l’autre. La moyenne des actions est evaluee selon le nombre de

simulation executee pour chaque tranche de missile. Il est ensuite possible de voir si une

approche a effectue beaucoup d’actions pour obtenir ces resultats. La difference entre

le nombre d’action moyen et le cout des ressources se situe dans le choix des actions

executees. Deux approches peuvent avoir un nombre moyen d’actions semblables, mais

une seule d’entre elles peut favoriser les ressources moins dispendieuses.

La moyenne d’options

Il est aussi possible d’observer le nombre d’options disponibles a chaque seconde.

Une option est une action qu’il est possible d’effectuer contre les menaces. Ainsi, plus

le nombre d’options est eleve, plus la defense sera facile a mettre en place.

La moyenne des options ponderees

Afin de voir si les options disponibles sont interessantes, une ponderation est ef-

fectuee sur les menaces. Pour y parvenir, plus la menace est dangereuse, plus son nombre

d’options sera bonifies.

Le temps de planification total

Le temps de planification est une metrique souvent utilisee dans les approches

deliberatives pour montrer la rapidite de l’algorithme pour construire un plan. Dans

notre cas, la planification est a court terme. Le temps de planification est tout de meme

calcule, car il permet de constater en combien de temps le CSP est resolu et le plan est

construit.

Le temps d’assignation

Le temps d’assignation est utilise pour comparer les methodes d’assignations. Cela

permet de savoir, en excluant la planification, laquelle des methodes d’assignation prend


le moins de temps a trouver une solution.

Metrique Unite Processus

Probabilite de survie % Global

Cout des ressources $ Global

Moyenne du nombre d’actions Action/Simulation Global

Moyenne des menaces detuites Menaces/Simulation Global

Nombre d’options disponibles Options/Seconde Engageabilite

Nombre d’options disponibles Options/Seconde Engageabilite

ponderees

Temps de planification Secondes Engageabilite-planification

Temps d’assignation Secondes Engageabilite-planification

Tab. 6.1 – Metriques

6.2 Les resultats

Dans cette section, nous allons presenter les resultats obtenus dans le projet, au

cours duquel nous avons teste les differentes approches dans les scenarios introduits

dans la section 2.3.1. Une caracteristique importante a considerer est la performance

des algorithmes qui utilisent l’engageabilite. Dans cette optique, nous avons teste les

approches dans divers scenarios, afin d’observer a quels endroits il y a eu des gains.

Tout d’abord, avant de presenter les resultats, nous allons faire un petit retour sur les

approches experimentees. En premier lieu, l’approche sur le niveau de menace (NM) est

une approche reactive qui considere uniquement les deux menaces les plus dangereuses.

De plus, comme les autres approches presentees, l’approche NM attaque les menaces le

plus tot possible, ce qui permet d’engager les menaces plus souvent, mais sans maximiser

la probabilite de survie. L’autre option possible est de tirer au plus tard, ce qui augmente

la probabilite de survie. Puis, l’approche sur le niveau d’engageabilite et le niveau de

menace (NENM) est l’approche effectuant une premiere assignation avec l’engageabilite

et une seconde en favorisant les menaces les plus dangereuses. Finalement, la derniere

approche executee est la NENM ponderee (NENMp), laquelle assigne un poids different

au niveau de l’engageabilite et de la menace.


Abreviation Approches

NM Niveau de menace seul (Reflex)

NENM Niveau d’engageabilite jumele au niveau de menace

NENMp Niveau d’engageabilite et niveau de menace pondere (0.7 / 0.3 )

Tab. 6.2 – Abreviation des approches

6.2.1 Niveau d’engageabilite et niveau de menace

Pour comparer les bienfaits de l’evaluation de l’engageabilite, nous allons verifier

quelles approches sont les plus performantes selon les metriques introduites ci-haut.

Une approche performante doit avoir un bon taux de survie dans plusieurs scenarios.

La figure 6.5 presente les resultats de l’approche NM, NENM et NENMp dans le scenario

uniforme 2.3.2. Il est possible de voir par le tableau 6.3 que c’est l’approche considerant

le niveau de menace qui est la meilleure. Elle domine les autres et a une moyenne de

survie legerement plus elevee.

Scénario Uniforme

0

20

40

60

80

100

120

1 2 3 4 5 6 7 8 9 10 11 12 13

Nombre de Menaces

Ps

NM

NENM

NENMp

Fig. 6.5 – Scenario uniforme

Approche Moyenne de survie

NM 79.62%

NENM 79.12% (-0.5%)

NENMp 78.46% (-1.6%)

Tab. 6.3 – Moyenne de survie sur scenario uniforme


Scénario Uniorme-D

0

20

40

60

80

100

120

1 2 3 4 5 6 7 8 9 10 11 12 13

Nombre de Menaces

Ps

NM

NENM

NENMp

Fig. 6.6 – Scenario uniforme-D

Approche Moyenne de Survie

NM 72.3%

NENM 73.14% (+0.84%)

NENMp 74.3% (+1.0%)

Tab. 6.4 – Moyenne de survie sur scenario uniforme-D

Les differences entre les moyennes sont minimes et s’expliquent par le fait que le

scenario uniforme est simple et contient des menaces progressant a la meme vitesse. Il

devient alors difficile d’exploiter les avantages de l’engageabilite, car la strategie la plus

performante est de toujours d’assigner la menace le plus pres de soi, ce que favorise un

agent considerant uniquement le niveau de menace.

Pour contrer ce probleme, nous avons utilise le scenario uniforme-D ou les menaces

ont differentes vitesses. Il est donc important d’effectuer une distinction entre les me-

naces pour ne pas se retrouver devant un manque d’alternatives. La figure 6.6 montre

les courbes sur 1300 simulations du scenario. Les algorithmes performent encore tres

bien. Par contre, la moyenne de survie a maintenant un ecart plus significatif comme le

presente la table des moyennes 6.4.

L’utilisation de l’engageabilite a donc augmentee la moyenne de la probabilite de

survie dans le cas ou il faut tenir en compte de la disponibilite des menaces et des

contraintes de l’environnement. L’ecart est le NM et le NENMp est de 2% et ce, sur


Scénario Contraints

0

10

20

30

40

50

60

70

80

90

100

1 2 3 4 5 6 7 8 9 10 11 12

Nombre de menaces

Ps

NM

NENM

NENMp

Fig. 6.7 – Scenario Contraint

Approche Moyenne de Survie

NM 62.42%

NENM 66.5% (+4.08%)

NENMp 66.58% (+4.16%)

Tab. 6.5 – Moyenne de PK sur scenario Contraint

une approche de planification reactive. Une approche plus sophistiquee permettant de

prendre des decisions ou une approche deliberative pourrait tirer davantage de l’enga-

geabilite.

Afin de constater les avantages de l’engageabilite sur le pourcentage de survie, nous

avons augmente les contraintes de la fregate. Le scenario Contraint est utilise pour

comprendre de quelle facon l’engageagbilite peut etre percu dans un environnement plus

contraint. Le graphique 6.7 exprime les resultats et la table 6.5 represente les moyennes.

En somme, l’engeagbilite a un avantage considerable, car elle considere le niveau

d’engageabilite et le niveau de menace. L’ecart est de 4% entre l’approche NM et celles

considerant l’engageabilite. C’est un gain appreciable qui prouve que l’engageabilite a

son utilite et doit desormais etre considere dans la planification militaire. Cette consta-

tation est evidente puisque notre approche vise a satisfaire les contraintes. Bref, plus il

y en a, plus l’approche peut y repondre adequatement.


Nombre de menaces détruites

0

1

2

3

4

5

6

7

8

9

10

11

3 6 9 12

Nombre de Menaces

Me

na

ce

s D

étr

uit

es

Mo

ye

ns

NM

NENM

NENMp

Fig. 6.8 – Nombre moyen de menaces detruites

Les menaces detruites

Le graphique 6.8 montre egalement que les approches considerant l’engageabilite

reussissent a detruire plus de menaces. Pour valider le tout, nous avons calcule le nombre

de menaces detruites dans un scenario contraint de 9 a 13 menaces. Il s’est avere que

l’approche NENM est celle qui se comporte le mieux et detruit le plus de missiles.

L’environnement que nous avons, qui comporte moins de 6 ressources et de 13 me-

naces, laisse l’ensemble de decisions restreint. Si nous avions une plateforme avec 20

ressources, attaques par 30 menaces, l’engeagbilite serait certainement plus efficace. Par

contre, comme le probleme est deja complexe, stochastique et en temps reel, il serait

tres difficile de trouver une solution efficace dans ce genre de circonstance.

Le cout des ressources

Pour evaluer le cout des ressources, nous avons regarde la moyenne des depenses sur

toutes les simulations des 3 scenarios et nous en avons fait une moyenne. Ccomme le

montre le tableau 6.6, aucune approche sur-utilise ou sous-utilise les ressources.


Approche Cout des ressources (kilo $)

NM 8 834 $

NENM 8 764 $

NENMp 8 920 $

Tab. 6.6 – Moyenne des couts pour tous les scenarios

6.2.2 Le nombre d’options disponibles

L’evaluation de l’engageabilite procure des gains en probabilite de survie, et il est

possible de mesurer son apport a l’aide du nombre d’options disponibles. Effective-

ment, le but de l’engageabilite est de permettre a l’operateur de choisir judicieusement

les menaces dans le but de se garder le plus options possibles pour le futur. Il faut donc

analyser le nombre moyen d’options pendant les simulations. A ce sujet, nous avons

execute 50 simulations de 3,6,9 et 12 menaces au cours desquelles nous avons evaluer la

moyenne d’options a chaque seconde de la simulation. La figure 6.9 montre les resultats

obtenus lors de cette simulation. Nous y constatons que les approches qui considerent

l’engageabilite possedent davantage d’options par seconde lorsqu’il y a plusieurs me-

naces (12).

Nombre d'options Moyens

0,00

0,50

1,00

1,50

2,00

2,50

3,00

3,50

4,00

4,50

3 6 9 12

Nombre de Menaces

Nb

Op

tio

ns

NM

NENM

NENMp

Fig. 6.9 – Nombre d’options

6.2.3 Le temps d’execution

Pour evaluer les performances des algorithmes, nous avons egalement evalue la vi-

tesse d’execution de la planification et de l’assignation. Le temps de planification est


traduit par le temps total passe a planifier pendant le scenario. Les trois approches

prennent sensiblement le meme temps de planification. Ce qui est normal puisqu’elles

planifies generalement le meme nombre d’actions. La figure 6.10 presente les courbes

de temps evoluant selon le nombre de menaces a gerer.

Temps de planification

0

5

10

15

20

25

30

9 10 11 12 13

Nombre de Menaces

Te

mp

s (

s)

NM

NENM

NENMp

Fig. 6.10 – Temps de planification

Temps d'assignation

0

0,2

0,4

0,6

0,8

1

1,2

1,4

9 10 11 12 13

Nombre de Menaces

Te

mp

s (

s)

NM

NENM

NENMp

Fig. 6.11 – Temps d’assignation

La figure 6.11 presente le temps d’assignation pour chaque algorithme. Le NENM


est beaucoup plus lent que NM puisque le NENM utilise l’algorithme NM. Par contre,

on constate que le NENMp est egal ou inferieur au temps du NM. Ceci est encourageant

puisqu’il est aussi l’algorithme le plus performant.

6.3 Recommandations futures

D’abord, l’evaluation de l’engageabilite est processus qui intervient avant la planifi-

cation et qui pourrait avoir de meilleurs resultats si elle etait utilisee dans une approche

plus sophistiquee. Ainsi, integrer l’engageabilite a une autre methode, comme l’appren-

tissage par renforcement, les MDPs ou le Rollout, pourrait servir ces algorithmes en leur

procurant un ensemble d’actions de base. Cet ensemble permettrait a l’agent d’avoir

un sous-ensemble d’actions possibles rapidement. Ce qui procurerait des actions qui

satisferaient les contraintes et offeraient de meilleures options pour les etapes futures.

Au niveau de l’evaluation de l’engageabilite elle-meme, il serait possible d’utiliser

le modele COP pour trouver la solution optimale. Par contre, nous pensons qu’une

autre modelisation du CSP devrait etre effectuee, car rien ne permet pour le moment

d’associer un NE aux ressources, tant et aussi longtemps que l’engageabilite n’a pas ete

evaluer. Or, notre CSP est resolu et nous sert par la suite a trouver le niveau d’enga-

geabilite pour chaque menace. Pour respecter cette modelisation, il faudrait resoudre

le modele CSP actuel, trouver le niveau d’engageabilite de chaque menace et resoudre

le COP avec ce niveau d’engageabilite injecte dans le ce nouveau modele. La solution

trouvee par le COP serait alors utilisee directement dans la phase d’assignation.

Les modeles d’assignation NENM et NENMp sont deux approches que nous avons

introduites et a notre connaissance il n’existe pas d’autres modeles d’assignations plus

performants, utilisant le niveau d’engageabilie et le niveau de menace. Une analyse

plus poussee dans les modeles d’assignations pourrait etre effectuee afin de trouver la

methode la plus efficace dans tous les scenarios.

6.4 Sommaire

Les resultats ont montre que les approches utilisant l’engageabilite ont tendance a

mieux performer que celles qui ne l’utilisent pas. Les simulations ont ete pratiquees sur

un simulateur militaire offrant un bon niveau de fidelite mais tres difficile a configurer

et a utiliser. Plus de 5000 simulations ont ete effectuees afin de valider les differences


entre les approches. Le nombre d’options a aussi montre que les decisions prises a

l’aide de l’evaluation de l’engageabilite permettent de donner davantage de choix dans

le futur. C’est d’ailleurs ce qui explique sa meilleure performance. De plus, il a ete

observe que l’evaluation de l’engageabilite est plus utilse lorsque l’agent evolue dans

un environnement contraint. Lorsqu’il y a beaucoup de contraintes et que l’espace de

faisabilite est reduit, il est avantageux d’utiliser l’engageabilite. En general, les resultats

obtenus sont ceux qui etaient prevus. Par contre, nous pensions que les ecarts seraient

plus grands entre les approches NM et NENMp. Les resultats sont encourageants et nous

sommes persuades qu’il serait possible d’avoir de meilleurs resultats avec une strategie

de planification plus sophistiquee.

Chapitre 7

Conclusion

Dans ce memoire, nous avons adresse le probleme de la gestion de ressources dans

un context militaire a l’aide d’une technique de l’intelligence artificielle, le CSP. Dans le

but d’accomplir cette tache, nous avons decris la problematique de gestion de ressource

sur une plateforme militaire dans le but de se defendre.

Le chapitre 2 a donc decrit la plateforme utilisee dans la problematique. Nous avons

explique la nature des ressources et des menaces presentes dans le projet. De plus,

nous avons introduit et explique les scenarios utilises pour effectuer les nombreuses

simulations.

Pour bien comprendre le probleme etudie, le chapitre 3 introduit l’evaluation de

l’engageabilite. Pour commencer, il aborde comment le probleme est modelise et les

techniques pour le resoudre. Il presente aussi pourquoi l’engageabilite a ete utilise et

comment ILOG permet de trouver une solution aux CSP. Le chapitre 4 est compose

d’une revue de litterature sur les CSP ou les differents modeles et algorithmes pour les

resoudre y sont presentes et expliques. Dans l’objectif de comprendre comment les CSP

et l’engageabilite sont liees, le chapitre 5 decrit la resolution complete de l’engageabilite

et du probleme de la gestion des ressources sur la plateforme.

Le tout est complete par le chapitre 6, ou le simulateur, les metriques et les resultats

des approches sont expliques. Differents tableaux et explications sont disponibles et

permettent d’observer qu’il y a des gains a utiliser l’engageabilite, surtout dans les

scenarios ou il y a beaucoup de contraintes a satisfaire.

Chapitre 7. Conclusion 98

7.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. Modeliser le probleme en CSP. Ce point a ete presente au chapitre 2 ou deux

modeles ont ete presentes.

2. Etudier les modeles de CSP, COP, DCSP. La revue de litterature a permis de

combler cet objectif adequatement en executant un survol des differents modeles

pour satisfaire les contraintes et les algorithmes pour les resoudre.

3. Definir ce qu’est le domaine de faisabilite. Le domaine de faisabilite a ete

explique dans le chapitre 3 ou l’espace de faisabilite est defini et presente graphi-

quement.

4. Definir comment faire la propagation dynamique des contraintes. Ce

point est aussi realise dans le 3 ou le but est d’utilise cette propagation pour

resoudre les CSP de facon dynamique.

5. Comparer diverses methodes pour utiliser l’engageabilite dans la pla-

nification. Nous avons presente deux approches, i) “Niveau de Menace” et ii)

“Niveau d’Engageabilite combine au Niveau de Menace”. Ils utilisent l’engagea-

bilite de manieres differentes et ils sont expliques dans le chapitre 5 et 6.

6. Implementer l’approche de planification sur un simulateur de la defense

afin de la valider. Le travail d’implementation a ete fait a l’interieur de nos

agents en C++ et ils ont ensuite ete exportes dans le simulateur pour valider

l’approche.

7.2 Les travaux futurs

Pour les travaux futurs, il serait preferable de commencer par effectuer les ameliorations

possibles presentees au chapitre 6. Par contre, dans le but de profiter pleinement de

l’evaluation de l’engageabilite, il serait tres interessant de l’utiliser dans une approche

se concentrant exclusivement sur la planification, de sorte qu’il serait possible de com-

parer cette approche de planification avec ou sans l’engageabilite afin de constater les

differences dans les metriques. De plus, migrer l’agent sur une autre plateforme avec

beaucoup plus de ressources et de menaces serait tres interessant, car cela permettrait

de voir encore plus l’efficacite de l’engageabilite.

Chapitre 7. Conclusion 99

Dans un context militaire, la cooperation est tres importante. Il arrive que plusieurs

fregates doivent cooperer ensemble pour se defendre. L’utilisation des modeles DCSP

(probleme de satisfaction de contraintes distribuees) pourrait alors etre utilisee afin

d’effectuer cette cooperation, d’utiliser les avantages de l’evaluation de l’engageabilite

afin de mieux se defendre.

Pour conclure, il pourrait etre tres interessant de construire un module permettant

a la fregate d’effectuer une rotation afin de se donner plus d’options de defense. Or, ce

probleme de rotation a deja ete etudie [40] mais en considerant seulement les secteurs

de la plateforme. Maintenant, avec l’engageabilite, il serait pertinent de creer un agent

qui ferait la rotation de la fregate par rapport au niveau d’engageabilite et du niveau

de menace.

Bibliographie

[1] Mackworth A.K. Consistency in networks of relations. In artificial Intelligence 8,

pages 99–118, 1977.

[2] Syed Ali, Sven Koenig, and Milind Tambe. Preprocessing techniques for accele-

rating the dcop algorithm adopt. In AAMAS ’05 : Proceedings of the fourth in-

ternational joint conference on Autonomous agents and multiagent systems, pages

1041–1048, New York, NY, USA, 2005.

[3] James F. Allen. Maintaining knowledge about temporal intervals. Commun. ACM,

26(11) :832–843, 1983.

[4] Roman Bartak. Constraint propagation and backtracking-based search. Contraint

Programming School 2005, 2005.

[5] S. Beale. Using branch-and-bound with constraint satisfaction in optimization

problems. AAAI, 1997.

[6] Wu C. Bertsekas D.P., Tsitsiklis J.N. Rollout algorithms for combinatorial opti-

mization. Journal of Heuristics, Volume 3, Issue 3, pages 245–262, 1997.

[7] C. Bessiere. Arc-consistency in dynamic constraint satisfaction problems. Procee-

dings of the 9th national Conference of the AAAI, 1991.

[8] J. R. Bitner and Reingold E. Backtracking programming techniques. Communi-

cations of the ACM, pages 18 :651–656, 1975.

[9] Dale Blodgett, Michel Gendreau, Francois Guertin, Jean-Yves Potvin, and Rene

Seguin. A tabu search heuristic for resource management in naval warfare, 1998.

Publication du Centre de Recherche en Transport, CRT-98-63, Montreal.

[10] M. Boddy and T.L. Dean. Solving time-dependent planning problems. In In Pro-

ceedings of the Eleventh International Joint Conference on Artificial Intelligence,

Detroit, Michigan, 1989.

[11] S. Cook. The complexity of theorem proving procedures. In Proceedings of the

third annual ACM symposium on Theory of computing, 1971.

BIBLIOGRAPHIE 101

[12] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT,

1990.

[13] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction a l’algorithmique.

MIT, 2001.

[14] John Davin and Pragnesh Jay Modi. Impact of problem centralization in distri-

buted constraint optimization algorithms. In AAMAS ’05 : Proceedings of the

fourth international joint conference on Autonomous agents and multiagent sys-

tems, pages 1057–1063, New York, NY, USA, 2005.

[15] Martin Davis, George Logemann, and Donald Loveland. A machine program for

theorem-proving. Commun. ACM, 5(7) :394–397, 1962.

[16] T.L Dean. Intractability and time-dependent planning. In In Proceedings of the

1986 Workshop on Reasoning about Actions and Plans, Los Altos, California, 1987.

Morgan Kaufmann.

[17] T.L. Dean and M. Boddy. An analysis of time-dependent planning. In In Procee-

dings of the Seventh National Conference on Artificial Intelligence, Minneapolis,

Minnesota, 1988.

[18] R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.

[19] R. Dechter and A. Dechter. Belief maintenance in dynamic constraint networks.

In n Proc. of the 7th National Conference on Artificial Intelligence (AAAI-88), St.

Paul, MN, USA, 1988. Springer-Verlag.

[20] Meiri I. Dechter R. and Pearl J. Temporal constraint networks. Artificial Intelli-

gence, 49 :61–95, 1991.

[21] Tadeusz P. Dobrowiecki. Anytime Algorithms. Budapest University of Technology

and Economics, 1990.

[22] Freuder E. Partial constraint satisfaction. In In Proceedings of the International

Joint Conference on Artificial Intelligence, pages 278–283, 1989.

[23] Freuder E. Complexity of k-tree structured constraint satisfaction problems. In

In Proceedings of the Eighth National Conference on Artificial Intelligence, pages

4–9, 1990.

[24] B. Faltings and S. Macho-Gonzalez. Open constraint satisfaction. In CP ’02 :

Proceedings of the 8th International Conference on Principles and Practice of

Constraint Programming, pages 356–370, London, UK, 2002. Springer-Verlag.

BIBLIOGRAPHIE 102

[25] Boi Faltings and Santiago Macho-Gonzalez. Open constraint optimization. In In

Proceedings of Principles and Practice of Constraint Programming, 2003.

[26] Robert W Floyd. Algorithm 97 : Shortest path. In Communications of the ACM

5, June 1962.

[27] H. Fragier and J. Lang. Uncertany in constraint satisfaction problems : a proba-

bilistic approach. ECSQARU Springler-Verlag, 1993.

[28] J. Gaschnig. Exactly how good are heuristics ? : Toward a realistic predictive

theory of best-first search. In Proc. IJCAI-77, pages 434–441, MIT, Cambridge,

MA, August 1977.

[29] J. Gaschnig. Performance measurement and analysis of certain search algorithms.

Carnegie-Mellon University, pages 685–700, 1979.

[30] R. Gennari. Temporal reasoning and constraint programming : A survey, 1998.

[31] Malik Ghallab and A. Mounir Alaoui. Managing efficiently temporal relations

through indexed spanning trees. In IJCAI, pages 1297–1303, 1989.

[32] Diana F. Gordon. An enhancer for reactive plans. In Machine Learning, pages

505–508, 1991.

[33] Katsutoshi Hirayama and Makoto Yokoo. An approach to over-constrained dis-

tributed constraint satisfaction problems : Distributed hierarchical constraint sa-

tisfaction. In ICMAS ’00 : Proceedings of the Fourth International Conference on

MultiAgent Systems (ICMAS-2000), page 135, Washington, DC, USA, 2000. IEEE

Computer Society.

[34] Davis A. L. and Rosenfeld A. Cooperating processes for low-level vision : A survey.

Artificial Intelligence, 17 :245–263, 1981.

[35] Waltz D. L. Understanding line drawings of scenes with shadows. In The Psycho-

logy of Computer Vision, 1975.

[36] Verfaillie G Lematre M. and Schiez T. Russian doll search for solving constraint

optimization problems. AAAI-96, 1996.

[37] Michael L. Littman and Stephen M. Majercik. Large-scale planning under uncer-

tainty : A survey, 1997.

[38] Witsenhausen H.S.. Lloyd S.P. Weapon allocation is np-complete. IEEE Summer

Simulation Conference, 1986.

BIBLIOGRAPHIE 103

[39] Roger Mailler and Victor Lesser. Solving distributed constraint optimization pro-

blems using cooperative mediation. In Proceedings of Third International Joint

Conference on Autonomous Agents and Multiagent Systems (AAMAS 2004), pages

438–445. IEEE Computer Society, 2004.

[40] Jean-Francois Morissette. Algorithmes de gestion de ressources en temps reel : po-

sitionnement et planification lors d’attaques aeriennes. Master’s thesis, Univeriste

Laval, 2005.

[41] David J. Musliner, James A. Hendler, Ashok K. Agrawala, Edmund H. Durfee,

Jay K. Strosnider, and C.j. Paul. The challenges of real-time ai. Computer,

28(1) :58–66, 1995.

[42] M. Yokoo P. modi, W.Shen. An asyncronous complete method for distributed

constraint optimization. AAMMAS, 2003.

[43] J. K. Pearson and P. G. Jeavons. A survey of tractable constraint satisfaction

problems. Technical Report CSD-TR-97-15, Royal Holloway University of London,

1997.

[44] Louise Pryor and Gregg Collins. Planning for contingencies : A decision-based

approach. Journal of Artificial Intelligence Research, 4 :287–339, 1996.

[45] Dechter R. Mini-buckets : A general shceme of generating approximations in au-

tomated reasoning. IJCAI-97, pages 1297–1302, 1997.

[46] Dechter R. and Pearl J. Network-based heuristics for constraint-satisfaction pro-

blems. Artificial Intelligence, 34 :1–38, 1988.

[47] Eddie Schwalb and Lluis Vila. Temporal constraints : A survey. Constraints,

3(2/3) :129–149, 1998.

[48] Pragnesh Jay Modi Hyuckchul Jung Milind Tambe Wei-Min Shen and Shriniwas

Kulkarni. A dynamic distributed constraint satisfaction approach to resource allo-

cation. CP, pages 685–700, 2001.

[49] Ibaraki T. Theoretical comparisons of search strategies in branch-and-bound al-

gortihmes. Computer Science, pages 5 :315–344, 1976.

[50] James R. Thompson. Simulation A Modeler’s Approach. Wiley Series, 2000.

[51] Alexander Toet and Huub de Waard. The weapon-target assignment problem,

1995.

[52] Montaanari U. Networks of constraint : Fundamental propertties and applications

to picture processing. Information Science, pages 95–32, 1974.

BIBLIOGRAPHIE 104

[53] G. Verfaillie and N. Jussien. Constraint solving in uncertain and dynamic environ-

ments : A survey. Springler Science, Constraint, 2005.

[54] Toby Walsh. Stochastic constraint programming. Proceedings of ECAI-2002, 2002.

[55] Kohler W.H. and Stieglitz K. Characterization and theoretical comparison of

branch-and-bound algorithmes for permutation problemes. Journal of ACM, pages

21 :140–146, 1974.

[56] Michael Woolridge and Michael J. Wooldridge. Introduction to Multiagent Systems.

John Wiley & Sons, Inc., New York, NY, USA, 2001.

[57] Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. The

distributed constraint satisfaction problem : Formalization and algorithms. Know-

ledge and Data Engineering, 10(5) :673–685, 1998.

Documents

Ordonnancement de ressources en temps réel avec