HDAStarMPI

Declared in astar/HDAStarMPI.h; the same class on the site of Doxygen.

template<Domain D, class Dist = StateHashDistribution<D>>
class HDAStarMPI

Hash Distributed A* with one MPI process per worker.

The original HDA* of Kishimoto, Fukunaga and Botea (AIJ 2013): each process owns the states that Dist assigns to it, keeps their nodes in its own memory, and sends the nodes it generates for the other processes in batches with non-blocking sends, checking for incoming batches between two expansions. State and Cost have to be trivially copyable, since the nodes travel as bytes, and Dist deterministic, since the path is rebuilt by asking the owner of each state for its parent.

A node records the state of its parent instead of a pointer. A process that improves the incumbent sends its cost to all the others. The end is detected with the four-counter method of Mattern by the mailbox of ADS, a process joining a wave only when it has no node with f below the incumbent and no batch to send. If a process reaches the node limit, it tells the others, and all of them stop expanding and only drain the messages until the end is detected.

MPI must be initialized by the caller, with at least MPI_THREAD_FUNNELED if the Domain uses threads; all the processes of the communicator call solve(), and all of them get the same Solution.

Public Types

using State = state_t<D>

the state type

using Cost = cost_t<D>

the cost type

using SolutionT = Solution<State, Cost>

the solution type

Public Functions

inline HDAStarMPI(

const D &domain,

const Dist &dist,

const ParallelOptions &options = {},

MPI_Comm comm = MPI_COMM_WORLD

)

constructor, taking the Domain, the distribution and the communicator

inline SolutionT solve(void) const

searches the Domain, returning the Solution (on every process)