L'exploration combinatoire guidée par des heuristiques est caractéristique des premiers développements de l'Intelligence Artificielle. Il s'agissait alors d'utiliser la puissance de l'ordinateur pour explorer toutes les alternatives qui s'offraient au moment de juger du meilleur plan à adopter. L'exemple le plus connu est celui du jeu d'échecs. Mais même l'ordinateur le plus puissant du monde est incapable de gérer la complexité intrinsèque, liée à l'explosion combinatoire, de la plupart des problèmes de planification (que ce soit le jeu d'échecs ou le problème bien connu du voyageur de commerce). L'attitude adoptée par les chercheurs de l'époque a été de renoncer à l'optimalité, pour tenter de trouver dans chaque cas une solution acceptable dans un temps raisonnable. Ils utilisèrent des heuristiques, des recettes approximatives, pour guider les choix et éviter une exploration exhaustive de l'espace des possibilités. Par exemple, pour le jeu d'échecs, une heuristique possible consiste à accorder des valeurs aux pièces, et à ne pas explorer les suites des actions qui mettent en péril des pièces trop précieuses.
Cette approche est moins utilisée maintenant. Trouver de bonnes heuristiques est loin d'être évident, et l'avantage obtenu sur les humains grâce à la puissance d'exploration est souvent peu significatif. De plus, il devenait de plus en plus difficile de qualifier d'intelligents de tels programmes si "brutaux". Les chercheurs se sont tournés alors vers des techniques plus élaborées.
Pendant que la plupart des chercheurs travaillaient à repousser les limites de la combinatoire, une équipe de l'université de Stanford s'efforçait dès 1965 de traiter un problème pour lequel aucune solution algorithmique, même hautement combinatoire, n'était connue. Il s'agissait d'associer au spectre de masse la formule développée du corps chimique correspondant. Leur programme, DENDRAL, constitue sans doute le premier système expert jamais conçu.
L'idée qui consistait à traiter des problèmes difficiles en utilisant la connaissance des experts n'était pas nouvelle. Elle avait déjà été employée par exemple pour le jeu d'échecs. Non, l'idée nouvelle, c'était de rendre cette connaissance explicite. Au lieu d'être traduite sous forme d'algorithme puis noyée dans le code du programme, la connaissance de l'expert est exprimée sous forme de règles. Le programme va lire ces règles, et il va raisonner en tentant de les enchaîner jusqu'à obtenir un résultat. Dans le cas de DENDRAL, le programme enchaînait des règles de manière à associer une formule chimique au spectre observé.
Certes, le travail de l'ordinateur reste en grande partie combinatoire. Mais cette fois, la connaissance experte du domaine (par ex. la chimie) n'intervient pas pour guider les choix, elle devient l'objet de ces choix. On peut alors plus facilement qualifier l'ordinateur d'intelligent : en prétendant que la combinatoire qu'il effectue est exactement celle qui est effectuée par les experts humains (ce point sera discuté ci-dessous).
Dès 1958, John McCarthy qui est l'un des fondateurs de l'I.A., a doté cette discipline d'un langage totalement nouveau, LISP, que certains ont pu considérer comme "parfait" à bien des égards (contrairement à FORTRAN ou COBOL qui étaient nés quelques mois plus tôt). LISP est un langage fonctionnel, inspiré des travaux de mathématiciens comme Kurt Gödel. Dans LISP, aucune distinction de forme n'est faite entre les instructions et les données. Tout est élément d'une liste. C'est le cas du programme lui même, ce qui ouvre la possibilité pour le programmeur d'écrire des programmes qui se modifient eux-mêmes en cours d'exécution !
L'autre langage de l'Intelligence Artificielle est certainement Prolog, qui a été créé en partie en France au début des années 1970. Programmer en Prolog, c'est programmer en logique. Ce qui veut dire : fournir une connaissance à la machine, au lieu de lui indiquer en détail ce qu'elle doit faire. La machine utilise le programme écrit en Prolog de la même façon que le système expert utilise la connaissance explicite fournie par l'expert humain et qui est contenue dans les règles. On parle de programmation déclarative, par opposition à la programmation impérative employée avec tous les autres langages.
Mais les listes ou la logique peuvent se révéler parfois inadéquats pour représenter les connaissances. Les chercheurs de l'I.A. ont eu recours à des langages leur permettant de représenter des graphes conceptuels, c'est-à-dire des langages dans lesquels ont peut exprimer ce que sont les concepts du domaine traité, leurs caractéristiques et leurs relations. Ces travaux ont conduit aux langages à objets (par exemple SmallTalk) qui sont actuellement très largement employés en génie logiciel.
Même si des langages comme LISP, Prolog ou SmallTalk se rapprochent des exigences de la pensée humaine, nous sommes encore très loin de la programmation au moyen de la langue naturelle. Les difficultés liées à la compréhension des langues humaines ont été considérablement sous-estimées au départ. Jusqu'en 1964, des efforts importants ont été consacrés à la recherche en traduction automatique (motivés en partie par la guerre froide et la nécessité d'accumuler des informations sur l'autre camp), lorsqu'il apparut assez soudainement que tout espoir de traduire sans une compréhension fine du sens du texte, réalisée à partir d'une base de connaissances, était tout à fait vain. Depuis cette époque, les efforts se sont surtout concentrés sur d'autres aspects du traitement des langues, notamment le traitement de la morphologie des mots et de la phrase.
La stratégie que l'on retrouve à tous les niveaux du traitement automatique de la langue consiste à reconnaître les "briques" et leur combinaison. Mais cela est loin d'être simple, car les langues semblent être extrêmement complexes, soit intrinsèquement, soit du fait de notre ignorance de leurs mécanismes.
Une langue s'appuie sur à peine quelques dizaines de phonèmes. Mais parmi toutes les combinaisons imaginables de ces briques de base, seules certaines sont acceptables dans cette langue. Des règles qui interdisent par exemple la succession "t"-"p" dans les mots du français sont précieuses lorsqu'il s'agit de segmenter un flot de parole orale ou de reconnaître des mots mal orthographiés. On retrouve la dualité brique/combinaison dans la structure de la phrase. Dans ce cas ce sont des morphèmes (les mots, les marques de temps, etc.) qui sont combinés selon les règles de la syntaxe. Reconnaître la syntaxe est un premier pas vers la compréhension du sens (identification du sujet, d'une subordonnée, etc.). Par exemple les deux sens de la phrase "La petite brise la glace" correspondent à deux structures syntaxiques différentes.
Dans un traitement automatique, la structure syntaxique va être représentée par un arbre. A partir des noeuds de cet arbre, on peut ensuite, dans un traitement sémantique, espérer reconnaître une structure de prédicat logique : "Le fils de Pierre aime Marie" [[[Le fils] [de Pierre]] [aime Marie]] aimer(jean, marie). Ce prédicat est lui même une brique dans une base de connaissance fournie à l'ordinateur. La machine peut alors reconnaître un argument logique dans cette phrase. Elle pourra peut-être déduire que Jacqueline risque d'être jalouse de Marie.
La robotique n'est pas à proprement parler une branche de l'Intelligence artificielle. Lorsqu'il s'agit de doter le robot de capacités de perception ou d'action, des disciplines comme le traitement du signal ou la mécanique sont également concernées. En revanche, lorsqu'on veut que le robot acquière une certaine autonomie comportementale, qu'il ait des capacités de résolution de problème, qu'il se préoccupe de sa viabilité (énergie, repérage, dangers, ...) on doit le doter de connaissances et de moyens de raisonner sur ces connaissances, bref : le doter d'une intelligence artificielle.
Mais la robotique est aussi une occasion pour certains chercheurs du courant Vie Artificielle d'explorer non pas l'intelligence telle qu'on la voit à l'oeuvre chez les humains ou les animaux, mais l'intelligence telle qu'elle pourrait être. Ces chercheurs tentent d'utiliser les contraintes de la viabilité pour faire évoluer des robots (réels ou virtuels) qui découvriront eux-mêmes des moyens originaux pour résoudre des problèmes. Certaines de ces créatures (penser à des fourmis artificielles) peuvent par exemple découvrir le moyen de résoudre des tâches collectivement, comme trouver un chemin optimal vers une source d'énergie (dans un environnement physique) ou détourner les ressources CPU d'un ordinateur (dans un environnement virtuel), sans qu'aucun individu ait une représentation de la solution dans son ensemble.
En prévoyant qu'avant la fin du XXdeg. siècle un ordinateur pourrait se faire passer pour un humain dans une communication à distance, Alan Turing pensait à un programme qui aurait appris par lui-même, au contact des humains, toutes les connaissances nécessaires. Il n'imaginait pas les difficultés considérables qui attendaient ceux qui, par la suite, se sont préoccupé d'apprendre aux machines à apprendre.
Avec le recul , on s'aperçoit que les programmes d'apprentissage utilisent fondamentalement deux types de méthodes pour extraire, à partir des données qui leur sont présentées, les formes qui sont "dignes" d'être mémorisées. La première méthode consiste à repérer des régularités statistiques, et à mémoriser ces régularités. Cela permet par exemple de former des concepts à partir d'une masse d'exemples. Un concept appris sera une conjonction d'attributs communs à tout un groupe d'exemples jugés suffisamment similaires. Un programme peut ainsi grouper les cas de maladie mentale et fournir les listes de symptômes (ou des arbres de décision) qui permettent de caractériser les groupes obtenus. La même technique peut permettre d'apprendre un plan d'action efficace ou d'apprendre à reconnaître une forme visuelle sous des apparences différentes.
La deuxième méthode pour apprendre est fondamentalement différente. Elle consiste à reconnaître une structure dans les données fournies, et à mémoriser cette structure. L'apprentissage par l'explication, par exemple, part de la description d'un objet particulier (un seul peut suffire). Il démontre par exemple qu'il s'agit d'un véhicule parce qu'il peut se mouvoir à l'aide de ses chenilles, qu'il comporte des sièges et que son moteur à énergie solaire le rend autonome. Il forme alors une spécialisation du concept de véhicule, et il pourra utiliser ce nouveau concept dans l'avenir pour reconnaître plus vite d'autres objets du même type (même si ces objets n'ont pas la même couleur, puisque la couleur n'est jamais intervenue pour démontrer qu'on avait affaire à un véhicule).
Dans ces deux méthodes, la méthode statistique et la méthode par reconnaissance de structure, l'existence d'une connaissance préalable est essentielle, soit pour caractériser les concepts invariants, soit pour reconnaître la structure. Toute la difficulté consiste à doter la machine de cette connaissance, des moyens de mesurer les ressemblances, et des moyens d'apparier les structures. Nous sommes encore très loin du rêve de Turing sur ce plan.
L'intelligence peut être source d'inspiration ou objet de modélisation. De nombreux chercheurs se sont donné comme objectif de reproduire sous forme de programme certains processus à l'oeuvre dans le cerveau humain. On peut ainsi chercher à reproduire des capacités de raisonnement, de mémorisation, de décision ou des capacités linguistiques, en prétendant que le programme est une image fidèle du processus mis en oeuvre dans le fonctionnement cérébral. On peut par exemple suggérer que les actions que nous enchaînons au restaurant (choix d'une table, lecture du menu, commande, commande des desserts, paiement, etc.) sont gouvernées par un script standard maintenu en mémoire. Puis laisser entendre que le programme qui reproduit la performance humaine au moyen de la sélection d'un script approprié reproduit ce que les humains réalisent de manière automatique.
Pendant longtemps, il a fallu se contenter de modèles du raisonnement et de la mémoire, sans qu'aucun chercheur parvienne à proposer de modèle crédible pour un type de processus pourtant extrêmement banal. L'association, l'analogie, la généralisation, que nous effectuons continuellement, instantanément et sans effort, restaient hors d'atteinte des tentatives pour réaliser des modélisations cognitives plausibles. Les années 1980 ont connu un bouleversement à cet égard. Certains chercheurs ont tenté de s'inspirer et de faire des modèles non pas de l'intelligence en tant que processus, mais du cerveau lui même ! L'idée était ancienne, mais elle n'est devenue crédible que lorsque certains sont parvenus à résoudre des problèmes non triviaux de classification et de généralisation au moyen de neurones artificiels.
Le connexionnisme est une branche de l'Intelligence Artificielle qui étudie les capacités, d'une richesse insoupçonnée au départ, des réseaux de neurones artificiels. Ces réseaux ont des capacités à peu près complémentaires de celles des autres techniques de l'I.A. Leur principal pouvoir est cette capacité de généraliser les exemples qui leur sont présentés, ce qui les rend très utiles notamment pour classifier (ils peuvent classer une forme visuelle qu'ils n'ont jamais vue auparavant, parce qu'elle ressemble globalement à certains exemples appris). Ils peuvent plus généralement apprendre un "mapping" quelconque d'un ensemble topologique dans un autre, en interpolant par continuité entre les exemples qui leur sont donnés.