MQAStar

Declared in astar/MQAStar.h; the same class on the site of Doxygen.

template<Domain D, ADS::WorkerExecutor Executor = ADS::ThreadPool> class MQAStar

MultiQueue A*: one relaxed OPEN list and one CLOSED list shared by the workers.

The OPEN list of MQAStar, a priority queue under one lock, is the bottleneck of that search when the expansions are fast; here it is the MultiQueue of ADS (Rihani, Sanders and Dementiev, 2015), with \( 2 p \) sequential queues each under its own lock, so that the workers rarely wait for one another. A pop takes the better of the least entries of two queues drawn at random: the expected number of entries of OPEN with a smaller f is less than \( \frac{5}{6} \cdot 2 p \), and therefore the order of the expansions departs from that of A* by little more than it does in SPAStar, where \( p \) nodes are expanded at once anyway. Postnikova et al. (2022) measure the MultiQueue as the scheduler of parallel searches on graphs.

CLOSED is the ConcurrentClosed of SPAStar, the incumbent is atomic, and the search ends when the atomic counter of the entries in OPEN or being expanded falls to 0 [see the pseudocode above]. The stickiness of the MultiQueue is 1, i.e., each operation draws its two queues, which keeps the bound on the rank error above. A node may be expanded before its g is optimal, and then reexpanded, as in SPAStar.