M1 Flashcards
Qu’est-ce qu’un agent réflexe (reflex agent) ?
C’est un agent qui agit en fonction de comment le monde lui apparaît (sa perception actuelle).
Qu’est-ce qu’un agent basé sur la recherche (planning agent) ?
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.
Qu’est-ce qu’un problème de recherche et comment le définir formellement ?
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
Qu’est-ce que la modélisation d’un problème ?
C’est l’opération consistant à encoder notre problème de base à l’aide d’une formalisation particulière.
Qu’est-ce que le niveau d’abstraction d’un problème ?
C’est la simplification de la réalité qui est faite en définissant le modèle.
Qu’est-ce que la taille de l’ensemble des états (ou actions) ?
C’est le nombre d’éléments distincts dans l’ensemble des états (ou actions) du problème de recherche.
Qu’est-ce qu’un graphe des états ?
C’est la représentation d’un problème de recherche en un graphe, en liant les états par leurs actions.
Qu’est-ce que la représentation en arbre ?
C’est la représentation du problème en arbre, sur base du graphe des états.
Qu’est-ce que la recherche en profondeur (DFS: depth first search) ?
C’est l’algorithme de recherche consistant à retirer systématiquement le dernier noeud ajouté à la fringe.
Qu’est-ce que la recherche en largeur (BFS: breadth first search) ?
C’est l’algorithme de recherche consistant à retirer systématiquement le plus ancien nœud de la fringe.
Qu’est-ce que la recherche à profondeur itérée (IDS: iterative deepening search) ?
C’est l’algorithme de recherche qui exécute des DFS en augmentant itérativement la profondeur maximale.
Qu’est-ce que la recherche à coût uniforme (UCS: uniform cost search) ?
C’est l’algorithme de recherche consistant à retirer systématiquement le nœud ayant le plus faible coût.
Qu’est-ce qu’une stratégie de recherche avec information (informed search) ?
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.
Qu’est-ce qu’une fonction heuristique ?
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.
Qu’est-ce que la recherche gloutonne (greedy best-first search) ?
C’est l’algorithme de recherche consistant à retirer le nœud le moins coûteux selon l’heuristique.
Qu’est-ce que la stratégie de recherche A* (A-star search) ?
C’est la stratégie qui consiste à retirer le noeud en fonction des coûts passés et d’une heuristique.
Qu’est-ce qu’une heuristique admissible ?
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.
Que peut-on dire sur l’optimalité d’une recherche A* en arbre ?
Avec une heuristique admissible, on a la garantie qu’une recherche A* en arbre est optimale.
Qu’est-ce que la relaxation d’un problème ?
C’est le fait de retirer certaines contraintes à un problème afin de le rendre plus facile à resoudre.
Qu’est-ce qu’une collection d’heuristique ?
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) ).
Qu’est-ce qu’une heuristique dominante ?
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).
Qu’est-ce qu’une heuristique consistante ?
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’).
