Parallel A* for Planning with Time-consuming State Expansions

June 2014

Parallel A* for Planning with Time-consuming State Expansions

Authors:

Mike Phillips, Sven Koenig, and Maxim Likhachev

Abstract:

Planners need to become faster as we seek to tackle increasingly 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 parallel processing. There are a number of planning domains where state expansions are slow. One example is robot motion planning, where most of the time is devoted 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 advantage of this property. While getting close to a linear speedup in the number of cores, we still preserve completeness and optimality of A* (bounded sub-optimality of weighted A*). PA*SE applies to any planning problem in which significant time is spent on generating successor states and computing transition costs. We present experimental results on a robot navigation domain (x,y,heading) which requires expensive 3D collision 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.
@conference{Phillips-2014-109531,
author = {Mike Phillips And Sven Koenig And Maxim Likhachev},
title = {Parallel A* for Planning with Time-consuming State Expansions},
booktitle = {Proceedings of 24th International Conference on Automated Planning and Scheduling (ICAPS '14)},
year = {2014},
month = {June},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.