The algorithms

We start from the sequential search (astar( d ) in AStar.h), which is A* with the goal test at the expansion and a node reopened when a cheaper path to it is found. Ties on f are broken in favour of the larger g, which on domains with many states in the last f layer usually reaches the goal much earlier. Next to it, idastar( d ) (IDAStar.h) is the iterative-deepening A* of Korf [7], a depth-first search bounded by f and repeated with a growing bound, which keeps only the current path and hence solves the problems whose CLOSED would not fit in memory, such as the 24-puzzle, at the price of expanding again the states reached by more than one path. Between the two, ddd_astar( d ) (DDDAStar.h) keeps OPEN and CLOSED in files on the disk, in buckets of equal g and h split by the hash of the state, which it expands by increasing f and then g, the duplicates of each file being removed in memory against the closed files of the same h, as in the External A* of Edelkamp, Jabbar and Schrödl [39] with the hash-based delayed duplicate detection of Korf [40]; its memory is that of the largest file of a bucket rather than that of all the states, at the price of the time of the disk, and it needs integer costs, a consistent heuristic and states that are trivially copyable. The parallel searches are the following, each one with the reference for its correctness and its typical behavior.

• SPAStar (SPAStar.h) is the Simple Parallel A* of Algorithm 2 of [1], in which the workers share one OPEN and one CLOSED list, protected by locks. It is the baseline of the survey, and it is not expected to scale beyond a few threads, since each expansion goes through the shared lists.

• MQAStar (MQAStar.h) is SPA* with a relaxed OPEN list, the MultiQueue of [37] from ADS: \(2p\) queues under a lock each, a node pushed into one drawn at random and popped from the better of two, so that the workers rarely wait for one another, at the price of expanding nodes a little out of the order of f; the search ends when a counter of the nodes in OPEN or being expanded falls to 0.

• HDAStar (HDAStar.h) is Hash Distributed A* [2]: a distribution function assigns each state to a worker, which keeps OPEN and CLOSED for the states it owns and receives, packed in batches, those generated by the others. The search ends when no worker has a node with f smaller than the incumbent and no batch is travelling. The distribution is a template parameter (Distribution.h), and the library provides those compared by Jinnai and Fukunaga [5], i.e., Zobrist hashing (HDA*[Z]), Abstract Zobrist hashing (AZHDA*), Zobrist hashing of an abstract state (AHDA* [3]) and the perfect hash modulo the number of workers (HDA*[P], the “bad” case of [3]). Furthermore, it provides the hash of the closed list and, as the baseline without duplicate detection across workers, a random assignment.

• HDAStarMPI (HDAStarMPI.h) is the same search with one MPI process per worker, a nonblocking exchange of the batches and the termination detection of Mattern [11] (four counters reduced with MPI_Iallreduce). At the end, the path is rebuilt state by state, each one sent by the process that holds it.

• SafePBNF (SafePBNF.h) is the livelock-free Parallel Best-NBlock-First search of Burns et al. [3], in which an abstraction partitions the state space into nblocks. A worker expands for a while the nodes of an nblock whose duplicate detection scope (its abstract successors) is not in use by another worker; hence, no lock is taken on the single node.

• PASE (PASE.h) is the Parallel A* for Slow Expansions of Phillips et al. [6], which expands in parallel only the states that the pairwise heuristic proves not to be reachable through a cheaper path from a state still in OPEN. It may pay off only when an expansion costs much more than the bookkeeping; SlowDomain.h adds a given amount of artificial work per expansion to study this regime.

• FarmAStar (FarmAStar.h) is a centralized parallel A* written as a farm with feedback, i.e., the master-worker scheme of [1]: a master holds OPEN and CLOSED, and the workers generate the successors of the nodes it sends them.

The shared-memory searches are templates also over the executor of ADS that runs the workers, i.e., its pool of C++ threads (ADS::ThreadPool, the default), ADS::OpenMPExecutor or ADS::FastFlowExecutor, and they take their channels, the mailbox that detects the end of HDA* and of the distributed B&B, and the farm with feedback from ADS as well (on FastFlow the farm is a farm of FastFlow, and the channels a mesh of single-producer single-consumer queues); a caller that runs many searches may give them an executor of its own by set_executor(), which saves the start of the threads at each search. Their options are in ParallelOptions: the number of workers, the size of a batch, the number of expansions between two flushes of a partially filled batch and the seed of the distribution.