  Heuristic search has traditionally relied on hand-crafted or programmatically
derived heuristics. Neural networks (NNs) are newer powerful tools which can be
used to learn complex mappings from states to cost-to-go heuristics. However,
their slow single inference time is a large overhead that can substantially
slow down planning time in optimized heuristic search implementations. Several
recent works have described ways to take advantage of NN's batch computations
to decrease overhead in planning, while retaining bounds on (sub)optimality.
However, all these methods have used the NN heuristic in a "blocking" manner
while building up their batches, and have ignored possible fast-to-compute
admissible heuristics (e.g. existing classically derived heuristics) that are
usually available to use. We introduce Non-Blocking Batch A* (NBBA*), a bounded
suboptimal method which lazily computes the NN heuristic in batches while
allowing expansions informed by a non-NN heuristic. We show how this subtle but
important change can lead to substantial reductions in expansions compared to
the current blocking alternative, and see that the performance is related to
the information difference between the batch computed NN and fast non-NN
heuristic.
