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

#include <PBeFS/astar/MQAStar.h>

Public Types
using	State = state_t< D >
	the state type
using	Cost = cost_t< D >
	the cost type
using	NodeT = Node< State , Cost >
	the node type
using	SolutionT = Solution< State , Cost >
	the solution type

Public Member Functions
	MQAStar (const D &domain, const ParallelOptions &options={})
	constructor, taking the Domain (which must outlive the MQAStar)
void	set_executor (Executor &ex) noexcept
	sets the Executor that runs the workers, which must outlive the searches; without it, each search builds one of as many threads as there are workers
SolutionT	solve (void) const
	searches the Domain, returning the Solution

Detailed Description

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

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.

See also: A. Postnikova, N. Koval, G. Nadiradze, D. Alistarh, Multi-queues can be state-of-the-art priority schedulers, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 353-367, 2022, doi:10.1145/3503221.3508432