How Do Common Pathfinding Algorithms Compare To Human Process

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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*.