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 hear what you are saying but I am not sure that you would want to. In an A* search you want to take the most optimal path and you don't want to do any calculations for the same path twice.

Look at the facts:

• The 'best' squares to choose are all next to eachother
• Calculating for any other square other than the 'best' choice is premature computation. The point of A* is that it's choices are efficient.

If you threaded the application you would need:

• a 'Waiter' in order to make sure that no thread touched the same square and to give them new squares to caclulate. They would all be working in such a tight knit area that they would be fighting for the path resources because all of the 'best' squares are next to eachother.

This problem is procedural and has no nice way of breaking it up into separate parts and thus is not a good choice for threading. In short nobody has done it because it is not a desirable thing to do. I hope this helps.

Answer 2

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.