Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 SYSTEMES DE RESOLUTION DE PROBLEMES II2 / FILIERE ISID Dr Wided Lejouad Chaar

1 SYSTEMES DE RESOLUTION DE PROBLEMES II2 / FILIERE ISID Dr Wided Lejouad Chaari Dr Ahlem Ben Hassine Dr Inès Alaya Cours SRP Dr W. Chaari Université Manouba ENSI 2 Cours SRP Dr W. Chaari BIBLIOGRAPHIE • Henri Farreny, Malik Ghallab. Eléments d ’intelligence artificielle. Traité des Nouvelles Technologies, HERMES, 1990. Cote I-35 • Avron Barr, Edward A. Feigenbaum. Le manuel de l ’Intelligence Artificielle. Tome I, EYROLLES, 1986. Cote I-80 • Jean-Louis Laurière. Intelligence Artificielle - représentation des connaissances. Tome II, EYROLLES, 1988. Cote I-110 3 Cours SRP Dr W. Chaari INTRODUCTION GENERALE 4 Cours SRP Dr W. Chaari Naissance de l’IA • 1956 : Naissance de la discipline • Logic Theorist [Newell, Shaw, Simon] : démonstration de théorèmes de la logique des propositions. • A partir de 1956 plusieurs travaux ont vu le jour : - Jeux d ’échecs - Démonstration de théorèmes en géométrie - Traduction automatique, … • Programmes et budgets de recherche : Institute for new generation COmputer Technology 500 millions de dollars (82-90) Strategic Computer Initiative de la DARPA 1 milliard de dollars (83-90) 5 Cours SRP Dr W. Chaari L ’IA : une science cognitive • Le champ d ’investigation de l ’IA est le raisonnement : l ’IA cherche à comprendre les mécanismes de compréhension. • Les sciences cognitives d ’intéressent à ce champ : psychologie, linguistique, philosophie, neurosciences • L ’IA vérifie ses modèles et ses théories sur la connaissance et le raisonnement en programmant et non pas en expérimentant sur des sujets humains. • Thèse populaire au début des années 70 au MIT [Minsky & Winston]. • Selon Charniak et McDermott, l ’IA est l ’étude des facultés mentales à travers l ’utilisations de modèles calculatoires. 6 Cours SRP Dr W. Chaari L ’IA : une branche de l ’informatique • L ’ordinateur n ’est pas seulement un outil d ’investigation, il est l ’objet de la recherche. • La question fondamentale de l ’IA : Comment rendre les ordinateurs plus habiles ? • L ’IA cherche à concevoir des méthodes exploitant les possibilités propres des ordinateurs pour leur faire réaliser des fonctions nécessitant de l ’intelligence : accomplir des tâches considérées comme une faculté humaine et qui impliquent du raisonnement symbolique... • L ’IA cherche à concevoir des programmes en mesure de traiter des problèmes pour lesquels on ne connaît pas de méthodes de résolution directes et assurées. 7 Cours SRP Dr W. Chaari Nature de la discipline • L ’IA est une science : elle cherche à découvrir le réel, les mécanismes de raisonnement et de compréhension. Interpréter, déduire, généraliser, apprendre, … • L ’IA est une technique : elle exploite les possibilités du réel, les chercheurs en IA font de l ’ingénierie de la machine intelligente. Démontrer un théorème, diagnostiquer une maladie ou une défaillance dans un équipement, planifier la réalisation d ’une tâche complexe, analyser une image et identifier son contenu, piloter un robot dans un univers inconnu, ... 8 Cours SRP Dr W. Chaari Applications de l ’IA • Les systèmes experts, • La reconnaissance de la parole, • Les interfaces homme-machine, • La vision par ordinateur, • La robotique, • La productique, • Tâches assistées par ordinateur : conception, traduction, enseignement, … 9 Cours SRP Dr W. Chaari REPRESENTATION DES PROBLEMES 10 Cours SRP Dr W. Chaari Exemples de problèmes  Problème des 8 reines Trouver une configuration de 8 reines sans prise sur un échiquier. Aucune ligne, colonne, ou diagonale ne doit comporter plus d ’une reine. Approche par transformation de solution potentielle Partir d ’une configuration, la tester, si elle ne constitue pas une solution, la modifier localement, et recommencer. Approche constructive Procéder à chaque étape en plaçant une ke reine sans prise sur un échiquier où figurent k-1 reines. 11 Cours SRP Dr W. Chaari  Problème des 4 couleurs Colorer une carte géographique sans que deux pays voisins ne soient identiquement colorés. Approche par transformation de solution potentielle Partir d ’une coloration complète, la tester et modifier localement si de part et d ’autre d ’une frontière on trouve la même couleur. Approche constructive Colorer un ke pays, lorsque k-1 le sont déjà, en le différenciant de ses voisins déjà colorés. 12 Cours SRP Dr W. Chaari  Plan de voyage La recherche d ’un itinéraire et d ’un plan de voyage entre deux points géographiquement éloignés. S ’intéresser au moyen de quitter le local où l ’on se trouve !!! Décomposition du problème en sous-problèmes Choisir le principal mode de transport et les étapes intermédiaires qu ’il impose : changement de continent, ports ou aéroports de départ et d ’arrivée, … Le même problème se pose entre le point de départ et la première de ces étapes, que l ’on peut décomposer à son tour en recherche d ’itinéraires plus simples ... 13 Cours SRP Dr W. Chaari  Tours de Hanoi On dispose de trois axes verticaux, sur le premier sont empilés N disques par ordre de rayon strictement décroissant. Le problème consiste à obtenir le même empilement sur le 3e axe en déplaçant les disques un à un sans superposer à aucun moment un disque sur un autre plus petit. Décomposition en sous-problèmes : - déplacer l ’empilement des (n-1) plus petits disques de l ’axe 1 à l ’axe 2; - déplacer le plus grand disque de l ’axe 1 à l ’axe 3; - déplacer l ’empilement des (n-1) plus petits disques de l ’axe 2 à l ’axe 3. 14 Cours SRP Dr W. Chaari En résumé deux ingrédients sont nécessaires à la mise en œuvre d ’une procédure constructive de résolution d ’un problème : - un ensemble de moyens de transformation du problème depuis une situation (initiale ou intermédiaire) en une ou plusieurs autres situations intermédiaires; - un ensemble de moyens de test des situations obtenues par rapport à l ’objectif. La représentation d ’un problème consiste à définir formellement ces ingrédients: - les états du problème (situations initiale et intermédiaires); - l ’objectif à atteindre; - les opérateurs de transformation que l ’on choisit. 15 Cours SRP Dr W. Chaari Représentation par graphe d ’états • On structure l ’ensemble des états du problème par un graphe orienté. • Un sommet du graphe est un état du problème. • Il y a un arc du nœud u au nœud v, ssi on dispose d ’un opérateur permettant de transformer l ’état u en l ’état v. • Pour un même problème donné plusieurs représentations par graphe d ’états sont possibles. 16 Cours SRP Dr W. Chaari Représentation par graphe d ’états  Les 8 reines • La position des pièces sur l ’échiquier définit complètement l ’état du problème. • Description de chaque état par un tableau : échiquier(i, j)  {vide, reine} avec i et j entre 1 et 8 • Un opérateur est nécessaire : « placer-reine (i, j) : si échiquier (i, j) = vide alors échiquier (i, j)  reine » • 2 tests complètent la représentation du problème : « échiquier-sans-prise » : au plus 1 reine par ligne, colonne ou diagonale. « échiquier-complet » : total de 8 reines dans l ’échiquier. 17 Cours SRP Dr W. Chaari • Du nœud initial (échiquier vide) partent 64 arcs (diverses façons de placer une reine). • De chacun des successeurs partent 63 arcs (placer une 2e reine) … • Ce graphe comporte des cycles (il est possible d ’atteindre le même état de diverses façons). 1- Une solution au problème est un chemin du graphe reliant le nœud initial à un nœud quelconque vérifiant les 2 tests. - Tous les nœuds sur un tel chemin doivent vérifier la condition : « échiquier-sans-prise ». - Une grande partie des 264 états de la représentation précédente est inutile : tout état avec une reine en prise ou tout successeur d ’un tel état. 18 Cours SRP Dr W. Chaari Il faut inclure le test « échiquier-sans-prise » dans les conditions d ’application de l ’opérateur « placer-reine ». 2- Intégrer une partie des contraintes du problème à la représentation : La description suivante par un vecteur à 8 composantes : « ligne(i) = j si la iè ligne de l ’échiquier comporte une reine en colonne j, et ligne(i) = 0 si cette ligne est vide » ne permet pas de représenter un état de l ’échiquier avec plus d ’une reine par ligne. Il reste à tester l ’absence de prise en colonne et diagonale. Ainsi on réduit l ’espace d ’états. 19 Cours SRP Dr W. Chaari Représentation par graphe d ’états  Génération de plans • Dans un univers de cubes, un bras articulé muni d ’une pince permet de saisir un objet, de le déplacer, de le poser sur un plan de travail ou de l ’empiler sur d ’autres objets. • La pince ne peut prendre qu ’un seul objet à la fois, seul un objet sur lequel rien n ’est empilé peut être uploads/Philosophie/ cours-srp-ii2.pdf