Wie vergleichen sich gängige Pfadfindungsalgorithmen mit menschlichen Prozessen?

11

Dies mag an die rechnergestützte Kognitionswissenschaft grenzen, aber ich bin gespannt, wie der Prozess, dem gängige Pfadfindungsalgorithmen (wie A * ) folgen, mit dem Prozess verglichen wird, den Menschen in verschiedenen Pfadfindungssituationen verwenden (mit denselben Informationen). Sind diese Prozesse ähnlich?

DorkRawk
quelle
3
Menschen können den A * -Pfadfindungsalgorithmus verwenden ... Ich meine, ein Algorithmus ist nur eine Technik, oder? Ich glaube nicht, dass es einen Algorithmus gibt, den ein Mensch nicht ausführen kann. Ich nehme an, ich versuche zu verstehen, dass Sie wahrscheinlich viel klarer sein sollten, was "den Prozess ausmacht, den Menschen in verschiedenen Situationen der Wegfindung anwenden". Ich glaube, niemand könnte Ihnen eine aussagekräftige Antwort geben, bis Sie sagen, wie Menschen es tatsächlich tun ... was im allgemeinen Fall wahrscheinlich problematisch ist und auch hier schwierig zu sein scheint.
Patrick87
Erklären Sie außerdem kurz, was A * tut und / oder verlinken Sie auf eine Referenz. Und willkommen!
Raphael
@ Patrick87 Natürlich KÖNNEN Menschen jeden Algorithmus machen, aber das ist keine sehr interessante Frage. Ich habe versucht zu verstehen, wie Pfadfindungsalgorithmen mit den Techniken verglichen werden, die von Menschen verwendet werden, um ein Problem selbst zu lösen (ohne vorherige Kenntnis der Pfadfindungsalgorithmen).
DorkRawk
3
Es gibt Studien zum menschlichen Verhalten in solchen Situationen: Eine vernünftige Antwort könnte auf tatsächliche Studien darüber hinweisen, wie Menschen Wegfindung betreiben.
Suresh
2
EIN

Antworten:

6

Menschen neigen dazu, nicht streng optimale, sondern nahezu kürzeste Lösungen zu wählen. Sie müssen sich also Fuzzy-Algorithmen (ungefähre Algorithmen) ansehen, nicht A *.

Der Algorithmus, der dem menschlichen Denken am nächsten kommt, ist eine Kontraktionshierarchie, die einem Reach- Bereinigungsalgorithmus ebenbürtig ist. Wenn ich auf der Karte einen Pfad zwischen A und B finden muss, mache ich einen schnellen Überblick, wobei ich berücksichtige, ob ein Fluss oder etwas anderes überquert wird, nach allgemeinen Wegen suche und dann Details hinzufüge, die den Pfad verkürzen könnten.

OM Nom Nom
quelle
Können Sie sagen, dass der letztere Ansatz nur kürzeste Wege sind, bei denen Sie mit einer groben Annäherung an den Graphen beginnen und den Graphen im Laufe der Zeit verfeinern?
Raphael
@Raphael Ja, eigentlich ist es eine Beschreibung dessen, was Kontraktionshierarchien (es gibt auch einen Vorverarbeitungsschritt, der ein Diagramm erstellt und es in eine Hierarchie mit unterschiedlichen Detailebenen zusammenfasst) und gleichzeitig das, was ich als Mensch tun werde
om-nom -nom
4

Hier sind einige Überlegungen. Die ersten beiden stammen aus der wunderbaren Promotion von Andreas Junghanns (jetzt zurück in der Industrie in Berlin und zählen ihn gerne zu meinen Freunden :)):

Breitensuche : Wenn Sie nur vor einem Möbel stehen und etwas Wertvolles (z. B. eine Münze oder ein Ring) fällt und unter das Möbel fällt, so dass Sie es nicht sehen können, winken Sie mit der Hand leicht ab Punkt, an dem Sie das Objekt verschwinden sahen. Wenn Sie es nicht finden, gehen Sie ein Stück weiter und gehen Sie so vor, bis Sie es entweder finden oder Ihre Geduld verlieren. Das ist genau die Breitensuche in Aktion: Zuerst betrachten Sie alle unbekannten Orte in Tiefe 1, dann in Tiefe 2 und so weiter.

Tiefensuche : Wenn Sie nach etwas suchen, das sich in der Ferne in Ihrer Umgebung befindet, wählen Sie niemals den oben genannten Algorithmus und legen stattdessen eine Richtung fest. Ein Beispiel ist Cristobal Colon, der sich im Westen engagiert, wenn er einen Weg zu den Indianern sucht. Nun, er hat sich geirrt, aber das wissen wir heutzutage. Stellen Sie sich vor, Colon versucht eine Breitensuche und bewegt sich entlang einer Spirale von Burgos, wo der Vertrag zwischen den Reyes Católicos und Colon unterzeichnet wurde. Stattdessen zeigte er auf eine bestimmte Richtung, ohne jemals zurückzugehen.

Ein weiteres Beispiel eines meiner Professoren an der Universität (José Cuena, der bereits verstorben ist) betrifft die bidirektionale Suche : Ingenieure, wenn Tunnel in Bergen gebaut werden, beginnen an beiden Enden gleichzeitig und enden, wenn sie sich irgendwo in der Mitte treffen. Der Grund ist einfach: Wenn sie nur an einem Ende beginnen, ist es sehr wahrscheinlich, dass es am anderen Ende eine große Abweichung gibt. Ausgehend von beiden Enden gleichzeitig wird die Abweichung im Treffpunkt minimiert.

Lassen Sie mich an dieselben Überlegungen erinnern, die ich meinen Schülern gegenüber gemacht habe:

  • Die offene Liste ist nur die Liste der offenen Möglichkeiten, die darauf warten, berücksichtigt zu werden. Alle Menschen tun dies, obwohl wir nicht so gut sind wie Computer, die sich an Dinge erinnern.
  • Die geschlossene Liste dient nur dazu, Zirkelschluss zu vermeiden oder weiter zu argumentieren, von einem Punkt, den wir bereits zuvor betrachtet haben. Dies passiert, wenn Sie mit lauter Stimme argumentieren und etwas wiederholen. Dann wird jemand erkennen und Ihnen sofort sagen: "Hey Mann, das haben Sie schon vorher gesagt."

Eine sehr interessante Frage, die von anderen irgendwie angesprochen wird, ist, ob Menschen einen Algorithmus ausführen können und (aus meiner Sicht noch interessanter) ob diese Algorithmen (oder im Allgemeinen die Art und Weise, wie wir künstliche Intelligenz aufbauen) unsere natürlichen intelligenten Verfahren nachahmen.

Carlos Linares López
quelle
Das von Carlos erwähnte Papier kann hier gelesen werden: svn.sable.mcgill.ca/sable/courses/COMP763/oldpapers/…
TFerrell
-2

Haben Sie einem Kind beim Navigieren in einem Raum zugesehen? Sie müssen ihnen sagen: "Gehen Sie um den Tisch herum. UM ".

Die Planung menschlicher Pfade ist eine Sammlung von Heuristiken, von denen einige angeboren und andere erlernt sind. Lookahead ist wahrscheinlich auf eine kleine Zahl festgelegt, sicherlich keine allgemeine Rekursion wie A *.

Trevor Blackwell
quelle
1
Diese Antwort enthält nur Spekulationen.
Raphael