Performance of an A* search implemented in Clojure

Question

I have implemented an A* search algorithm for finding a shortest path between two states. Algorithm uses a hash-map for storing best known distances for visited states. And one hash-map for storing child-parent relationships needed for reconstruction of the shortest path.

Here is the code. Implementation of the algorithm is generic (states only need to be "hashable" and "comparable") but in this particular case states are pairs (vectors) of ints [x y] and they represent one cell in a given heightmap (cost for jumping to neighboring cell depends on the difference in heights).

Question is whether it's possible to improve performance and how? Maybe by using some features from 1.2 or future versions, by changing logic of the algorithm implementation (e.g. using different way to store path) or changing state representation in this particular case?

Java implementation runs in an instant for this map and Clojure implementation takes about 40 seconds. Of course, there are some natural and obvious reasons for this: dynamic typing, persistent data structures, unnecessary (un)boxing of primitive types...

Using transients didn't make much difference.

Answer 1

Using priority-map instead of sorted-set

I first used sorted-set for storing open nodes (search frontier), switching to priority-map improved performance: now it takes 15-20 seconds for this map (before it took 40s).

This blog post was very helpful. And "my" new implementation is pretty much the same.

New a*-search can be found here.

Answer 2

I don't know Clojure, but I can give you some general advice about improving the performance of Vanilla A*.

• Consider implementing IDA*, which is a variant of A* that uses less memory, if it's suitable for your domain.

• Try a different heuristic. A good heuristic can have a significant impact on the number of node expansions required.

• Use a cache, Often called a "transposition table" in search algorithms. Since search graphs are usually Directed Acyclic Graphs and not true trees, you can end up repeating the search of a state more than once; a cache to remember previously-searched nodes reduces node expansions.

Dr. Jonathan Schaeffer has some slides on this subject:

http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/10.Single-agentSearch.pdf

http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf