Abstract:
Search-based planning algorithms enable autonomous agents like robots to come up with well-reasoned long horizon plans to achieve a given task objective. They do so by optimizing a task-specific cost function while respecting the constraints on either the agent (e.g. motion constraints) or the environment (e.g. obstacles). In robotics, such as in motion planning for navigation or manipulation, the major chunk of computational effort is spent on edge evaluations as opposed to searching the graph. For such domains, lazy search algorithms have been developed to achieve greater time efficiency. The existing lazy search algorithms achieve this by intelligently balancing computational effort between searching the graph and evaluating edges. However, they are designed to run as a single process and do not leverage the multithreading capability of modern processors. On the other hand, parallel search algorithms achieve faster planning by parallelizing some aspects of the search like either the generation of successors or state expansions. However, these are not maximally efficient in domains where edge evaluations are expensive, as we show in this thesis.

Therefore, in this thesis, we propose a class of algorithms called Massively Parallelized Lazy Planning (MPLP) algorithms that combine the key characteristics of lazy search as well as parallel search algorithms. In doing so, they achieve a drastic improvement in planning times across a range of planning domains over state-of-the-art baselines from either of these two categories of planning algorithms. The key idea that MPLP exploits are that searching the graph and evaluation of edges can be performed asynchronously in parallel. In the first part of the completed work, we present the first instantiation of MPLP and validate it on two different planning domains: 1) motion planning for 3D humanoid navigation and 2) task and motion planning for a robotic assembly task. On the theoretical front, we show that MPLP provides rigorous guarantees on completeness and bounded suboptimality.

In some domains, the generation of successors can also take a non-trivial amount of time. Such domains can benefit from the parallelization of the search itself. To that end, in the second part of the completed work, we present Edge-based Parallel A* for Slow Evaluations (ePA*SE). ePA*SE improves on an existing parallel search algorithm (PA*SE) using several novel ideas that enable it to efficiently parallelize edge evaluations. As is the case 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. ePA*SE on the other hand does not rely on this assumption and can parallelize any search while maintaining optimality.

In domains where states can be generated lazily, however, the lazy state generation takes a non-trivial amount of time, the two different parallelization strategies used by MPLP and ePA*SE can be combined. On the algorithmic front of our proposed work, we will explore this insight. On the practical front, we propose to validate the algorithms developed in this thesis on hard planning domains, that currently take an infeasible amount of time to solve. Finally, we will develop a manual for the robotics community that provides our recommendation on what parallel search algorithm to use given the characteristics of their domain.

Thesis Committee Members:
Maxim Likhachev, Chair
Oliver Kroemer
Stephen Smith
Oren Salzman, Technion-Israel Institute of Technology

More Information