Parallelized Search on Graphs with Expensive-to-Compute Edges

Abstract

Search-based planning algorithms enable robots to come up with well-reasoned long-horizon plans to achieve a given task objective. They formulate the problem as a shortest path problem on a graph embedded in the state space of the domain. Much research has been dedicated to achieving greater planning speeds to enable robots to respond quickly to changes in the environment. Additionally, as the task complexity increases, it becomes important to incorporate more sophisticated models like simulators in the planning loop. However, these complex models are expensive to compute and prohibitively reduce planning speed. Because of the plateau in CPU clock speed, single-threaded planning algorithms have hit a performance plateau. On the other hand, the number of CPU cores has grown significantly, a trend that is likely to continue. This calls for the need for planning algorithms that exploit parallelization. However, unlike sampling-based planning algorithms, parallelizing search-based planning algorithms is not trivial if optimality or bounded sub-optimality is to be maintained due to their sequential nature. A key feature of robotics domains is that the major chunk of computational effort during planning is spent on computing the outcome of an action and the cost of the resulting edge instead of searching the graph. In this thesis, we exploit this insight and develop several parallel search-based planning algorithms that harness the multithreading capability of modern processors to parallelize edge computations. We show that these novel algorithms drastically improve planning times across several domains.

Our first contribution is a parallelized lazy search algorithm, Massively Parallelized Lazy Planning (MPLP). The existing lazy search algorithms are designed to run as a single process and achieve faster planning by intelligently balancing computational effort between searching the graph and evaluating edges. The key idea that MPLP exploits is that searching the graph and evaluating edges can be performed asynchronously in parallel. On the theoretical front, we show that MPLP provides rigorous guarantees of completeness and bounded suboptimality.

As with all lazy search algorithms, MPLP assumes that successor states can be generated without evaluating edges, which allows the algorithm to defer edge evaluations and lazily proceed with the search. However, this assumption does not always hold, for example, in the case of simulation-in-the-loop planning, which uses a computationally expensive simulator to generate successors. To that end, our second contribution is Edge-Based Parallel A* for Slow Evaluations (ePA*SE), which interleaves planning with the parallel evaluation of edges while guaranteeing optimality. We also present its bounded suboptimal variant that trades off optimality for planning speed.

For its applicability in real-time robotics, ePA*SE must compute plans under a time budget and therefore have anytime performance. Though lower solution cost is desired, it is not the first priority in such settings. Our third contribution is Anytime Edge-Based Parallel A* for Slow Evaluations (A-ePA*SE), which brings the anytime property to ePA*SE.

ePA*SE targets domains with expensive but similar edge computation times. However, in several robotics domains, the action space is heterogenous in the computational effort required to evaluate the outcome of an action and its cost. Therefore, our fourth contribution is Generalized Edge-Based Parallel A* for Slow Evaluations (GePA*SE), which generalizes ePA*SE to domains where edge computations vary significantly. We show that GePA*SE outperforms ePA*SE and other baselines in domains with heterogenous actions by employing a parallelization strategy that explicitly reasons about the computational effort required for their evaluation.

Finally, we demonstrate the utility of parallelization in an algorithm that integrates graph search techniques with trajectory optimization (INSAT). Since trajectory optimization is computationally expensive, running INSAT on a single thread limits its practical use. The proposed parallelized version Parallelized Interleaving of Search and Trajectory Optimization (PINSAT) achieves several multiple increases in planning speed and significantly higher success rates.