FarmAStar
Declared in astar/FarmAStar.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 FarmAStar 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.
Public Types
Public Functions
-
inline explicit 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
-
inline explicit FarmAStar(const D &domain, const ParallelOptions &options = {})