Separate Generation and Evaluation for Parallel Greedy Best-First Search

Parallelization of combinatorial search algorithms is important in order to maximize search algorithm performance on modern, multi-core CPUs. In the case of cost-optimal search, parallelization of the standard A* algorithm (Hart, Nilsson, and Raphael 1968) is somewhat well understood, and viable, practical approaches have been proposed. The optimality requirement imposes a relatively strong constraint on the set of states which must be expanded by any parallel A* (all nodes with $f$-values less than the optimal path cost $C*$ must be expanded), so previous work has focused on approaches for expanding those required states while minimizing synchronization and communication overheads and avoiding expansion of non-required states (Burns et al. 2010; Kishimoto, Fukunaga, and Botea 2013; Phillips, Likhachev, and Koenig 2014; Fukunaga et al. 2017).

For satisficing search where the object is to quickly find any valid solution path (regardless of path cost), parallelization is not well understood. Greedy Best First Search (GBFS; Doran and Michie (1966)) is a widely used satisficing search algorithm. However, the performance of straightforward parallelizations of GBFS is non-monotonic with respect to resource usage – there is a significant risk that using $k$ threads can result in significantly worse performance than using fewer than $k$ threads. It has been shown experimentally that parallel GBFS can expand orders of magnitude more states than GBFS (Kuroiwa and Fukunaga 2019), and it has been shown theoretically that KPGBFS, a straightforward parallelization of GBFS, can expand arbitrarily many more states than GBFS (Kuroiwa and Fukunaga 2020).

Unlike parallel cost-optimal search, there is no obvious set of states which a parallel satisficing search must explore in order to be considered a “correct” parallelization of the sequential algorithm. Recent theoretical analysis of GBFS has yielded a promising direction for determining which states should be expanded. Heusner, Keller, and Helmert (2017) identified the Bench Transition System ($\mathit{BTS}$), the set of all states that can be expanded by GBFS under some tie-breaking policy (conversely, if a state is not in the BTS, there does not exist any tie-breaking strategy for GBFS which will expand that state). Limiting search to states in the $\mathit{BTS}$ provides a natural constraint for parallel GBFS.

Recent work has proposed parallel GBFS algorithms which expand states from $\mathit{Open}$ only if some constraint is satisfied. Kuroiwa and Fukunaga (2020) proposed PUHF, a parallel GBFS which guarantees that only states which are in the $\mathit{BTS}$ will be expanded. However, this guarantee comes at a cost in performance. Since PUHF prevents expansion of any state unless it is certain that the state is in the $\mathit{BTS}$, threads can be forced to be idle while they wait until a state which is guaranteed to be in the $\mathit{BTS}$ become available, resulting in significantly worse performance than KPGBFS. Improved versions of PUHF with looser constraints (which still guarantee that only states in the BTS are expanded) have been proposed (Shimoda and Fukunaga 2023), but these still have a significantly lower state evaluation rate than parallel GBFS without expansion constraints.

In this paper, we propose Separate Generation and Evaluation (SGE), which decouples state expansion and evaluation so that instead of waiting for a single thread to fully expand a state (generating and evaluating its successors), multiple threads can be used to evaluate the successors. We show that this significantly improves the state evaluation rate in parallel GBFS with expansion constraints.

The rest of the paper is structured as follows. Section 2 reviews background and previous work. Section 3 presents Constrained Parallel GBFS (CPGBFS), which unifies KPGBFS and all previous versions of PUHF as instances of a class of search algorithms with various state expansion constraints. Section 4 discusses the state expansion bottlenecks in CPGBFS. Section 5 proposes SGE. Section 6 experimentally evaluates SGE and compares them to PUHF and KPGBFS. Section 7 concludes with a discussion and directions for future work.

As described above, the original proposing PUHF and PUHF2–4 presented these algorithms as marking states guaranteed to be in the BTS as certain, and only expanding nodes marked as certain. The stage in the algorithm where states were marked as certain were specific to the specific algorithm (PUHF, PUHF2–4). However, the the similarities and differences among KPGBFS, PUHF, and PUHF2–4 can be clarified by reframing this behavior in terms of satisfying an algorithm-specific expansion constraint.

We present a unified framework, Constrained Parallel GBFS (CPGBFS) (Algorithm 1), which subsumes KPGBFS, PUHF, and PUHF2–4. CPGBFS is a schema for a class of parallel search algorithms based on KPGBFS, which only expands nodes which satisfy some algorithm-specific constraint in line 7, where $\mathit{satisfies(s)}$ is a function which returns $true$ if and only if $s$ satisfies the algorithm-specific expansion constraint.

KPGBFS is a special case of CPGBFS where $\mathit{satisfies(s)}$ always returns $true$. The previously proposed BTS-constrained search algorithms (PUHF and PUHF2–4) are instances of CPGBFS where the $\mathit{satisfies(s)}$ function implements a check for the sufficient constraint which guarantees that $s$ is in the BTS – the specific implementation details of $\mathit{satisfies}$ depend on whether the algorithm is PUHF, PUHF2, PUHF3, or PUHF4. In addition, algorithm-specific auxiliary computations related to $\mathit{satisfies}$ are omitted for clarity.

Previous work has shown that CPGBFS (all of the PUHF variants) have a significantly lower state evaluation rate than unconstrained parallel search (KPGBFS). There are two, related reasons for the low state evaluation rate in CPGBFS: (1) the expansion constraint, and (2) eager evaluation policy.

In this section, we propose SGE, an approach for increasing the state evaluation rate in constrained best-first search algorithms such as PUHF. SGE alleviates the batch successor insertion bottleneck described above.

Continuing the example from the previous section, in the case of Figure 1, instead of waiting idly while one thread expands $s_{1,1}$ (which includes computing all of the heuristic values for $s_{2,1},s_{2,2}^{1},..,s_{2,2}^{x}$), it would be more efficient to parallelize the evaluation of $s_{2,1},s_{2,2}^{1},..,s_{2,2}^{x}$ among available threads.

We propose Separate Generation and Evaluation (SGE), which parallelizes state evaluations in addition to expansions. The main idea is to decompose the expansion of state $s$ into separate units of work which can be parallelized: (1) successor generation, which generates $succ(s)$, the successors of $s$, and (2) successor evaluation, which evaluates $succ(s)$.

Algorithm 2 shows Constrained Parallel GBFS with SGE. After a thread selects a state for expansion from the shared $\mathit{Open}$, it generates $succ(s)$, and inserts $succ(s)$ into the shared $\mathit{Unevaluated}$ queue. The evaluation of states in $\mathit{Unevaluated}$ is done in parallel, taking precedence over selection of states for expansion (a thread will select a state for expansion from $\mathit{Open}$ only if $\mathit{Unevaluated}$ is currently empty (Algorithm 2, line 5)).

Evaluated states are not immediately inserted into $\mathit{Open}$. Instead, we insert all of the successors of $s$ simultaneously into $\mathit{Open}$, after they have all been evaluated (lines 10-16). This is so that the parallel search is able to prioritize $succ(s)$ similarly to GBFS (otherwise, $succ(s)$ can be expanded in a completely different order than by GBFS, which we are trying to prevent).

Consider the search behavior of BTS-constrained parallel search such as PUHF with SGE on the search space in Figure 1. First, a thread pops $s_{0}$ from $\mathit{Open}$ ($satisfied(s_{0})=true$), and generates its successors ($s_{1,1},s_{1,2}^{1},..,s_{1,2}^{x}$), which are inserted in $\mathit{Unevaluated}$. Available threads will pop these successors from $\mathit{Unevaluated}$ and evaluate them. When all successors of $s_{0}$ have been evaluated, they are all inserted in $\mathit{Open}$. Next, some thread removes $s_{1,1}$ ($satisfied(s_{1,1})=true$), generates its successors ($s_{2,1},s_{2,2}^{1},..,s_{2,2}^{x}$), and inserts them in $\mathit{Unevaluated}$. While generating the successors of $s_{1,1}$, other threads may try to pop a state from $\mathit{Open}$, but since the top state at that time ($s_{1,2}^{i}$) is not in the BTS ($satisfied(s_{1,2}^{i})=false$), $\mathit{Open}$ will remain untouched. After the successors of $s_{1,1}$ have been inserted in $\mathit{Unevaluated}$, the available threads will remove them from $\mathit{Unevaluated}$ and evaluate them. The search continues similarly until $s_{goal}$ is found. Each time a state’s successors are generated, multiple available threads evaluate the successors in parallel. This clearly improves thread utilization compared to BTS-constrained search without SGE, which only uses one thread to expand (generate and evaluate successors of) each state so that only 1 thread is active throughout the search space in Figure 1.

The basic idea of decoupling state generation and state evaluation is similar to that of ePA*SE, which decouples state generation and edge evaluations in a parallel A* (Mukherjee, Aine, and Likhachev 2022), where an edge evaluation is the computation required to evaluate the application of an operator, e.g., collision checking using a simulation model in robot motion planning). In both cases, using only a single thread to fully process a state expansion causes a bottleneck forcing other threads to be idle, as search algorithm constraints for constrained parallel GBFS and A* requires waiting until that expansion is fully processed, so decomposing the expansion process and parallelizing it among the available threads leads to better processor utilization. Because the requirements and objectives of GBFS (satisficing search) and A* (cost-optimal search) differ, the implementation of SGE is somewhat simpler (using an $\mathit{Unevaluated}$ queue instead of dummy/real edges as in ePA*SE).

In this section, we experimentally evaluate SGE. We emphasize that the goal of this experimental study is to evaluate and understand SGE as an implementation technique which can be applied to a wide range of parallel best-first search algorithms. Thus, we focus on comparing PUHF2 vs. PUHF2_S to evaluate the effect of SGE on constrained parallel best-first search, and we compare KPGBFS vs. KPGBFS_S to evaluate the effect of SGE on unconstrained parallel best-first search. Comparing constrained parallel search vs. unconstrained parallel search (e.g., PUHF2_S vs. KPGBFS) is beyond the scope of this study.

To evaluate SGE, we use the satisficing instances of the Autoscale-21.11 benchmark set (42 STRIPS domains, 30 instances/domain, 1260 total instances) (Torralba, Seipp, and Sievers 2021), an improved benchmark suite based on the IPC classical planning benchmarks. All search algorithms use the FF heuristic (Hoffmann and Nebel 2001). Each run has a run time limit of 5 minutes and 3 GB RAM/thread (e.g., 24 GB total for a 8-thread run) limit on a Intel(R) Xeon(R) CPU E5-2670 v3 @ 2.30GHz processor.

All tie-breaking is First-In-First-Out.

We evaluate all algorithms on $k\in\{4,8,16\}$ threads. We also report some results for single-threaded GBFS as a baseline.

Table 1(a) and Figure 2 compares the state evaluation rates of the algorithms. Table 1(b) and Figure 3 compares the number of states expanded by the algorithms. Table 1(c) and Figure 4 compares search time by the algorithms. Table 1(d) shows the speedup compared to single-threaded GBFS.

Table 2(a) shows the number of instances solved by each algorithm, and Table 2(b) shows the number of problems solved by algorithm $x$ but not by algorithm $y$ for $x,y\in\{\text{KPGBFS},\text{KPGBFS${}_{S}$},\text{PUHF2},\text{PUHF2${}_{S}$}\}$.

In Tables 1(a)-1(d), we include only the 412 instances solved by all algorithms so that means can be computed. Figures 2–4 show all instances – instances which were not solved (due to either timeout or memory exhaustion) are shown as either $x=\mathit{fail}$ or $y=\mathit{fail}$.

We proposed SGE, an approach to increase state evaluation rates in constrained parallel search algorithm by separating successor generation and evaluation. We showed SGE significantly increases the state evaluation rate of PUHF2, resulting in improved overall performance for PUHF2_S compared to PUHF2. Preliminary experiments with PUHF and PUHF3 have yielded similar results, suggesting that SGE consistently yields performance improvements for parallel GBFS algorithms with state expansion constraints. For unconstrained search such as KPGBFS, SGE results in a decrease in evaluation rate, as there are no bottlenecks in unconstrained search, and the additional complexity of SGE imposes an overhead.

We also showed that SGE results in more efficient search (fewer expansions to solve an instance) for both PUHF2 (constrained search) as well as for KPGBFS (unconstrained search). While we hypothesize that this is because SGE with $k$ threads behaves as if there were fewer, faster threads as explained in Section 5, a deeper experimental investigation of the expansion order with and without SGE is an avenue for future work.

The batch successor insertion state bottleneck addressed by SGE (Section 4) is a byproduct of implementing a parallel search algorithm which is limited to expanding a set of states similar to the states expanded by single-threaded GBFS with a standard eager evaluation policy, where states are evaluated immediately after they are generated and before being inserted in $\mathit{Open}$. In lazy (deferred) evaluation (Richter and Helmert 2009), where states are not evaluated before insertion into $\mathit{Open}$ and are inserted into $\mathit{Open}$ based on their parent’s $f$-value (and later evaluated when they are expanded), the batch successor insertion bottleneck would not apply. Search with lazy evaluation behaves quite differently than search with eager evaluation, and parallel satisficing search with lazy evaluation is an avenue for future work.