PA*SE: Parallel A * for Slow Expansions

Planners need to become faster as we seek to tackle in-creasingly complicated problems. Much of the recent improvements in computer speed is due to multi-core processors. For planners to take advantage of these types of architectures, we must adapt algorithms for par-allel processing. There are a number of planning do-mains where state expansions are slow. One example is robot motion planning, where most of the time is de-voted to collision checking. In this work, we present PA*SE, a novel, parallel version of A * (and weighted A*) which parallelizes state expansions by taking ad-vantage of this property. While getting close to a linear speedup in the number of cores, we still preserve com-pleteness and optimality of A * (bounded sub-optimality of weighted A*). PA*SE applies to any planning prob-lem in which significant time is spent on generating successor states and computing transition costs. We present experimental results on a robot navigation do-main (x,y,heading) which requires expensive 3D colli-sion checking for the PR2 robot. We also provide an in-depth analysis of the algorithm’s performance on a 2D navigation problem as we vary the number of cores (up to 32) as well as the time it takes to collision check successors during state expansions