Pathfinding Algorithm Comparison Essay

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.

  • 1.

    Van Toll, W.G., Cook, A.F., Geraerts, R.: Real-time density-based crowd simulation. Computer Animation and Virtual Worlds Archive 23(1), 59–69 (2012)CrossRefGoogle Scholar

  • 2.

    Daamen, W.: Modelling passenger flows in public transport facilities. PhD thesis T2004/6, Delft University of Technology (2004)Google Scholar

  • 3.

    Hale, D.H.: A growth-based approach to the automatic generation of navigation meshes. Technical report, The University of North Carolina at Charlotte (2011)Google Scholar

  • 4.

    Kavraki, L.E., et al.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12(4), 566–580 (1996)CrossRefGoogle Scholar

  • 5.

    Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 2nd edn., pp. 97–104. Prentice Hall (2003). ISBN 978-0137903955Google Scholar

  • 6.

    Botea, A., Muller, M., Schaeffer, J.: Near optimal hierarchical path-finding. Report, Department of Computer Science, University Alberta (2004)Google Scholar

  • 7.

    Geraerts, R.: Planning short paths with clearance using explicit corridors. In: Proc. to IEEE ICRA International Conference on Robotics and Automation (2010)Google Scholar

  • 8.

    Geraerts, R.: Sampling-based motion planning: analysis and path quality. PhD thesis, The Utrecht University, The Netherlands (2006)Google Scholar

  • 9.

    Kaminski, R.T., Koszalka, L., Pozniak-Koszalka, I., Kasprzak, A.: Evaluation and comparison of task allocation algorithms for mesh networks. In: Proc. 9th International Conference on Networks, pp. 104–108. IEEE Computer Society Press (2010)Google Scholar

  • 10.

    Kmiecik, W., Wojcikowski, M., Koszalka, L., Kasprzak, A.: Task allocation in mesh connected processors with local search meta-heuristic algorithms. In: Nguyen, N.T., Le, M.T., Świątek, J. (eds.) Intelligent Information and Database Systems. LNCS, vol. 5991, pp. 215–224. Springer, Heidelberg (2010)CrossRefGoogle Scholar


    Leave a Reply

    Your email address will not be published. Required fields are marked *