Dans le carrefour interdisciplinaire reliant les sciences informatiques, la psychologie cognitive et la mod\u00e9lisation computationnelle de l’esprit, l’exploration syst\u00e9matique d’espaces de probl\u00e8mes complexes constitue un d\u00e9fi fondamental pour comprendre tant les machines que l’intelligence humaine. L’algorithme de recherche A* s’impose historiquement comme l’un des paradigmes les plus rigoureux et influents pour appr\u00e9hender la mani\u00e8re dont un agent rationnel navigue au sein d’environnements structur\u00e9s sous contrainte de ressources. En combinant le co\u00fbt r\u00e9el d\u00e9j\u00e0 encouru et une estimation prospective heuristique de la distance vers un objectif, ce formalisme propose une lentille th\u00e9orique f\u00e9conde pour analyser la planification, la navigation spatiale et la prise de d\u00e9cision adaptative.<\/p>\n
L’algorithme A*<\/strong> (prononc\u00e9 \u00ab A \u00e9toile \u00bb) est une m\u00e9thode de recherche heuristique de chemin optimal au sein d’un graphe orient\u00e9 ou non, con\u00e7ue pour d\u00e9terminer la trajectoire la moins co\u00fbteuse entre un n\u0153ud initial et un n\u0153ud cible pr\u00e9d\u00e9fini. Reposant sur une fonction d’\u00e9valuation math\u00e9matique combinant le co\u00fbt exact accumul\u00e9 depuis l’origine et une fonction heuristique admissible estimant le co\u00fbt restant, cet algorithme garantit, sous certaines conditions formelles, la d\u00e9couverte du chemin optimal tout en minimisant le nombre d’\u00e9tats explor\u00e9s par rapport aux m\u00e9thodes de recherche exhaustive.<\/p>\n Sur le plan des sciences cognitives<\/a> et de la psychologie computationnelle, la recherche A* transcende son statut d’outil math\u00e9matique pour devenir un mod\u00e8le th\u00e9orique de la rationalit\u00e9 instrumentale et de la r\u00e9solution de probl\u00e8mes. Elle sert de r\u00e9f\u00e9rence normative pour \u00e9valuer comment l’esprit humain r\u00e9sout des dilemmes de planification \u00e0 \u00e9tapes multiples, tels que les labyrinthes, la navigation spatiale mentale ou les jeux combinatoires comme le jeu de taquin et les tours de Hano\u00ef. En fournissant une formalisation explicite de l’interaction entre m\u00e9moire r\u00e9trospective et anticipation prospective, A* mat\u00e9rialise l’op\u00e9rationnalisation formelle des m\u00e9canismes sous-tendant le raisonnement t\u00e9l\u00e9ologique.<\/p>\n Contrairement aux algorithmes aveugles ou aux m\u00e9thodes purement probabilistes, A* incarne une forme d’arbitrage computationnel rigoureux entre exploration guid\u00e9e et optimalit\u00e9 garantie. Il offre ainsi un cadre d’analyse math\u00e9matique permettant aux chercheurs d’\u00e9tudier les d\u00e9viations syst\u00e9matiques observ\u00e9es chez les sujets humains face \u00e0 des probl\u00e8mes d’optimisation s\u00e9quentielle, r\u00e9v\u00e9lant la nature des heuristiques simplificatrices adopt\u00e9es par le syst\u00e8me cognitif confront\u00e9 \u00e0 une puissance de calcul intrins\u00e8quement born\u00e9e.<\/p>\n L’appellation \u00ab A* \u00bb d\u00e9coule d’une convention de nomenclature interne n\u00e9e dans les laboratoires d’intelligence artificielle de la fin des ann\u00e9es 1960. \u00c0 l’origine, les chercheurs du Stanford Research Institute<\/em> (SRI) d\u00e9veloppaient une variante optimis\u00e9e de l’algorithme de recherche heuristique con\u00e7u par Nils Nilsson, initialement d\u00e9sign\u00e9 sous le label exp\u00e9rimental d’algorithme \u00ab A1 \u00bb. Face aux perfectionnements apport\u00e9s par ses coll\u00e8gues pour assurer l’optimalit\u00e9 formelle, une version interm\u00e9diaire nomm\u00e9e \u00ab A2 \u00bb fut \u00e9labor\u00e9e.<\/p>\n Le recours \u00e0 l’ast\u00e9risque (\u00ab * \u00bb), symbole souvent d\u00e9sign\u00e9 sous l’appellation d’\u00e9toile de Kleene en logique math\u00e9matique et en linguistique formelle, fut propos\u00e9 pour d\u00e9signer la variante finale de l’algorithme qui d\u00e9montrait une efficacit\u00e9 optimale prouv\u00e9e. L’ast\u00e9risque signifiait math\u00e9matiquement que cette version repr\u00e9sentait l’aboutissement absolu et ind\u00e9passable de la famille d’algorithmes de classe A lorsqu’elle est dot\u00e9e d’une heuristique admissible : aucune autre proc\u00e9dure d\u00e9terministe utilisant la m\u00eame fonction d’estimation ne peut \u00e9tendre strictement moins de n\u0153uds tout en garantissant un r\u00e9sultat optimal.<\/p>\n Le terme a \u00e9t\u00e9 introduit officiellement dans la litt\u00e9rature scientifique en 1968 par Peter E. Hart, Nils J. Nilsson et Bertram Raphael dans leur publication fondatrice parue dans les IEEE Transactions on Systems Science and Cybernetics<\/em>. Depuis lors, l’expression a conserv\u00e9 sa graphie originelle en anglais (A* search algorithm<\/em>) et a \u00e9t\u00e9 int\u00e9gr\u00e9e dans la taxonomie francophone sous les syntagmes \u00ab recherche A* \u00bb, \u00ab algorithme A* \u00bb ou plus rarement \u00ab exploration A-\u00e9toile \u00bb.<\/p>\n Dans la francophonie acad\u00e9mique, le syntagme s’\u00e9nonce invariablement sous la forme phon\u00e9tique \/a etwal\/. L’usage d’une prononciation calqu\u00e9e sur l’anglais (\/e\u026a st\u0251\u02d0r\/) demeure marginal dans les milieux de recherche francophones en psychologie et en informatique formelle, o\u00f9 la transcription litt\u00e9rale du symbole typographique pr\u00e9vaut.<\/p>\n Sur le plan grammatical, \u00ab A* \u00bb fonctionne g\u00e9n\u00e9ralement comme un \u00e9pith\u00e8te invariablement postpos\u00e9 \u00e0 un substantif masculin singulier : \u00ab l’algorithme A* \u00bb, \u00ab le moteur de recherche A* \u00bb, \u00ab le mod\u00e8le A* \u00bb. Lorsque le mot est employ\u00e9 seul de mani\u00e8re elliptique par m\u00e9tonymie (\u00ab le A* \u00bb), il conserve le genre masculin. Dans le champ lexical des sciences cognitives, on observe \u00e9galement des formes adjectiv\u00e9es ou d\u00e9riv\u00e9es compos\u00e9es, telles que \u00ab heuristique de type A* \u00bb ou \u00ab comportement compatible A* \u00bb, destin\u00e9es \u00e0 qualifier des d\u00e9marches de planification mentale respectant l’ordonnancement math\u00e9matique sous-jacent.<\/p>\n Les variantes typographiques doivent imp\u00e9rativement conserver la majuscule de la lettre latine suivie sans espace de l’ast\u00e9risque en exposant ou au niveau de la ligne (\u00ab A* \u00bb). Toute tentative de transcription phon\u00e9tique dans le texte \u00e9crit (comme \u00ab A-\u00e9toile \u00bb) est proscrite dans les contextes \u00e9ditoriaux formels et les manuels de r\u00e9f\u00e9rence, bien qu’elle soit admise \u00e0 l’oral pour des raisons d’intelligibilit\u00e9 didactique.<\/p>\n Le fonctionnement conceptuel de la recherche A* repose sur l’\u00e9valuation dynamique d’un ensemble de n\u0153uds candidats au sein d’un graphe repr\u00e9sentant l’espace des \u00e9tats d’un probl\u00e8me donn\u00e9. \u00c0 chaque \u00e9tape de la recherche, l’algorithme doit d\u00e9cider quel \u00e9tat inexplor\u00e9 m\u00e9rite d’\u00eatre examin\u00e9 en priorit\u00e9. Pour op\u00e9rer ce choix critique, il applique une fonction de co\u00fbt not\u00e9e traditionnellement f(n)<\/em> \u00e0 chaque n\u0153ud n<\/em> situ\u00e9 sur la fronti\u00e8re de recherche. Cette fonction ma\u00eetresse d\u00e9compose l’estimation de l’effort total en deux composantes fondamentales et compl\u00e9mentaires :<\/p>\n f(n) = g(n) + h(n)<\/em><\/p>\n La composante g(n)<\/em> quantifie le co\u00fbt r\u00e9el et certain encouru pour voyager depuis la configuration initiale jusqu’au n\u0153ud courant n<\/em>. Ce param\u00e8tre repr\u00e9sente l’ancrage empirique et r\u00e9trospectif du syst\u00e8me : il pr\u00e9vient la d\u00e9rive vers des solutions s\u00e9duisantes mais excessivement co\u00fbteuses \u00e0 amorcer. \u00c0 l’inverse, h(n)<\/em> constitue l’estimation heuristique prospective du co\u00fbt n\u00e9cessaire pour atteindre l’\u00e9tat final d\u00e9sir\u00e9 \u00e0 partir du n\u0153ud n<\/em>. Cette dimension pr\u00e9dictive refl\u00e8te les connaissances expertes, intuitions ou simplifications g\u00e9om\u00e9triques inject\u00e9es dans le syst\u00e8me pour orienter la recherche directement vers la cible sans disperser les ressources dans des zones manifestement non pertinentes.<\/p>\n L’\u00e9l\u00e9gance architecturale de l’algorithme d\u00e9coule de l’\u00e9quilibre parfait qu’il instaure entre la pr\u00e9cision r\u00e9trospective et l’anticipation projective. Si h(n)<\/em> est fix\u00e9e de mani\u00e8re constante \u00e0 z\u00e9ro, l’algorithme A* r\u00e9gresse formellement vers l’algorithme de Dijkstra, explorant l’espace de mani\u00e8re concentrique et exhaustive sans aucune t\u00e9l\u00e9ologie orient\u00e9e. Si, au contraire, g(n)<\/em> est ignor\u00e9e au profit exclusif de h(n)<\/em>, l’algorithme se transforme en une recherche gloutonne purement myope, vuln\u00e9rable aux impasses locales et incapable de garantir le moindre r\u00e9sultat d’optimalit\u00e9 globale.<\/p>\n Sur le plan de la dynamique de traitement, l’algorithme maintient deux structures de donn\u00e9es conjointes : la liste ouverte (l’ensemble des \u00e9tats candidats identifi\u00e9s mais non encore d\u00e9velopp\u00e9s) et la liste ferm\u00e9e (l’ensemble des configurations d\u00e9j\u00e0 analys\u00e9es). En extrayant de mani\u00e8re r\u00e9p\u00e9t\u00e9e le n\u0153ud minimisant la fonction f(n)<\/em> au sein de la liste ouverte, A* propage une vague de d\u00e9cision qui se d\u00e9forme dynamiquement en fonction de la topographie de l’espace du probl\u00e8me, \u00e9pousant les contours des obstacles conceptuels ou physiques pour converger vers la cible selon la g\u00e9od\u00e9sique du moindre effort cognitif ou mat\u00e9riel.<\/p>\n La propri\u00e9t\u00e9 la plus d\u00e9cisive r\u00e9gissant le comportement de cet algorithme r\u00e9side dans le concept d’admissibilit\u00e9 heuristique. Une fonction heuristique h(n)<\/em> est qualifi\u00e9e d’admissible lorsqu’elle ne surestime jamais le co\u00fbt r\u00e9el requis pour atteindre l’objectif depuis n’importe quel n\u0153ud. Formellement, pour tout n<\/em>, h(n) \u2264 h*(n)<\/em>, o\u00f9 h*(n)<\/em> repr\u00e9sente le co\u00fbt minimal exact. Lorsque cette condition d’optimisme prudent est strictement respect\u00e9e, il est math\u00e9matiquement d\u00e9montr\u00e9 que le premier chemin complet d\u00e9couvert par A* est irr\u00e9futablement optimal, \u00e9vitant ainsi le risque d’adopter pr\u00e9matur\u00e9ment une solution sous-optimale par exc\u00e8s de confiance prospective.<\/p>\n L’\u00e9mergence de la recherche A* s’inscrit au c\u0153ur de l’\u00e2ge d’or des th\u00e9ories cybern\u00e9tiques et des premi\u00e8res conceptualisations de la psychologie computationnelle dans les ann\u00e9es 1960. Au Stanford Research Institute, l’\u00e9quipe men\u00e9e par Bertram Raphael, Nils Nilsson et Peter Hart avait pour mandat de d\u00e9velopper le logiciel de contr\u00f4le d\u00e9cisionnel de Shakey<\/a>, reconnu internationalement comme le premier robot mobile autonome capable de raisonner sur ses propres actions dans un monde r\u00e9el encombr\u00e9 d’obstacles.<\/p>\n \u00c0 cette p\u00e9riode, les mod\u00e8les dominants pour la planification d’itin\u00e9raires et la r\u00e9solution de casse-t\u00eates reposaient soit sur la programmation dynamique de Richard Bellman, soit sur l’algorithme de recherche de chemins les plus courts formul\u00e9 par Edsger Dijkstra en 1959. Bien que math\u00e9matiquement rigoureux, ces paradigmes souffraient d’une inefficacit\u00e9 r\u00e9dhibitoire pour des syst\u00e8mes embarqu\u00e9s aux capacit\u00e9s de m\u00e9moire limit\u00e9es : ils exploraient uniform\u00e9ment l’espace dans toutes les directions, simulant une diffusion isotrope d\u00e9pourvue d’intentionnalit\u00e9. Parall\u00e8lement, les psychologues et pionniers de l’intelligence artificielle Allen Newell et Herbert Simon formulaient le General Problem Solver<\/em> (GPS), introduisant la notion fondamentale d’analyse fins-moyens et d’espace d’\u00e9tats pour mod\u00e9liser le comportement de r\u00e9solution de probl\u00e8mes chez l’\u00eatre humain.<\/p>\n S’inspirant de ces r\u00e9flexions sur l’utilisation d’indices simplificateurs par l’esprit humain, Nils Nilsson con\u00e7ut en 1967 l’algorithme A1, une heuristique d’orientation qui permettait \u00e0 Shakey d’acc\u00e9l\u00e9rer ses calculs spatiaux en formulant des hypoth\u00e8ses sur la proximit\u00e9 physique de sa destination. N\u00e9anmoins, l’algorithme A1 ne garantissait en rien que le chemin emprunt\u00e9 f\u00fbt le plus \u00e9conomique. C’est \u00e0 ce tournant que Peter Hart formula la condition d’admissibilit\u00e9 math\u00e9matique, prouvant rigoureusement qu’en imposant une sous-estimation syst\u00e9matique du co\u00fbt restant, l’algorithme pr\u00e9servait l’optimalit\u00e9 formelle tout en surclassant la vitesse d’ex\u00e9cution de toutes les m\u00e9thodes concurrentes. En 1968, les trois chercheurs formalis\u00e8rent l’algorithme A*.<\/p>\n Au cours des d\u00e9cennies 1970 et 1980, les d\u00e9veloppements th\u00e9oriques autour de A* connurent une extension majeure gr\u00e2ce aux travaux de Judea Pearl, qui publia en 1984 un ouvrage de r\u00e9f\u00e9rence fondateur sur les heuristiques. Pearl y \u00e9tablit les th\u00e9or\u00e8mes de complexit\u00e9 moyenne, la notion de coh\u00e9rence ou monotonie de l’heuristique, et posa les bases m\u00e9thodologiques qui allaient faire le pont entre les architectures formelles de recherche et les th\u00e9ories cognitives du jugement probabiliste. Plus tard, Richard Korf introduisit en 1985 la variante Iterative Deepening A*<\/em> (IDA*), permettant de surmonter la limitation r\u00e9dhibitoire de l’algorithme classique : la saturation exponentielle de la m\u00e9moire de travail.<\/p>\n D’un point de vue \u00e9pist\u00e9mologique et psychologique, l’algorithme A* prend racine dans la th\u00e9orie computationnelle de l’esprit (Computational Theory of Mind<\/em>) et s’inscrit au sein du paradigme de traitement de l’information th\u00e9oris\u00e9 par Allen Newell et Herbert Simon. Selon cette perspective, la pens\u00e9e humaine, lorsqu’elle est confront\u00e9e \u00e0 une t\u00e2che orient\u00e9e vers un but, proc\u00e8de par transformations successives de structures symboliques au sein d’un \u00ab espace probl\u00e8me \u00bb (problem space<\/em>). L’esprit est mod\u00e9lis\u00e9 comme un agent rationnel op\u00e9rant des transitions d’\u00e9tats cognitifs en mobilisant des op\u00e9rateurs mentaux sp\u00e9cifiques.<\/p>\n Un autre pilier th\u00e9orique r\u00e9side dans le principe de rationalit\u00e9 limit\u00e9e formul\u00e9 par Herbert Simon. Alors qu’un agent disposant de ressources computationnelles infinies pourrait th\u00e9oriquement explorer l’ensemble des ramifications d’un arbre de d\u00e9cision complexe sans jamais commettre d’erreur, un syst\u00e8me biologique incarn\u00e9 est brid\u00e9 par des contraintes neurobiologiques de temps, d’attention et de m\u00e9moire de travail. A* formalise avec pr\u00e9cision cette dialectique : l’heuristique n’est pas une simple approximation paresseuse, mais un dispositif computationnel indispensable permettant de maximiser l’efficience d\u00e9cisionnelle face \u00e0 une explosion combinatoire d’options alternatives.<\/p>\n De surcro\u00eet, les fondements de A* dialoguent intimement avec la th\u00e9orie des repr\u00e9sentations spatiales et des cartes cognitives introduite initialement par Edward Tolman. Tolman a d\u00e9montr\u00e9 que les organismes vivants n’acqui\u00e8rent pas de simples cha\u00eenes d’associations stimulus-r\u00e9ponse, mais encodent une structure g\u00e9om\u00e9trique globale de leur milieu. Au sein de l’algorithme A*, la composante heuristique h(n)<\/em> agit pr\u00e9cis\u00e9ment comme l’analogue num\u00e9rique de cette carte mentale : elle injecte la connaissance globale des relations spatiales pour r\u00e9guler l’activation des sous-buts imm\u00e9diats.<\/p>\n Enfin, la th\u00e9orie des graphes sous-jacente \u00e0 A* illustre le concept d’isomorphisme cognitif. Qu’il s’agisse de d\u00e9placer des pi\u00e8ces physiques dans l’espace, de naviguer dans une m\u00e9tropole complexe ou d’encha\u00eener des inf\u00e9rences d\u00e9ductives pour r\u00e9soudre un th\u00e9or\u00e8me logique, ces activit\u00e9s mentales h\u00e9t\u00e9rog\u00e8nes partagent la m\u00eame topologie formelle : un \u00e9tat initial, un \u00e9tat final d\u00e9sir\u00e9 et une succession d’\u00e9tats interm\u00e9diaires s\u00e9par\u00e9s par des co\u00fbts d’action ou de charge cognitive distincts. L’algorithme unifie ces processus sous une m\u00eame \u00e9quation de minimisation de l’\u00e9nergie et du temps.<\/p>\n Pour appr\u00e9hender la m\u00e9canique intime de l’algorithme et ses transpositions psychologiques, il convient de diss\u00e9quer ses composantes structurelles et fonctionnelles, ainsi que les taxonomies qui en r\u00e9gissent l’application pratique au travers des dimensions suivantes :<\/p>\n Un cas classique permettant de mat\u00e9rialiser le fonctionnement de la recherche A* et d’\u00e9tudier les parall\u00e8les cognitifs est le jeu du taquin (le \u00ab 8-puzzle \u00bb). Ce casse-t\u00eate consiste en une grille de neuf cases contenant huit tuiles num\u00e9rot\u00e9es et un emplacement vide. L’objectif consiste \u00e0 r\u00e9organiser les tuiles depuis une disposition chaotique vers une configuration ordonn\u00e9e. Les r\u00e8gles imposent de glisser une tuile adjacente dans la case vide \u00e0 chaque \u00e9tape.<\/p>\n Pour r\u00e9soudre ce probl\u00e8me \u00e0 l’aide de l’algorithme A*, deux heuristiques admissibles sont classiquement mobilis\u00e9es :<\/p>\n Dans un protocole exp\u00e9rimental de psychologie cognitive, lorsqu’un sujet humain r\u00e9sout le jeu du taquin, on constate qu’il utilise des strat\u00e9gies de projection mentale ressemblant remarquablement \u00e0 une version d\u00e9grad\u00e9e de l’heuristique de Manhattan. Toutefois, d\u00e8s que la r\u00e9solution n\u00e9cessite d’effectuer un coup contre-intuitif \u2013 c’est-\u00e0-dire d\u00e9placer temporairement une tuile pourtant bien plac\u00e9e pour lib\u00e9rer un passage critique, ce qui implique une augmentation transitoire de la fonction f(n)<\/em> \u2013, le participant humain pr\u00e9sente un blocage cognitif et un allongement significatif de ses temps de fixation oculaire, l\u00e0 o\u00f9 un algorithme A* rigoureusement param\u00e9tr\u00e9 franchit cette barri\u00e8re sans h\u00e9sitation \u00e9motionnelle d\u00e8s que le co\u00fbt cumul\u00e9 reste le plus bas.<\/p>\n Un second exemple probant concerne la navigation pi\u00e9tonne au sein d’une ville dot\u00e9e d’une trame viaire non orthogonale. Face \u00e0 un obstacle infranchissable (comme des travaux fermant une art\u00e8re majeure), un pi\u00e9ton guid\u00e9 par une heuristique purement g\u00e9om\u00e9trique (distance \u00e0 vol d’oiseau) s’engagera obstin\u00e9ment dans les ruelles orient\u00e9es vers l’objectif jusqu’\u00e0 buter contre le cul-de-sac. L’application d’un mod\u00e8le computationnel A* permet d’analyser \u00e0 quel moment la prise en compte du co\u00fbt r\u00e9trospectif g(n)<\/em> (la fatigue, le d\u00e9tour accumul\u00e9) contraint l’agent \u00e0 rebrousser chemin et \u00e0 restructurer enti\u00e8rement son plan d’action.<\/p>\n L’\u00e9valuation des performances et de la validit\u00e9 de la recherche A* s’articule autour de m\u00e9triques d’analyse algorithmique ainsi que de protocoles de mesure psychom\u00e9triques et comportementaux lors de son utilisation comme outil de mod\u00e9lisation cognitive :<\/p>\n Sur le plan computationnel pur, l’algorithme est \u00e9valu\u00e9 \u00e0 travers sa complexit\u00e9 temporelle<\/em> (le nombre d’\u00e9tapes de calcul avant de trouver la trajectoire terminale) et sa complexit\u00e9 spatiale<\/em> (le volume maximal de m\u00e9moire vive allou\u00e9 aux listes ouverte et ferm\u00e9e). Ces deux m\u00e9triques d\u00e9pendent intimement du facteur de ramification effectif du probl\u00e8me (le nombre moyen de transitions possibles par \u00e9tat) not\u00e9 b*<\/em>. Une heuristique est qualifi\u00e9e de sup\u00e9rieurement informative si son application fait tendre b*<\/em> vers la valeur limite id\u00e9ale de 1, signifiant que la trajectoire a \u00e9t\u00e9 d\u00e9couverte de mani\u00e8re rectiligne sans aucune ramification parasite.<\/p>\n En psychologie exp\u00e9rimentale et dans les paradigmes d’\u00e9valuation neuropsychologique, la confrontation des sujets humains aux pr\u00e9dictions du mod\u00e8le A* mobilise des dispositifs d’enregistrement comportemental standardis\u00e9s :<\/p>\n La puissance d’abstraction de la recherche A* conf\u00e8re \u00e0 ce formalisme un spectre d’applications remarquablement vaste, allant de l’ing\u00e9nierie logicielle avanc\u00e9e aux interventions cliniques et organisationnelles :<\/p>\n Dans le domaine des neurosciences cognitives et de la neuropsychologie<\/em>, les mod\u00e8les d\u00e9riv\u00e9s de A* sont employ\u00e9s pour concevoir des tests diagnostiques informatis\u00e9s des fonctions ex\u00e9cutives. Le test de la tour de Londres ou le test des labyrinthes de Porteus mesurent l’int\u00e9grit\u00e9 de la capacit\u00e9 de planification chez des patients pr\u00e9sentant des l\u00e9sions du cortex pr\u00e9frontal ou des troubles neurod\u00e9g\u00e9n\u00e9ratifs. En utilisant A* pour calculer le patron de recherche math\u00e9matiquement id\u00e9al pour chaque configuration de test, les cliniciens disposent d’une ligne de base infaillible permettant d’isoler avec exactitude si le d\u00e9ficit du patient rel\u00e8ve d’une incapacit\u00e9 \u00e0 formuler une estimation prospective (d\u00e9faillance de l’heuristique h<\/em>) ou d’une perte d’inhibition des options d\u00e9j\u00e0 test\u00e9es (d\u00e9faillance de la liste ferm\u00e9e).<\/p>\n En ergonomie cognitive et ing\u00e9nierie des facteurs humains<\/em>, A* est employ\u00e9 pour concevoir les syst\u00e8mes d’assistance \u00e0 la navigation routi\u00e8re ou a\u00e9rienne (GPS) et les interfaces homme-machine complexes. La compr\u00e9hension des r\u00e8gles de visibilit\u00e9 et de distance heuristique permet de mod\u00e9liser comment un pilote ou un op\u00e9rateur de centrale nucl\u00e9aire se repr\u00e9sentera le chemin de reprise de contr\u00f4le face \u00e0 une situation de crise, optimisant l’affichage des informations pour \u00e9viter que la charge de calcul mentale de l’op\u00e9rateur ne s’effondre.<\/p>\n Au sein de la robotique cognitive et de l’intelligence artificielle incarn\u00e9e<\/em>, A* demeure le socle fondamental pour la planification de trajectoires (motion planning<\/em>) et la coordination cin\u00e9matique des bras manipulateurs dans un espace encombr\u00e9. De l’exploration spatiale martienne par les astromobiles autonomes \u00e0 la logistique robotis\u00e9e au sein des entrep\u00f4ts automatis\u00e9s, le principe d’arbitrage de A* permet d’assurer des d\u00e9placements sans collision au moindre co\u00fbt \u00e9nerg\u00e9tique possible.<\/p>\n Enfin, dans l’industrie des jeux vid\u00e9o et de la simulation comportementale<\/em>, A* est la norme absolue pour animer les agents non-joueurs (PNJ). Qu’il s’agisse de simuler des comportements de foule lors d’\u00e9vacuations d’urgence dans des mod\u00e8les d’architecture urbaine ou de conf\u00e9rer une intelligence tactique cr\u00e9dible \u00e0 des adversaires virtuels, l’algorithme produit des mouvements fluides et r\u00e9alistes que les observateurs humains per\u00e7oivent intuitivement comme rationnels et intelligents.<\/p>\n Depuis le d\u00e9but des ann\u00e9es 1990, une production empirique f\u00e9conde s’est consacr\u00e9e \u00e0 comparer formellement les architectures de recherche de type A* avec les comportements humains r\u00e9els de r\u00e9solution de probl\u00e8mes.<\/p>\n Les travaux novateurs de James Staszewski sur l’expertise mn\u00e9sique et de Richard Korf sur les espaces combinatoires ont montr\u00e9 que si la recherche A* permet de surclasser les \u00eatres humains sur des jeux de moyenne complexit\u00e9 gr\u00e2ce \u00e0 sa vitesse de traitement brut, les experts humains (par exemple, les ma\u00eetres aux \u00e9checs ou au jeu de go) d\u00e9ploient une heuristique radicalement diff\u00e9rente. Plut\u00f4t que de d\u00e9velopper un grand nombre de n\u0153uds selon un crit\u00e8re purement math\u00e9matique, l’expert humain utilise une reconnaissance de motifs (pattern recognition<\/em>) issue de sa m\u00e9moire \u00e0 long terme pour \u00e9laguer a priori 99 % des branches de l’arbre d\u00e9cisionnel, r\u00e9duisant l’espace de recherche \u00e0 quelques alternatives hautement probables.<\/p>\n En 2008, des \u00e9tudes men\u00e9es par Thomas Griffiths, Joshua Tenenbaum et leurs collaborateurs ont explor\u00e9 comment des principes bay\u00e9siens pouvaient \u00eatre combin\u00e9s \u00e0 la recherche heuristique pour mod\u00e9liser l’apprentissage causal et l’induction conceptuelle. Leurs donn\u00e9es confirment que lorsque l’espace de d\u00e9cision pr\u00e9sente une structure probabiliste incertaine, les mod\u00e8les informatiques qui int\u00e8grent des heuristiques directionnelles guid\u00e9es \u00e0 la mani\u00e8re de A* pr\u00e9disent avec une excellente corr\u00e9lation (r > 0.85) la trajectoire des d\u00e9ductions formul\u00e9es par des \u00e9tudiants universitaires confront\u00e9s \u00e0 des probl\u00e8mes d’extrapolation logique.<\/p>\n Dans le domaine de l’imagerie c\u00e9r\u00e9brale fonctionnelle, des recherches en IRMf coordonn\u00e9es notamment par Eleanor Maguire sur les chauffeurs de taxi londoniens ont mis en \u00e9vidence l’implication pr\u00e9pond\u00e9rante de l’hippocampe post\u00e9rieur dans le stockage des repr\u00e9sentations topologiques globales, tandis que le cortex pr\u00e9frontal dorsolat\u00e9ral s’active de mani\u00e8re proportionnelle \u00e0 la complexit\u00e9 des d\u00e9tours requis lors de la planification d’itin\u00e9raires. Ces r\u00e9sultats fournissent une assise neurobiologique distincte \u00e0 la dissociation computationnelle de A* : l’hippocampe encode le gradient spatial heuristique correspondant \u00e0 h(n)<\/em>, tandis que les circuits fronto-striataux g\u00e8rent l’arbitrage s\u00e9quentiel et la m\u00e9moire des \u00e9tats explor\u00e9s correspondant \u00e0 g(n)<\/em> et \u00e0 la tenue des listes d’\u00e9tats.<\/p>\n L’application d’un mod\u00e8le formel comme la recherche A* \u00e0 l’\u00e9tude des processus cognitifs humains n\u00e9cessite d’int\u00e9grer les variabilit\u00e9s culturelles quant \u00e0 la structuration de l’espace, de la logique et du raisonnement t\u00e9l\u00e9ologique.<\/p>\n En premier lieu, les syst\u00e8mes de r\u00e9f\u00e9rence spatiale varient profond\u00e9ment selon les groupes linguistiques et culturels, comme l’ont d\u00e9montr\u00e9 les travaux anthropologiques et linguistiques de Stephen Levinson. Dans les soci\u00e9t\u00e9s occidentales industrialis\u00e9es, les individus recourent pr\u00e9f\u00e9rentiellement \u00e0 un cadre de r\u00e9f\u00e9rence \u00e9gocentrique (\u00ab \u00e0 ma gauche \u00bb, \u00ab devant moi \u00bb) ou relatif pour planifier des trajectoires. \u00c0 l’oppos\u00e9, au sein de nombreuses populations autochtones (telles que les Guugu Yimithirr en Australie ou les Mayas Tzeltal au Mexique), la conceptualisation spatiale est strictement absolue et g\u00e9ocentrique (\u00ab vers le nord \u00bb, \u00ab vers l’aval \u00bb). Lorsque l’on traduit une t\u00e2che de navigation dans un mod\u00e8le A*, la formalisation de la fonction heuristique h(n)<\/em> doit imp\u00e9rativement \u00eatre adapt\u00e9e : une distance relative \u00e0 la position du corps \u00e9chouera totalement \u00e0 mod\u00e9liser les performances cognitives de sujets dont la boussole mentale est ancr\u00e9e sur des coordonn\u00e9es topographiques absolues et ind\u00e9pendantes de leur posture corporelle.<\/p>\n En second lieu, la notion m\u00eame d’optimalit\u00e9 d’un cheminement n’est pas universellement partag\u00e9e. Dans les mod\u00e8les \u00e9conomiques et computationnels occidentaux, l’efficacit\u00e9 est traditionnellement d\u00e9finie comme la minimisation absolue du temps ou de la distance kilom\u00e9trique. Cependant, dans de nombreux contextes \u00e9cologiques et traditionnels, la s\u00e9lection d’une trajectoire int\u00e8gre des dimensions de s\u00e9curit\u00e9 communautaire, de pr\u00e9servation rituelle ou de consolidation de liens sociaux le long du parcours. Un trajet per\u00e7u comme sous-optimal par un algorithme A* fond\u00e9 uniquement sur la distance m\u00e9trique s’av\u00e8re parfaitement rationnel lorsqu’il optimise simultan\u00e9ment des contraintes multifactorielles complexes non r\u00e9ductibles \u00e0 une g\u00e9od\u00e9sique physique.<\/p>\n Enfin, l’acculturation technologique contemporaine \u2013 marqu\u00e9e par la d\u00e9pendance g\u00e9n\u00e9ralis\u00e9e aux assistants de navigation num\u00e9rique bas\u00e9s sur des algorithmes de type A* \u2013 modifie profond\u00e9ment les habitudes cognitives. Les \u00e9tudes contemporaines montrent une atrophie relative des capacit\u00e9s d’orientation spontan\u00e9e et une diminution de la granularit\u00e9 des cartes cognitives hippocampiques chez les utilisateurs chroniques de GPS, illustrant comment l’externalisation de la recherche heuristique vers des algorithmes artificiels r\u00e9troagit sur le fonctionnement neuropsychologique humain.<\/p>\n En d\u00e9pit de son \u00e9l\u00e9gance math\u00e9matique et de son omnipr\u00e9sence acad\u00e9mique, l’algorithme A* et son extrapolation aux mod\u00e8les de la cognition font l’objet de vives critiques \u00e9pist\u00e9mologiques et techniques :<\/p>\n Le principal \u00e9cueil computationnel de A* r\u00e9side dans son app\u00e9tit gargantuesque en m\u00e9moire vive. L’algorithme conserve l’int\u00e9gralit\u00e9 des n\u0153uds g\u00e9n\u00e9r\u00e9s au sein de la liste ouverte afin de pr\u00e9server sa garantie formelle d’optimalit\u00e9. Dans des espaces d’\u00e9tats \u00e0 grande \u00e9chelle ou \u00e0 haut facteur de ramification (comme le jeu d’\u00e9checs ou la pr\u00e9diction du repliement des prot\u00e9ines), la m\u00e9moire physique est quasi syst\u00e9matiquement satur\u00e9e bien avant que le temps de calcul ne devienne un facteur limitant. Cet aspect rend le mod\u00e8le originel A* psychologiquement invraisemblable en tant que description litt\u00e9rale du cerveau humain, dont la m\u00e9moire de travail est notoirement limit\u00e9e \u00e0 un nombre restreint d’\u00e9l\u00e9ments actifs simultan\u00e9s.<\/p>\n Sur le plan des sciences cognitives, des th\u00e9oriciens de la cognition incarn\u00e9e et situ\u00e9e, tels qu’Andy Clark ou Francisco Varela, ont s\u00e9v\u00e8rement contest\u00e9 le postulat selon lequel l’esprit r\u00e9soudrait les d\u00e9fis de l’existence par la construction d’arbres de recherche cart\u00e9siens au sein d’un graphe symbolique statique. Dans le monde biologique r\u00e9el, les environnements sont hautement dynamiques, bruyants et impr\u00e9visibles. Un calcul exhaustif d’optimalit\u00e9 pr\u00e9alable s’av\u00e8re fr\u00e9quemment inadapt\u00e9 voire mortel face \u00e0 des pr\u00e9dateurs ou des p\u00e9rils urgents. La psychologie de la d\u00e9cision, incarn\u00e9e notamment par les travaux de Gerd Gigerenzer sur les heuristiques \u00ab rapides et frugales \u00bb (fast and frugal heuristics<\/em>), soutient que les \u00eatres vivants n’optimisent presque jamais au sens formel de A*, mais s’appuient sur des r\u00e8gles d’arr\u00eat d’exploration brutales (comme le principe de \u00ab satisficing \u00bb d’Herbert Simon) pour agir avec succ\u00e8s sous une pression temporelle intense.<\/p>\n Un autre d\u00e9bat th\u00e9orique majeur concerne la d\u00e9pendance critique de A* envers la qualit\u00e9 de sa fonction heuristique. Concevoir une heuristique admissible mais suffisamment discriminante pour \u00e9viter de retomber dans les travers de la recherche exhaustive constitue une t\u00e2che complexe qui rel\u00e8ve souvent de l’ing\u00e9nierie ad hoc. Si h(n)<\/em> sous-estime trop grossi\u00e8rement la r\u00e9alit\u00e9, A* explore des millions de n\u0153uds superflus ; si par m\u00e9garde h(n)<\/em> surestime ne serait-ce qu’une fois le co\u00fbt, l’optimalit\u00e9 formelle s’effondre irr\u00e9m\u00e9diablement. Cette fragilit\u00e9 param\u00e9trique limite son autonomie adaptative dans des univers dont la physique n’est pas parfaitement connue \u00e0 l’avance.<\/p>\n Pour clarifier sans ambigu\u00eft\u00e9 la place de l’algorithme A* au sein de la famille des m\u00e9thodes de recherche et de mod\u00e9lisation, il est essentiel d’\u00e9tablir ses fronti\u00e8res conceptuelles avec des notions voisines :<\/p>\n L’algorithme de recherche A* repr\u00e9sente un pilier incontournable reliant la logique computationnelle de la recherche de chemin \u00e0 la mod\u00e9lisation formelle des processus de r\u00e9solution de probl\u00e8mes et de d\u00e9cision s\u00e9quentielle. Sa structure repose sur le mariage harmonieux de deux r\u00e9alit\u00e9s temporelles : l’effort d\u00e9j\u00e0 accompli dans le pass\u00e9, repr\u00e9sent\u00e9 par g(n)<\/em>, et l’anticipation prospective de l’avenir, incarn\u00e9e par l’heuristique h(n)<\/em>.<\/p>\n Le g\u00e9nie m\u00e9thodologique de A* r\u00e9side dans son th\u00e9or\u00e8me d’optimalit\u00e9 : d\u00e8s lors que la fonction heuristique respecte la contrainte d’admissibilit\u00e9 (c’est-\u00e0-dire qu’elle se garde bien de surestimer l’effort requis pour atteindre l’objectif), l’algorithme a l’assurance math\u00e9matique d’identifier la meilleure solution possible tout en minimisant scrupuleusement l’effort d’exploration computationnelle par rapport \u00e0 tout autre algorithme de recherche inform\u00e9e utilisant la m\u00eame structure de connaissances.<\/p>\n Au-del\u00e0 de son ubiquit\u00e9 technologique dans le guidage par satellite, la robotique mobile et l’industrie du divertissement num\u00e9rique, A* offre aux sciences cognitives et \u00e0 la psychologie un instrument conceptuel de premier plan. Il sert d’\u00e9talon normatif id\u00e9al pour mesurer et diss\u00e9quer la rationalit\u00e9 humaine, mettant en lumi\u00e8re le conflit permanent qui oppose le souci d’optimalit\u00e9 absolue aux contraintes physiques et neurophysiologiques de ressources qui forcent tout esprit biologique \u00e0 embrasser des compromis adaptatifs.<\/p>\n L’algorithme A* est un mod\u00e8le de recherche heuristique de chemin optimal combinant co\u00fbt accumul\u00e9 et anticipation prospective, \u00e9clairant les sciences cognitives.<\/p>\n","protected":false},"author":1,"featured_media":0,"template":"","categories":[5114,4285,1486],"tags":[30735,10486,424,30736,11807,2110,1808],"class_list":["post-19165","psych_term","type-psych_term","status-publish","hentry","category-psychologie-computationnelle","category-resolution-de-problemes","category-sciences-cognitives","tag-algorithme-a","tag-heuristique","tag-intelligence-artificielle","tag-planification-mentale","tag-psychologie-computationnelle","tag-resolution-de-problemes","tag-sciences-cognitives"],"_links":{"self":[{"href":"https:\/\/french.arabpsychology.com\/index.php?rest_route=\/wp\/v2\/psych_term\/19165","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/french.arabpsychology.com\/index.php?rest_route=\/wp\/v2\/psych_term"}],"about":[{"href":"https:\/\/french.arabpsychology.com\/index.php?rest_route=\/wp\/v2\/types\/psych_term"}],"author":[{"embeddable":true,"href":"https:\/\/french.arabpsychology.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"version-history":[{"count":0,"href":"https:\/\/french.arabpsychology.com\/index.php?rest_route=\/wp\/v2\/psych_term\/19165\/revisions"}],"wp:attachment":[{"href":"https:\/\/french.arabpsychology.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=19165"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/french.arabpsychology.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=19165"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/french.arabpsychology.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=19165"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}2. \u00c9tymologie et origines linguistiques<\/h3>\n
3. Prononciation et forme grammaticale<\/h3>\n
4. Explication conceptuelle d\u00e9taill\u00e9e<\/h3>\n
5. \u00c9volution historique<\/h3>\n
6. Fondements th\u00e9oriques<\/h3>\n
7. Composantes cl\u00e9s, types et dimensions<\/h3>\n
\n
8. Exemples et cas illustratifs<\/h3>\n
\n
9. Mesure et \u00e9valuation<\/h3>\n
\n
10. Applications et pertinence pratique<\/h3>\n
11. Recherche et preuves empiriques<\/h3>\n
12. Consid\u00e9rations culturelles et transculturelles<\/h3>\n
13. Critiques, d\u00e9bats et limites<\/h3>\n
14. Termes connexes et distinctions<\/h3>\n
\n
15. Synth\u00e8se et points cl\u00e9s \u00e0 retenir<\/h3>\n
R\u00e9f\u00e9rences<\/h2>\n
\n