Non-Blocking Batch A* (Technical Report)
This work addresses a bottleneck in planning algorithms for AI and robotics by improving efficiency, though it is incremental as it builds on existing batch computation methods.
The paper tackles the problem of slow neural network inference in heuristic search by introducing Non-Blocking Batch A* (NBBA*), which lazily computes NN heuristics in batches while allowing expansions with fast non-NN heuristics, resulting in substantial reductions in expansions compared to blocking methods.
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.