Cela pourrait être à la limite de la science cognitive computationnelle, mais je suis curieux de savoir comment le processus suivi par les algorithmes de recherche de chemin commun (tels que A * ) se compare au processus que les humains utilisent dans différentes situations de recherche de chemin (avec les mêmes informations). Ces processus sont-ils similaires?
algorithms
graphs
artificial-intelligence
DorkRawk
la source
la source
Réponses:
Les humains ont tendance à choisir non pas strictement optimaux, mais proches des solutions les plus courtes. Vous devrez donc regarder des algorithmes flous (approximatifs), pas A *.
L'algorithme le plus proche de la pensée humaine que j'ai connu est une hiérarchie de contaction comparable à un algorithme d'élagage Reach . Lorsque j'ai besoin de trouver un chemin entre A et B sur la carte, je fais un bref aperçu, en tenant compte s'il y a une traversée de rivière ou autre et en cherchant des moyens généraux, puis en ajoutant des détails qui pourraient raccourcir le chemin.
la source
Voici un certain nombre de considérations. Les deux premiers sont tirés du merveilleux doctorat d'Andreas Junghanns (maintenant de retour à l'industrie à Berlin, en Allemagne et heureux de le compter parmi mes amis :)):
Recherche en largeur : si vous vous tenez juste devant un meuble et que quelque chose de précieux (par exemple une pièce de monnaie ou une bague) tombe et passe sous le meuble, de sorte que vous ne pouvez pas le voir, alors vous agitez légèrement la main à partir du point où vous avez vu l'objet disparaître. Si vous ne le trouvez pas, vous allez un peu plus loin et continuez ainsi jusqu'à ce que vous le trouviez ou que vous perdiez patience. C'est exactement la première recherche en action: d'abord, vous considérez tous les emplacements inconnus à la profondeur 1, puis à la profondeur 2 et ainsi de suite.
Recherche en profondeur d'abord : lorsque vous recherchez quelque chose qui est situé à distance de votre environnement, vous ne choisissez jamais l'algorithme susmentionné et vous vous engagez plutôt dans une direction. Un exemple est Cristobal Colon s'engageant à l'ouest lorsqu'il cherche une route vers les Indiens. Eh bien, il avait tort, mais nous le savons de nos jours. Imaginez Colon essayant une recherche en profondeur et se déplaçant le long d'une spirale de Burgos où le contrat entre les Reyes Católicos et Colon a été signé. Au lieu de cela, il a indiqué une direction donnée sans jamais revenir en arrière.
Un autre exemple de l'un de mes professeurs à l'Université (José Cuena, qui est déjà décédé) concerne la recherche bidirectionnelle : les ingénieurs, lorsque la construction de tunnels dans les montagnes commence simultanément aux deux extrémités et se termine quand ils se rencontrent quelque part au milieu. La raison est simple, si elles partent d'un seul bout, il est très probable qu'il y aura une énorme déviation à l'autre bout. Partir des deux extrémités minimise simultanément la déviation du point de rencontre.
Une question très intéressante abordée par d'autres est de savoir si les humains peuvent exécuter n'importe quel algorithme et (encore plus intéressant de mon point de vue) si ces algorithmes (ou, en général, la façon dont nous construisons l'intelligence artificielle) imitent nos procédures intelligentes naturelles.
la source
Avez-vous vu un enfant apprendre à naviguer dans une pièce? Vous devez leur dire: «Faites le tour de la table. AUTOUR ».
La planification du chemin humain est un sac à main d'heuristiques, certaines innées et d'autres apprises. Lookahead est probablement fixé à un petit nombre, certainement pas une récursivité générale comme A *.
la source