Introduction I.A.

des relations avec la linguistique, les mathématiques discrètes, la psychologie cognitive, ... et … l’informatique

3

L’IA par rapport à l’Informatique

Etudie les problèmes « difficiles » ou insolubles en informatique classique

– Problèmes NP-complets ou problèmes avec solution inconnue – Des paramètres difficiles à maîtriser : connaissances incertaines, vagues, hypothétiques, ...

Exigences d’explication ou de communication sophistiquée avec les utilisateurs Objectif d’adaptation et d’apprentissage avec l’expérience ...

Historique (1)

1. Origines ... XVIIe siècle : Descartes et ses « animaux-machines » XVIIIe siècle : Leibniz définit la notion d’heuristique 1748 : La Mettrie et son « homme-machine » 1854 : Leibniz, Boole « The laws of thinking » 1910 : Whitehead, Russel « Principia Mathematica » 1930 : Gödel « Théorème d’incomplétude » 1934 : Tarsky, Herbrand ou Church « Théorème d’indécidabilité », « le lambda-calcul »

4

Historique (2)

2. Emergence de l’Intelligence Artificielle (~1938~1956) Entre 1938 et 1951 : Invention de calculateurs programmables puis ordinateurs 1954 : Turing (programme de fin de parties de jeux d’échecs) 1956 : Naissance du terme IA au Colloque à Dartmunth College 1956 : Newell, Shaw et Simon (Démonstrateur de théorèmes en logique des propositions) 1957 : Programme de jeu d’échecs

Historique (3)

3. Phase algorithmique (~1956-~1980) 1958-61 : John McCarthy (Invention du langage Lisp) 1959-61 : Newel et Simon (Résolveurs universels de problèmes - GPS) Notion pragmatique d’heuristiques Premières réalisations : jeux, calcul symbolique, recherche d’itinéraires, essais de traduction automatique, diagnostic médical,…

5

Historique (4)

4. Phase logique - “Knowledge is power” (~1970 - …) 1965 : principe de résolution de Robinson/démonstration automatique de théorèmes 1970 : Emergence des systèmes experts (MYCIN en médecine) 1972 : Langage de PROgrammation LOGique PROLOG (Colmerauer)

Historique (5)

5. Phase Objet (~1972 - ...) 1972 : Smalltalk (XEROX) issu de Lisp et Simula C++, Java, … 6. Phase Acteurs&Agents (~1977 - ...) 1977 : Hewitt : notion d’acteurs Modélisation de systèmes sociaux 7. Phase Intelligence Distribuée (~1985 - ...)

Coopération d’entités autonomes ayant chacune ses propres connaissances

8. Phase Vie Artificielle (~1995 - ...)

Les algorithmes génétiques

6

Domaines d’application (1)

Ordonnancement et planification

– Système DART de la DARPA utilisé pour la logistique des opérations «Desert storm» et «Desert shield» – Système de planification et d’ordonnancement pour l’assemblage des vols spatiaux européens (ESA)

Reconnaissance de la parole

– Interface PEGASUS du système SABRE de réservation de sièges sur American Airlines

Vision par ordinateur/Traitement d’image

– Systèmes de reconnaissance de visage par les banques, et systèmes de surveillance – Reconnaissance de l’écriture manuscrite – Inspection de bagages, construction de modèles géométriques 3D, …

Domaines d’application (2)

Systèmes de diagnostic

– Systèmes Pathfinder et Internist en médecine (supérieurs aux médecins) – Système d’aide aux consommateurs (Whirlpool)

Systèmes de conception et configuration

– Système XCON de DEC pour aider à la configuration de systèmes informatiques

Aide à la décision (e.g. financière)

– Systèmes de détection de fraude (banques (cartes de crédit), prêts, …) – Aide aux demandes de financement des particuliers

7

Domaines d’application (3)

Systèmes de classification

– SKYSURVEY de la NASA

Démonstration automatique de théorèmes Traduction automatique

– Systèmes de traduction de AltaVista ou de Google – Traduction des manuels de Caterpillar Truck Company dans 20 langues

Systèmes de jeu

– Champions du monde aux dames (anglosaxonnes), Othello, backgammon, échecs

Exemple : Jeux

8

Exemple : Robotique

Exemple : Intelligence ambiante

Omniprésence d’objets «intelligents»

– Percevant leur environnement – Communiquant entre eux – Prenant des décisions

Objectifs : Aide aux personnes

– – – – Domotique Aide aux personnes handicapées Conduite sans pilote …

9

Différentes approches de l’IA

– General Problem Solver – Algorithmes de recherche de chemins dans un espace d’état par un seul agent

• Satisfaction de contraintes

– Théorie des jeux – Réseaux de neurones – Algorithmes à base de populations

• Algorithmes génétiques • Ant Colony Optimisation

– Réseaux sémantiques – Notion d’apprentissage – Logiques / Systèmes experts

GPS (General Problem Solver) : approche 0 de l’IA

Tout problème est caractérisé par :

– Une situation de départ / Une situation d’arrivée – Chaque situation est définie par une liste de traits (attribut, valeur). – Le problème se définit comme une liste de différences qualitatives à réduire – On dispose d’opérateurs (propriété = réduire une de ces différences)

Stratégie GPS :

– On cherche la différence principale à réduire dans le problème posé et la liste des opérateurs associés – On applique à la situation chaque opérateur, du plus recommandé au moins recommandé, jusqu’à trouver un cas adapté – L’application d’un opérateur induit deux sous-problèmes qu’on traite récursivement. – La différence principale étant réduite, passer de la nouvelle situation engendrée à la situation finale cherchée

10

GPS : exemple

Problème : Je suis au Département Informatique de l’INSA de Lyon et je dois rencontrer un collègue du Département MA de l’EPFL de Lausanne Différence principale à réduire : aller de Lyon à Lausanne Problème principal : Gare de Lyon Part-Dieu -> Gare de Lausanne-CFF

– Opérateur de transport recommandé : le train

Sous-problème 1 : Département IF -> Gare de Lyon Part-Dieu Sous-problème 2 : Gare de Lausanne CFF -> Département MA de l’EPFL Sous-sous-problème 1.1 : Département IF -> Station de tramway GB

– – Opérateur : marcher à pied Opérateur : le tramway

Sous-sous-problème 1.2 : Station de tramway GB -> Gare de Lyon Part-Dieu

Sous-sous-problème 2.1 : Gare de Lausanne CFF -> Station métro – Ecublens

– Opérateur : le métro

Sous-sous-problème 2.2 : Station métro – Ecublens > Département MA de l’EPFL

– Opérateur : marcher à pied

Algorithmes de recherche de chemins dans un espace d’état

Algorithmes de recherche = catégorie générique de mécanismes de résolution de problèmes en IA. L'IA s'intéresse aux problèmes pour lesquels les étapes pour aboutir à une solution :

– ne sont pas connues a priori, – mais doivent être découvertes par l'exploration d'alternatives.

Ces problèmes peuvent se répartir en (au moins) 3 catégories :

– la recherche de chemins par un unique agent, – les jeux à n joueurs (avec n le plus souvent égal à 2 !) – les problèmes de satisfaction de contraintes.

11

Algorithmes de recherche de chemins dans un espace d’état