Parallel A* for Slow Expansions. More...

#include <PBeFS/astar/PASE.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
	PASE (const D &domain, const PASEOptions &options={})
	constructor, taking the Domain (which must outlive the PASE)
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<PairwiseDomain D, ADS::WorkerExecutor Executor = ADS::ThreadPool>
class PBeFS_di_unipi_it::PASE< D, Executor >

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.