I ) I INTRODUCTION

I-1) LES ORIGINES DE L‘INTELLIGENCE ARTIFICIELLE

II ) LES SYSTÈMES EXPERTS

II-1 ) CARACTÉRISTIQUES GÉNÉRALES

III ) EFFICACITÉ DES SYSTÈMES EXPERTS

IV ) LES MODELS DE RÈGLES

V ) LES SYSTÈMES DE PRODUCTION

VI ) DESCRIPTION D UN SYSTÈME DE PRODUCTION

VII ) SIGNIFICATION DE L HEURISTIQUE ET DE LA RECHERCHE HEURISTIQUE

EXEMPLE D APPLICATION

L’intelligence artificielle est la partie de l’informatique dont le but est d’élaborer des systèmes intelligent , c’est-à-dire des systèmes qui possèdent les caractéristiques que nous associons avec l’intelligence dans le comportement humain - le langage de compréhension ,l’apprentissage , le raisonnement ,le solutionnement de problèmes ,etc. nombreux sont ceux qui pensent qu’une approche de la nature de l’esprit peut être réalisée en étudiant le fonctionnement de tels programmes. Depuis que ce domaine se développa pour la première fois dans les années 50 , les chercheurs en IA ont invente des douzaines de techniques de programmation qui sont la base type de comportement. Le Manuel de l’intelligence Artificielle est une encyclopédie sur les développements majeurs des 25 premières années dans ce domaine – les Programmes, les techniques de programmation, et les concepts informatiques utilisés pour les décrire.

Qu’ils conduisent ou non à une meilleure compréhension de l’esprit, il y a de nombreuses certitudes que ces développements conduiront à une nouvelle technologie intelligente qui peut avoir des effets fantastiques sur notre société. Les systèmes d’IA expérimentaux ont déjà généré intérêt et enthousiasme dans l’industrie et sont développés commercialement. Les systèmes expérimentaux comprennent des programmes qui :

1. Résolvent des problèmes difficiles en chimie, biologie, géologie, ingénierie et médecine au niveau des spécialistes,

2.Manipulent des systèmes robotisés pour réaliser des tâches utiles, répétitives avec des moteurs et des systèmes sensitifs,

2. Répondent à des questions posées de façon simple en anglais (ou français, japonais ou tout autre langage naturel comme on les nomme).

Il y’à toute indication que des programmes d’IA utiles joueront une part importante du rôle croissant des ordinateurs dans notre vie – un rôle qui est passé, au cours d’une génération, du distant au quotidien, à des chances d ‘évoluer, plus loin encore de l’utile à l’essentiel.

Le manuel est composé de courts paragraphes qui les concepts d’IA, techniques et systèmes, groupés en chapitre qui correspondant aux subdivisions majeures du domaine. Ce premier article du Manuel traite de ce que nous entendons par " Intelligence Artificielle ", à la fois en termes d’intérêt et de méthodes de ceux qui font de la recherche en IA, et en termes de types de programmes intelligents qu’ils ont étudiés. Nous espérons que cette brève introduction élucidera non seulement l’impact fantastique potentiel de la technologie intelligent sur la société, mais aussi les possibilités que la recherche sur l’IA offre pour de nouvelles approches du Puzzle que représente l’intelligence humaine.

Les deux autres paragraphes de ce chapitre d’introduction sont envisagés comme des guides d’étude. L’in décrit le manuel lui-même – son organisation, ce qu’il contient et ce qu’il ne contient pas – alors que le second offre des guides pour trouver un matériau suffisant dans la littérature.

" Les domaines scientifiques apparaissent quant l’attention des savants se fixe sur des phénomènes. Les sciences ne sont pas définies, elles sont reconnues  " (Nowell, 1973 a,P.1)

Les courants intellectuels de leur époque guident les scientifiques vers l’étude de certains phénomènes. Pour l’évolution de l’IA, les deux forces les plus importantes dans l’environnement intellectuel des années 1939 et 1940 étaient la logique intellectuelle, qui avait connu un développement rapide depuis la fin du 19e Siècle, et de nouvelles idées sur l’informatique ". Les systèmes logiques de Frege Whitehead et Russel, Tarski e d’autres, montraient que certains aspects de la logique pouvaient être formalisés dans un cadre relativement simple. La logique mathématique a continué d’être une partie active de la recherche sur l’IA, en partie parce que des systèmes de déduction logique ont été appliqués avec succès sur des organisateurs. Mais même avant qu’il y eût des ordinateurs, la formalisation mathématique du raisonnement logique a orienté la conception vers la relation entre calcul et intelligence.  

Un certain nombre de logiciels informatiques issus de recherche en Intelligence Artificielle connaissent aujourd’hui une grande vogue sous l’appellation de " systèmes-experts ". Edward Feigenbaum, l’un des plus illustres spécialistes en la matière, responsable d’une prestigieuse équipe de l’Université de Stanford, en Californie, définit les systèmes-experts comme : " des programmes conçus pour raisonner habilement à propos de tâches dont on pense qu’elles requièrent une expertise (c’est –à- dire une compétence spécifique)humaine considérable ". En vérité cette définition est assez peu éclairante : un logiciel mettant sous forme de programme ,un algorithme mathématique subtil, par exemple pour résoudre toute équation de degré inférieur à cent, raisonne-t-il habilement ? La tâche traitée requiert certainement une expertise humaine considérable : mais qui, sur cette base le logiciel correspondant est classé " système-expert ", quelle est la nouveauté introduite par cette expression ?

La définition d’Edward Feigenbaum nous laisse d’autant plus perplexes que les sytèmes-experts existant n’utilisent que des schémas très rudimentaires de raisonnement : la modélisation, en vue d’une exploitation informatique, de raisonnements approchés, analogiques, inductifs ou autres formes de " raisonnements naturels ", n’en est qu’à ses débuts .

Pour tenter de cerner la notion actuelle de systèmes-experts nous examinerons d’abord les caractéristiques générales recherchées par la relation entre les usagers d’un systèmes –expert, d’une part, et le système expert, d’autre part, aux différents stades de la vie de ce systèmes. Nous présenterons des extraites d’une session de consultation du plus célèbre des systèmes experts : Mycin-Teiresias.Nous décrions ensuite les principes généraux de construction et fonctionnement des " systèmes de règles de production ",

Lorsque le processus intellectuel par lequel un humain évalue une situation ou prend une décision est précisément modélisé, il est relativement aisé de le programmer. C’est le cas, par exemple, dans des domaines tels que la comptabilité, le calcul scientifique ou la commande numérique de machines-outils classique. Cependant, dans certains domaines importants de la vie sociale tels que le diagnostic médical ou l’orientation scolaire, il est largement fait appel à des connaissances heuristiques, acquises souvent par expérience, souvent parcellaires, et éventuellement sujettes à révisions. C’est ce genre de connaissances que l’on cherche à prendre en compte par des " systèmes-experts ".

Un système-expert comporte toujours un langage d’expression (1) et des structures d’accueil pour la connaissance spécifique d’un domaine d’application recueillie après d’experts humains (parfois aussi accumulée au fil des expérimentations). Par structures d’accueil ; on entend une organisation en bases de données distinctes au sein de laquelle vont, selon une certaine logique, venir se distribuer des connaissances. Les langages naturels sont, bien entendu, souvent (mais pas toujours) la forme la plus confortable de communication avec un système-expert, du point de vue de l’usager humain, qu’il s’agisse d’instruire le système ( usager-expert) ou de le consulter (simple usager). Un certain nombre de systèmes sont aptes à dialoguer un langage naturel (anglais le plus souvent) objectivement restreint par la spécificité du domaine d’application.

Les éléments de connaissance sont organisés en une " base des connaissances ". Couramment, au sein de celle-ci, on distingue des " connaissances assertionnelles "décrivant des situations considérées comme établies ou à établir, et des " connaissances opératoires " qui représentent le savoir-faire sur le domaine : quelles conséquences tirer ou quelles actions accomplir dans telle ou telle situation ?

L’exploitation de la base des connaissances est régie par des stratégies intégrées à un logiciel séparé : " l’interpréteur ".la séparation entre interpréteur et base des connaissances se prête à des révisions relativement indépendantes, de l’une et de l’autre. Dans nombre de domaines d’application, le savoir-faire (les connaissances opératoires peut être représenté par des unités d’assez faible envergure pour être comprises aisément par un usager tout en correspondant à des opérations distinctes significatives dans le domaine :on parle de " granulés " de connaissance.

Ces granulés ne sont généralement pas accessibles par un nom, comme c’est le cas des procédures informatiques classiques, mais par " filtrage " : l’expression représentative de chacun d’eux précise dans quelles situations le granule de connaissances doit être mis en œuvre. La granularité de la connaissance et l’invocation par filtrage concourent à faciliter les ajouts traits, modifications de la base des connaissances. Ils confèrent donc aux systèmes-experts une flexibilité appréciable. Par ailleurs, les sytèmes-experts sont souvent utilisés comme des partenaires experts des usagers humains non experts plutôt que comme des substituts aux experts humains. On cherche donc à pourvoir les systèmes-experts de l’aptitude à expliquer leurs propres comportements, ne serait-ce qu’en présentant les connaissances exploitées aux différents stades du traitement : on parle " d’auto-explicativité ". Cette aptitude favorise aussi, pour l’expert humain, la mise au point des granules de connaissance transmis au système-expert.  

Le formalisme des règles de production n’est que la représentation externe de la connaissance ; La plupart des systèmes " compilent " la base de règles pour obtenir une représentation interne efficace. La représentation interne à pour effet de structurer la connaissance en groupant en listes (au sens de LISP) règles et les prémisses. Deux réalisations en ce sens vont être décrites : POLITICS de J. Carbonell Jr. (1978), qui utilise une structure de règles imbriquées plus riche que le formalisme initial et le système PROSPECTOR (Duda 80) qui travaille en fait que un multigraphe. Les moteurs OPS et TANGO s’intéressent également par d’autres voies à optimiser la phase de déclenchement par des représentations internes des règles qui perdent en place mémoire pour gagner en temps calcul. L’interprétation, dans les deux cas, fait place à une compilation : la phase de déclenchement est facilitée. Il est important de noter que cette structuration de la connaissance est laissée à la charge du système puisqu’elle change profondément lorsque change la base de règles, ce qui est le cas commun.

Certains informaticiens ont part ailleurs pris récemment l’habitude de la modélisation par réseaux de Pétri. L’analogie entre ceux-ci et les représentations internes utilisées dans les systèmes experts est profonde : en particulier les réseaux de Pétri " à prédicats " ne sont qu’une redécouverte des systèmes de règles de production basés sur la logique du premier ordre. Soulignons enfin que la modularité essentielle des systèmes de règles est en elle-même un facteur d’efficacité. En effet, l’activation d’une règle se fait de façon associative et non dans un ordre imposé par une procédure : toute nouvelle conclusion n’évoque que les règles qui parlent d’elles. Les règles sont activés , et éventuellement déclenchées en activant alors d’autres règles et ainsi que suite.

D’aune manière générale, et, soit parce que plusieurs règles peuvent se déclencher et que toutes sauf une sont mises en attente, soit parce que une règle demande en partie action l’exécution de plusieurs tâches,, les tâches sont généralement mis es en attente dans un agenda. Un agenda est une structure de données sont les éléments sont affectés de priorités ou plus généralement de prédicats qui rythment leur sortie. Point n’est besoins de balayer les cas qui ne correspondent pas à) la situation actuelle (instructions et tests de la programmation classique). Seuls ceux qui servent sont directement appelés par la base des faits, par les données. Les inférences, la résolution sont ainsi très différentes pour des données différentes. Ceci semble une condition indispensable à) l’efficacité. Ce n’est pas un hasard, si l’homme lui-même n’agit pas en déroulant des algorithmes :même pour un cas trivial, comme la multiplication de deux nombres, nous utilisons chaque fois une méthode adaptée aux données : nombre le plus long " en haut ", sauf s’il comporte des 0, des 1 ou des chiffres répétés, prise en compte de la valeur de ceux-ci : petits chiffres en cas si possible.

L’expérience montre par ailleurs concrètement, que la mise au point d’un corps de règles est agréable et rapide : il s’écoule quelques minutes entre la détection d’une erreur à l’exécution et la correction de la règle fautive et/ou l’adjonction d’une nouvelle règle. En revanche, dans un programme, une erreur détectée n’est pas toujours facilement corrigée à cause des " effets de bord " dus à la séquentialité : la correction effective peut demander, disons des heures……et ne peut être le seul fait de l’expert : elle passe nécessairement par un informaticien, intermédiaire gênant et coûteux.

" Schéma général d’un système actuel de règle de production "

Ces modèles sont des descriptions succinctes de haut niveau, décrivant, par abstraction et généralisation, des sous-ensembles de règles du niveau inférieur qui ont quelque chose en commun. Un modèle de règles se compose de quatre parties :

• Une liste d’exemples : c’est simplement le sous-ensemble des règles à partir desquelles le modèle a été constitué :

• Une description d’un élément caractéristique du sous-ensemble, ici : caractérisation des prémisses et des conclusions par les attributs qui apparaissent fréquemment et corrélations de ces attributs entre eux : ces renseignements sont obtenus par une analyse statistique sommaire :

• Deux listes de règles les unes plus spécifiques, les autres plus générales. L’ensemble des modèles est ainsi organisé en un arbre dont la racine est le concept le plus général.
  
  C’est TEIRESIAS lui-même qui fabrique ces modèles à mesure que croît sa base de connaissance et dès que plusieurs règles portent sur un même domaine.

. Exemple de modèle de règle :

Modèle " X est –un-domaine-d’investissement " :

Exemples : R116, R80, R95……

Description :

-prémisses : le revenu est/la durée est/la tendance est/

-corrélations (revenu, durée)/(tranche impôts, expérience, attention)/

Conclusions : domaine/risque

Plus général : " un-domaine-d’investissement ".

Moins général : " entreprises-de-services-publics-est-un-domaine-d’investissement ".

Quand TEIRESIAS s’attend à recevoir une nouvelle règle ‘phase 3 dans l’exemple), il parcourt l’arbre des modèles en partant de la racine et en cherchant à retrouver ce qu’il sait déjà propos de la règle. Ici, le modèle le plus spécifique connu qui lui permet de conclure qu’un domaine d’investissement possible est la technologie avancée, est précisément celui donné dans le modèle ci-dessus.

C’est la fréquence d’apparition des prédicats dans les modèles qui facilite la compréhension des clauses entrées en langue naturelle, tandis que les corrélations entre occurrences de ces mêmes prédicats permettent de vérifier que l’expert n’a rien oublié d’important.

C’est d’ailleurs cette utilisation des modèles qui supplée à la faiblesse de l’analyse linguistique : c’est elle aussi qui fait qu’une caractéristique importante du système est de tendre à ne comprendre que ce qu’il s’attend à comprendre.

L’arbre des modèles de règles permet en outre à TEIRESIAS de mesurer ce qu’il ne sait pas : domaines où existent peu de règles ou peu de règles sûres. Il sait ainsi ce qui est pour lui le plus urgent d’apprendre et peut dont poser lui-même des questions sur ces sujets (part contre il n’a pas de mesure de ce qui reste en fait à apprendre et n‘a aucun moyen de juger d’entrée de jeu la vraisemblance d’un fait nouveau pour lui). Le même arbre permet enfin une mise en forme de la connaissance données en vrac par l’expert et de la structure au profit des experts eux-mêmes.

Ce paragraphe a d’une part pour but de définir plus précisément ce qu’est un système-expert et comment il est possible de le programmer, et d’autre part de faire le bilan des systèmes-experts actuels.

Une règle de production est une expression de la forme :

MG è MD

Dans laquelle le membre gauche MG décrit une certaine situation, représentée dans un formalisme approprié pour l’univers de travail, et où le membre droit MD donne l’action à envisager lorsque la sitation associée est détectée. Une telle règle ressemble fort à un théorème et en enchainement de règles enboîtées par leurs prémises MG et leurs conclusions MD s’apparente à un syllogisme. Le mide de raisonnement sousèjacent des systèmes qui utilisent comme base de connaissance des ensembles de telles régles est le modus ponens (de p et p >q on conclut q), il est à ce titre aisèment compréhensible lors de l’analyse des résultats, mais ce n’est pas le seul.

Le schéma de calcul par règles de production, s’il s’oppose en pratique aux systèmes procéduraux , ne leur est pas moins formellement équivalent. Il fut proposé la première fois par E. Post (Post 36) et notamment utilisé depuis pour définir les langages et les grammaires formelles ‘Chmsky 63). Il est à la base, depuis 1974, de nombreux programmes, qualifiés de "systèmes experts". Ces systèmes sont spécialisés dans des domaines particuliers où la résolution de proboèmes demande des raisonnmenets simples tout en présentant un fort aspect cognitif. Ce sont des règles de production qui sont chargées de supporter toute la connaissance. Cette connaissance est ainsi donnée de façon modulaire et aisèment modifiable, puisqu’elle n’est pas mêlée au corps des prgrammes.

Par ailleurs, il est remarquable que les mêmes systèmes de production servent actuellement et concurrement à des psychlogues pour tener de modéliser certains processus intellectuelsl. A. Nawell pense par exemple (Newell 72) que c’est le bon formalisme pour exprimer les transfert entre mémoire à court terme et mémoire à long terme chez l’lhomme et que ces systèmes constituent un modèle correct de la gestion de nos connaissances.

Leur utilisation en I.A n’est donc pas une simple coîncidence !

Le système global, outre sa banque de connaissance qui est l’ensemble des règles de production, se compose d’un espace de travail (ou base des faits) et d’un interprète programmé.

L’espace de travail contient l’ensemble des faits que le programme a pu déduire à un instant donné. Seul y figure initialement l’énoncé du problème à résoudre. Cet espace joue le rôle ‘une " mémoire à court terme " qui contient de simples assertions relatives à la description statique de l’univers et est ainsi fonctionnellement différent de la banque de connaissances dynamiques de la " mémoire à long terme " qui contient les opérateurs des transformations sous forme de règles. Ces règles

peuvent contenir des variables dont les valeurs sont précisées (" instantiées ") par l’interprète lors de chaque exécution pour les mettre en accord avec les faits connus par " semi-unification "ou " filtrage ".

"  Cycle de base d’un interprète de règles "

L’unification est ainsi le mécanisme fondamental qui permet aux systèmes de productions de fonctionner : dans toute sa généralité il permet de dire s’il existe un jeu de substitutions de variables qui permet de rendre deux formules logiques identiques. Il ui correspondant un algorithme parfaitement défini.

L’interprète est alors une partie clé du système qui contrôle complètement l’ordre des déductions successives. Une exécution a toujours lieu suivant une séquence de cycles élémentaires parfaitement semblables les uns aux autres, dont la forme est donnée par la figure 4

Le problème crucial est le problème du " déclenchement " : plusieurs solutions sont été retenues, ceci n’entre pas dans notre cas d’étude .

les systèmes de productions différent ici selon que l’information nouvelle obtenue par cette déduction vient s’ajouter simplement à la base des faits ou bien est ajoutée en détruisant et en remplaçant l’un des faits qui y étaient présents .

La recherche du but elle-même se fait de façon naturelle, comme en démonstration de théorèmes, et est aisément représentable à l’aide d’un arbre ET-OU.

En fait, cet arbre ( arbre ET-OU) potentiel peut être construit et parcouru soit depuis les faits vers la conclusion, soit depuis la conclusion , considérée alors comme conjecture, vers les faits. On parle dans le premier cas de chaînage avant ,dans le second de chaînage arrière. Le plus suivant, c’est cette dernière

Solution qui est choisie, car d’une part les faits ne sont pas indépendants et d’autre part beaucoup d’entre eux ne sont pas pertinents pour le problème : cette démarche évite ainsi, de prime abord, l’explosion combinatoire car peu de conclusions sont a priori envisageables. Elle est adoptées notamment dans MYCIN et DENDRAL.

*Un interprète LISP, par appels récursifs en cascade, assure dans ce cas, la majeure partie du travail d’évaluation. Le schéma général d’un tel système est donnée par la figure 6. Mais notons qu’un bon interprète doit en réalité, pour des raisons naturelles de commodité d’emploi, être capable, suivant l’étape et le type du raisonnement, de cheminer en avant ou en arrière.

principaux sont inclus dans les programmes de la Section II. D. Malgré tout, un bref résumé des façons dont l’Heuristique et la recherche heuristique ont été utilisées peut prévenir le fait de prendre l’une quelconque de ces définitions trop sérieusement.

Comme adjectif, la définition du dictionnaire la plus souvent citée est " sert à découvrir ", comme nom ;, se référant à une branche obscure de philosophie, le mot signifiait l’étude des méthodes et des règles de découverte et d’invention (voir Polya, 1957, P.112).

Quand le terme est venu à être utilisé par décrire des techniques d’IA, quelques auteurs ont fait des distinctions entre les méthodes pour découvrir des solutions et des méthodes pour les fournir algorithmiquement. Ainsi, Newell, Shaw et Simon déclaraient en 1957 : " un processus qui peut résoudre un problème donné, mais n’offre aucune garantie de le faire, est appelé une heuristique pour ce problème " (Newell, Shaw et Simon, 1963b, p. 114). Mais la signification n’a pas été universellement acceptée. Minsky, par exemple disait dans un article de 1961 :

L’adjectif " heuristique ", tel qu’il est utilisé ici et largement dans la littérature, signifie liée à l’amélioration de la performance dans la résolution de problème ; comme un nom ; il est aussi utilisé en relation avec toute méthode ou astuce utilisée pour améliorer l’efficacité d’un programme de résolution de problème….. Mais les méthodes imparfaites ne sont pas nécessairement heuristiques, et vice versa. De fait "heuristique " ne devrait pas être regardé comme opposé à " fiable " ; ceci a causé quelque confusion dans la littérature.

Minsky, 1963, p. 407n.)

Ces deux définitions se réfèrent, bien que vaguement, à deux différents ensembles – des mécanismes qui améliorent l’efficacité et des mécanismes qui ne sont pas garantis. Feigenbaum et Feldman (1963) apparemment limitent l’heuristique à des systèmes ayant les deux propriétés :

Une heuristique (règle heuristique ;, méthode heuristique) est une règle d’estimation, stratégie, astuce, simplification, ou toute autre sorte de système qui limite drastiquement la recherche des solutions dans les espaces de problèmes étendus. L’heuristique ne garantit pas des solutions optimales : en fait ; elle ne garantit aucune solution du tout : tout ce qui peut être dit d’une heuristique utile est qu’elle offre des solutions qui sont suffisamment bonnes la plupart du temps (p.6, l’italique est le texte original).

Même cette définition, malgré tout, ne s’accorde pas toujours avec l’usage courant, parce qu’elle manque de dimension historique. Un mécanisme introduit à l’origine comme heuristique au sens de Feldman et Feigenbaum peut plus tard être montré comme garantissant une solution optimale à la fin du compte. Quand ceci se produit, le label heuristique peut être ou ne pas être abandonné, il n’a pas été évincé par exemple, dans le cas de l’algorithme A* ( § II.C3b). L’élagage alpha-bêta (§II.C5b) ; d’un côté, n’est plus appelé heuristique.

Il faut noter que les définitions citées ci-dessus s’étalent dans le temps de 1957 à 1963, se réfèrent à des règles heuristiques, des méthodes et de programmes, mais elles n’utilisent pas le terme de recherche heuristique. Ce terme composite semble avoir été introduit pour la première fois en 1965, dans un article de Newell et Ernst, "  La Recherche pour la Généralité " (voir Newell et Simon , 1972, p. 888) . L’article présentait un cadre pour la comparaison des méthodes utilisées dans les programmes de résolution de problèmes jusqu’à cette époque. Le cadre de base, alors appelé recherche heuristique était celui appelé recherche d’espace - d’état dans ce chapitre-ci. Les méthodes de recherches aveugles étaient incluses dans le néologisme de recherche heuristique.

Une signification similaire pour recherche heuristique apparaît chez Newell et Simon (1972,pp. 91-105) . Là encore, aucun contraste n’est défini entre la recherche heuristique et la recherche aveugle : : plutôt, la recherche heuristique est distinguée d’une Méthode de résolution de problème appelée génération et test. La différence entre les deux est que le dernier génère simplement des éléments de l’espace de recherche (ex. des états) et teste chacun tout à tour jusqu’à ce qu’il en trouve un satisfaisant la condition de but : alors que dans la recherche heuristique l’ordre de génération peut dépendre à la fois de l’information obtenue dans les tests précédents et des caractéristiques du but. Mais la distinction de Newell et Simon n’est pas du type pur et dur. A l’époque de leur conférence de 1976 sur Turing, ils semblent avoir fusionné les deux méthodes en une seule :

Recherche heuristique. Une deuxième loi de structure qualitative pour l’IA est que les systèmes symboliques résolvent des problèmes en générant des solutions potentielles et en les testant, c’est à dire par la recherche (Newell et Simon 1976, P. 126).

Dans le présent article, la signification attachée à recherche heuristique ne prend pas son origine chez Newell et Simon, mais chez Nilsson, dont le livre de 1971 donne le traitement le plus détaillé et d’influence sur le sujet, qui soit paru jusqu’ici. Pour Nilsson, la distinction entre recherche heuristique et recherche aveugle est le point important. La recherche aveugle correspondant approximativement à la génération systématique et au test des éléments de l’espace - d’état, mais il opère à l’intérieur d’un formalisme qui laisse la place pour une information additionnelle sur le domaine spécifique du problème de introduire, plutôt qu’en l’excluant par définition. Si une telle information, qui va plus loin que ce qui est nécessaire pour simplement caractériser une classe de problèmes comme des problèmes de recherche, est en fait introduite, il peut être possible de réduire la recherche de façon drastique. Que la restriction soit fiable ou non, la recherche est alors appelée heuristique plutôt qu’aveugle.

Voir AMAREL(1968), Feigenbaum et Feldman (1963), Good (1968à, Jackson (1974), Kowalski (1972), Minsky (1963à, Newell et Ernst (1965à, Newell, Shaw, et Simon (1963b), Newell et Simon (1972, 1976à, Nilsson (1971), Polya (1957), Raphael (1976), Samuel (1963à, Shannon (1950, 1956à, et Vandebrug et Minker (1975)

On veut calculer dans un atelier flexible le chemin le plus court pour une pièce donner , cette dernière doit subir des opérations d’usinage dans quatre poste d’usinage respectivement 

A,B,C,D près dispose de tel façon