11
$\begingroup$

This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different pathfinding situations (given the same information). Are these processes similar?

$\endgroup$
  • 3
    $\begingroup$ Humans can use the A* pathfinding algorithm... I mean, an algorithm is just a technique, right? I don't think there's any algorithm a human being couldn't perform. I suppose what I'm trying to get at is that you should probably be a lot more clear in terms of what constitutes "the process humans use in different pathfinding situations". I don't think anybody could give you a meaningful answer until you say how humans actually do it... which is probably problematic in the general case, and it seems to be difficult here as well. $\endgroup$ – Patrick87 Mar 20 '12 at 20:59
  • $\begingroup$ Also, please explain shortly what A* does and/or link to a reference. And: welcome! $\endgroup$ – Raphael Mar 20 '12 at 21:33
  • $\begingroup$ @Patrick87 Certainly humans CAN do any algorithm, but that's not a very interesting question. What I was trying to get at was how pathfinding algorithms compare to the techniques used by humans when left to solve a problem on their own (without prior knowledge of pathfinding algorithms). $\endgroup$ – DorkRawk Mar 20 '12 at 23:19
  • 3
    $\begingroup$ There are studies of human behavior in such situations: a reasonable answer might point to actual studies of how humans do pathfinding. $\endgroup$ – Suresh Mar 20 '12 at 23:53
  • 2
    $\begingroup$ Humans really don't do very well with million-node graphs, especially given as adjacency lists, but $A^*$ works just fine. (In other words: How humans do what exactly?) $\endgroup$ – JeffE May 2 '12 at 8:05
6
$\begingroup$

Humans tend to choose not strictly optimal, but close to shortest solutions. So you'll need to look at fuzzy (approximate) algorithms, not at A*.

The closest algorithm to human thinking I've aware of is a Contaction hierarchies on par with a Reach pruning algorithm. When I need to find a path between A and B on the map, I do a quick overview, taking into account if there is crossing river or something else and looking for some general ways and then adding details that could shorten path.

$\endgroup$
  • $\begingroup$ Can you say the latter approach is shortest paths only that you start on a rough approximation of the graph and refine the graph as you go along? $\endgroup$ – Raphael Mar 20 '12 at 22:59
  • $\begingroup$ @Raphael Yes, actually it is description of what Contaction Hierarchies (there is also a preprocessing step, that takes graph and collapses it into hierarchy with different details level) do and simultaneously of what I'll do as a human being $\endgroup$ – om-nom-nom Mar 20 '12 at 23:04
4
$\begingroup$

Here you are a number of considerations. The first two are taken from the wonderful PhD by Andreas Junghanns (now back to Industry in Berlin, Germany and happy to count him among my friends :) ):

Breadth-First Search: If you are just standing in front of a furniture and something valuable (say a coin, or a ring) falls and goes beneath the furniture, so that you cannot see it, then you wave your hand slightly starting from the point where you saw the object dissapearing. If you do not find it you go a little bit further and proceed this way until either you find it or you loose your patience. That is exactly breadth-first search in action: first, you consider all the unknown locations at depth 1, then at depth 2 and so on.

Depth-First Search: when looking for something that is remotely located to your surroundings you never choose the aforementioned algorithm and instead you commit to a direction. An example is Cristobal Colon committing to the west when seeking a route to the Indians. Well, he was wrong but we know that nowadays. Imagine Colon trying a breadth-first search and moving along a spiral from Burgos where the contract between the Reyes Católicos and Colon was signed. Instead he pointed to a given direction without ever backtracking.

Another example from one of my professors at the University (José Cuena, who already passed away) regards bidirectional search: engineers, when building tunnels in mountains start from both ends simultaneously and end when they meet somewhere in the middle. The reason is simple, if they start just from one end it is very likely that there will be a huge deviation in the other end. Starting from both ends simultaneously minimizes the deviation in the meeting point.

Now, even in the case of A$^*$ let me recall the same considerations I make to my students:

  • The open list is just the list of open possibilities awaiting to be considered. All humans do this though we are not as good as computers remembering things.
  • The closed list just serves to avoid circular reasoning or continuing reasoning from a point that we already considered before. This happens if you are reasoning at loud voice and you repeat something. Then, someone will realize and will immediately tell you "hey man, you already said that before"

A very interesting question somehow addressed by others is whether humans can run any algorithm and (even more interesting from my point of view) whether these algorithms (or, in general, the way we build Artificial Intelligence) mimic our natural intelligent procedures.

$\endgroup$
-2
$\begingroup$

Have you watched a child learning to navigate a room? You have to tell them, "Go around the table. AROUND".

Human path planning is a grab bag of heuristics, some innate and some learned. Lookahead is probably fixed to a small number, certainly not a general recursion like A*.

$\endgroup$
  • 1
    $\begingroup$ This answers contains only speculation. $\endgroup$ – Raphael Mar 21 '12 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.