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.
2 (5 pts) Est-ce qu’un agent qui a une perception partielle de l’environnement peut être
parfaitement rationnel ? Expliquez.
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.
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.
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
b) Profondeur itératif
c) Meilleur d’abord avare
d) A*
1
S
2 5
3
A 2
2 1
B 1 C
1 3
4
4
8 1 1
G1
0
5 5
D
9 1
1
E 7 G2
6 0
6 (9 pts) Est-ce que les heuristiques suivantes sont admissibles ? Expliquez pourquoi.
a) L’heuristique de la question précédente.
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.
c) h(n) = 0 pour le jeu du 8-puzzle.
7 (3 pts) Est-ce que Hill-climbing est un algorithme complet pour résoudre un problème de
résolution de contraintes?
2
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.
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.
c) Trouvez une solution à ce problème en utilisant l’algorithme min-conflict. 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. Commencez avec la configuration
initiale : A = 2, B = 3 et C = 3.
{1,2,3}
A
A<B A<C
B C {1,2,3}
{1,2,3} B≠C
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 ?
b) Dans combien de modèles, la phrase suivante est-elle fausse ?
(RadioFonctionne ∧ AutoDémarre) ⇒ (¬PasDeGaz ∧ ¬PileMorte)
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.
3
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))
b) B(1, x, 2) et B(y, F(y), 2)
c) C(G(x, y), x) et C(z, 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)
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))
b) Position(Verre, Table, Result(a, s))
4
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
S
2 5
3
A 2
2 1
B 1 C
1 3
4
4
8 1 1
G1
0
5 5
D
9 1
1
E 7 G2
6 0
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
{1,2,3}
A
A<B A<C
B C {1,2,3}
{1,2,3} B≠C
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 Valeur de la
phrase en b) 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