Any-goal bidirectional A* pathfinding reference

Question

I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that important). The standard (I believe) way to do this with the A* algorithm is to use a distance-to-closest-goal heuristic (which is admissable) and exit as soon as any of the goal nodes is reached.

However, in my scenario (which is game AI, if that matters) some (or all) of the goals might be unreachable; furthermore, the set of nodes reachable from such goals is typically quite small (or, at least, I want to optimize in that particular case). For the case of a single goal, bidirectional search sounds promising: the reverse search direction would quickly exhaust all reachable nodes and conclude that no path exists. These slides by Andrew Goldberg et al. describes the bidirectional A* algorithm with proper conditions on the heuristics, as well as stopping conditions.

My question is: is there a way to combine these two approaches, i.e. to perform bidirectional A* to find path to any of a specified set of goal nodes? I'm not sure what heuristic function to choose for the reverse search direction, what are the stopping conditions, etc.

Answer 1

It is definitely possible to make a bidirectional graph search algorithm with several possible destinations. Simply add all the destination nodes to the destination-search priority queue, all of them with weight 0. The backward search will start from all the destinations at once, instead of just starting from a single one.

In short, when you're initializing your priority queues and your empty set, use:

src_seen = set()
dst_seen = set()

src_prio_queue = heapify([(0, src)])
dst_prio_queue = heapify([(0, dst1), (0, dst2), (0, dst3), ...])

while src_prio_queue and dst_prio_queue:
    ...  # regular bidirectional A*
```