CORALS : Aide à la décision sous incertitude dans un contexte naval

Éric Beaudry, Ph.D.

Systèmes d’aides à la décisionRDDC – Valcartier

6 juin 2011IFT615 – Intelligence artificielle

2

MISE EN CONTEXTE

3

Missions canadiennes

• Missions humanitaire et de maintien de la paix de l’ONU

• Supporter nos engagements dans l’OTAN• Protéger les navires commerciaux des pirates en mers• Combattre le terrorisme

4

Conflit en Libye (2011)

5

Menaces

• Différentes menaces (cruise missiles, bombs, shoulder-launched rockets, etc.)

• Les menaces peuvent être coordonnées et provenir de l’air, en mer ou du sol

6

Moyens de défenses

7

Défis

• Volume important d’informations• Incertitude

– Données imparfaites de plusieurs sources– Interprétation humaine

• Facteurs temporels:– Temps de réaction très court– Prise de décisions sous pression– Environnement dynamique : la situation

évolue dans le temps

8

Buts et contraintes

• But :– Maximiser la survie du navire– Protéger des volumes d’intérêts

• Contraintes– Zones aveugles– Règles d’engagement– Coordination des ressources– Ressources limitées

9

Efficacité probabiliste des moyens de défense

10

CORALSUn système d’aide à la décision

11

La solution : CORALS

• Système d’aide à la décision pour suggérer les moyens de défenses face aux menaces

12

Plans de défense

13

Algorithme de planification

• Résolution de conflits par une recherche dans un espace de plans

14

15

HEURISTIQUES

16

Solution en tout temps (anytime)

• Contraintes de temps réel• Pas toujours possible de garantir une solutions

optimale ou proche optimal• Heuristiques et stratégies de recherche

17

If LowerBound(n0)=L, then there exists at least a node n’ in {n1,n2,n3} were Quality(n’) >= L

€

LowerBound(n) <=n '∈reachale(n )max Quality(n)

LowerBound(n) <=n '∈successors(n )

max LowerBound(n)

n0

n2n1 n3

Idée : estimer une borne inférieure sur la qualité des plans …

18

Heuristiques

H1 – Retrait des actions en conflits

H2 – Retrait arbitraire d’actions pour éliminer les conflits

H3 – Retrait des actions avec la plus faible probabilité de succès

H4 – Retrait des actions selon le contexte

19

Exemple de plan avec 2 conflits (4 actions en conflits)

Target 11. SK / CWJamming : Jamming (75%)

2. HK / ESSM : (40%)

3. HK / CIWS : CIWS (40%)

Target 25. SK / CWJamming : Jamming (75%)

6. HK / ESSM : (85%)

8. HK / GUN57 (45%)

0 20 40 60 80 100 120

4. HK / GUN57 (40%)

7. HK / CIWS : CIWS (55%)

1

2

20

H1 – Retrait des actions en conflits

Target 11. SK / CWJamming : Jamming (75%)

2. HK / ESSM : (40%)

3. HK / CIWS : CIWS (40%)

Target 25. SK / CWJamming : Jamming (75%)

6. HK / ESSM : (85%)

8. HK / GUN57 (45%)

0 20 40 60 80 100 120

4. HK / GUN57 (40%)

7. HK / CIWS : CIWS (55%)

85%

96.25%

85% * 96.25% = 81.81%

21

H2 – Retrait arbitraire d’actions pour éliminer les conflits

• If two or more actions are conflictual, one of them is arbitary choosen to be enabled.

Target 11. SK / CWJamming : Jamming (75%)

2. HK / ESSM : (40%)

3. HK / CIWS : CIWS (40%)

Target 25. SK / CWJamming : Jamming (75%)

6. HK / ESSM : (85%)

8. HK / GUN57 (45%)

0 20 40 60 80 100 120

4. HK / GUN57 (40%)

7. HK / CIWS : CIWS (55%)

91%

97.79%

91% * 97.79% = 89.12%

22

H3 – Retrait des actions avec la plus faible probabilité de succès

• If two or more actions are conflictual, we keep the best one.

Target 11. SK / CWJamming : Jamming (75%)

2. HK / ESSM : (40%)

3. HK / CIWS : CIWS (40%)

Target 25. SK / CWJamming : Jamming (75%)

6. HK / ESSM : (85%)

8. HK / GUN57 (45%)

0 20 40 60 80 100 120

4. HK / GUN57 (40%)

7. HK / CIWS : CIWS (55%)

85%

99.07%

85% * 99.07% = 84.21%

23

H4 – Retrait des actions selon le contexte

• If two or more actions are conflictual, we keep the one that will give the highest global result.

Target 11. SK / CWJamming : Jamming (75%)

2. HK / ESSM : (40%)

3. HK / CIWS : CIWS (40%)

Target 25. SK / CWJamming : Jamming (75%)

6. HK / ESSM : (85%)

8. HK / GUN57 (45%)

0 20 40 60 80 100 120

4. HK / GUN57 (40%)

7. HK / CIWS : CIWS (55%)

94.6%

96.25%

94.6% * 96.25% = 91.05%

24

Summary of Exemple

• Even LowerBoundV4 produce better lower bound estimation, its computation cost is much higher because partial sub-plan have to be re-estimated on each action with conflicts. Its means that fewer nodes per seconds could be generated.

• In fact, * log(n) is implicitly added for all since plans are balanced trees that require log(n) for each action removal.

Lower Bound Algorithm(For each conflict)

Computation Cost(c = nb conflictsn = nb actions; t=nb target)

Value of Example Plan

V1 (CORALS 4.2) Remove all conflicts actions

O(c) 81.81 %

V2 Keep arbitary actions O(n * c) 89.12 %

V3 Keep best actions O(n * c) 84.21 %

V4 Keep the action that have the highest gain.

O(t * n * c) 91.05 %

25

STRATÉGIE DE RECHERCHE ENFORCED HILL CLIMBING (EHC)

26

1

2 6

4

5

7

8

Example Enforced Hill Climbingwith a depth parameter of 3

27

Complexité (coût) des heuristiques

Maximum planning time set to 10 secondes.25 runs on scenarios with 10 targets.

V1 V2 V3 V40

5

10

15

20

25

30

35

40

45

GeneratedVisited

Lower Bound Algorithm

Nod

es (0

00)

28

Performance

V1 (CORALS 4.2) V2 V3 V4 (CORALS 4.3)0%

10%

20%

30%

40%

50%

60%

70%

80%

Qua

lity

(Sur

viva

l Pro

babi

lity)

29

Réactivité

Maximum planning time set to 10 secondes.25 runs on scenarios with 10 targets.

0 1 2 3 4 5 6 7 8 9 100

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

V1

V2

V3

V4

Planning Time

Qua

lity

(Sur

viva

l Pro

babi

lity)

30

À CONSIDÉRER

31

Travaux futures

• Interaction avec opérateurs– Interfaces multi-touch

• Single-Ship Multi-Ship

32

CES DÉFIS VOUS INTÉRESSENT ?

33

Stage YRD0 01 01 [Automne 2011]

34

QUESTIONS ?

35