M1

Question 1

Qu’est-ce qu’un agent réflexe (reflex agent) ?

Answer 1

C’est un agent qui agit en fonction de comment le monde lui apparaît (sa perception actuelle).

Question 2

Qu’est-ce qu’un agent basé sur la recherche (planning agent) ?

Answer 2

C’est un agent qui va dérouler une série de scénarios, découlant des actions permises, afin de trouver une séquence d’actions amenant à la réalisation de l’objectif.

Question 3

Qu’est-ce qu’un problème de recherche et comment le définir formellement ?

Answer 3

C’est un problème consistant à trouver la meilleure séquence d’actions pour atteindre un état final à partir d’un état initial. Il est formellement défini par :
-S : un ensemble d’états (contenant un état initial et un/des états finaux)
-A : un ensemble d’actions
-T : (S×A -> S) : une fonction de transition décrivant le nouvel état émanant d’une action
-C : (S×A -> R) : une fonction décrivant le coût d’effectuer une action à partir d’un état

Question 4

Qu’est-ce que la modélisation d’un problème ?

Answer 4

C’est l’opération consistant à encoder notre problème de base à l’aide d’une formalisation particulière.

Question 5

Qu’est-ce que le niveau d’abstraction d’un problème ?

Answer 5

C’est la simplification de la réalité qui est faite en définissant le modèle.

Question 6

Qu’est-ce que la taille de l’ensemble des états (ou actions) ?

Answer 6

C’est le nombre d’éléments distincts dans l’ensemble des états (ou actions) du problème de recherche.

Question 7

Qu’est-ce qu’un graphe des états ?

Answer 7

C’est la représentation d’un problème de recherche en un graphe, en liant les états par leurs actions.

Question 8

Qu’est-ce que la représentation en arbre ?

Answer 8

C’est la représentation du problème en arbre, sur base du graphe des états.

Question 9

Qu’est-ce que la recherche en profondeur (DFS: depth first search) ?

Answer 9

C’est l’algorithme de recherche consistant à retirer systématiquement le dernier noeud ajouté à la fringe.

Question 10

Qu’est-ce que la recherche en largeur (BFS: breadth first search) ?

Answer 10

C’est l’algorithme de recherche consistant à retirer systématiquement le plus ancien nœud de la fringe.

Question 11

Qu’est-ce que la recherche à profondeur itérée (IDS: iterative deepening search) ?

Answer 11

C’est l’algorithme de recherche qui exécute des DFS en augmentant itérativement la profondeur maximale.

Question 12

Qu’est-ce que la recherche à coût uniforme (UCS: uniform cost search) ?

Answer 12

C’est l’algorithme de recherche consistant à retirer systématiquement le nœud ayant le plus faible coût.

Question 13

Qu’est-ce qu’une stratégie de recherche avec information (informed search) ?

Answer 13

C’est une stratégie de recherche qui utilise des connaissances spécifiques au problème afin d’orienter la recherche vers des états qui nous paraissent plus prometteurs.

Question 14

Qu’est-ce qu’une fonction heuristique ?

Answer 14

C’est l’intuition que l’on a sur le coût nécessaire pour atteindre un état final à partir d’un certain état : h(n) = coût estimé pour atteindre un état final à partir d’un état n.

Question 15

Qu’est-ce que la recherche gloutonne (greedy best-first search) ?

Answer 15

C’est l’algorithme de recherche consistant à retirer le nœud le moins coûteux selon l’heuristique.

Question 16

Qu’est-ce que la stratégie de recherche A* (A-star search) ?

Answer 16

C’est la stratégie qui consiste à retirer le noeud en fonction des coûts passés et d’une heuristique.

Question 17

Qu’est-ce qu’une heuristique admissible ?

Answer 17

Une heuristique est admissible (ou optimiste) si elle ne surestime jamais le coût pour atteindre le meilleur état final : pour tout n, 0 <= h(n) <= h*(n), où h*(n) désigne le coût optimal pour atteindre l’état final à partir de n.

Question 18

Que peut-on dire sur l’optimalité d’une recherche A* en arbre ?

Answer 18

Avec une heuristique admissible, on a la garantie qu’une recherche A* en arbre est optimale.

Question 19

Qu’est-ce que la relaxation d’un problème ?

Answer 19

C’est le fait de retirer certaines contraintes à un problème afin de le rendre plus facile à resoudre.

Question 20

Qu’est-ce qu’une collection d’heuristique ?

Answer 20

C’est le fait d’évaluer plusieurs heuristiques (au lieu d’une seule) et de prendre la meilleure pour chaque nœud : h(n) = max( h1(n), h2(n), … , hk(n) ).

Question 21

Qu’est-ce qu’une heuristique dominante ?

Answer 21

Une heuristique h2 domine une autre heuristique h1 si elle est strictement plus précise que cette dernière : pour chaque état n, h1(n) < h2(n).

Question 22

Qu’est-ce qu’une heuristique consistante ?

Answer 22

Une heuristique est consistante si sa valeur appliquée à un arc de transition ne surestime jamais le coût de l’arc : pour toute paire d’états-sucesseurs (n -> n’), h(n) - h(n’) <= c(n -> n’).