Simple Parallel A*: one OPEN and one CLOSED list shared by the workers. More...

#include <PBeFS/astar/SPAStar.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
	SPAStar (const D &domain, const ParallelOptions &options={})
	constructor, taking the Domain (which must outlive the SPAStar)
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 Open = std::conditional_t< std::is_integral_v< cost_t< D > > , BucketOpenList< Node< state_t< D > , cost_t< D > > > , HeapOpenList< Node< state_t< D > , cost_t< D > > > >>
class PBeFS_di_unipi_it::SPAStar< D, Executor, Open >

Simple Parallel A*: one OPEN and one CLOSED list shared by the workers.

This is Algorithm 2 of Fukunaga et al. (2017), due to Irani and Shih (1986): each worker takes the best node from the shared OPEN list, expands it, and puts the successors back; the incumbent prunes the nodes with f not smaller, and the search ends when OPEN has no node with f smaller than the incumbent and no worker is expanding. A node may be expanded before its g is optimal, and then re-expanded, as with most parallel A* variants.

OPEN is protected by one lock. CLOSED is the ConcurrentClosed of the data structures chosen [see ConcurrentClosed.h]: with those of ADS a lock-free set of the nodes, whose fields that change are protected by 256 locks chosen by the address of the node, taken at line 21 only when \( v \) is in CLOSED and \( g' \) is smaller than its g read without the lock; with the others 256 shards, each with its own lock, which also protects the nodes of its states. The stale test of an entry popped from OPEN is done under the lock of its node. The expansion itself runs with no lock held. The survey reports that, when the expansions are as fast as on the sliding-tile puzzle, the lock of OPEN makes SPA* slower than A*; it pays when the expansions are slow.