Examen mi-session Intelligence Artificielle II (IFT …lafamilledurefuge.free.fr/doc/S8/Intelligence Artificielle/DS 2001... · Examen mi-session Intelligence Artificielle II (IFT-17587)

Examen mi-session

Intelligence Artificielle II (IFT-17587)

Jeudi 1er mars 2001

De 8h30 à 11h15 en salle 3775 PLT

Les documents permis sont le livre, les acétates du cours et une double page de notes

------------------------------------------------------------------------

1) (18 pts) Donner la PAGE et les caractéristiques de l’environnement d’un agent en

charge de la mise en place des ouvrages dans une bibliothèque. On pourrait supposer

qu’un tel agent prend les livres d’une place donnée et les range à la bonne place selon

les côtes des livres.

Percepts : Pixel d’intensité variable (caméra), cote du livre (lecteur de code barre).

Actions :

• Prendre un livre, s’il y a un nouveau livre à ranger.

• Lire la cote.

• Se déplacer (avancer, tourner, arrêter) pour aller ranger un livre ou revenir au chariot des

retours et pour éviter les obstacles.

• Déposer un livre lorsqu’il est arrivée à la position où le livre doit être rangé.

But : Le but de l’agent est de mettre les livres, qui sont dans le chariot des retours, à la bonne

position dans les rayons de la bibliothèque.

Environnement : L’environnement de l’agent est une bibliothèque. L’environnement est

inaccessible, parce que l’agent ne peut pas avoir accès à toutes les informations sur

l’environnement. L’environnement est non-déterminé, parce que les actions de l’agent n’ont pas un

effet garanti et il y a de l’incertain. Lorsque l’agent avance, il peut frapper un obstacle qu’il n’avait

pas vu. L’environnement est non-épisodique , car les actions de l’agent dans le passé peut influencer

ses actions. Par exemple, s’il doit replacer un deuxième livre, il va pouvoir tenir compte des

obstacles qu’il avait rencontrer lors du rangement du livre précédent. Cela va influencer le chemin

qu’il va emprunter. L’environnement est dynamique, parce qu’il y a une multitude d’événements

qui peuvent se produire pendant que l’agent délibère. Un nouvel obstacle à éviter, un nouveau livre

à ranger, etc. L’environnement est continu, car il y a plusieurs perceptions possibles et plusieurs

actions possibles.

2) a) (8 pts) Donner un exemple de chacune des quatre architectures d’agent et expliquer

votre choix.

Tout exemple qui correspond bien aux architectures est accepté. Les quatre architectures sont :

agent simple réflexe, agent réflexe avec état interne, agent avec des buts et agent avec utilité.

b) (4 pts) Si on veut un agent qui combinerait « but » et « utilité » qu’elle serait

d’après vous l’architecture d’un tel agent ? Donnez un exemple de ce type d’agent et

justifiez le.

L’architecture, c’est un mélange des deux architectures but et utilité aux pages 44 et 45 du livre.

Elle comprend toutes les composantes de l’architecture du but, auquel ion ajoute une couche sous le

but pour tester l’utilité. De cette manière, un agent peut choisir son but, et choisir la meilleure façon

de l’atteindre avec l’utilité. Ou si l’agent a plusieurs buts, il peut choisir un but avec la fonction

d’utilité. Pour les exemples, tout exemple logique est bon.

3) Supposons que vous voulez implémenter un programme qui joue au tic-tac-toe,

L’utilisateur humain joue toujours O et la machine toujours X. Chaque case sur le

board est appelée aij où i est la ligne et j la colonne.

a) (6 pts) Définir les états, le but (test) et les opérateurs pour ce problème, en

termes de aij. Combien d’états y a t-il ?

État : Configuration du jeu = <a11,a12,…,a33>

But : Trois X en ligne

Opérateur : Mettre un X ou un O sur le jeu

Nombre d’états : On s’est rendu compte que c’est un problème difficile de combinatoire, par

conséquent, tout raisonnement logique sera accepté. Si vous avez trouvé la bonne réponse, vous

allez avoir deux points bonis.

La fonction de combinatoire qui est utilisée est {n m} = n! / (m! x (n – m)!) (le nombre de façon de

choisir m boules noires identiques parmi un mélange de n boule blanches et noires). Il est à noter

que le nombre d’état possible est différent du nombre de nœuds dans l’espace de recherche, parce

qu’il y a beaucoup d’états identiques dans l’espace de recherche. La solution est :

1 O => {9 1} = 9 états

1 O, 1 X => {9 1}x{8 1} = 72

2 O, 1 X => {9 2}x{7 1} = 252

2 O, 2 X => {9 2}x{7 2} = 756

3 O, 2 X => {9 3}x{6 2} = 1260

Jusqu’à maintenant, on ne pouvait pas générer des configurations illégales, mais à partir de

maintenant, c’est possible d’avoir trois X et trois O dans deux lignes ou colonnes et nous devons en

tenir compte.

3 O, 3 X => {9 3}x{6 3} = 1680, le nombre d’état dans lequel l’humain a déjà gagné = 8 x {6 3} =

160

4 O, 3 X => {9 4}x{5 3} = 1260, le nombre d’états où X gagne = 8 x {6 4} = 120

4 O, 4 X => {9 4}x{5 4} = 630, le nombre d’état dans lequel O gagne et non X = 2 x 8 x {6 4} =

240

5 O, 4 X => {9 5}x{4 4} = 126, le nombre d’états où X gagne = 8 x {6 1} = 48

Donc, le nombre d’états possibles est 6046 – 160 – 120 – 240 – 48 = 5478

b) (4 pts) Quelle algorithme de recherche pensez vous utiliser pour

implémenter un tel programme ? Pourquoi ?

Il y a plusieurs réponses ici et nous acceptons toutes les réponses pourvu qu’elles soient justifiées.

c) (3pts) Décrire brièvement une fonction qui évalue la valeur d’un état, tel

que décrit en a), pour le joueur-machine.

Toute fonction raisonnable sera accepté. L’idée c’est que la fonction doit pénalisé les coups

perdants et donner une « récompense » pour les coups gagnants. Par exemple, le nombre de X dans

une même ligne moins le nombre de O dans une même ligne est une fonction possible.

4) Dans l’espace de recherche ci-dessous, le nombre placé à côté de chaque lien dénote le

coût associé au lien entre nœuds, et h est le coût estimé du nœud jusqu’au but final G.

a) (4 pts) Donner alors l’ordre dans lequel les nœuds sont visités lorsqu’on

utilise le A*. Donner alors f(n) pour chacun des nœuds n.

f(B)=3, f(C) =14, f(D)=11, f(E)=6, f(H)=14, f(F) = 11, f(I)=22, f(G)= 12

A, B, E, D, H, C, F, G.

b) (4 pts) Un algorithme « vorace » du type meilleur-d’abord peut-il faire

mieux ? Combien de nœuds, un tel algo traverse-t-il avant d’atteindre le but

G.

Les nœuds visités sont : A, B, E, D, H, C, G. Donc oui, dans cet exemple, l’algorithme meilleur -

d’abord est plus efficace , il visite un nœud de moins.

c) (5 pts) Autant la largeur-d’abord que le A* consomment de la mémoire

(C’est exponentiel !). Comment pouvez vous modifier A* de façon à utiliser

moins d’espace mémoire ? Quelle est alors la complexité en espace du

nouvel algo ?

On peut utiliser l’algorithme IDA* avec le coût comme limite de profondeur. Pour la complexité en

espace, voir le livre à la page 106. Dans le pire des cas, IDA* demande bf*/δ où δ est le plus petit

coût d’un opérateur, b le facteur de branchement et f* le coût de la solution optimale. Dans notre

cas, le facteur de branchement est 2, le coût de la solution optimale est 12 et le coût du plus petit

opérateur est 1, donc l’algorithme demande 24 nœuds. Dans la plupart des cas, on peut estime le

nombre de nœuds visité par bd où d est la profondeur de la solution, ce qui donne 2 x 2 = 4 nœuds.

d) (4 pts) Si H est aussi un but, lequel parmi largeur-d’abord, profondeur-

d’abord et le profondeur-itératif peut trouver la solution optimale ?

Seulement la recherche en profondeur d’abord va trouver la solution optimale H.

e) (5 pts) La fonction heuristique h pose un problème dans la mesure où elle

surestime trop le coût de C à G. Quelle propriété de A* n’est plus remplie si

h a ce problème ?.

A* ne sera plus optimal.

5) (10 pts) Supposons qu’on veut céduler un problème de salles de cours. Dans ce

problème, on a c salles et k cours, chaque cours débute à Sk et finit à Ek, avec Sk et Ek

des entiers naturels. Sachant qu’aucun cours ne doit partager avec un autre la même

salle, que les salles sont seulement disponibles entre 1 :00 et 5 :00, formulez ce

problème comme un CSP (constraint solving problem). Suggérez alors une heuristique

pour résoudre ce problème et expliquer pourquoi pensez-vous que votre heuristique

peut résoudre un tel problème .

Le problème consiste à choisir une classe pour chaque cours.

Variables : C1, …, Ck (les différentes classes pour chacun des cours)

Domaine : {1, …, c}

Contraintes : Pour tout les i,j, si (Ei >= Ej > Si OU Si <= Sj < Ei) alors (Ci != Cj)

Si < Ei, Si > 1 (pour 1 :00), Ei < 5

Vous pouvez utiliser n’importe quelle heuristique vu en classe, comme par exemple l’heuristique

min-conflicts.

6) Pour chacune des assignations suivantes, dites si KB |== a est valide

a) (3 pts) KB = (A ∨ B → C) ∧ A et a = C

A B C (α) A∨B A∨B→C (A∨B→C)∧A

T T T T T T

T T F T F F

T F T T T T

T F F T F F

F T T T T F

F T F T F F

F F T F T F

F F F F T F

Quand KB est vrai, a (C dans ce cas) est toujours vrai, donc KB |== a est valide.

b) (3 pts) KB = (A → B) et a = B

A B A→B

T T T

T F F

F T T

F F T

KB |== a n’est pas valide, parce que a (B dans ce cas) n’est pas toujours vrai quand KB est vrai

(voir ligne 4).

c) (3 pts) KB = (A →B) ∧ (B → C) et a = (A → C)

A B C A→B B→C (A→B) ∧

(B→C)

A→C

T T T T T T T

T T F T F F F

T F T F T F T

T F F F T F F

F T T T T T T

F T F T F F T

F F T T T T T

F F F T T T T

Quand KB est vrai, a (A → C dans ce cas) est toujours vrai, donc KB |== a est valide.

7) Donner l’axiome successeur comme il a été introduit dans le cours pour les actions

suivantes :

a) (3 pts) Cassé(x,Resultat(a,s)) où x est une variable dénotant un verre

a = tomber(x) ∨ [cassé(x,s) ∧ a ≠ réparer(x)]

b) (3 pts) Avoir(lait,Resultat(a,s))

a = acheté(lait) ∨ [avoir(lait,s ) ∧ a ≠ renverser(lait)]

8) Dans l’algorithme de rétropropagation qui est utilisée pour les réseaux de neurones,

l’erreur pour une unité de sortie est donnée par la formule suivante :

)o)(to(1od kkkkk −−← . Pour une unité cachée, l’erreur est donnée par la formule

suivante : ∑∈

−←sortiesk

kkhhhh dw)o(1od .

a) (3 pts) Expliquer pourquoi on n’utilise pas la même formule pour les unités

cachées.

On n’utilise pas la même formule, parce que pour les unités de sortie, on a accès à la valeur désirée

de l’unité directement, ce qui n’est pas le cas pour les unités cachées.

b) (2 pts) Expliquer l’idée derrière l’utilisation de la somme ∑∈sortiesk

kkhdw pour

calculer l’erreur faite par l’unité cachée.

Pour calculer l’erreur faite par l’unité cachée, on regarde sa participation dans l’erreur des unités de

sortie. Donc, pour chaque unité de sortie à laquelle l’unité cachée est connectée, on pondère l’erreur

de l’unité de sortie par le poids du lien. Plus le poids est fort, plus l’unité cachée a participé à

l’erreur de l’unité de sortie. En d’autres mots, l’erreur de l’unité cachée, c’est la somme de ses

participations aux erreurs des unités de sortie auxquelles elle est connectée.

9) (5 pts) Dans les algorithmes génétiques, expliquer les effets du taux du mutation sur la

population. Que se passe-t-il s’il est trop grand ou trop faible ?

Dans les algorithmes génétiques, si le taux de mutation est trop élevée, les individu de la population

vont toujours être modifiés, donc, il n’y aura pas de convergence vers un meilleur individu. La

population va être trop hétérogène.

Si le taux de mutation est trop faible, alors la population va devenir très homogène. Tous les

individus vont être identiques ou très proches. La qualité de la population ne pourra plus

augmenter. On perd la chance qu’une mutation nous donne un individus plus fort.

1

Examen mi-session

Intelligence Artificielle II (IFT-17587)

Jeudi 21 février 2001

De 15h30 à 18h20 en salle PLT-2341

�� Les documents permis sont le livre, les acétates du cours et une double page de notes.

�� Les temps entre parenthèses représentes les temps suggérer pour répondre à chacune des

questions.

�� Le nombre de points accordés à chacune des questions est aussi inscrit entre parenthèses.

------------------------------------------------------------------------

1. (15 pts) (20 min) Pour chacun des exemples d’agents suivants, dites quelle architecture d’agent

est la plus appropriée (simple réflexe, réflexe avec état interne, but et utilité) et pourquoi ?

a. Un agent contrôlant une valve de pression d’une centrale nucléaire.

b. Un agent devant sortir d’un labyrinthe.

c. Un agent conduisant un automobile.

d. Un agent qui achète et vend des actions sur Internet.

e. Un agent qui nettoie la vaisselle et qui la range dans les armoires.

2. (22 pts) (35 min) Un fermier a une chèvre, un loup et une laitue sur la rive ouest d’une rivière.

Il veut amener ses animaux et sa laitue de l’autre côté de la rivière, sur la rive est. Le fermier a

un petit bateau à rame et il n’y a de la place que pour lui et une autre chose. De plus, le loup va

manger la chèvre s’ils sont laissés seuls ensemble et la chèvre va manger la laitue si elle est

laissée seule avec. Comment le fermier peut faire pour transporter tous les éléments sur la rive

est ?

a. Formuler ce problème comme un problème de recherche. C’est-à-dire, donner la

représentation des états, l’état de départ, l’état but et les opérateurs pour passer d’un état

à un autre.

b. Résoudre ce problème de recherche (en utilisant la méthode de votre choix). Dessiner

l’arbre de recherche et donner la solution finale.

2

3. (21 pts) (35 min) Derek est un ingénieur en robotique et il a conçu un robot qui doit se déplacer

entre les édifices sur le campus pour délivrer le courrier. Il a implémenté l’algorithme A* pour

la recherche de chemin (en utilisant la distance en ligne droite comme fonction heuristique),

toutefois l’algorithme ne semble pas fonctionner correctement, car le robot choisit souvent un

chemin qui n’est pas optimal. Voici le pseudo code qu’il utilise (où F est une file, D est le nœud

de départ et h est la fonction heuristique) :

F = {D}

Tant que F n’est pas vide

Prendre F1, le premier élément dans F

Nœuds_enfants = développer(F1)

Éliminer les nœuds dans Nœuds_enfants qui ont déjà été visités

Pour tous les nœuds restant dans Nœuds_enfants, faire

Si l’enfant est un état but

Retourner Succès et Sortir

Fin pour tous

Ajouter les enfants à F

Trier F selon la fonction suivante : f = coûtChemin(D à nœud) + h(nœud)

Fin tant que

a. Cet algorithme ne donne pas toujours la solution optimale, car il contient une erreur.

Identifiez cette erreur et expliquez pourquoi la solution retournée n’est pas toujours

optimale.

b. Corrigez alors l’erreur de Derek et écrivez le bon pseudo code pour A*.

3

4. (15 pts) (30 min) Anna est en charge de l’écriture d’un programme pour contrôler une machine

d’assemblage. La machine est constituée d’un bras robotisé qui doit souder des puces

électroniques sur une carte de circuit imprimé à certain points {A, B, C, D, E, F, G, H} comme

montré sur la figure suivante :

H

C G

F

ED

B

A

Le bras commence dans le coin en haut à gauche et il doit visiter chaque point sur la carte de

circuit imprimé et retourner à son point de départ. Aider Anna à minimiser la distance total que

le bras doit emprunter en modélisant ce problème à l’aide d’algorithmes génétiques. Vous

devez décrire tout ce qui est nécessaire aux algorithmes génétiques (les individus, les opérateurs

génétiques, l’évaluation des individus, etc.) et expliquer le fonctionnement de l’algorithme pour

trouver une bonne solution pour le problème.

5. (15 pts) (30 min) Considérons l’exemple de l’aspirateur illustré sur la figure suivante. Dans cet

environnement, il y a un petit robot aspirateur qui doit nettoyer la maison. Le robot est équipé

de détecteurs qui lui permettent de savoir s’il est par dessus de la saleté et d’un aspirateur qui

lui permet d’aspirer la saleté. De plus, le robot a toujours une orientation bien définie (nord,

sud, est ou ouest). En plus de pouvoir aspirer la saleté, le robot est capable d’avancer d’un pas

ou de tourner à droite de 90°. L’agent se déplace dans une pièce divisée en case de grandeurs

identiques. Le robot ne fait rien d’autre que nettoyer et donc il ne quitte jamais la pièce. Pour

simplifier le problème, les dimensions de la pièce sont de 3x3 et le robot commence toujours

dans la case (0,0) en regardant vers le nord.

En résumé, l’agent peut recevoir la perception saleté (signifiant qu’il y a de la saleté en dessous

de lui), ou rien (indiquant aucune information spéciale). Il peut exécuter une des trois actions

suivantes : avancer, aspirer, tourner. Le but de l’agent est de traverser toute la pièce en

cherchant et en ramassant la saleté.

4

Le comportement de l’agent est géré par un ensemble de règles. Les trois prédicats simples

suivants sont utilisés :

Pos(x,y) l’agent est à la position (x,y)

Saleté(x,y) il y a de la saleté à la position (x,y)

Orientation(d) l’agent regarde dans la direction d

Le robot se promène toujours dans l’environnement en passant de (0,0) à (0,1) à (0,2) à (1,2), à

(1,1) et ainsi de suite. Lorsque l’agent a atteint la case (2,2), il doit revenir à la case (0,0). Les

règles pour permettre au robot de se déplacer sur la première ligne droite sont très simples :

Pos(0,0) � Orientation(Nord) � �Saleté(0,0) � Faire(avancer)

Pos(0,1) � Orientation (Nord) � �Saleté (0,1) � Faire(avancer)

Pos(0,2) � Orientation (Nord) � �Saleté (0,2) � Faire(tourner)

Pos(0,2) � Orientation (Est) � Faire(avancer)

Complétez la base de règles pour que l’agent puisse se rendre à la case (2,2) et ensuite revenir à

la case (0,0) en nettoyant la salle.

(0,0)

(0,1)

(0,2) (1,2)

(1,1)

(1,0) (2,0)

(2,1)

(2,2)saleté saleté

Nord

Est

Sud

Ouest

5

6. (12 pts) (20 min) Effectuez un tour de l’algorithme de rétropropagation des erreurs et indiquez

la valeur des nouveaux poids. Vous devez présenter tous les calculs. La valeur de la constante

d’apprentissage est � = 0,05. La fonction d’activation est la fonction suivante :

��

��

�

�

��

��

sinon 1

0xw si 1 f

n

0iii

x1 x2

x3

x4

Entrée

3

Sorties

1

1

W21 = 0,3

W32 = 0,1

W42 = 0,6

x5

x6

x7

W25 = -1,1

W36 = -0,5

W42 = -0,9

11

1

6

Annexe : Algorithme de rétropropagation des erreurs

Pour chaque exemple d'entraînement

�� Calculer les sorties du réseau

�� Pour toutes les unités de sortie k, calculer l'erreur �k de la façon suivante:

)o)(to(1oδ kkkkk ��

�� Pour toutes les unités cachées h, calculer l'erreur �h de la façon suivante:

��

��

sortieskkkhhhh δw)o(1oδ

�� Mettre à jour tous les poids wji de la façon suivante:

jijiji www ��

ou

jijji xw ��

Xji : l'entrée qui provient de l'unité i vers l'unité j.

Wji : le poids du lien entre l’unité i et j.

Tk : la sortie attendue du réseau.

Ok : la sortie obtenue du réseau.

Corrigé de l’examen de mi-session Intelligence artificielle II (IFT-17587)

1. a. Simple-réflexe : l’agent ne fait qu’obéir à des règles simples. Par exemple, si la

pression dépasse une certaine valeur, ouvrir la valve.

b. But : L’agent a le but de sortir du labyrinthe.

c. Utilité : Il y a plusieurs alternatives et de l’incertain.

d. Utilité : Il y a des décisions à prendre entre la sécurité et le rendement et il y de

l’incertain.

e. Réflexe : Un agent réflexe est suffisant pour cette tâche, mais j’accepte aussi réflexe

avec état interne si on tient compte que l’agent doit se souvenir si les armoires sont

pleines.

2. a. Il y a plusieurs manières possibles de formuler un problème de recherche. Mais

voici une des réponses possibles :

Représentation des états : Les états peuvent être représentés par deux ensembles O et

E contenant les éléments sur la rive ouest et est respectivement. Pour les éléments, on

peut utiliser les symboles fermier, chèvre, loup et laitue.

Opérateurs : Déplacer fermier de l’ensemble E à l’ensemble O et vice versa. Déplacer

fermier et un des éléments chèvre, loup ou laitue de l’ensemble E à l’ensemble O et

vice versa.

État de départ : O = { fermier, chèvre, loup, laitue }, E = {}

État but : O = {}, E = { fermier, chèvre, loup, laitue }

b. Voici un arbre de recherche possible.

W = {fermier, chèvre, loup, laitue}, E = {}

W = {chèvre, laitue}, E = {fermier, loup}

W = {loup, laitue}, E = {fermier, chèvre}

W = {chèvre, loup}, E = {fermier, laitue}

W = {fermier, loup, laitue}, E = {chèvre}

W = {chèvre, loup, laitue}, E = {fermier}Illégal

Illégal

W = {fermier, chèvre, loup, laitue}, E = {}

Répétition

W = {laitue}, E = {fermier, loup, chèvre} W = {loup, laitue}, E = {fermier, chèvre}

W = {loup}, E = {fermier, chèvre, laitue}Répétition

W = {fermier, laitue}, E = {loup, chèvre}

Illégal

W = {fermier, loup, laitue}, E = {chèvre}

W = {fermier, chèvre, laitue}, E = {loup}

Répétition

W = {chèvre, laitue}, E = {fermier, loup}

W = {chèvre}, E = {fermier, loup, laitue}

W = {laitue}, E = {fermier, loup, chèvre}Répétition

Illégal

W = {fermier, chèvre}, E = {loup , laitue}

W = {fermier, loup, chèvre}, E = {laitue}

W = {fermier, chèvre, laitue}, E = {loup}

Répétition

W = {}, E = {fermier, chèvre, loup, laitue}

But

3. a. Le code devrait vérifier si F1 est un but dès qu’il est sortie de la liste. Le code ne

devrait pas vérifier si les enfants sont des buts. Ceci fait en sorte de contourner la liste

qui est triée en fonction de la fonction de coût. De cette manière, un fils qui est une

solution coûteuse peut être choisie avant une meilleure solution qu’on aurait trouver si

on avait utilisé la liste.

b. Le bon pseudo-code est le suivant :

F = {D}

Tant que F n’est pas vide

Prendre F1, le premier élément dans F

Si F1 est un but

Retourner Succès et Sortir

Nœuds_enfants = développer(F1)

Éliminer les nœuds dans Nœuds_enfants qui ont déjà été visités

Ajouter les enfants à F

Trier F selon la fonction suivante : f = coûtChemin(D à nœud) + h(nœud)

Fin tant que

4. Gêne : Points à visiter

Individu : Liste de points (chaque individu est un parcours possible)

Population : Un ensemble de parcours

Opérateur de reproduction :

�� On choisit aléatoirement deux points de coupe. �� On intervertit, entre les deux individus, les parties qui se trouvent entre ces

deux points. �� On supprime, à l’extérieur des points de coupes, les gênes qui sont déjà

placées entre les points de coupe. �� On recense les gênes qui n’apparaissent pas dans chacun des deux

parcours. �� On remplit aléatoirement les trous dans chaque parcours.

Opérateur de mutation : On choisit aléatoirement deux gênes dans l’individus et on

les intervertit.

Évaluation des individus : Plus le chemin est court, plus l’individu est fort. Donc, on

peut prendre l’inverse de la distance comme fonction d’utilité.

Pour le fonctionnement, il suffit d’expliquer le fonctionnement des algorithmes

génétiques.

5. Voici les règles à ajouter. Pour qu’il n’y ait pas de conflit entre les règles, il fallait

ajouter un nouveau prédicat RetournerDebut qui indique si l’agent a atteint la case (2,2)

ou non. Lorsque l’agent atteint la case (2,2), RetournerDebut est mis à vrai.

Pos(x,y) � Saleté(x,y) � Faire(aspirer)



Pos(0,2) � Orientation(Nord) � �Saleté(0,2) � Faire(tourner)

Pos(0,2) � Orientation(Est) � Faire(avancer)

Pos(1,2) � Orientation(Est) � �Saleté(1,2) � Faire(tourner)

Pos(1,2) � Orientation(Sud) � Faire(avancer)

Pos(1,1) � Orientation(Sud) � �Saleté(1,1) � Faire(avancer)

Pos(1,0) � Orientation(Sud) � �Saleté(1,0) � Faire(tourner)

Pos(1,0) � Orientation(Ouest) � �RetournerDebut � Faire(tourner)

Pos(1,0) � Orientation(Nord) � Faire(tourner)

Pos(1,0) � Orientation(Est) � Faire(avancer)

Pos(2,0) � Orientation(Est) � �Saleté(2,0) � Faire(tourner)

Pos(2,0) � Orientation(Sud) � �RetournerDebut � Faire(tourner)

Pos(2,0) � Orientation(Ouest) � �RetournerDebut � Faire(tourner)

Pos(2,0) � Orientation(Nord) � Faire(avancer)


Pos(2,2) � Orientation(Nord) � �Saleté(2,2) � Faire(tourner)

Pos(2,2) � Orientation(Est) � Faire(tourner)



Pos(2,0) � Orientation(Sud) � RetournerDebut � Faire(tourner)

Pos(2,0) � Orientation(Ouest) � RetournerDebut � Faire(avancer)

Pos(1,0) � Orientation(Ouest) � RetournerDebut � Faire(avancer)

6. Voici les calculs

y2 = (3*0,3) + (1 * -1,1) = -0,2 o2 = -1

y3 = (0,1*-1) + (1 * -0,5) = -0,6 o3 = -1

y4 = (0,6*-1) + (1 * -0,9) = -1,5 o4 = -1

�3 = -1(1 + 1)(1 + 1) = -4

�4 = -1(1 + 1)(1 + 1) = -4

�2 = -1(1 + 1)((0,1 * -4) + (0,6 * -4)) = 5,6

�w21 = 0,05 * 5,6 * 3 = 0,84

�w25 = 0,05 * 5,6 * 1 = 0,28

�w32 = 0,05 * -4 * -1 = 0,2

�w36 = 0,05 * -4 * 1 = -0,2

�w42 = 0,05 * -4 * -1 = 0,2

�w47 = 0,05 * -4 * 1 = -0,2

w21 = 0,3 + 0,84 = 1,14

w25 = -1,1 + 0,28 = -0,82

w32 = 0,1 + 0,2 = 0,3

w36 = -0,5 + -0,2 = -0,7

w42 = 0,6 + 0,2 = 0,8

w47 = -0,9 + -0,2 = -1,1

Solution Examen mi-session Intelligence Artificielle II (IFT-17587)

Mercredi 26 février 2003

De 12h30 à 15h20 en salles PLT-2765 (A à Marchand) et PLT-2546 (Moisan à Z)

• Tout document est permis.

• Le nombre de points accordés à chacune des questions est inscrit entre parenthèses.

• Le questionnaire a 12 questions sur 4 pages.

------------------------------------------------------------------------

1 (3 pts) Est-ce qu’un système doit penser comme un humain pour passer le test de

Turing? Expliquez.

Non, il n’a seulement qu’à agir comme un humain.

2 (5 pts) Est-ce qu’un agent qui a une perception partielle de l’environnement peut être

parfaitement rationnel ? Expliquez.

Oui, la rationalité et l’omniscience sont des concepts différents. Un agent n’a pas besoin de tout

percevoir pour pouvoir agir rationnellement. Il doit percevoir tout ce qu’il peut et agir par la suite

au meilleur de ses connaissances.

3 (5 pts) Est-ce que l’affirmation suivante est vraie : un agent rationnel est meilleur que

tous les agents non rationnels parce qu’il sait le résultat réel de ses actions ?

Expliquez.

Non, dans un environnement inaccessible et/ou stochastique, un agent rationnel ne peut pas savoir

les résultats réels de ses actions. Dans ce type d’environnement, s’il n’est pas chanceux, il pourrait

être moins bon qu’un agent non rationnel.

1

4 (10 pts) Donnez la PEAS et les propriétés de l’environnement pour un robot d’inspection

sur Mars. Le robot doit trouver des échantillons intéressants, les analyser et

transmettre ses analyses sur Terre.

Mesure de performance : Nombre d’échantillons différents analysés, la qualité des échantillons,

minimiser le temps de déplacement, la surface parcourue, etc.

Environnement : Sable, roches, autres robots, vent, poussière, etc. En fait, tout l’environnement de

la planète Mars.

Effecteurs : Moteurs, pince, outils pour l’inspection, émetteur radio, etc.

Capteurs : Cameras, récepteur radio, outils d’analyse d’échantillon, etc.

Propriétés de l’environnement : Partiellement observable, stochastique, séquentiel, dynamique,

continu et multiagent (si on considère qu’il y a plusieurs robots), j’accepte aussi simple agent si on

considère que l’agent est seul sur Mars.

5 (12 pts) Dans l’espace de recherche suivant, l’état S est l’état de départ et les états G1 et

G2 sont des états qui satisfont le test de but. Le nombre au dessus d’un arc

représente le coût pour le parcourir. La valeur de la fonction heuristique h est

inscrite dans le cercle. Pour chacune des méthodes de recherche suivantes :

indiquez quel but est atteint et donnez la liste, dans l’ordre, de tous les états qui

ont été choisis pour être explorés.

a) Coût uniforme

S, A, B, C, C, D, D, D, G2

b) Profondeur itératif

S, S, A, C, S, A, B, E, C, D, G2

c) Meilleur d’abord avare

S, A, B, G1

d) A*

S, A, B, D, G2

2

S5

A2

B1

C3

D1

E6

G10

G20

2

1

4

32

4

1

1

1

5

1

7

5

9

8

6 (9 pts) Est-ce que les heuristiques suivantes sont admissibles ? Expliquez pourquoi.

a) L’heuristique de la question précédente.

Non, l’évaluation en C surestime le coût pour se rendre au but. H(C) = 3, alors que le coût pour se

rendre en G2 est de 2.

b) La distance de Manhattan (livre p.106) pour un problème qui consiste à

minimiser le nombre de déplacements pour déplacer une pièce sur un

échiquier d’une case A à une case B. Dans ce jeu, une pièce peut bouger en

ligne droite (horizontalement ou verticalement) de n’importe quel nombre de

cases, mais elle ne peut pas sauter par dessus une autre pièce.

Non, la distance de Manhattan surestime le coût, une pièce peut traverser l’échiquier en un seul

coup.

c) h(n) = 0 pour le jeu du 8-puzzle.

Oui, 0 sous-estime toujours le vrai coût pour se rendre au but.

3

7 (3 pts) Est-ce que Hill-climbing est un algorithme complet pour résoudre un problème de

résolution de contraintes?

Non, il peut rester coincé sur des maxima locaux et ne pas trouver une solution.

8 (15 pts) Dans le graphe de contraintes suivant, les contraintes sont identifiées sur les liens

et le domaine de chacune des variables est indiqué entre accolades.

a) Montrez toutes les étapes de l’algorithme de cohérence des arcs sur ce

problème. Vous devez identifier tous les arcs qui sont vérifiés et montrer les

changements aux domaines de valeur des variables à chaque étape.

Domaine A Domaine B Domaine C Arcs à vérifier

{1,2,3} {1,2,3} {1,2,3} A-B, A-C, B-A, B-C, C-A, C-B

{1,2} A-C, B-A, B-C, C-A, C-B

{2,3} B-A, B-C, C-A, C-B

B-C, C-A, C-B, A-B

{2,3} C-A, C-B, A-B

C-B, A-B, A-C

A-B, A-C

A-C

Les domaines de valeurs à la fin de l’algorithme sont donc: DA = {1,2}, DB = {2,3} et DC = {2,3}.

4

b) Trouvez une solution à ce problème en utilisant l’algorithme de recherche

en avant (forward checking). Utilisez l’heuristique MRV (livre p. 143) pour

choisir les variables. S’il y a des égalités entre les variables, choisissez-les

dans l’ordre alphabétique inverse. Les valeurs sont essayées en ordre

croissant.

A B C

{1,2,3} {1,2,3} {1,2,3}

{} {2,3} 1

Erreur, on fait un retour arrière et on essaie une autre valeur.

{1} {1,3} 2

1 {3} 2

1 3 2

La solution trouvée est donc : A = 1, B = 3, C = 2.

c) Trouvez une solution à ce problème en utilisant l’algorithme min-conflict.

Commencez avec la configuration initiale : A = 2, B = 3 et C = 3. S’il y a des

égalités entre les variables, choisissez-les dans l’ordre alphabétique inverse.

Les valeurs sont essayées en ordre croissant.

A B C

2 3 3 Les variables B et C sont en conflits. Il faut donc changer une des valeurs de ces

variables. Il y a quatre possibilité : B = 2 (1 conflit), B = 1 (1 conflit), C = 2 (1

conflit), C = 1 (1 conflit). Les quatre sont égales, donc on en prend C = 1, parce

que c’est l’ordre définit pour la question en cas d’égalité.

2 3 1 Les variables A et C sont en conflits. Il faut donc changer une des valeurs de ces

variables. Il y a quatre possibilité : A = 1 (1 conflit), A = 3 (2 conflits), C = 2 (1

conflit), C = 3 (1 conflit). Il y a trois possibilité égales, donc on prend C = 2.

2 3 2 Les variables A et C sont en conflits. Il faut donc changer une des valeurs de ces

variables. Il y a quatre possibilité : A = 1 (0 conflit), A = 3 (2 conflits), C = 1 (1

conflit), C = 3 (1 conflit). Donc on choisit A = 1.

1 3 2 Aucun conflit. C’est la solution qui est trouvée.

5

A

B C

A < CA < B

B ≠ C

{1,2,3}

{1,2,3}{1,2,3}

9 (11 pts) Supposons que nous avons les propositions suivantes : PileMorte,

RadioFonctionne, PasDeGaz et AutoDémarre.

a) Quel est le nombre total de modèles possibles ?

Il y a 4 variables binaires, donc 24 = 16 modèles possibles.

6

b) Dans combien de modèles, la phrase suivante est-elle fausse ?

(RadioFonctionne ∧ AutoDémarre) ⇒ (¬PasDeGaz ∧ ¬PileMorte)

PileMorte RadioFonctionne PasDeGaz AutoDémarre Valeur de la phrase

V V V V F

V V V F V

V V F V F

V V F F V

V F V V V

V F V F V

V F F V V

V F F F V

F V V V F

F V V F V

F V F V V

F V F F V

F F V V V

F F V F V

F F F V V

F F F F V

La phrase est donc fausse dans trois modèles.

7

c) Supposons que nous avons une base de connaissances qui ne contient que la

phrase en b). Est-ce que l’on peut inférer la phrase suivante à partir de cette

base de connaissances : RadioFonctionne ⇒ ¬PileMorte ? Prouvez-le à l’aide

des modèles.

PileMorte RadioFonctionne PasDeGaz AutoDémarre Valeur de la

phrase en b)

Valeur de la

phrase en c)

V V V V F F

V V V F V F

V V F V F F

V V F F V F

V F V V V V

V F V F V V

V F F V V V

V F F F V V

F V V V F V

F V V F V V

F V F V V V

F V F F V V

F F V V V V

F F V F V V

F F F V V V

F F F F V V

Il existe des modèles où b) est vraie et où c) est fausse, donc M(b)) ⊄ M(c)), par conséquent on ne

peut pas inférer la phrase en c) à partir de la phrase en b).

8

10 (6 pts) Donnez l’unificateur le plus général, si possible, unifiant chacune des pairs de

phrases suivantes. Les variables des deux phrases ne sont pas indépendantes, donc s’il y a une

variable qui est utilisée dans les deux phrases, elle ne peut pas être renommée différemment

dans une des phrases.

a) R(F(y), y, x) et R(x, F(A), F(v))

{x/ F(F(A)), y/ F(A), v/F(A)}, ce qui donne : R(F(F(A)), F(A), F(F(A)))

b) B(1, x, 2) et B(y, F(y), 2)

{y/1, x/F(1)}, ce qui donne : B(1, F(1), 2)

c) C(G(x, y), x) et C(z, F(y))

{x/F(y), z/G(F(y),y)}, ce qui donne : C(G(F(y),y), F(y))

11 (15 pts) En supposant la base de connaissances suivante, prouver à l’aide de l’algorithme

de résolution que C(3) est vrai.

A(x, y) ∧ B(y) ⇒ C(x)

D(x) ⇒ B(x)

E(y) ⇒ A(y, x)

D(7)

E(3)

On doit d’abord mettre les phrases sous forme CNF, ce qui donne :

¬A(x, y) ∨ ¬B(y) ∨ C(x)

¬D(x) ∨ B(x)

¬E(y) ∨ A(y, x)

D(7)

E(3)

9

Maintenant, on peut appliquer l’algorithme de résolution :

Phrase utilisée Preuve

¬A(x, y) ∨ ¬B(y) ∨ C(x) ¬C(3)

¬E(z) ∨ A(z, x) ¬A(3, y) ∨ ¬B(y)

E(3) ¬E(3) ∨ ¬B(y)

¬D(x) ∨ B(x) ¬B(y)

D(7) ¬D(y)

{}

On arrive à un ensemble vide, donc on a prouvé que C(3) est vrai.

12 (6 pts) Donnez l’axiome successeur comme il a été introduit dans le cours pour les actions

suivantes :

a) Vide(Verre, Result(a, s))

Poss(a, s) ⇒

(Vide(Verre, Result(a, s)) ⇔ ¬Vide(Verre, s) ∧ a = Vider(Verre)

∨ (Vide(Verre, s) ∧ a ≠ Remplir(Verre)))

b) Position(Verre, Table, Result(a, s))

Poss(a,s) ⇒

(Position(Verre, Table, Result(a, s)) ⇔ Position(Verre,x,s) ∧ a = Déplacer(Verre, x, Table)

∨ (Position(Verre, Table, s) ∧

a ≠ Déplacer(Verre, Table, y)))

10

1

Solution Examen mi-session Intelligence Artificielle II (IFT-17587)

Dimanche 21 mars 2004

De 8h30 à 11h20 en salles PLT-2341




------------------------------------------------------------------------

1 (12 pts) Donnez la PEAS et les propriétés de l’environnement pour un agent responsable des

lumières à une intersection. Quelle architecture d’agent utiliseriez-vous pour ce type

d’agents et pourquoi?

• Mesure de performance : Le temps d’attente moyen des autos et des piétons.

• Environnement : Les autos, les lumières, les routes, les piétons.

• Effecteur : Les lumières pour les autos et pour les piétons.

• Capteur : Pesé sur la route et bouton pour les piétons.

Propriétés de l’environnement : Partiellement observable, stochastique, séquentiel, dynamique,

continu, mono agents.

Architecture : Agent basé sur l’utilité. La fonction d’utilité doit tenir compte du temps moyen

d’attente des autos et des piétons.

2 (4 pts) Quel est l’état initial, le test de but, la fonction successeur et la fonction de coût pour

un problème qui consiste à colorier une carte en utilisant seulement quatre couleurs de

manière à ce qu’aucunes régions adjacentes n’est la même couleur?

État initial : Carte vide

But : Carte où toutes les régions sont coloriées.

Fonction successeur : Colorier une région vide.

Fonction coût : 1 par assignation de couleur à une région.

2

3 (10 pts) Dans l’espace de recherche suivant, l’état S est l’état de départ et les états G1 et G2

sont des états qui satisfont le test de but. Le nombre au dessus d’un arc représente le

coût pour le parcourir. La valeur de la fonction heuristique h est inscrite dans le cercle.

Pour chacune des méthodes de recherche suivantes : indiquez quel but est atteint et

donnez la liste, dans l’ordre, de tous les états qui ont été choisis pour être explorés. S’il

y a égalité, choisissez les nœuds en ordre alphabétique.

a) Profondeur itérative (profondeur d’abord)

S-S-C-D-S-C-A-H-D-B-F-S-C-A-E-G2

b) A*

S-D-B-A-G2

c) Recherche bidirectionnelle pour le but G2. Les deux algorithmes doivent être des

algorithmes de recherche à coût uniforme. Pour l’algorithme partant du but, considérez

les flèches à l’envers. Vous devez identifier clairement les nœuds développés par les

deux algorithmes.

2 recherches : S-D-B et G2-A-B, donc le chemin final est S-D-B-A-G2

S5

D2

B1

C3

A1

G10

E9

G20

2

1

4

3

2

41

1

3

5

1

7

59

5

F2

3

2

H3

4

3

4 (15 pts) En considérant les instances suivantes, à l’aide de la technique des k-voisins les plus

proches avec distance pondérée, quelle serait la valeur pour la fonction visée de la

nouvelle instance : {2,4,6,1,3}. La fonction visée est une fonction continue. Montrez

tous les calculs.

Instances A1 A2 A3 A4 A5 Fonction visée

X1 3 5 4 6 1 1,5

X2 4 6 10 3 2 2

X3 8 3 4 2 6 3,2

X4 2 1 4 3 6 1,8

X5 2 5 1 4 8 2,1

Dist(X, X1)2 = 35, Dist(X, X2)2 = 29, Dist(X, X3)2 = 51, Dist(X, X4)2 = 26, Dist(X, X5)2 = 60

F(X) = (1/35 * 1.5 + 1/29 * 2 + 1/51 * 3.2 + 1/26 * 1.8 + 1/60 * 2.1) / (1/35 + 1/29 + 1/51 + 1/26 +

1/60)

F(X) = 0.2788 / 0.1378 = 2.02

4

5 (15 pts) En considérant les exemples d’apprentissage suivant, quel serait la racine de l’arbre de

décision construit à partir de ces données? Montrer tous les calculs.

Exemples A B C Classification

1 S W Z Non

2 S X Z Oui

3 V W Z Oui

4 S W Y Non

5 T W Z Oui

6 V X Z Oui

7 S W Z Non

8 V W Y Non

9 T X Y Oui

10 S W Y Non

11 S X Z Oui

12 V X Z Oui

13 S X Y Oui

14 V W Z Oui

Dans la réponse, tous les log sont des log en base 2.

Entropie : (-9/14) log(9/14) + (-5/14) log(5/14) = 0.94

Pour l’attribut A :

Entropie S : (-3/7)log(3/7) + (-4/7)log(4/7) = 0.985

Entropie T : (-2/2)log(2/2) + (-0/2)log(0/2) = 0

Entropie V : (-4/5)log(4/5) + (-1/5)log(1/5) = 0.722

Gain : 0.94 – ((7/14) * 0.985 + 0 + (5/14) * 0.722) = 0.1896

Pour l’attribut B :

Entropie W : (-3/8)log(3/8) + (-5/8)log(5/8) = 0.954

Entropie X : (-6/6)log(6/6) + 0 = 0

Gain : 0.94 – ((8/14) * 0.954 + 0) = 0.395

5

Pour l’attribut C :

Entropie Z : (-7/9)log(7/9) + (-2/9)log(2/9) = 0.764

Entropie Y : (-2/5)log(2/5) + (-3/5)log(3/5) = 0.971

Gain : 0.94 – ((9/14) * 0.764 + (5/14)*0.971) = 0.102

Donc, on choisit l’attribut B comme racine de l’arbre de décision.

6 (15 pts) En utilisant les mêmes exemples que la question précédente, utilisez l’algorithme de

recherche de la meilleure hypothèse courante, vu au chapitre 19. Vous devez montrer

les trois premières étapes de l’algorithme, c’est-à-dire les hypothèses générer à partir

des trois premiers exemples. Vous devez montrer clairement tout le raisonnement en

spécifiant et justifiant les étapes de spécialisation ou de généralisation.

H1 : ∀x Classification(x) ⇔ False

On généralise parce que l’exemple 2 est un faux négatif.

H2 : ∀x Classification(x) ⇔ B(x, X)

On spécialise parce que l’exemple 3 est un faux positif

H3 : ∀x Classification(x) ⇔ B(x, X) ∨ A(x, V)

7 (14 pts) Dans le graphe de contraintes suivant, les contraintes sont identifiées sur les liens et le

domaine de chacune des variables est indiqué entre accolades.

a) Montrez toutes les étapes de l’algorithme de cohérence des arcs sur ce problème.

Vous devez identifier tous les arcs qui sont vérifiés et montrer les changements

aux domaines de valeur des variables à chaque étape.

A B C D Arcs à visiter

{1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} A-B, B-A, A-C, C-A, C-D, D-C, B-D, D-B

{2,3,4,5} B-A, A-C, C-A, C-D, D-C, B-D, D-B

{1,2,3,4} A-C, C-A, C-D, D-C, B-D, D-B, A-B

{2,3,4} C-A, C-D, D-C, B-D, D-B, A-B, B-A

{3,4,5} C-D, D-C, B-D, D-B, A-B, B-A, A-C

6

D-C, B-D, D-B, A-B, B-A, A-C

{1,2,3,4} B-D, D-B, A-B, B-A, A-C, C-D

{1,2,3} D-B, A-B, B-A, A-C, C-D

{2,3,4} A-B, B-A, A-C, C-D, B-D

B-A, A-C, C-D, B-D

A-C, C-D, B-D

C-D, B-D

B-D

Donc, les domaines finaux sont: A({2,3,4}), B({1,2,3}), C({3,4,5}), D({2,3,4})

b) Trouvez une solution à ce problème en utilisant l’algorithme de recherche en

avant (forward checking). Utilisez l’heuristique MRV (livre p. 143) pour choisir

les variables. S’il y a des égalités entre les variables, choisissez-les dans l’ordre

alphabétique. Les valeurs sont essayées en ordre croissant.

A B C D

{1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5}

1 {} {2,3,4,5} {1,2,3,4,5}

Échec

2 {1} {3,4,5} {1,2,3,4,5}

2 1 {3,4,5} {2,3,4,5}

2 1 3 {2}

2 1 3 2

La solution est d’assigner 2 à A, 1 à B, 3 à C et 2 à D.

A

C D

A > B

A < C

C > D

{1,2,3,4,5}B{1,2,3,4,5}

{1,2,3,4,5} {1,2,3,4,5}

B < D

7

8 (15 pts) En considérant la table des Q-valeurs suivantes pour un agent utilisant l’algorithme du

Q-learning pour atteindre le but. Supposons que l’agent choisi toujours la meilleure

action à chaque tour, donnez le chemin parcouru par l’agent pour se rendre au but (3,2)

en partant de l’état de départ (1,1). Par ailleurs, effectuez toutes les mises à jour aux Q-

valeurs occasionnées par cette nouvelle expérience. Le renforcement est de 0 partout,

sauf pour l’état but où il est de 100. γ = 0.8

1001009081

60604545100

5555

But0

5054

65 737360

Q(s,a)

A1

1

2

2 3

L’agent va et (1,2). Le poids de 55 entre la case (1,1) et (1,2) est mis à jour de la manière suivante :

NouvelleValeur = 0 + 0.8 * max{65,73,54} = 58.4

Par la suite, l’agent va en (1,3). Le poids de 73 entre les cases (1,2) et (1,3) est mis à jour de la

manière suivante :

NouvelleValeur = 0 + 0.8 * max{60,100} = 80

Par la suite, l’agent va en (2,3). Le poids de 100 entre les cases (1,3) et (2,3) est mis à jour de la

manière suivante :

NouvelleValeur = 100 + 0.8 * max{0} = 100

Département d’informatique Université Laval

Examen final IA2 de 8h45 à 11h45, salle 3775 PLT 1. Soit à exprimer le problème suivant dans le système STRIPS Avant de sortir de chez lui, un robot nommé Toto doit mettre ses chaussures, son pantalon, son caleçon, sa camisole et son gilet.

١. Donner la représentation des actions ; ٢. Donner un plan POP ٣. Donner une linéarisation d’un tel plan ٤. D’après vous combien y a t-il de linéarisations possibles

2. Le monde de Shakey (voir figure à la fin du texte) Le robot Shakey peut se déplacer, pousser les objets amovibles tels que les boites, grimper sur et descendre des boîtes, allumer et éteindre les lumières. Il possède les actions suivantes :

�� L’action Aller(y). La précondition Esta(x) établit la position courante, et pour que Shakey puisse aller de x à y, il faut que x et y soient dans la même pièce. Pour permettre à Shakey de changer de pièce, nous adopterons la convention de dire qu’une porte « Est dans » les deux pièces qu’elle relie.

�� Pousser un objet d’un endroit à un autre (si l’objet est repoussable…).

�� Grimper/descendre d’un objet, si Shakey est au même endroit que le dit objet, et que de plus Shakey est

sur le sol/sur l’objet.

�� Allumer ou éteindre une lumière, si Shakey est dans une pièce ou se trouve un interrupteur, et que de plus il se trouve sur une boite suffisamment près de l’interrupteur (Shakey est trop petit pour atteindre l’objet sinon).

Choisissez une description de type STRIPS du monde de Shakey et construisez un plan d’action permettant à Shakey de déplacer le bloc 2 dans la pièce 2. 3. Consultant IA Vous êtes un consultant IA pour une compagnie de cartes de crédit et on vous demande de construire un réseau de croyances qui permettrait à la compagnie de déterminer si oui ou non on peut donner une carte de crédit à un client.

�� Quelles sont alors les variables d’évidence ? ce sont en fait les variables pour lesquelles vous pouvez obtenir de l’information, sur la base desquelles il est légal de prendre des décisions et qui sont utiles (relevant) à la prise de décision. Ainsi, par exemple, « Age » pourrait être une de ces variables, mais sûrement pas l’ « appartenance politique ». Il y a une douzaine possible de telles variables, donnez un minimum de 5.

�� Quelle est la variable de sortie (i.e., la variable sur laquelle va s’appuyer la compagnie pour examiner

la probabilité d’accepter ou non la carte de crédit) ? Exclure le cas de la variable « Décision » avec oui ou non puisque la compagnie a le plein contrôle sur cette variable.

�� Construire alors votre réseau de croyances de manière incrémentale (comme montré en cours et dans le

livre) en ajoutant les variables dans l’ordre causal. Vous pouvez en cours de route ajouter des nœuds comme « FiablitéDuDemandeur » ou « FuturGains ». Ecrire des commentaires pour expliquer votre construction et donc votre raisonnement.

4. Centrale nucléaire Dans votre centrale nucléaire, il y a une alarme qui se déclenche quand la jauge température atteint un seuil donné. La jauge mesure la température du cœur de la centrale. Si on considère les variables Booléennes suivantes : A (Alarme sonne), FA (Alarme est en défaut), FG (Jauge est en défaut), G (une variable multi-valuée indiquant que la jauge est en train de lire les données) et T (température actuelle du cœur).

�� Dessinez un réseau de croyances pour ce domaine, étant donné que la jauge a plus de chance de tomber en panne quand la température du cœur devient trop haute.

�� Supposons qu’il y a juste 2 possibles mesures de températures. Normal et Haut ; et que la jauge donne

une température incorrecte x% du temps quand elle fonctionne, mais y% du temps quand elle en défaut. Donner alors les probabilités conditionnelles associées à G.

�� Supposons maintenant que l’alarme a une efficacité de 100% a moins qu’elle soit en défaut. Donner

alors les probabilités conditionnelles associées à A. 5. Apprentissage. Pour faire des diagnostiques A, B ou C, des medecins se basent sur une analyse morphologique des cellules bactériennes prélevées dans le sang de leurs patients. Après avoir observé les douzes échantillons suivants : No Maladie Nb Noyaux Nb Flagelles Coloration Paroi 1 A 1 1 pâle fine 2 A 2 1 pâle fine 3 A 1 1 pâle épaisse 4 A 1 1 foncée fine 5 A 1 1 foncée épaisse 6 B 2 2 pâle fine 7 B 2 2 foncée fine 8 B 2 2 foncée épaisse 9 C 2 1 foncée fine 10 C 2 1 foncée épaisse 11 C 1 2 pâle fine 12 C 1 2 pâle épaisse Ils aimerait construire l’arbre de décision le plus simple possible pour classer leurs instances. Montrez comment cet arbre peut être construit en applicant l’algorithme ID3. Donnez uniquement les 2 premiers nœuds de cet arbre en indiquant tous vos calculs. 6. Réseau XOR Construire à la main un réseau de neurones qui compute la fonction XOR avec 2 entrées. Expliquer pourquoi un perceptron ne peut représenter un XOR.

Ls4 Room 4 Door 4 Ls3 Door 3 Shakey Room 3

Corridor Ls2

Room 2 Door 2 Ls1 Room 1 Door 1

Box3

Box4

Box2

Box1

Solutionnaire examen final 2001

Réponse 1

1.

�� Op(Action : MettreSouliers, Précond : Mis(Pantalon), Effect : Mis(Souliers))

�� Op(Action : MettrePantalon, Précond : Mis(Caleçon), Effect : Mis(Pantalon))

�� Op(Action : MettreCaleçon, Précond : , Effect : Mis(Caleçon))

�� Op(Action : MettreCamisole, Précond :, Effect : Mis(Camisole))

�� Op(Action : MettreGilet, Précond : Mis(Camisole), Effect : Mis(Gilet))

2.

Start

MettreCaleçon

MettrePantalon

MettreSouliers

MettreCamisole

MettreGilet

Finish

Mis(Caleçon)

Mis(Pantalon)

Mis(Camisole)

Mis(Souliers), Mis(Gilet)

3.

Start

MettreCaleçon

MettrePantalon

MettreSouliers

MettreCamisole

MettreGilet

Finish

4. 10 possibilités

Réponse 2

(excusez la réponse en anglais)

Op(ACTION : Go(x, y), PRECOND : At(Shakey, x) � In(x, r) � In(y, r),

EFFECT: At(Shakey, y) � �(at(Shakey, x)))

Op(ACTION: Push(b, x, y), PRECOND: At(Shakey, x) � At(b, x) � Pushable(b)

� In(x, r) � In(y, r),

EFFECT: At(b, y) � At(Shakey, y) � �At(b, x) � �At(Shakey, x))

Op(ACTION: Climb(b), PRECOND: At(Shakey, x) � At(b, x) � Climbable(b),

EFFECT: On(Shakey, b) � �On(Shakey, Floor))

Op(ACTION: Down(b), PRECOND: On(Shakey, b),

EFFECT: On(Shakey, Floor) � �On(Shakey, b))

Op(ACTION: TurnOn(l), PRECOND: On(Shakey, b) � At(Shakey, x) � At(l, x),

EFFECT: TurnedOn(l))

Op(ACTION: TurnOff(l), PRECOND: On(Shakey, b) � At(Shakey, x) � At(l, x),

EFFECT: �TurnedOn(l))

Début

Go(x, Door3)

At(Shakey, x) � In(x, Room3) � In(Door3, Room3)

Push(Box2, PosBox2, Door1)

Go(Door3, Door1)

� In(Door3, Corridor) � In(Door1, Corridor)

Go(Door1, PosBox2)

� In(Door1, Room1) � In(PosBox2, Room1)

Push(Box2, Door1, Door2)

Push(Box2, Door2, y)

Fin

At(Box2, Room2)

At(Box2, PosBox2) � Pushable(Box2)� In(PosBox2, Room1) � In(Door1, Room1)

Pushable(Box2) � In(Door1, Corridor)� In(Door2, Corridor)

Pushable(Box2) � In(Door2, Room2) � In(y, Room2)

At(Shakey, Door3)

At(Shakey, Door1)

� At(Shakey, PosBox2)

� At(Shakey, Door1) � At(Box2, Door1)

At(Shakey, Door2) � At(Box2, Door2) �

Réponse 3

Variables d’évidence: âge, Occupation, Éducation, Marié ou non, Années à la présente

adresse, Faillites, Délinquance, Hypothèque, etc.

Variable de sortie : profit espéré

Réponse 4

T

FG

G

FA

A

T = Normal T = Haut

FG ¬FG FG ¬FG

G = Normal 1 - y 1 - x y x

G = Haut y x 1 - y 1 - x

G = Normal G = Haut

FA ¬FA FA ¬FA

A 0 0 0 1

¬A 1 1 1 0

5.

Les probabilités pour chaque maladie sont:

p(A) = 5/12, p(B) = 1/4, p(C) = 1/3

Calculons l'information totale de la table:

55,1

)58,1(31

)2(41

)26,1(125

)31

(31

)41

(41

)125

(125

)( logloglog222

�

��

��TableI

Il faut maintenant calculer les gains d'information pour chaque attribut.

Nb.Noyaux

L'attribut Nb.Noyaux sépare les exemples en échantillons:

C1 = 1, 3, 4, 5, 11, 12

C2 = 2, 6, 7, 8, 9, 10

Pour C1 on a: p(A) = 2/3, p(B) = 0 et p(C) = 1/3. Donc,

92,031

log31

32

log32

)( 221

�

��

��

��

�

��

��CI

Pour C2 on a: p(A) = 1/6, p(B) = 1/2 et p(C) = 1/3. Donc,

46,131

log31

21

log21

61

log61

)( 2222

�

��

��

��

�

��

��

�

��

��CI

Ainsi, on peut calculer l’information espérée pour compléter l’arbre en choisissant

l’attribut Nb.Noyaux:

19,1

)46,1(21

)92,0(21

)(21

)(21

).( 21

�

��

�� CICINoyauxNbE

Le gain d’information en choisissant Nb.Noyaux est donc :

36,0

19,155,1).()().(

�

��

�� NoyauxNbETableINoyauxNbgain

Nb.Flagelles

L'attribut Nb.Flagelles sépare les exemples en échantillons:

C1 = 1, 2, 3, 4, 5, 9, 10

C2 = 6, 7, 8, 11, 12


87,072

log72

75

log75

)( 221

�

��

��

��

�

��

��CI

Pour C2 on a: p(A) = 0, p(B) = 3/5 et p(C) = 2/5. Donc,

97,052

log52

53

log53

)( 222

�

��

��

��

�

��

��CI


l’attribut Nb.Flagelles:

91,0

)97,0(125

)87,0(127

)(125

)(127

).( 21

�

��

�� CICIFlagellesNbE

Le gain d’information en choisissant Nb.Flagelles est donc :

64,0

91,055,1).()().(

�

��

�� FlagellesNbETableIFlagellesNbgain

Colloration

L'attribut Colloration sépare les exemples en échantillons:

C1 = 1, 2, 3, 6, 11, 12

C2 = 4, 5, 7, 8, 9, 10


46,131

log31

61

log61

21

log21

)( 2221

�

��

��

��

�

��

��

�

��

��CI


58,131

log31

31

log31

31

log31

)( 2222

�

��

��

��

�

��

��

�

��

��CI


l’attribut Colloration:

52,1

)58,1(21

)46,1(21

)(21

)(21

)( 21

�

��

�� CICInColloratioE

Le gain d’information en choisissant Colloration est donc :

03,0

52,155,1)()()(

�

��

�� nColloratioETableInColloratiogain

Paroi

L'attribut Paroi sépare les exemples en échantillons:

C1 = 1, 2, 4, 6, 7, 9, 11

C2 = 3, 5, 8, 10, 12


55,172

log72

72

log72

73

log73

)( 2221

�

��

��

��

�

��

��

�

��

��CI


52,152

log52

51

log51

52

log52

)( 2222

�

��

��

��

�

��

��

�

��

��CI


l’attribut Paroi:

53,1

)52,1(125

)55,1(127

)(125

)(127

)( 21

�

��

�� CICIParoiE

Le gain d’information en choisissant Paroi est donc :

02,0

53,155,1)()()(

�

��

�� ParoiETableIParoigain

On choisira donc l’attribut Nb.Flagelles, car il offre le meilleur gain d’information.

On pose maintenant Nb.Flagelles à 1 et on cherche le deuxième nœud de l’arbre.

Les probabilités pour chaque maladie sont:

p(A) = 5/7, p(B) = 0, p(C) = 2/7


87,0

)81,1(72

)49,0(75

)72

(72

)75

(75

)( loglog22

�

��

��TableI


Nb.Noyaux

L'attribut Nb.Noyaux sépare les exemples en échantillons:

C1 = 1, 3, 4, 5

C2 = 2, 9, 10

Pour C1 on a: p(A) = 1, p(B) = 0 et p(C) = 0. Donc,

� � 01log1)( 21 ��CI


92,032

log32

31

log31

)( 222

�

��

��

��

�

��

��CI


l’attribut Nb.Noyaux:

39,0

)92,0(73

)0(74

)(73

)(74

).( 21

�

��

�� CICINoyauxNbE

Le gain d’information en choisissant Nb.Noyaux est donc :

48,0

39,087,0).()().(

�

��

�� NoyauxNbETableINoyauxNbgain

Colloration

L'attribut Colloration sépare les exemples en échantillons:

C1 = 1, 2, 3

C2 = 4, 5, 9, 10

Pour C1 on a: p(A) = 1, p(B) = 0 et p(C) = 0. Donc,

� � 01log1)( 21 ��CI


121

log21

21

log21

)( 222

�

��

��

��

�

��

��CI


l’attribut Colloration:

57,0

)1(74

)0(73

)(74

)(73

)( 21

�

��

�� CICInColloratioE

Le gain d’information en choisissant Colloration est donc :

3,0

57,087,0)()()(

�

��

�� nColloratioETableInColloratiogain

Paroi

L'attribut Paroi sépare les exemples en échantillons:

C1 = 1, 2, 4, 9

C2 = 3, 5, 10


81,041

log41

43

log43

)( 221

�

��

��

��

�

��

��CI


92,031

log31

32

log32

)( 222

�

��

��

��

�

��

��CI


l’attribut Paroi:

86,0

)92,0(73

)81,0(74

)(73

)(74

)( 21

�

��

�� CICIParoiE

Le gain d’information en choisissant Paroi est donc :

01,0

86,087,0)()()(

�

��

�� ParoiETableIParoigain

On choisira donc l’attribut Nb.Noyaux, car il offre le meilleur gain d’information.

Les deux premiers nœuds de l’arbre sont donc Nb.Flagelles et Nb.Noyaux.

6.

Un perceptron ne peut pas représenter une fonction XOR, car cette fonction n’est pas

linéairement séparable.

1

1

11

1

1

-1

-10

0

x y

(x � y) (x � y)

(x XOR y)

1

La fonction d’activation est : ��

�

��

5,015,00

)(xsixsi

xf

Page 1 de 17

Corriger Examen final Intelligence artificielle II (IFT-17587)

De 15h30 à 18h20 le 2 mai 2002, salle PLT-2341

Question 1 (15 points) Transformer l’expression suivante, écrite en logique du premier ordre, pour qu’elle soit

en forme normale conjonctive.

S(x))R(x)x ( x)))M(y,(Q(x)P(x)y x( ∧∃∨∧⇒∃∀ ¬

Réponse :

(∀x ∃y P(x) ⇒ (Q(x) ∧ M(y,x))) ∨ ¬(∃x R(x) ∧ S(x))

Élimination des implications

(∀x ∃y ¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ ¬(∃x R(x) ∧ S(x))

Déplacer les signes de négation sur les atomes

(∀x ∃y ¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ (∀x ¬(R(x) ∧ S(x)))

(∀x ∃y ¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ (∀x ¬R(x) ∨ ¬S(x))

Standardiser les variables

(∀x ∃y ¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ (∀z ¬R(z) ∨ ¬S(z))

Déplacer les quantificateurs à gauche

∀x ∃y ∀z (¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ (¬R(z) ∨ ¬S(z))

Skolemization

∀x ∀z (¬P(x) ∨ (Q(x) ∧ M(F(x),x))) ∨ (¬R(z) ∨ ¬S(z))

(¬P(x) ∨ (Q(x) ∧ M(F(x),x))) ∨ (¬R(z) ∨ ¬S(z))

Distribuer les ∧ par rapport au ∨

((¬P(x) ∨ Q(x)) ∧ (¬P(x) ∨ M(F(x),x))) ∨ (¬R(z) ∨ ¬S(z))

((¬P(x) ∨ Q(x)) ∨ (¬R(z) ∨ ¬S(z))) ∧ ((¬P(x) ∨ M(F(x),x)) ∨ (¬R(z) ∨ ¬S(z)))

Regrouper les ∧ et les ∨

(¬P(x) ∨ Q(x) ∨ ¬R(z) ∨ ¬S(z)) ∧ (¬P(x) ∨ M(F(x),x) ∨ ¬R(z) ∨ ¬S(z))

Page 2 de 17

Question 2 (30 points) Un robot mécanique, constitué de 2 bras, doit déplacer des objets de boîte en boîte. Ses

deux bras se termine par une pince qu’il peut utiliser pour prendre des objets. Pour tenter

de diminuer les collisions possibles entre les deux bras, les concepteurs ont décidé qu’il

n’y aurais qu’un seul bras qui pourrait se déplacer à la fois. Ce robot a 5 actions à sa

disposition pour déplacer un objet d’une boîte à une autre :

• Prendre(O, P) pour prendre l’objet O avec la pince P. Bien entendu, il ne peut

prendre l’objet que si la pince est vide, l’objet est libre et que la pince et l’objet

sont à la même place.

• Soulever(O, P) permet au robot de soulever l’objet pour le sortir de la boîte. Bien

entendu, l’objet doit être déplaçable et le robot doit la tenir entre une de ses

pinces.

• Déplacer(O, P, l1, l2) déplace l’objet O avec la pince P de la position l1 à la

position l2. Pour déplacer l’objet, la pince doit tenir l’objet dans les airs, au dessus

des boîtes.

• DéplacerPince(P, l1, l2) déplace la pince P de la position l1 à la position l2.

• Déposer(O, P) dépose l’objet O avec la pince P dans une des boîtes.

• Relâcher(O, P) relâche l’objet O tenu par la pince P. Par sûreté, le robot ne peut

pas relâcher un objet s’il est dans les airs.

a) (10 points) Vous devez définir les opérateurs STRIPS pour chacune de ces

actions. Pour ce faire, vous devez définir tous les prédicats nécessaires et donnez

une courte explication pour chacun.

Réponse :

Prédicats :

• At(x, y) : L’objet ou la pince x est à la position y. Pour les objets, on

considère qu’ils sont à une certaine position uniquement s’ils ne sont pas

tenu par une pince. Si l’objet est tenu par une pince, c’est la position de la

pince qui est importante.

Page 3 de 17

• Libre(O) : L’objet O est libre, c’est-à-dire qu’il n’est pas tenu par une

pince.

• Vide(P) : La pince P ne tient aucun objet.

• Tient(P,O) : La pince P tient l’objet O.

• Déplaçable(O) : L’objet O est déplaçable.

• Enbas(P) : Indique que la pince est en bas, c’est-à-dire qu’elle est dans une

des boîtes et qu’elle peut donc soit saisir un objet ou en déposer un.

Opérateurs :

• OP(ACTION : Prendre(O,P,L), PRECOND : At(P,L) ∧ At(O,L) ∧ Libre(O) ∧

Vide(P) ∧ EnBas(P), EFFECT : ¬Libre(O) ∧ ¬Vide(P) ∧ Tient(P,O))

• OP(ACTION : Soulever(O,P), PRECOND : Déplaçable(O) ∧ Tient(P,O) ∧

EnBas(P), EFFECT : ¬EnBas(P))

• OP(ACTION : Déplacer(O,P, l1, l2), PRECOND : ¬EnBas(P) ∧ Tient(P,O) ∧

At(P,l1), EFFECT : At(P,l2) ∧ ¬At(P,l1))

• OP(ACTION : DéplacerPince(P, l1, l2), PRECOND : ¬EnBas(P) ∧ At(P,l1),

EFFECT : At(P,l2) ∧ ¬At(P,l1))

• OP(ACTION : Déposer(O,P), PRECOND : ¬EnBas(P) ∧ Tient(P,O),

EFFECT : EnBas(P))

• OP(ACTION : Relâcher(O,P,L), PRECOND : EnBas(P) ∧ Tient(P,O) ∧

At(P,L), EFFECT : ¬Tient(P,O) ∧ Libre(O) ∧ Vide(P) ∧ At(O,L))

b) (5 points) Construisez le plan partiel pour un robot qui voudrait déplacer deux

objets vers la boîte 3. Le premier objet est dans la boîte 1 et le deuxième objet est

dans la boîte 2. Les deux pinces commencent à des positions aléatoires.

Page 4 de 17

Début

Fin

Prendre(O1,P1,B1)

Soulever(O1,P1)

Déplacer(O1,P1, B1, B3)

Déposer(O1,P1)

Relâcher(O1,P1,B3)

At(P1,B1) ∧ At(O1,B1) ∧ Libre(O1) ∧ Vide(P1) ∧ EnBas(P1)

Déplaçable(O1) ∧ Tient(P1,O1) ∧ EnBas(P1)

¬EnBas(P1) ∧ Tient(P1,O1) ∧ At(P1,B1)

¬EnBas(P1) ∧ Tient(P1,O1)

EnBas(P1) ∧ Tient(P1,O1) ∧ At(P1,B3)

At(O1,B3) ∧ At(O2,B3)

DéplacerPince(P1, l1, B1)

¬EnBas(P1) ∧ At(P1,l1)

Prendre(O2,P2,B2)

Soulever(O2,P2)


Déposer(O2,P2)

Relâcher(O2,P2,B3)

At(P2,B2) ∧ At(O2,B2) ∧ Libre(O2) ∧ Vide(P2) ∧ EnBas(P2)

Déplaçable(O2) ∧ Tient(P2,O2) ∧ EnBas(P2)

¬EnBas(P2) ∧ Tient(P2,O2) ∧ At(P2,B2)

¬EnBas(P2) ∧ Tient(P2,O2)

EnBas(P2) ∧ Tient(P2,O2) ∧ At(P2,B3)


¬EnBas(P2) ∧ At(P2,l2)

c) (5 points) Combien y a-t-il de linéarisations possibles pour ce plan ?

Réponse : Il y a 12 actions à placer. Toutefois, les six actions pour chacun des objets

doivent rester dans le même ordre. Ce qui peut changer, c’est l’alternance entre les

actions pour l’objet 1 et celles pour l’objet 2. Pour un objet, il y a six actions. Il faut

donc choisir 6 positions possibles parmi 12. Par la suite, on remplit les positions

restantes avec les six actions de l’autre objet. Pour calculer le nombre de groupes de

six positions possibles parmi 12, on peut utiliser la formule suivante : C(12, 6) = 924.

Il y a donc 924 linéarisations possibles.

Page 5 de 17

d) (10 points) Supposons maintenant que le robot ne sait pas si les objets sont

déplaçables avec une seule pince. Si l’objet est trop lourd ou trop grand, le robot

doit utiliser ces deux pinces pour le soulever et le déplacer. Pour ce faire, le robot

doit avoir une autre action Vérifier(O), qui vérifie si l’objet peut être déplacé avec

une seule pince ou deux. En utilisant les actions précédentes et cette nouvelle

action, construisez un plan conditionnel partiellement ordonné pour déplacer un

objet d’une boîte à une autre. La deux pinces commencent à des positions

aléatoires. Par ailleurs, si vous avez besoin de modifier les opérateurs existants,

indiquez-le.

Réponse :

Pour les actions Soulever, Déplacer, Déposer et Relâcher, on doit ajouter un autre

argument pour la deuxième pince lorsque les deux pinces sont utilisées sur le même

objet.

Page 6 de 17

Début

Fin

Prendre(O1,P1,B1)

Soulever(O1,P1)


Déposer(O1,P1)

Relâcher(O1,P1,B3)


Vérifier(O1)


Prendre(O1,P2,B1)

Soulever(O1,P1, P2)

Déplacer(O1,P1, P2, B1, B3)

Déposer(O1,P1, P2)

Relâcher(O1,P1,P2,B3)

(Déplaçable(O1)) (¬Déplaçable(O1))

Fin

Page 7 de 17

Question 3 (15 points) Un patient se rend chez son médecin parce qu’il a de la fièvre et qu’il ressent des douleur

dans le dos. Le médecin soupçonne que le patient a la maladie M. La probabilité d’avoir

la maladie M est de 1%. La probabilité d’avoir mal au dos si on a la maladie M est de

95%, tandis que la probabilité d’avoir mal au dos si on n’a pas la maladie M est de 30%.

La probabilité d’avoir de la fièvre si on a la maladie M est de 80%, tandis que la

probabilité d’avoir de la fièvre si on n’a pas la maladie M est de 40%. La probabilité

d’avoir mal au dos si on a de la fièvre est de 50%. Finalement, la probabilité d’avoir de la

fièvre si on a la maladie M et mal au dos est de 90%. Traduisez ce problème sous forme

de probabilités à priori et conditionnelles en utilisant les variables M(pour maladie),

F(pour fièvre) et D(pour mal au dos). Donnez la probabilité que le patient ait la maladie

M étant donné qu’il a mal au dos et qu’il a de la fièvre, c’est-à-dire P(M | F, D).

Réponse :

P(M) = 0,01

P(¬M) = 0,99

P(D|M) = 0,95

P(D|¬M) = 0,3

P(F|M) = 0,8

P(F|¬M) = 0,4

P(D|F) = 0,5

P(F|M,D) = 0,9

Ce qu’il faut trouver: P(M|F,D) = P(F|M,D) * P(M|D) / P(F|D)

On a donc besoin de : P(M|D) = P(D|M) * P(M) / P(D) et P(F|D) = P(D|F) * P(F) / P(D)

On a donc besoin de : P(D) = P(D|M) * P(M) + P(D|¬M) * P(¬M)

= 0.95 * 0.01 + 0.3 * 0.99 = 0.3065

et de : P(F) = P(F|M) * P(M) + P(F|¬M) * P(¬M)

= 0.8 * 0.01 + 0.4 * 0.99 = 0.404

Donc, P(F|D) = P(D|F) * P(F) / P(D) = 0.5 * 0.404 / 0.3065 = 0.6591

Et, P(M|D) = P(D|M) * P(M) / P(D) = 0.95 * 0.01 / 0.3065 = 0.031

Page 8 de 17

Finalement, P(M|F,D) = P(F|M,D) * P(M|D) / P(F|D) = 0.9 * 0.031 / 0.6591 = 0.0423

Le patient a donc 4,2% de chance d’avoir la maladie M, sachant qu’il a mal au dos et

qu’il fait de la fièvre.

Question 4 (15 points) Sur votre nouvelle voiture, il y a un dispositif qui vous donne un avertissement s’il y a un

objet trop proche de votre voiture. Votre voiture utilise un détecteur d’objets, lui

permettant de voir les objets qui se trouve autour de votre voiture. En considérant la

vitesse de la voiture et la position des objets, ce dispositif d’avertissement se déclenchera

pour vous avertir du danger si un objet est trop proche de votre voiture. Considérons les

variables suivantes : V (vitesse de la voiture), CV (compteur de vitesse), CVD (compteur

de vitesse défectueux), DO (détecteur d’objets), O (objets), DOD (Détecteur d’objets

défectueux), SA (système d’avertissement) et SAD (système d’avertissement défectueux).

a) (8 points) Dessinez un réseau de croyance pour ce domaine, sachant que le

compteur de vitesse a tendance à être plus imprécis lorsque la vitesse augmente et

que le détecteur d’objet détecte plus difficilement les objets qui sont petits.

V

CVD

CV

O

DO

DOD

SA

SAD

b) (7 points) Supposons qu’il n’y a que deux valeurs possibles pour la vitesse

(Normale ou Élevée) et que le compteur de vitesse donne la bonne vitesse x% du

temps lorsqu’il fonctionne, mais uniquement y% du temps lorsqu’il est

défectueux. Donnez alors la table de probabilités conditionnelles pour CV.

Page 9 de 17

V = Normale V = Élevée

CVD ¬CVD CVD ¬CVD

CV = Normale y x 1 - y 1 - x

CV = Élevée 1 - y 1 - x y x

Question 5 (15 points) Avec un de vos partenaires de bureau, vous effectuez des paris sur l’issue des parties de

votre équipe de hockey favorite. Toutefois, au lieu de tout simplement vous fiez à votre

instinct, vous avez décidé d’utiliser un arbre de décision pour vous aider à choisir. Pour

ce faire, vous avez enregistré les résultats des parties passées, en notant si les parties se

jouaient à l’extérieur ou à domicile, si votre gardien super vedette était partant et si

l’autre équipe était mieux positionnée dans le classement.

Page 10 de 17

No Endroit GSV partant Autre Équipe Gagné

1 Domicile Oui Meilleure Oui

2 Étranger Oui Meilleure Non

3 Domicile Oui Moins bonne Oui

4 Domicile Non Moins bonne Oui

5 Étranger Non Moins bonne Non


7 Étranger Non Meilleure Non

8 Étranger Oui Moins bonne Non

9 Étranger Oui Meilleure Oui


Construisez l’arbre de décision à partir de ces données. Donnez uniquement les deux

premiers niveaux de l’arbre, c’est à dire les trois premiers nœuds avec les ensembles

contenant les numéros de parties présents à chaque nœud. (4 points bonis pour ceux qui

terminent l’arbre avec tous les calculs).

Réponse :

Les probabilités de gagner ou non la partie sont:

P(G) = 3/5, P(¬G) = 2/5


971,0

)322,1(52

)737,0(53

)52

(log52

)53

(log53

)( 22

=

−−−−=

−−=TableI


Endroit

L'attribut Endroit sépare les exemples en échantillons:

C1 = 1, 3, 4, 6, 10

C2 = 2, 5, 7, 8, 9

Page 11 de 17

Pour C1 on a: P(G) = 1 et P(¬G) = 0. Donc,

( ) 01log 1)( 21 =−=CI

Pour C2 on a: P(G) = 1/5 et P(¬G) = 4/5. Donc,

722,0

)322,0(54

)322,2(51

54

log54

51

log51

)( 222

=

−−−−=

−

−=CI


l’attribut Endroit:

361,0

)722,0(21

)0(21

)(21

)(21

)( 21

=

+=

+= CICIEndroitE

Le gain d’information en choisissant Endroit est donc :

61,0

361,0971,0)()()(

=−=

−= EndroitETableIEndroitgain

GSV partant

L'attribut GSV partant sépare les exemples en échantillons:

C1 = 1, 2, 3, 6, 8, 9, 10

C2 = 4, 5, 7


863,0

)807,1(72

)485,0(75

72

log72

75

log75

)( 221

=

−−−−=

−

−=CI


Page 12 de 17

918,0

)585,0(32

)585,1(31

32

log32

31

log31

)( 222

=

−−−−=

−

−=CI


l’attribut GSV partant:

880,0

)918,0(103

)863,0(107

)(103

)(107

)tan( 21

=

+=

+= CICItGSVparE

Le gain d’information en choisissant GSV partant est donc :

091,0

880,0971,0)tan()()tan(

=−=

−= tGSVparETableItGSVpargain

Autre Équipe

L'attribut Autre Équipe sépare les exemples en échantillons:

C1 = 1, 2, 7, 9

C2 = 3, 4, 5, 6, 8, 10

Pour C1 on a: P(G) = 1//2 et P(¬G) = 1//2. Donc,

1

)1(21

)1(21

21

log21

21

log21

)( 221

=

−−−−=

−

−=CI

Pour C2 on a: P(G) = 2//3 et P(¬G) = 1//3. Donc,

918,0

)585,1(31

)585,0(32

31

log31

32

log32

)( 222

=

−−−−=

−

−=CI


l’attribut Autre Équipe:

Page 13 de 17

951,0

)918,0(53

)1(52

)(53

)(52

)( 21

=

+=

+= CICIeAutreÉquipE

Le gain d’information en choisissant Autre Équipe est donc :

02,0

951,0971,0)()()(

=−=

−= eAutreÉquipETableIeAutreÉquipgain

On choisira donc l’attribut Endroit, car il offre le meilleur gain d’information.

On pose maintenant Endroit égale à Domicile et on cherche le deuxième nœud de

l’arbre.


P(G) = 1, P(¬G) = 0


0)1(log1)( 2 =−=TableI

On a donc plus besoin de continuer.

On pose maintenant Endroit égale à Étranger et on cherche le troisième nœud de

l’arbre.


P(G) = 1/5, P(¬G) = 4/5


722,0

)322,0(54

)322,2(51

54

log54

51

log51

)( 22

=

−−−−=

−

−=TableI

Il faut maintenant calculer les gains d'information pour chaque attribut restant.

GSV partant

Page 14 de 17

L'attribut GSV partant sépare les exemples en échantillons:

C1 = 2, 8, 9

C2 = 5, 7


918,0

)585,0(32

)585,1(31

32

log32

31

log31

)( 221

=

−−−−=

−

−=CI


( ) 01log1)( 22 =−=CI


l’attribut GSV partant:

551,0

)0(52

)918,0(53

)(52

)(53

)tan( 21

=

+=

+= CICItGSVparE

Le gain d’information en choisissant GSV partant est donc :

171,0

551,0722,0)tan()()tan(

=−=

−= tGSVparETableItGSVpargain

Autre Équipe

L'attribut Autre Équipe sépare les exemples en échantillons:

C1 = 2, 7, 9

C2 = 5, 8


918,0

)585,0(32

)585,1(31

32

log32

31

log31

)( 221

=

−−−−=

−

−=CI

Page 15 de 17


( ) 01log1)( 22 =−=CI


l’attribut Autre Équipe:

551,0

)0(52

)918,0(53

)(52

)(53

)( 21

=

+=

+= CICIeAutreÉquipE

Le gain d’information en choisissant Autre Équipe est donc :

171,0

551,0722,0)()()(

=−=

−= eAutreÉquipETableIeAutreÉquipgain

Les deux nœuds ont le même gain d’information, donc on peut choisir un des deux. Le

troisième nœud est donc soit GSV partant ou Autre Équipe.

Pour les 4 points bonis, les étudiants devrons ajouter le nœud suivant et dire que l’on ne

peut pas trouver l’arbre de décision, car deux exemples ont exactement la même

description, mais avec une classification différente. Il y a donc du bruit dans les données.

Page 16 de 17

Endroit

Oui: 1, 3, 4, 6, 10Non:

Oui: 9Non: 2, 5, 7, 8

ÉtrangerDomicile

GSV partant

Autre Équipe

Oui Non

Meilleure Moins bonne

Oui

Non

NonProblème!

Oui: Non: 5, 7

Oui: 9Non: 2, 8

Oui: 9Non: 2

Oui: Non: 8

Question 6 (10 points) Construisez un réseau de neurones permettant de connaître la valeur de vérité de

l’expression suivante : (¬A ∨ B) ⇒ C. Vous devez spécifier tous les poids et toutes les

fonctions d’activation.

Réponse :

Tout d’abord, on peut modifier l’expression de la manière suivante :

(¬A ∨ B) ⇒ C

¬(¬A ∨ B) ∨ C

(A ∧ ¬B) ∨ C

Dans le réseau de neurones, toutes les fonctions d’activation sont des fonctions à étage

(Step function) avec comme borne le nombre indiqué dans le nœud. La fonction d’entrée

est tout simplement la somme des entrées.

Page 17 de 17

-0,5

1,5

0,5

A

B

C

1

11

1

-1

Solution Examen final Intelligence Artificielle II (IFT-17587)

Mercredi 30 avril 2003





------------------------------------------------------------------------

1 (25 pts) Supposons une machine à trois registres A, B et C. Initialement, ils contiennent les

valeurs 1, 2 et 3 respectivement. Il y a une seule instruction, appelée Assigner(x,y) qui

copie la valeur du registre x dans le registre y. Le seul prédicat est Valeur(x, v), qui dit

que le registre x contient la valeur v. Nous voulons utiliser un algorithme de

planification partiellement ordonné pour construire un plan pour inverser les contenus

des registres A et B. Pour les questions b), c), d), e) et f), tous les changements apportés

au plan doivent être indiqués clairement.

a) En utilisant la notation graphique pour les opérateurs STRIPS, décrivez

l’opérateur Assigner avec ses préconditions et ses effets.

Assigner(x,y)

Valeur(x, v1), Valeur(y, v2)

Valeur(y, v1), ¬Valeur(y, v2)

b) Dessinez le plan initial du problème en utilisant la notation graphique.

Départ FinValeur(A, 1)Valeur(B, 2)Valeur(C, 3)

Valeur(A, 2)Valeur(B, 1)

1

c) Maintenant, le planificateur décide d’accomplir la condition du but qui dit que B

doit avoir la valeur 1. Ajoutez dans le plan l’action Assigner pour que cette

condition soit satisfaite. Effectuez toutes les assignations de variables nécessaires.



Assigner(x,B)Valeur(x, 1)Valeur(B, v2)

Valeur(B, 1)¬Valeur(B, v2)

d) Maintenant, supposons que le planificateur décide d’accomplir les préconditions

de l’action Assigner en la connectant à l’étape Départ. Mettre à jour votre plan en

effectuant toutes les assignations nécessaires.



Assigner(A,B)Valeur(A, 1)Valeur(B, 2)

Valeur(B, 1)¬Valeur(B, 2)

e) Maintenant, le planificateur décide d’accomplir l’autre condition du but, c’est-à-

dire que A contienne la valeur 2. Expliquez les différentes étapes lors de l’ajout

d’une autre action Assigner pour accomplir cette précondition. Dessinez votre

plan avec cette nouvelle action.

2




Assigner(x,A)Valeur(x, 2)Valeur(A, v2)

¬Valeur(A, v2)Valeur(A, 2)


f) Expliquez les étapes pour compléter le plan et complétez votre plan.




Assigner(C,A)Valeur(C, 2)Valeur(A, 1)

Assigner(B,C)Valeur(B, 2)Valeur(C, 3) Valeur(C, 2)

¬Valeur(C, 3)

¬Valeur(A, 1)Valeur(A, 2)


g) Représentez votre plan final en donnant toutes les composantes du plan sous

forme d’ensembles. Les quatre ensembles sont : actions, liens d’ordonnancement,

liens causaux et préconditions ouvertes.

Actions : {Assigner(A,B), Assigner(B,C), Assigner(C,A), Départ, Fin}

Liens d’ordonnancement : {Assigner(B,C) < Assigner(A,B), Assigner(A,B) <

Assigner(C,A), Départ < Assigner(B,C), Départ < Assigner(A,B), Départ <

Assigner(C,A), Départ < Fin, Assigner(B,C) < Fin, Assigner(A,B) < Fin,

Assigner(C,A) < Fin}

3

Liens causaux : {Départ Valeur(A,1) Assigner(A,B), Départ Valeur(B,2)

Assigner(A,B), Départ Valeur(A,1) Assigner(C,A), Départ Valeur(B,2)

Assigner(B,C), Départ Valeur(C,3) Assigner(B,C), Assigner(B,C) Valeur(C,2)

Assigner(C,A), Assigner(C,A) Valeur(A,2) Fin, Assigner(A,B) Valeur(B,1) Fin }

Préconditions ouvertes : {}

2 (21 pts) Considérez le réseau bayésien suivant.

H

S

T

E

P(H)0,1 H

T

F

P(S)0,3

0,9HT

T

F

F

P(T)0,9

0,5

0,8

0,2

ST

F

T

F TT

F

P(E)0,6

0,1

a) Selon la structure du réseau, est-ce que les équations suivantes sont vrais ou fausses,

expliquez?

i) P(H,S) = P(H)P(S)

Faux, parce que S est dependant de H.

ii) P(E|T,H) = P(E|T)

Vrai, parce qu’un noeud est conditionnellement indépendant de ses

non décendants sachant ses parents.

b) Calculez les probabilités suivantes en montrant les calculs :

i) P(e, h, s, t)

P(e, h, s, t) = P(e|t)P(t|h,s)P(s|h)P(h) = 0,6 * 0,9 * 0,3 * 0,1 = 0,0162

ii) P(¬e, h, s, t)

P(¬e, h, s, t) = P(¬e|t)P(t|h,s)P(s|h)P(h) = 0,4 * 0,9 * 0,3 * 0,1 = 0,0108

4

iii) P(e, h, s, ¬t)

P(e, h, s, ¬t) = P(e|¬t)P(¬t|h,s)P(s|h)P(h) = 0,1 * 0,1 * 0,3 * 0,1 = 0,0003

iv) P(¬e, h, s, ¬t)

P(¬e, h, s, ¬t) = P(¬e|¬t)P(¬t|h,s)P(s|h)P(h) = 0,9 * 0,1 * 0,3 * 0,1 = 0,0027

c) Calculez P(E| h,s) en montrant les calculs.

P(E| h,s) = α P(E, h, s, T) = α (P(E, h, s, t) + P(E, h, s, ¬t)) = α (<0.0162, 0.0108> +

<0.0003, 0.0027>) = α (<0.0165, 0.0135>) = <0.55, 0.45>

Où α = 1/(0.0165 + 0.0135) = 33.33333333

3 (10 pts) Après avoir passé un test de dépistage du SRAS, le médecin de John lui dit que le test

de dépistage a retourné qu’il était atteint du SRAS. Le test de dépistage est précis à 90%

(ce qui veut dire que la probabilité de tester positif lorsque l’on est atteint du SRAS est

de 90% et que la probabilité de tester négatif si l’on a pas le SRAS est de 90%). La

maladie ne touche qu’une personne sur 20000. Quelle est la probabilité que John soit

atteint du SRAS?

P(tp|s) = 0.9

P(tn|¬s) = 0.9

P(s) = 0.00005

P(s|tp) = (P(tp|s) * P(s)) / (P(tp|s)P(s) + P(tp|¬s)P(¬s)) = (0.9 * 0.00005) / (0.9*0.00005

+ 0.1*0.99995) = 0.0004498

4 (15 pts) Supposons un problème de classification consistant à déterminer la classe

d’appartenance de chacune des instances. Le domaine de valeurs des classes possibles

est : {1, 2, 3}. Selon la base de connaissance suivante, déterminez la classe de l’instance

< 3, 12, 4, 7, 8 > à l’aide de l’algorithme des k-voisins les plus proches avec distances

pondérées. Montrez tous les calculs.

Instances A1 A2 A3 A4 A5 Classe

X1 3 5 4 6 1 1

X2 4 6 10 3 2 2

X3 8 3 4 2 6 3

5

X4 2 1 4 3 6 3

X5 2 5 1 4 8 2

Dist(Y, X1)2 = 99, Dist(Y, X2)2 = 125, Dist(Y, X3)2 = 135, Dist(Y, X4)2 = 142, Dist(Y, X5)2 = 68

Pour la valeur 1, la somme donne : 1/99 = 0.0101

Pour la valeur 2, la somme donne : 1/125 + 1/68 = 0.0227

Pour la valeur 3, la somme donne : 1/135 + 1/142 = 0.01445

La plus grande somme est pour la valeur 2, donc la classe retournée est la classe 2.

5 (7 pts) Construisez un réseau de neurones retournant la fonction majorité pour 5 attributs en

entrée. Les attributs peuvent avoir les valeurs 0 ou 1. La fonction majorité retourne 1 si

au moins la moitié des entrées sont à 1.

Les cinq entrées sont connectées au même neurone. Les poids sont tous de valeur 1. La borne de la

fonction d’activation est de 2.5. Donc, le neurone retourne 1 si la somme est plus grande que 2.5, ce

qui survient uniquement lorsque plus de la moitié des entrées sont à 1.

6 (7 pts) Expliquez brièvement (2 à 4 phrases) l’utilisation d’un ensemble d’entraînement et d’un

ensemble de test lors de l’évaluation d’un programme d’apprentissage.

Lorsque l’on veut évaluer un programme avec un ensemble fixe d’exemples, normalement, on le

divise en deux ensembles, un ensemble d’entraînement et un ensemble de test ou de validation. Le

programme utilise l’ensemble d’entraînement pour l’apprentissage. Par la suite, on teste l’efficacité

du programme sur l’ensemble de test. En faisant cela, on s’assure que le programme n’apprend pas

uniquement les exemples, mais qu’il apprend le concept sous jacent.

6

7 (15 pts) Vrai ou Faux?

a) On peut dire qu’un agent qui apprend est un agent qui ajuste son standard de

performance pour améliorer son efficacité.

Faux

b) Les agents apprenants n’utilisent pas toujours le comportement appris pour

choisir leurs actions.

Vrai

c) Lorsque l’on utilise l’apprentissage par renforcement, l’agent ne sait pas ce qu’il

doit apprendre.

Vrai

d) Pour tous les plans partiellement ordonnés avec aucune précondition non

satisfaite et aucun conflit, il existe au moins une linéarisation du plan qui est une

solution correcte.

Vrai

e) L’architecture la plus utilisée en robotique est l’architecture de subsomption.

Faux

f) Dans les systèmes multiagents, tous les agents doivent coopérer ensemble pour

atteindre un but.

Faux

g) Une architecture réflective est une architecture permettant à l’agent de délibérer

sur ses propres composantes de calculs.

Vrai

h) Un algorithme en tout temps (de type « anytime ») peut retourner le meilleur

plan n’importe quand.

Faux

i) Il n’y a qu’une décomposition possible par action lorsque l’on utilise la

décomposition hiérarchique pour la planification.

Faux

j) En planification conditionnelle, l’agent a un plan pour toutes les situations

possibles.

Vrai

7

1

Solution Examen final Intelligence Artificielle II (IFT-17587)

Jeudi 29 avril 2004


• Tout document est permis. • Le nombre de points accordés à chacune des questions est inscrit entre parenthèses. • Le questionnaire a 6 questions sur 3 pages. ------------------------------------------------------------------------ 1 (10 pts) Dans l’environnement simple suivant, une souris doit se promener dans

l’environnement en essayant d’éviter de rencontrer un chat. La souris a appris à sentir la présence d’un chat une case d’avance. Donc, lorsqu’il y a un chat sur une case, la souris perçoit une odeur dans les cases adjacentes. Dans le problème suivant, on considère que la souris a commencé dans la case (1,1), quelle a fait un déplacement vers la droite en (2,1) et un mouvement vers le bas en (2,2). Dans les deux premières cases qu’elle a parcourues, elle n’a rien perçue. Toutefois, en (2,2), elle a perçu une odeur. Partant de ses observations, la souris aimerait déterminer les cases sécuritaires, c’est-à-dire, quelles sont les cases qui contiennent un chat parmi les quatre cases non visitées. En utilisant l’algorithme d’inférence de vérification de modèles, dites (en expliquant) si la base de connaissances découlant des perceptions de la souris permet d’inférer les phrases suivantes.

a) Il n’y a pas de chat en (1,2). b) Il n’y a pas de chat en (3,2).

1 Rien Rien ? 2 ? Odeur ? 3 ?

1 2 3

2

La présence où non d’un chat dans les quatre cases peut être représentée par quatre variables booléennes. On peut représenter la base de connaissance de l’agent ainsi que la véracité des deux phrases à l’aide de la table de vérité suivante où sont listées tous les modèles possibles. Cas à un seul chat :

(1,2) (2,3) (3,1) (3,2) BC a) b) V V V V F F F V V V F F F V V V F V F F F V V F F F F V V F V V F F F V F V F F F V V F F V F F F V F F F F F V F V V V F V F F V V F F V V F V F V F V F F V F F V V V F F V V F V F F F V F F V V F F F V V V F F F F F F V V

Cas où il peut y avoir plus d’un chat :

(1,2) (2,3) (3,1) (3,2) BC a) b) V V V V F F F V V V F F F V V V F V F F F V V F F F F V V F V V F F F V F V F F F V V F F V F F F V F F F F F V F V V V F V F F V V F F V V F V F V V V F F V F F V V V F F V V F V F F F V F F V V F F F V V V F F F F F F V V

Le résultat est le même qu’il y ait un ou plusieurs chats. Partout où la base de connaissance est vraie, la phrase en a) est vraie, donc M(BC) ⊆ M(a)), par conséquent, BC permet d’inférer a). Il y a au moins un cas où la base de connaissance est vraie et où b) est fausse, donc M(BC) ⊄ M(b)), par conséquent, BC ne permet pas d’inférer b).

3

2 (18 pts) En considérant la description du problème ici-bas, utilisez l’algorithme « Graphplan »

pour trouver le plan ou les plans permettant d’atteindre le but tel que précisé ci-dessous. Vous devez présenter toutes les étapes de l’algorithme clairement.

INITIAL(x) BUT(y ∧ z) Action(A, PRECOND : x, EFFET : ¬x ∧ y) Action(B, PREDOND: w, EFFET : z)

Action(C, PREDOND: x, EFFET : w)

x

¬w

¬y

¬z

x

¬w

¬y

¬z

A ¬x

y

wC

x

¬w

¬y

¬z

¬x

y

w

z

A

B

C

S0 A1 S1 A2 S2

À partir de ce Graph de planification, on peut extraire le plan suivant :

FinB

zy

w

Ax

z

y¬x

Début xC wx

4

3 (18 pts) En considérant le réseau bayésien suivant, calculez la distribution de probabilités P(G|e) à l’aide l’algorithme d’inférence par élimination de variables. Vous devez montrer tous les calculs.

M

G

E

P(M)0,2

GT

F

P(E)0,7

0,1

A GT

F

P(A)0,8

0,3

MT

F

P(G)0,8

0,1

Réponse :

∑∑=a m

G)P(e|G)P(a|P(m)P(G|m)αP(G|e)

∑ ∑=m a

GaPmGPmPαP(e|G)P(G|e) )|()|()(

∑=m

mGPmPαP(e|G)P(G|e) )|()(

⎟⎟⎠

⎞⎜⎜⎝

⎛=⎟⎟

⎠

⎞⎜⎜⎝

⎛¬

=

⎟⎟⎠

⎞⎜⎜⎝

⎛=⎟⎟

⎠

⎞⎜⎜⎝

⎛×+××+×

=⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

¬=

¬×¬+×=×=

⎟⎟⎠

⎞⎜⎜⎝

⎛=⎟⎟

⎠

⎞⎜⎜⎝

⎛¬

=

⎟⎟⎠

⎞⎜⎜⎝

⎛=⎟⎟

⎠

⎞⎜⎜⎝

⎛¬¬¬

¬=

∑

1,07,0

)|()|(

)(

76,024,0

9,08,02,02,01,08,08,02,0

)(

)(

),()(),()(),()()(

8,02,0

)()(

)(

9,02,01,08,0

),(),(

),(),(

),(

gePgeP

G

g

g

mGmmGmmGmG

mPmP

M

mgPmgP

mgPmgP

MG

f

ff

fffffff

f

f

E

GM

GM

GMGMm

GMGM

M

G

>>=<<>=××<=×= 311.0,689.0076.0,168.076.01.0,24.07.0)()( ααGGαP(G|e) ff GME

5

4 (18 pts) En considérant le réseau bayésien dynamique suivant, montrez tous les calculs du

processus de filtrage pour les deux premiers états (S1 et S2). Pour cela, il faudra considérer que P(S0) = <0.4, 0.6>, E1 = vrai et E2 = faux.

St-1 St

EtEt-1

St

T

F

P(Et)0,8

0,3

St-1

T

F

P(St)0,9

0,2

E1 = vrai, donc la prédiction du temps t = 0 à t = 1 est :

>=<×><+×>=<= ∑ 52.0,48.06.08.0,2.04.01.0,9.0)()|()(0

0011s

sPsSPSP

La mise à jour avec l’évidence au temps t = 1 est : >>=<<>=><<== 29.0,71.0156.0,384.052.0,48.03.0,8.0)()|()|( 11111 ααα SPSePeSP

E2 = faux, donc la prédiction du temps t = 1 à t = 2 est :

>=<×><+×>=<= ∑ 303.0,697.029.08.0,2.071.01.0,9.0)|()|()|(1

111212s

esPsSPeSP

La mise à jour avec l’évidence au temps t = 2 est :

>>=<<=>><<==

603.0,397.02121.0,1394.0303.0,697.07.0,2.0)|()|(),|( 1222212

ααα eSPSePeeSP

6

5 (18 pts) Bob désire s’acheter une maison. La maison a une valeur sur le marché de 100 000$, mais il pourrait l’obtenir pour 90 000$. Toutefois, avant d’acheter la maison, il aimerait bien la faire évaluer pour être certain de faire un bon choix. L’évaluateur lui charge 1000$ pour faire l’évaluation. Si jamais la maison n’est pas en bon état, le coût des réparations pourrait aller jusqu’à 15 000$. Bob estime que la maison a 80% de chance d’être en bon état. La probabilité que l’évaluateur dise que la maison est en bon état si elle est effectivement en bon état est de 90%, de plus la probabilité qu’il dise qu’elle est en bon état si elle n’est pas en bon état (donc qu’il ne voit pas le problème) est de 15%.

a) Quel est le gain espéré de Bob en achetant cette maison sans faire de test? EU(acheter) = P(bonEtat) Gain(bonEtat) + P(¬bonEtat) Gain(¬bonEtat) = 0.8 * (100 000 – 90 000) + 0.2 * (100 000 – 105 000) = 7000$ b) Quel est le gain espéré de Bob en achetant cette maison si l’évaluateur dit qu’elle est

en bon état? P(testOK) = P(testOK|bonEtat) * P(bonEtat) + P(testOK|¬bonEtat) * P(¬bonEtat) = 0.9 * 0.8 + 0.15 * 0.2 = 0.75 P(bonEtat|testOK) = P(testOK|bonEtat) * P(bonEtat) / P(testOK) = 0.9 * 0.8 / 0.75 = 0.96 EU(acheter|testOK) = P(bonEtat|testOK) Gain(bonEtat) + P(¬bonEtat|testOK) Gain(¬bonEtat) = 0.96 * (100 000 – 90 000) + (1 - 0.96) * (100 000 – 105 000)= 0.96 * 10000 + 0.04 * -5000 = 9400$ c) Quel est le gain espéré de Bob en achetant cette maison si l’évaluateur dit qu’elle

n’est pas en bon état? P(¬testOK) = 1 – P(testOK) = 1 – 0.75 = 0.25 P(bonEtat|¬testOK) = P(¬testOK|bonEtat) * P(bonEtat) / P(¬testOK) = 0.1 * 0.8 / 0.25 = 0.32 EU(acheter|¬testOK) = P(bonEtat|¬testOK) Gain(bonEtat) + P(¬bonEtat|¬testOK) Gain(¬bonEtat) = 0.32 * 10000 + (1 – 0.32) * -5000 = -200$ d) Est-ce que ça vaut la peine de faire évaluer la maison. Quelle est la valeur de cette

information? La meilleure action à faire si le test est OK, c’est d’acheter la maison, car l’utilité d’acheter la maison (9400$) est plus grande que l’utilité de ne pas l’acheter (0$). La meilleure action à faire si le test n’est pas OK est de ne pas acheter la maison, parce que l’utilité de ne pas acheter la maison (0$) est plus grande que l’utilité de l’acheter (-200$). La meilleure action si Bob ne fait pas de test est d’acheter, car l’utilité d’acheter (7000$) est plus grande que l’utilité de ne pas acheter (0$). VPI(test) = (P(testOK) * EU(acheter|testOK) + P(¬testOK) * EU(¬acheter|¬testOK)) – EU(acheter) = (0.75 * 9400 + 0.25 * 0) – 7000 = 50$ Donc, ça ne vaut pas la peine de faire le test, parce que la valeur de l’information est plus petite que son coût.

7

6 (18 pts) On considère un environnement avec deux actions possibles : se déplacer vers la gauche ou se déplacer vers la droite. Si l’agent rencontre un mur, il reste sur place. Pour chaque déplacement, le modèle de transition spécifie les probabilités suivantes :

• 0.7 : l’agent se déplace dans la direction désirée. • 0.2 : L’agent reste sur place. • 0.1 : L’agent se déplace dans la direction opposée.

Fonction de récompense : -0.05 -0.05 +1

1 2 3 Politique à l’itération i (πi(s)) :

← ← ← 1 2 3

Valeurs des utilités au temps i :

0.8 0.6 0.3 1 2 3

Appliquez à cet environnement l’algorithme modifié d’itération de politique (« policy iteration ») en utilisant la fonction de mise à jour simplifiée de Bellman. Montrez tous les calculs pour deux itérations. Fonction simplifiée de Bellman :

Pour l’exemple, le paramètre γ vaut 0.8.

Ui+1(1) = -0.05 + 0.8 * (0.9*0.8 + 0.1*0.6) = 0.574 Ui+1(2) = -0.05 + 0.8 * (0.7*0.8 + 0.2*0.6 + 0.1*0.3) = 0.518 Ui+1(3) = 1 + 0.8 * (0.7*0.6 + 0.3*0.3) = 1.408 Maintenant, il faut calculer la nouvelle politique. Pour l’état 1 :

Action Gauche : (0.9*0.574 + 0.1*0.518) = 0.5684 Action Droite : (0.7*0.518 + 0.3*0.574) = 0.5348

L’action Gauche est donc l’action optimale en 1. Pour l’état 2 :

Action Gauche : (0.7*0.574 + 0.2*0.518 + 0.1*1.408) = 0.6462 Action Droite : (0.7*1.408 + 0.2*0.518 + 0.1*0.574) = 1.1466

L’action Droite est donc l’action optimale en 2. Pour l’état 3 :


L’action Droite est donc l’action optimale en 3.

8

Ui+2(1) = -0.05 + 0.8 * (0.9*0.574 + 0.1*0.518) = 0.40472 Ui+2(2) = -0.05 + 0.8 * (0.7*1.408 + 0.2*0.518 + 0.1*0.574) = 0.86728 Ui+2(3) = 1 + 0.8 * (0.9*1.408 + 0.1*0.518) = 2.0552 Maintenant, il faut calculer la nouvelle politique. Pour l’état 1 :



Action Gauche : (0.7*0.40472 + 0.2*0.86728 + 0.1*2.0552) = 0.66228 Action Droite : (0.7*2.0552 + 0.2*0.86728 + 0.1*0.40472) = 1.652568



L’action Droite est donc l’action optimale en 3.

Exercice 1 (Solutionnaire)

1. (5 pts) Quelle est la différence entre une mesure de performance et une fonction

d’utilité pour un agent?

Une mesure de performance est une fonction utilisée par un observateur externe pour

évaluer la performance d’un agent. Une fonction d’utilité est utilisée par l’agent lui-même

pour évaluer à quel point les états sont désirables.

N.B. La fonction d’utilité peut être différente de la mesure de performance. Un agent peut

ne pas avoir de fonction d’utilité explicite, mais il y a toujours une mesure de

performance.

2. (25 pts) Donner la PAGE et les caractéristiques de l’environnement d’un agent

devant jouer au tennis.

Percepts : La balle, le joueur adverse, sa position sur le terrain.

Actions :

�� Frapper la balle (coup droit, revers, smash, service, etc.).

�� Se déplacer (dans toutes les directions).

But : Le but général est de gagner la partie. Un but intermédiaire serait de frapper la balle

pour qu’elle tombe dans la partie de terrain de l’adversaire et que celui-ci ne soit pas

capable de la retourner.

Environnement : L’environnement de l’agent est le terrain de tennis sur lequel il joue

avec un adversaire. L’environnement est accessible, parce que l’agent peut voir tout ce

qui se passe sur le terrain. L’environnement est non-déterminé, parce que les actions de

l’agent n’ont pas un effet garanti et il y a de l’incertain. Lorsque l’agent frappe la balle, il

ne sait pas si elle va tomber dans le jeu et il ne sait pas si l’autre joueur va la retourner.

L’environnement est non-épisodique, car les actions de l’agent dans le passé peut

influencer ses actions actuelles. Par exemple, il peut avoir trouvé une faiblesse à son

adversaire ou il peut jouer différemment s’il mène la partie. L’environnement est

dynamique, parce que l’environnement peut être modifié pendant que l’agent délibère.

L’autre joueur peut se déplacer et la balle se déplace. L’environnement est continu, car il

y a plusieurs perceptions possibles et plusieurs actions possibles. La force de frappe et la

direction de la balle sont des valeurs continues.

3. (20 pts) Donner un exemple d’agent pour chacune des quatre architectures

d’agent (simple réflexe, réflexe avec état interne, buts, utilité) et expliquer votre

choix.

Tout exemple qui correspond bien aux architectures est accepté.

4. (10 pts) Supposons que l’on exécute un algorithme de recherche vorace (greedy

search), quelle sorte de recherche l’algorithme de recherche vorace simule-t-il si

a. h(n) = -g(n)?

Profondeur d’abord, parce que les fils auront toujours une valeur plus petite

que les parents. Donc, l’algorithme développera le fils, puis le fils du fils,

jusqu’à ce qu’il atteigne une feuille, ce qui est le comportement de

l’algorithme de profondeur d’abord.

b. h(n) = g(n)?

Largeur d’abord, parce que les parents auront toujours une valeur plus petite

que leurs fils. Donc, tous les nœuds d’un même niveau seront développés

avant de passer au niveau suivant, ce qui est le comportement de l’algorithme

de largeur d’abord.

5. (25 pts) Dans l’espace de recherche ci-dessous, le nombre placé à côté de chaque

lien dénote le coût associé au lien entre les nœuds et h est le coût estimé du nœud

jusqu’au but final G.

a. Donner l’ordre dans lequel les nœuds sont visités lorsqu’on utilise A*.

Donner alors f(n) pour chacun des nœuds n.

f(B) = 5, f(C) = 8, f(D) = 20, f(E) = 19, f(F) = 11, f(I) = 31, f(G) = 13, f(H) =

14, f(J) = 34. Donc, l’ordre de visite est: A-B-C-F-E-D-G

b. Un algorithme « vorace » de type meilleur d’abord peut-il faire

mieux? Combien de nœuds, un tel algorithme traverse-t-il avant

d’atteindre le but G.

f(B) = 4, f(C) = 2, f(D) = 15, f(E) = 16, f(F) = 3, f(I) = 20, f(G) = 0, f(H) = 4.

Donc, l’ordre de visite est: A-C-F-B-D-G, ce qui est un nœud de moins que

A*, 6 au lieu de 7.

c. Si le nœud I est aussi un but, lequel (ou lesquels) parmi largeur

d’abord, profondeur d’abord et profondeur itératif peut (ou peuvent)

trouver la solution optimale? Donner pour chaque algorithme la liste

des nœuds développés.

Largeur d’abord : A-B-C-D-E-F-G

Profondeur d’abord : A-B-E-J-C-F-I

Profondeur itératif : A-B-C-D-A-B-E-C-F-D-G

Seulement la recherche en profondeur d’abord va trouver la solution optimale I.

d. La fonction heuristique h pose un problème dans la mesure où elle

surestime trop le coût de D à G. Quelle propriété de A* n’est plus

remplie si h a ce problème?

A* n’est plus optimale.

A

B C D

E F

I

G H

J

1 6 5

5822

153

h = 4 h = 2 h = 15

h = 0 h = 4

h = 3h = 16

h = 16h = 20

6. (15 pts) Supposons que l’on veut établir les horaires pour un problème de salles

de cours. Dans ce problème, on a 5 salles et 10 cours, chaque cours débute à Di

heure et finit à Fi heure, avec Di et Fi des entiers naturels. Sachant qu’aucun

cours ne doit partager avec un autre la même salle en même temps, et que les

salles sont seulement disponibles entre 12h00 et 17h00 du lundi au vendredi,

formulez ce problème comme un CSP (constraint solving problem), c’est-à-dire

en spécifiant les variables, les domaines et les contraintes. Suggérez alors une

heuristique pour résoudre ce problème et expliquer pourquoi pensez-vous que

votre heuristique peut résoudre un tel problème.

Le problème consiste à choisir une salle pour chaque cours.

Variables : S1, …, S10 (les différentes salles pour chacun des cours)

D1, …, D10 (les différentes heures de début pour chacun des cours)

F1, …, F10 (les différentes heures de fin pour chacun des cours)

Domaine : Si : {1 à 5}

Di : {12 à 16h30} (Si on suppose des cours d’une demi heure)

Fi : {12h30 à 17} (Si on suppose des cours d’une demi heure)

Contraintes : Pour tous les i,j, si (Fi >= Fj > Di OU Di <= Dj < Fi) alors (Si != Sj)

Di < Fi, Di >= 12 (pour 12h00), Fi <= 17 (pour 17h00)

Vous pouvez utiliser n’importe quelle heuristique vue en classe, comme par exemple

l’heuristique des conflits minimums (min-conflicts).

file:///D|/Mes%20Cours/05_ENIT%20-%20S8/Intelligence%20Artificielle/Elements%20Internet/Exercice2(2002).html

Exercice 2 à rendre pour le 2 avril à 18 h. (en individuel et vraiment en indivudel--merci)

1. Soit à considérer une version du milk/banana/drill, comme vue en cours, dans laquelle on inclut la monnaie (au moins de façon assez simple). Partant de là,

a) Soit CC la carte de crédit que lágent peut utiliser pour acheter un objet. Modifier alors Buy de manière à ce que lágent puisse avoir sa carte de crédit pour acheter ce quíl veut.

b) Écrire lópérateur PickUp qui permet à lágent de posséder (Have) un objet si cet objet est portable et si cet objet est localisé à la même place que lágent.

c) Supposons maintenant que la carte de crédit est à la maison mais que Have(CC) is initiallement faux. Construire un plan partiellement ordonné qui réalise le but. Un tel plan doit montré les contraintes dórdre et les liens causaux.

d) Expliquez en détails, ce qui arrive durant le processus de planification quand lágent explore un plan partiel dans lequel il quitte la maison sans la carte de crédit.

Cet exercice, est pris du livre Russel et Norvig. Cést léxercice 11.2 page 364, dont jái fait une traduction libre.

2. Dans cet exercice, nous essayons de faire de la planification dans le monde du robot Shakey tel quíl est décrit en page 361 figure 11.15.

a) Décrire les 6 actions de ce robot telles que données en page 360-361 du Russel et Norvig, en utilisant la notation du calcul des situations;

b) Translatez ces 6 actions dans le langage STRIPS;

c) Contruisez a plan pour Shakey qui déplace Box2 de la configuration de départ présentée en figure 11.15 à la configuration finale qui est Room2;

d) Supposons que Shakey a n boites dans une salle et quíl a besoin de les déplacer dans une autre salle. Quelle est la complexité du processus

file:///D|/Mes%20Cours/05_ENIT%20-%20S8/Intelligence...rtificielle/Elements%20Internet/Exercice2(2002).html (1 sur 2) [15/01/2008 22:30:03]

file:///D|/Mes%20Cours/05_ENIT%20-%20S8/Intelligence%20Artificielle/Elements%20Internet/Exercice2(2002).html

de planification en termes de n.

Cet exercice, est pris du livre de Russel et Norvig. Cést léxercice 11.7 page 365, dont jái fait une traduction libre.

3. Deux astronomes localisés à différents endroits du monde, font des mesures M1 et M2 du vrai nombre d´étoiles N dúne petite région du ciel et ce, en utilisant leur téléscopes. Chaque téléscope peut être aussi en panne de focus (évenements F1 et F2 avec une probabilité f. Si un téléscope est OUT en focus, alors lástronome peut compter en moins 3 ou plus d´étoiles (ceci signifie que si le vrai nombre d´étoiles N est inférieur ou égal à 3, alors lástronome comptera 0).

a) Dessinez alors le réseau de croyances représentant cette information;

b) Donnez une table de probabilités conditionnelles pour le noeud M1. Pour la simplicité. considérez seulement N = 1,2, ou 3 et les probabilités que M1 = 0,1,2 ou 3.

c) Supposons maintenant que M1 =1 et M2 = 3. Quelles sont les possibles valeurs de N? Indice: vous pouvez soit faire une raisonnement en avant de manière à essayer chaque valeur possible de N et voir si les mesures M1 =1 et M2 = 3 sont possibles, ou vous pouvez énumérer les états et voir (en faisant un raisonnement en arrière cette fois-ci) les valeurs possibles de N pour chaque état.

Cette exercice st inspiré de léxercice 15.3 du Norvig et Russel.

4. Supposons quún docteur effectue des tests pour déterminer si une femme est enceinte. Le test donne soit un résultat positive soit un résultat négatif. La plupart du temp, le test est très précis : seulement un résultat positif parmi 100 est incorrect et seulement un résultat négatif parmi 1000 est incorrect. Étant donné que le docteur a trouvé que 70% des femmes qui viennent le consulter pour des tests de grossesse sont en fait enceintes, utilisez la règle de Bayes pour calculer la probabilité quúne femme (que le docteur voit pour ce genre de tests) soit enceinte dans le cas où le test de grossesse ait donné un résultat positif.

file:///D|/Mes%20Cours/05_ENIT%20-%20S8/Intelligence...rtificielle/Elements%20Internet/Exercice2(2002).html (2 sur 2) [15/01/2008 22:30:03]

1

Corriger Exercice 2 (2002)

Question 1

a) Op(ACTION : Buy(x), PRECOND : At(agent,store) � Sells(store,x) � Have(CC),

EFFECT : Have(x))

b) Op(ACTION : PickUp(x), PRECOND : Portable(x) � At(agent,loc) � At(x,loc),

EFFECT : Have(x))

c)

d) Lorsque l’agent explore un « plan partiel » où il quitte la maison (Go(SM)) sans la

carte de crédit, il ne travaille pas inutilement pour autant! Il est dans ce cas dans une

position où il reste une précondition à remplir (Have(Agent,CC)). Il n’a qu’à rajouter

l’action PickUp(CC). Ce qui est intéressant dans un plan partiel, c’est que l’ordre

d’insertion des étapes n’a rien à voir avec l’ordre d’exécution du plan! L’action

PickUp(CC) peut donc être insérée avant Go(SM) pour respecter la précondition

At(Agent,Home).

Start

Pickup(cc) Go(SM)

Buy(milk)

Finish

At(Agent,Home) At(CC,Home)

At(Agent,Home) At(Agent,Home)

Have(Agent,CC), At(Agent,SM), Sell(SM,Milk)

Have(Milk)

2

Question 2 a) � x, y, a, s At(Shakey, y, Result(a, s)) �

(At(Shakey, x, s) � � r In(x, r) � In(y, r) � a = Go(x, y))

� (At(Shakey, y, s) � a � Go)

� x, y, b, a, s (b � Shakey) � (At(b, y, Result(a, s)) �

(At(b, x, s) � � r In(x, r) � In(y, r) � Pushable(b) �

a = Push(b, x, y)) � (At(b, y, s) � a � Push))

� x, b, a, s b � Floor � (On(Shakey, b, Result(a, s)) �

(On(Shakey, Floor, s) � At(Shakey, x, s) � At(b, x, s) �

Climbable(b) � a = Climb(b)) � (On(Shakey, b, s) � a � Down(b)))

� a, s On(Shakey, Floor, Result(a,s)) �

(� b On(Shakey, b, s) � a = Down(b))

� (On(Shakey, Floor, s) � a � Climb)

� l, a, s TurnedOn(l, Result(a, s)) �

(� b, x On(Shakey, b, s) � At(b, x, s) � At(l, x, s) � a = TurnOn(l))

� (TurnedOn(l, s) � �(� b, x On(Shakey, b, s) � At(b, x, s) � At(l, x, s) �

a = TurnOff(l))

� x Pushable(x) � Box(x)

� x Climbable(x) � Box(x)

b) Op(ACTION : Go(x, y), PRECOND : At(Shakey, x) � In(x, r) � In(y, r),

EFFECT: At(Shakey, y) � �(at(Shakey, x)))

Op(ACTION: Push(b, x, y), PRECOND: At(Shakey, x) � At(b, x) � Pushable(b)

� In(x, r) � In(y, r),

EFFECT: At(b, y) � At(Shakey, y) � �At(b, x) � �At(Shakey, x))

Op(ACTION: Climb(b), PRECOND: At(Shakey, x) � At(b, x) � Climbable(b),

EFFECT: On(Shakey, b) � �On(Shakey, Floor))

Op(ACTION: Down(b), PRECOND: On(Shakey, b),

EFFECT: On(Shakey, Floor) � �On(Shakey, b))

3

Op(ACTION: TurnOn(l), PRECOND: On(Shakey, b) � At(Shakey, x) � At(l, x),

EFFECT: TurnedOn(l))

Op(ACTION: TurnOff(l), PRECOND: On(Shakey, b) � At(Shakey, x) � At(l, x),

EFFECT: �TurnedOn(l))

4

c)

Début

Go(x, Door3)

At(Shakey, x) � In(x, Room3) � In(Door3, Room3)

Push(Box2, PosBox2, Door1)

Go(Door3, Door1)

� In(Door3, Corridor) � In(Door1, Corridor)

Go(Door1, PosBox2)

� In(Door1, Room1) � In(PosBox2, Room1)

Push(Box2, Door1, Door2)

Push(Box2, Door2, y)

Fin

At(Box2, Room2)

At(Box2, PosBox2) � Pushable(Box2)� In(PosBox2, Room1) � In(Door1, Room1)

Pushable(Box2) � In(Door1, Corridor)� In(Door2, Corridor)

Pushable(Box2) � In(Door2, Room2) � In(y, Room2)

At(Shakey, Door3)

At(Shakey, Door1)

� At(Shakey, PosBox2)

� At(Shakey, Door1) � At(Box2, Door1)

At(Shakey, Door2) � At(Box2, Door2) �

d) Comme on peut le voir sur le plan précédent, l’agent doit accomplir 3 actions Go et 3

actions Push pour chacune des boîtes. Pour ces 6 actions, il y a 24 pré-conditions à

remplir. Dans l’algorithme de planification de la page 356, on peut voir qu’il y a une

5

boucle principale. L’algorithme effectue un tour de boucle pour chacune des pré-

conditions, ce qui donne 24 tours de boucle. La seule autre boucle dans l’algorithme est

pour la gestion des conflits. Toutefois, comme il n’y a qu’un plan possible par boîte, et

que les plans ne peuvent pas vraiment être effectué en parallèle, c’est-à-dire que l’agent

devra déplacer les boîtes une par une, alors on peut faire la supposition qu’il n’y aura que

très de conflits ou même aucun. En fin de compte, on arrive donc à 24 tours pour une

boîte fois n boîtes plus la pré-condition pour l’état de fin. Ce qui donne : 24n + 1. Ceci

donne donc une complexité dans l’ordre de n, O(n). Il est à noter toutefois que la

constante cachée sera très grande, due aux nombreuses étapes effectuées à chaque tour,

mais que cette constante est indépendante du nombre de boîtes.

Question 3 a)

F1 F2N

M1 M2

b)

N F1 P(M1 = 0) P(M1 = 1) P(M1 = 2) P(M1 = 3)

0 V 1 0 0 0

1 V 1 0 0 0

2 V 1 0 0 0

3 V 1 0 0 0

0 F 1 0 0 0

1 F 0 1 0 0

2 F 0 0 1 0

3 F 0 0 0 1

c) N 6

6

Question 4 P(Enceinte) = 0,7

P(+ | Enceinte) = 0,99

P(+ | �Enceinte) = 0,001

P(+) = P(+ | Enceinte) * P(Enceinte) + P(+ | �Enceinte) * P(�Enceinte)

= 0,99 * 0,7 + 0,001 * 0,3

= 0,6933

P(Enceinte | +) = (P(+ | Enceinte) P(Enceinte)) / P(+)

= (0,99 * 0,7) / 0,6933

= 0,999567287

Documents

Examen mi-session Intelligence Artificielle II (IFT …lafamilledurefuge.free.fr/doc/S8/Intelligence Artificielle/DS 2001... · Examen mi-session Intelligence Artificielle II (IFT-17587)