Decoupling Generation and Evaluation for Parallel Greedy Best-First Search(extended version)
This work addresses a bottleneck in parallel search algorithms for AI planning or optimization, offering an incremental improvement to reduce thread idle time.
The paper tackled the inefficiency of constrained parallel greedy best-first search algorithms, where threads idle while waiting for states that meet expansion constraints, by proposing a method that decouples state generation and evaluation, which significantly improved state evaluation rate and search performance.
In order to understand and control the search behavior of parallel search, recent work has proposed a class of constrained parallel greedy best-first search algorithms which only expands states that satisfy some constraint.However, enforcing such constraints can be costly, as threads must be waiting idly until a state that satisfies the expansion constraint is available. We propose an improvement to constrained parallel search which decouples state generation and state evaluation and significantly improves state evaluation rate, resulting in better search performance.