Speculative Path Planning
This addresses performance bottlenecks in path planning for robotics or gaming, though it is incremental as it builds on existing A* methods.
The paper tackles the limited parallelism in A* path planning by proposing Speculative Path Planning, which predicts and pre-evaluates future states to accelerate search, achieving average speedups of 11x over single-threaded and 10x over multi-threaded implementations on a 32-core machine.
Parallelization of A* path planning is mostly limited by the number of possible motions, which is far less than the level of parallelism that modern processors support. In this paper, we go beyond the limitations of traditional parallelism of A* and propose Speculative Path Planning to accelerate the search when there are abundant idle resources. The key idea of our approach is predicting future state expansions relying on patterns among expansions and aggressively parallelize the computations of prospective states (i.e. pre-evaluate the expensive collision checking operation of prospective nodes). This method allows us to maintain the same search order as of vanilla A* and safeguard any optimality guarantees. We evaluate our method on various configurations and show that on a machine with 32 physical cores, our method improves the performance around 11x and 10x on average over counterpart single-threaded and multi-threaded implementations respectively. The code to our paper can be found here: https://github.com/bakhshalipour/speculative-path-planning.