HDAStar.h File Reference

Header file for the class template HDAStar, Hash Distributed A* on a shared-memory machine, whose workers run on an executor of ADS and exchange nodes through the mailbox of ADS on its channels. More...

#include <atomic>
#include <memory>
#include <mutex>
#include <optional>
#include <string>
#include <type_traits>
#include <vector>
#include "PBeFS/astar/AStar.h"
#include "PBeFS/astar/Distribution.h"
#include "PBeFS/core/SearchUtils.h"
#include "ADS/parallel/Channels.h"
#include "ADS/parallel/Mailbox.h"

Go to the source code of this file.

Classes
struct	ParallelOptions
	the options of the parallel searches: those of the sequential search, and the parameters of the parallel ones [see ParallelParams], with batches of 64 nodes flushed every 64 expansions More...
class	HDAStar< D, Dist, Executor, Open >
	Hash Distributed A* on a shared-memory machine. More...
struct	HDAStar< D, Dist, Executor, Open >::Msg
	a node travelling to its owner More...

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

Detailed Description

Header file for the class template HDAStar, Hash Distributed A* on a shared-memory machine, whose workers run on an executor of ADS and exchange nodes through the mailbox of ADS on its channels.

The search follows section 3 of Kishimoto, Fukunaga and Botea (AIJ 2013) and section 4.1 of Fukunaga et al. (2017), with the notation of the page "Best-first search and A*" of the documentation; the worker \( i \) owns the states \( v \) with \( \mathrm{owner}( v ) = i \), which only it stores, in its lists \( \mathrm{OPEN}_i \) and \( \mathrm{CLOSED}_i \), the incumbent \( z \) is atomic, and a message \( ( v , g' , u ) \) carries a state with the cost and the predecessor of the path that reached it:

 1  procedure HDA*(s₀, p, owner)
 2     z ← ∞;  INSERT(s₀, 0, nil) on owner(s₀)
 3     in parallel, on each worker i = 0, ..., p − 1 do
 4        while the search is not over do
 5           for each message (v, g', u) received do INSERT(v, g', u)
 6           if OPEN_i has a node of f < z then
 7              u ← the first node of OPEN_i, removed (stale entries
                    dropped);  close u
 8              if u is a goal then
 9                 z ← min(z, g(u)), recording u if g(u) < z
10              else for each successor v of u do
11                 g' ← g(u) + c(u, v)
12                 if g' + h(v) ≥ z then continue
13                 if owner(v) = i then INSERT(v, g', u)
14                 else send (v, g', u) to owner(v)
15              every k expansions, send the outboxes not yet full
16           else
17              send all the outboxes;  wait for mail or for the end
18     return the path to the goal of cost z, if z < ∞
19  procedure INSERT(v, g', u)                       ▷ on the owner i of v
20     if g' + h(v) ≥ z then return
21     if v ∉ CLOSED_i then
22        add v to CLOSED_i, with g(v) ← g' and parent(v) ← u
23     else if g' < g(v) then
24        g(v) ← g';  parent(v) ← u;  v is not closed
25     else return                                         ▷ a duplicate
26     push (g' + h(v), g', v) in OPEN_i

The messages travel in batches of batch nodes, and an outbox is sent when it is full (line 14), every flush_period expansions (line 15) and before the worker waits (line 17); the wait ends when mail arrives or when the mailbox detects the end, i.e., when no worker has a node of \( f < z \) and no message is in transit, which is the condition of the page "Parallel A*" for an optimal \( z \). The parents cross the workers, and the path is followed only after all the workers have finished.

Author

Donato Meoli
Dipartimento di Informatica
Università di Pisa

Copyright

© by Donato Meoli