FarmAStar.h File Reference

Header file for the class template FarmAStar, a centralized parallel A* written as a farm with feedback on an executor of ADS: a master holds OPEN and CLOSED, and the workers expand the nodes it sends them. More...

#include <memory>
#include <stdexcept>
#include <tuple>
#include <type_traits>
#include <vector>
#include "PBeFS/astar/HDAStar.h"
#include "ADS/parallel/Farm.h"

Go to the source code of this file.

Classes
class	FarmAStar< D, Executor, Open >
	a master-worker parallel A* on a farm with feedback More...

Namespaces
namespace	PBeFS_di_unipi_it
	namespace for the Parallel Best-First Search library

Detailed Description

Header file for the class template FarmAStar, a centralized parallel A* written as a farm with feedback on an executor of ADS: a master holds OPEN and CLOSED, and the workers expand the nodes it sends them.

The search is the centralized scheme of section 3.2 of Fukunaga et al. (2017), written as a farm with feedback, with the notation of the page "Best-first search and A*" of the documentation: the master alone holds OPEN, CLOSED, the nodes and the incumbent \( z \), out counts the tasks at the workers, and INSERT is the one of HDA* [see HDAStar.h] on the lists of the master:

 1  procedure MASTER(s₀, p)
 2     z ← ∞;  out ← 0;  INSERT(s₀, 0, nil)
 3     loop
 4        DISPATCH()
 5        if out = 0 and OPEN has no node of f < z then return
 6        receive a task T back from a worker;  out ← out − 1
 7        for each successor v of a node u of T, with c(u, v) and h(v) do
 8           if g(u) + c(u, v) + h(v) < z then INSERT(v, g(u) + c(u, v), u)
 9  procedure DISPATCH()
10     while out < p and OPEN has a node of f < z do
11        T ← ∅
12        while |T| < batch and OPEN has a node of f < z do
13           u ← the first node of OPEN, removed;  close u
14           if u is a goal then z ← min(z, g(u)), recording u if g(u) < z
15           else T ← T ∪ {u}
16        if T = ∅ then return
17        send T to a free worker;  out ← out + 1
18  procedure WORKER(T)                       ▷ on each of the p workers
19     for each u ∈ T, add to T the successors v of u, with c(u, v), h(v)
20     send T back to the master

The test of line 5 is exact, since the master alone changes OPEN and \( z \) and a node is either in OPEN or in a task that is out; the workers only generate the successors, and therefore the scheme pays when the generation costs much more than the bookkeeping of line 8, which the master does alone.

Author

Donato Meoli
Dipartimento di Informatica
Università di Pisa

Copyright

© by Donato Meoli