The search problem

We are concerned with finding a path of minimum cost from the initial state to a goal state, in a graph with nonnegative edge costs, when h is admissible (it never overestimates the cost of reaching a goal). For the searches that do not reopen the closed nodes we also assume that h is consistent, i.e., \(h(u) \leq c(u, v) + h(v)\) for each edge \((u, v)\). Under these conditions the searches of the library return an optimal path (cf. [2] for HDA* and [3] for Safe PBNF). Without consistency the sequential A* is still exact, since it reopens a closed node reached through a cheaper path; the parallel searches, however, may pay several re-expansions for the same node.

All the algorithms are templates over the problem, which is described by a type satisfying the concept Domain of include/PBeFS/astar/Domain.h. Such a type gives state_type and an arithmetic cost_type, together with the methods initial_state(), is_goal( s ), heuristic( s ), hash( s ) and for_each_successor( s , h_s , f ); the latter calls f( t , c , h_t ) for each successor t of s. Note that h(s) is passed in, so that h(t) can be computed incrementally when the heuristic allows it (as the Manhattan distance of the sliding-tile puzzle does). Since all calls are resolved at compile time, no virtual function is paid in the inner loop, which is the first design choice of the fast implementation of Burns et al. [4].

Some algorithms need more than a Domain, and each extra requirement is a refinement of the concept. Thus, FeatureDomain describes a state as a set of propositions (as Zobrist hashing requires), IncrementalFeatureDomain gives the features that a move changes, so that the Zobrist hash of a successor is computed from that of its parent, and AbstractFeatureDomain adds a projection of the features, for Abstract Zobrist hashing [5]. AbstractStateDomain and NBlockDomain give an abstraction of the state space (for AHDA* and PBNF [3]), PairwiseDomain a heuristic between any two states (for PA*SE [6]), and PerfectHashDomain an injective map of the states to the integers. As examples, the library provides the sliding-tile puzzle of any size with the Manhattan distance (SlidingTile.h, which satisfies all of the concepts) and pathfinding with 4 or 8 moves on a grid with cell costs (Grid.h), read from a Moving AI map [15] or generated at random. Also, ExplicitGraph.h holds a weighted graph given by its arcs, which serves for the route-finding problem on the map of Romania of Russell and Norvig [13].