Hash Distributed A* with one MPI process per worker. More...

#include <PBeFS/astar/HDAStarMPI.h>

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 Member Functions
	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
SolutionT	solve (void) const
	searches the Domain, returning the Solution (on every process)

Detailed Description

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

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.