Speculative Path Planning. (arXiv:2102.06261v1 [cs.RO])

[CoffeeKumazaki]

Speculative Path Planning. (arXiv:2102.06261v1 [cs.RO])
https://ift.tt/3qmQmIR

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://ift.tt/37guvet.

via cs.RO updates on arXiv.org http://arxiv.org/

[CoffeeKumazaki]

Astar アルゴリズムを高速化する手法の提案
処理の重い判定を事前に並列で評価しておく（投機的実行?）ことで、並列化の効果を最大限に引き出しており、性能もAstarと同一になることを保証している