a master-worker parallel A* on a farm with feedback More...

#include <PBeFS/astar/FarmAStar.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
	FarmAStar (const D &domain, const ParallelOptions &options={})
	constructor, taking the Domain (which must outlive the FarmAStar); threads is the number of workers, batch the nodes per task
void	set_executor (Executor &ex) noexcept
	sets the Executor that runs the master and the workers, which must outlive the searches and have at least threads + 1 threads; without it, each search builds one of threads + 1 threads
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::FarmAStar< D, Executor, Open >

a master-worker parallel A* on a farm with feedback

The master of the farm alone owns OPEN, CLOSED and the nodes, so it needs no lock. It sends the best nodes of OPEN, batch at a time, to the workers that are free (the farm schedules on demand); a worker generates the successors of its nodes with their costs and heuristic values and sends them back on the feedback channel, and the master checks them against CLOSED and puts the new and improved ones in OPEN. It is the centralized approach of Kumar, Ramesh and Rao (1988), the same as SPAStar but with the master in place of the locks, close to the K-best-first search of Felner, Kraus and Korf (2003) without its synchronization at each round. A node may be expanded before its g is optimal, and then re-expanded; the incumbent prunes, and the search ends when no node of OPEN has f below the incumbent and no node is out at a worker. Since the master does all the bookkeeping, FarmAStar pays only when the expansions are slow.

The farm runs threads + 1 threads, those of an Executor of ADS [see ADS::feedbackFarm()]: with PBEFS_PIN the master takes the first CPU of the affinity mask and the worker \( i \) the CPU \( i + 1 \) of it, counting from 0 [see pin_worker()], but for the thread of the caller.