Parallelized Search on Graphs with Expensive-to-Compute Edges

<p> </p> <p>Search-based planning algorithms enable robots to come up with well-<br> reasoned long-horizon plans to achieve a given task objective. They for-<br> mulate the problem as a shortest path problem on a graph embedded<br> in the state space of the domain. Much research has been dedicated to<br> achieving greater planning speeds to enable robots to respond quickly<br> to changes in the environment. Additionally, as the task complexity in-<br> creases, it becomes important to incorporate more sophisticated models<br> like simulators in the planning loop. However, these complex models are<br> expensive to compute and prohibitively reduce planning speed. Because<br> of the plateau in CPU clock speed, single-threaded planning algorithms<br> have hit a performance plateau. On the other hand, the number of<br> CPU cores has grown significantly, a trend that is likely to continue.<br> This calls for the need for planning algorithms that exploit paralleliza-<br> tion. However, unlike sampling-based planning algorithms, parallelizing<br> search-based planning algorithms is not trivial if optimality or bounded<br> sub-optimality is to be maintained due to their sequential nature. A key<br> feature of robotics domains is that the major chunk of computational<br> effort during planning is spent on computing the outcome of an action<br> and the cost of the resulting edge instead of searching the graph. In this<br> thesis, we exploit this insight and develop several parallel search-based<br> planning algorithms that harness the multithreading capability of mod-<br> ern processors to parallelize edge computations. We show that these novel<br> algorithms drastically improve planning times across several domains.<br> </p> <p>Our first contribution is a parallelized lazy search algorithm, Massively<br> Parallelized Lazy Planning (MPLP). The existing lazy search algorithms<br> are designed to run as a single process and achieve faster planning by in-<br> telligently balancing computational effort between searching the graph<br> and evaluating edges. The key idea that MPLP exploits is that search-<br> ing the graph and evaluating edges can be performed asynchronously in<br> parallel. On the theoretical front, we show that MPLP provides rigorous<br> guarantees of completeness and bounded suboptimality.<br> </p> <p>As with all lazy search algorithms, MPLP assumes that successor states<br> can be generated without evaluating edges, which allows the algorithm to<br> defer edge evaluations and lazily proceed with the search. However, this<br> assumption does not always hold, for example, in the case of simulation-<br> in-the-loop planning, which uses a computationally expensive simulator<br> to generate successors. To that end, our second contribution is Edge-<br> Based Parallel A* for Slow Evaluations (ePA*SE) which interleaves plan-<br> ning with the parallel evaluation of edges while guaranteeing optimality.<br> We also present its bounded suboptimal variant that trades off optimality<br> for planning speed.<br> </p> <p>For its applicability in real-time robotics, ePA*SE must compute plans<br> under a time budget and therefore have anytime performance. Though<br> lower solution cost is desired, it is not the first priority in such settings.<br> Our third contribution is Anytime Edge-Based Parallel A* for Slow Eval-<br> uations (A-ePA*SE), which brings the anytime property to ePA*SE.<br> </p> <p>ePA*SE targets domains with expensive but similar edge computation<br> times. However, in several robotics domains, the action space is heteroge-<br> nous in the computational effort required to evaluate the outcome of an<br> action and its cost. Therefore, our fourth contribution is Generalized<br> Edge-Based Parallel A* for Slow Evaluations (GePA*SE), which gener-<br> alizes ePA*SE to domains where edge computations vary significantly.<br> We show that GePA*SE outperforms ePA*SE and other baselines in do-<br> mains with heterogenous actions by employing a parallelization strategy<br> that explicitly reasons about the computational effort required for their<br> evaluation.<br> Finally, we demonstrate the utility of parallelization in an algorithm that<br> integrates graph search techniques with trajectory optimization (INSAT).<br> Since trajectory optimization is computationally expensive, running INSAT<br> on a single thread limits its practical use. The proposed parallelized<br> version Parallelized Interleaving of Search and Trajectory Optimization<br> (PINSAT) achieves several multiple increases in planning speed and sig-<br> nificantly higher success rates.</p>