Multithreaded A* Search in Java or Lisp or C#

Question

Is there a good way to do a multithreaded A* search? Single threaded is fairly easy, as given in (for example) Artificial Intelligence: A Modern Approach, but I have not come across a good multithreaded version.

Assume a sane language like Java or C# or Lisp where we have thread pools and work blocks, and of course garbage collection.

Answer 1

I recommend reading this paper:

"Parallel bidirectional A* search on a symmetry multiprocessor"

There is also another paper, also at IEEE called:

"Parallel Astar search on message-passing architectures"

Both papers find novel methods for gaining quite a bit of speedup.