Safe Parallel Best-NBlock-First search. More...

#include <PBeFS/astar/SafePBNF.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
	SafePBNF (const D &domain, const PBNFOptions &options={})
	constructor, taking the Domain (which must outlive the SafePBNF)
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<NBlockDomain 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::SafePBNF< D, Executor, Open >

Safe Parallel Best-NBlock-First search.

The state space is partitioned into nblocks by the abstraction of the Domain, each nblock with its own OPEN and CLOSED lists. The duplicate detection scope of an nblock is the nblock and its abstract successors, the only nblocks its children can fall in; a worker acquires an nblock whose scope does not overlap the scope of any nblock in use, and then expands its nodes and checks their children for duplicates with no lock at all [see Zhou and Hansen, AAAI 2007, for parallel structured duplicate detection]. The nblocks that can be acquired form the free list, ordered by the best f of their OPEN lists: a worker keeps its nblock while it is not worse than the best free one and than the best nblock its use prevents, after min_expansions expansions at least, and otherwise releases it and acquires the best free one.

The interference scope of an nblock b is made of the predecessors, the successors and the predecessors of the successors of b: the nblocks that cannot be acquired while b is in use. \( \sigma( b ) \) counts the nblocks in use whose interference scope contains b. A worker whose nblock interferes with a better one marks it hot, and \( \sigma_h( b ) \) counts the hot nblocks with b in their scope: a nblock interfering with a hot one is not free, and its worker releases it, so that every hot nblock eventually becomes free, which is what prevents the livelock of plain PBNF in an infinite state space. This is the pseudocode of appendix A of Burns et al. (JAIR 2010); one lock protects the nblock graph ( \( \sigma \), \( \sigma_h \), the hot flags and the free list), and a worker with no free nblock waits on a condition variable.

The incumbent prunes the nodes with f not smaller, a goal is tested when it is selected for expansion, and the search ends when no nblock is in use and the free list is empty. The best f of the nblocks in use by other workers, read to decide whether to switch, is a value they publish after each expansion, which may be slightly out of date.