Parallelized Search on Graphs with Expensive-to-Compute Edges

 

Search-based planning algorithms enable robots to come up with well-
reasoned long-horizon plans to achieve a given task objective. They for-
mulate 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 in-
creases, 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 paralleliza-
tion. 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 mod-
ern 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 in-
telligently balancing computational effort between searching the graph
and evaluating edges. The key idea that MPLP exploits is that search-
ing 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 plan-
ning 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 Eval-
uations (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 heteroge-
nous 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 gener-
alizes ePA*SE to domains where edge computations vary significantly.
We show that GePA*SE outperforms ePA*SE and other baselines in do-
mains 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 sig-
nificantly higher success rates.