Search code examples
multithreadingsearchartificial-intelligencea-star

Multithreaded A* Search in Java or Lisp or C#

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.

Solution

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