SPAStar
Declared in astar/SPAStar.h; the same class on the site of Doxygen.
-
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 SPAStar 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.
Public Types
Public Functions
-
inline explicit SPAStar(const D &domain, const ParallelOptions &options = {})
constructor, taking the Domain (which must outlive the SPAStar)
-
inline explicit SPAStar(const D &domain, const ParallelOptions &options = {})