PASE

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

template<PairwiseDomain D, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class PASE

Parallel A* for Slow Expansions.

A state \( s \) is independent of a state \( s' \) if \( g( s ) - g( s' ) \leq \varepsilon_p \, h( s' , s ) \), \( h( s' , s ) \) being the forward-backward consistent pairwise heuristic of the Domain: then no path through \( s' \) can lower \( g( s ) \) below \( g( s ) / \varepsilon_p \). A state is safe to expand if it is independent of all the states being expanded (the set BE) and of all the states of OPEN with a smaller f [see Theorem 2 of the paper]. Each worker takes from OPEN the safe state of smallest f, expands it outside the lock and puts back the successors whose g has improved; a state is expanded at most once, and when it is expanded its g is optimal (with \( \varepsilon_p = 1 \)). The search ends when the goal is safe to expand, or when OPEN and BE are both empty. This is Algorithm 1 of the paper; OPEN is an ordered set scanned in increasing f, and a worker that finds no safe state waits until OPEN or BE change.

Finding a safe state costs a scan of the states of OPEN with a smaller f and of BE, all under one lock: PASE pays only when the expansions are slow, as in motion planning with collision checks.

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 Functions

inline explicit PASE(const D &domain, const PASEOptions &options = {})

constructor, taking the Domain (which must outlive the PASE)

inline 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

inline SolutionT solve(void) const

searches the Domain, returning the Solution