  Anytime search algorithms are useful for planning problems where a solution
is desired under a limited time budget. Anytime algorithms first aim to provide
a feasible solution quickly and then attempt to improve it until the time
budget expires. On the other hand, parallel search algorithms utilize the
multithreading capability of modern processors to speed up the search. One such
algorithm, ePA*SE (Edge-Based Parallel A* for Slow Evaluations), parallelizes
edge evaluations to achieve faster planning and is especially useful in domains
with expensive-to-compute edges. In this work, we propose an extension that
brings the anytime property to ePA*SE, resulting in A-ePA*SE. We evaluate
A-ePA*SE experimentally and show that it is significantly more efficient than
other anytime search methods. The open-source code for A-ePA*SE, along with the
baselines, is available here: https://github.com/shohinm/parallel_search
