Intelligence Artificielle AI - Prolog : Chapitre3 Résolution de problèmes en IA
Télécharger PDFIntroduction à l’Intelligence Artificielle : Résolution de Problèmes par les Jeux à un Joueur
1. Modéliser un problème en Intelligence Artificielle
Un problème en IA est modélisé en considérant ses différents états possibles. Les états correspondent aux diverses configurations obtenues en combinant les paramètres du problème. Résoudre un problème revient à appliquer les opérateurs disponibles pour passer d’un état initial (I) à un état final (F).
2. Définition d’un problème P
Un problème P est défini par trois éléments :
- I : état initial du problème
- O : les opérateurs permettant de passer d’un état à un autre
- F : état final du problème, c’est-à-dire la solution à atteindre
Un problème est une situation où la suite des actions à effectuer n’est pas immédiatement évidente. Pour le représenter, il faut abstraire la complexité du monde réel afin de simplifier l’espace des états possibles.
3. Les problèmes à état unique
Les problèmes à état unique sont définis par quatre éléments :
- Un état initial
- Des opérateurs (ou une fonction successeur s(x))
- Un test-but : une fonction permettant de vérifier si un état est la solution
- Un coût-chemin : une méthode pour déterminer le meilleur chemin vers la solution si plusieurs existent
Une solution est une séquence d’opérateurs appliqués à partir de l’état initial pour atteindre l’état final.
4. Exemple : Le jeu du Taquin
Le Taquin est un problème à état unique. Il se caractérise par :
- État initial : positions des 8 pièces dans une des 9 cases
- Opérateurs : déplacer la case vide selon quatre directions possibles
- Test-but : vérifier si l’état courant correspond à l’état final
- Coût-chemin : chaque déplacement coûte 1, donc le coût total est égal au nombre de déplacements
L’application des opérateurs sur les états permet de construire un arbre de recherche.
5. Espace et graphe d’états
La résolution d’un problème P = (I, O, F) consiste à chercher un chemin de l’état initial (I) à l’état final (F) dans le graphe d’états. Ce graphe est défini par :
- Les sommets représentant les états possibles
- Les arcs représentant l’application des opérateurs pour passer d’un état à un autre
6. Méthodes de recherche
Les méthodes de recherche se divisent en deux catégories :
- Explorations non informées (méthodes aveugles) :
- Recherche en largeur
- Recherche en profondeur
- Recherche en profondeur limitée
- Recherche par approfondissement itératif
- Explorations informées (méthodes heuristiques) :
- Utilisation d’informations supplémentaires pour guider la recherche
7. Critères d’évaluation des méthodes de recherche
Les méthodes de recherche sont évaluées selon quatre critères :
- Complétude : la méthode garantit-elle la découverte d’une solution si elle existe ?
- Complexité en temps : combien de temps faut-il pour trouver la solution ?
- Complexité en espace : quel espace mémoire est nécessaire pour la recherche ?
- Optimalité : la méthode trouve-t-elle la meilleure solution si plusieurs existent ?
Les complexités en temps et en espace sont souvent exprimées en fonction de :
- b : facteur de branchement maximum de l’arbre de recherche
- d : profondeur du nœud solution
- m : profondeur maximale de l’espace de recherche (peut être infinie)
8. Recherche en largeur (Breadth-First Search)
Principe : les nœuds les moins récemment générés sont explorés en premier. L’arbre est construit niveau par niveau, de manière horizontale.
Stratégie : étendre le nœud le moins profond.
Implémentation : insérer les successeurs à la fin de la file d’attente.
Évaluation :
- Complétude : oui (si b est fini)
- Complexité en temps : O(bd) (exponentielle en fonction de d)
- Complexité en espace : O(bd) (tous les nœuds doivent être mémorisés)
- Optimalité : oui si le coût est de 1 par étape, mais généralement non optimale
9. Recherche en profondeur (Depth-First Search)
Stratégie : étendre le nœud le plus profond.
Implémentation : insérer les successeurs en tête de la file d’attente.
Risque : cycles infinis. Il faut éliminer les nœuds déjà rencontrés pour éviter cette situation.
Évaluation :
- Complétude : non (échec dans les espaces infinis ou sans cycles)
- Complexité en temps : O(bm) (importante si m est beaucoup plus grand que d)
- Complexité en espace : O(b*m), donc linéaire
- Optimalité : non
10. Recherche en profondeur limitée
Principe : algorithme de recherche en profondeur avec une limite de profondeur d’exploration L.
Implémentation : les nœuds de profondeur L n’ont pas de successeurs.
Évaluation :
- Complétude : oui si L ≥ d
- Complexité en temps : O(bL)
- Complexité en espace : O(b*L)
- Optimalité : non
11. Recherche itérative en profondeur
Problème : la recherche en profondeur limitée nécessite de fixer correctement la valeur de L.
Principe : essayer toutes les valeurs possibles de L, en commençant par L = 0 et en incrémentant progressivement la limite.
Cet algorithme combine les avantages de la recherche en largeur et en profondeur :
- Complet et optimal comme la recherche en largeur
- Économe en espace comme la recherche en profondeur
Il est particulièrement utile lorsque l’espace de recherche est grand et que la profondeur de la solution est inconnue.
Évaluation :
- Complétude : oui
- Complexité en temps : O(bd)
- Complexité en espace : O(b*d)
- Optimalité : oui si le coût est de 1 par étape
12. Vers les méthodes heuristiques
Les méthodes non informées, bien qu’efficaces, peuvent rencontrer des limites pratiques en termes de temps d’exécution et d’espace mémoire. Pour accélérer la recherche, on utilise une heuristique, qui signifie "aider à découvrir".
Les méthodes heuristiques exploitent des informations supplémentaires spécifiques au domaine d’application pour guider la recherche.
13. Recherche heuristique
La recherche heuristique est une approche courante en IA. Pour un problème particulier dans un domaine d’application, elle repose sur :
- La définition d’une heuristique
- L’utilisation d’une fonction de coût pour chaque opérateur
- La recherche du meilleur chemin (le moins coûteux)
Les heuristiques sont inspirées ou déduites du domaine d’application.
14. Algorithme A*
Principe : construction progressive de l’arbre des solutions et choix de la branche optimale à chaque étape.
Objectif : trouver un chemin solution, un chemin optimal rapidement et un bon chemin rapidement.
Heuristique : fonction d’estimation du coût entre un nœud et le but (le nœud à atteindre).
15. Jeux et Intelligence Artificielle
Certains jeux sont adaptés à l’étude par des techniques d’IA, notamment ceux à :
- Somme nulle
- Information complète et parfaite
Exemples de jeux étudiés :
- Jeux asynchrones à somme nulle : échecs, dames, dominos, jeux de cartes (Poker, rami, belote, tarot)
- Jeux synchrones à somme nulle : feuille-papier-ciseaux
16. Théorie des jeux
La théorie des jeux est une branche des mathématiques qui étudie les situations où plusieurs personnes doivent prendre des décisions influençant un résultat commun. Elle repose sur deux facteurs principaux : la coopération et la compétition.
Trois classes de problèmes sont distinguées :
- Jeux de coopération à l’état pur : décisions concordantes pour un intérêt général
- Jeux de compétition à l’état pur : duels à deux joueurs avec des intérêts strictement opposés
- Jeux de compétition et de coopération : situations réelles où les deux facteurs sont présents
17. Informations dans les jeux
Jeux à information complète : chaque joueur connaît ses actions possibles, celles des autres joueurs, les gains résultants et les mouvements des adversaires.
Jeux à information parfaite : les joueurs ont connaissance détaillée de toutes les actions effectuées avant leur tour.
18. Gains et tours dans les jeux
Jeux à somme nulle : ce que gagne un joueur est perdu par un autre, la somme algébrique des gains est constante.
Jeux à somme non nulle : certaines issues sont globalement profitables ou dommageables pour tous les joueurs.
Jeux synchrones : les joueurs décident simultanément sans connaître les actions des autres.
Jeux asynchrones (alternatifs) : les joueurs décident à tour de rôle, avec connaissance des actions précédentes des adversaires.
FAQ
Qu’est-ce qu’un problème à état unique en IA ?
C’est un problème où l’on peut définir un état initial, des opérateurs pour passer d’un état à un autre, un test-but pour identifier la solution et un coût-chemin pour évaluer la qualité des solutions.
Quelle est la différence entre un jeu à somme nulle et un jeu à somme non nulle ?
Dans un jeu à somme nulle, les gains des joueurs sont strictement opposés : ce que l’un gagne, l’autre le perd. Dans un jeu à somme non nulle, certaines issues peuvent être avantageuses ou désavantageuses pour tous les joueurs.
Pourquoi la recherche itérative en profondeur est-elle souvent préférée dans les jeux ?
Elle combine les avantages de la recherche en largeur et en profondeur : elle est complète et optimale comme la recherche en largeur, mais économise l’espace mémoire comme la recherche en profondeur.