I'm trying to perform A* with a cost function that is time-consuming to compute. The cost function is single threaded, can take several seconds, and cannot be optimized.
I would like to compute as many costs as possible in parallel.
In case it matters, I have an admissible heuristic that is cheap to compute.
There are two things to discuss in the answer. The first is algorithmic efficiency. The second is parallelism.
There is a research paper that studies this case and creates an A* variant, DEA*. It uses a cheap admissible heuristic on the edge cost to get a lower-bound on the cost of successors, and then only computes the actual cost of an edge when it is shown that the successor could be on an optimal path.
Normally A* expands a node by (1) generating successors with their new f-cost, and (2) placing them in open. The DEA* algorithm (1) generates successors with estimated (lower bounds on) f-costs and (2) places them on open. If a state is removed from open with only a f-cost estimate, the exact edge/f-cost is computed and the state is placed back on open.
This is a variant of the general idea of Partial Expansion, and other work has explored the expensive edge issue as well.
In this model, you can avoid computing many expensive edges, which is helpful. But, it would still be useful to compute the remaining edges in parallel. Depending on the exact cost, there are many ways to do this. If your open list is multi-threaded, it can compute the edge costs each time a state is added to open. But, it would be more efficient to essentially have two priority queues.
One priority queue would contain states with their edge costs computed, and the other would contain those that need the computation done. Parallel code can be written to take states from the second priority queue and compute their edge costs, adding them to the first queue when they are complete. Then, the regular program can process states from the first queue in the regular priority order.
The key point is that the parallel part can focus on computing edge costs for states that are about to be expanded next instead of doing all states as they are added to the queue.
Note that a process like this could result in exploring a longer path before a shorter path is discovered. So, you need to keep track of when you find a shorter path to a state (on open or closed) and make sure you move states from closed back to open when a shorter path is discovered.
Related to this, you can't terminate once you find a solution - it won't necessarily be optimal. You need to finish expanding any states that have f-cost lower than the solution you've found. (You can discard any states that have solution cost greater than or equal to your found solution.) [Note that I've given a general direction on good approaches here; if you're stuck on specific details you can ask for clarification.]
