7. Bidirectional and external-memory search¶
[Source: include/PBeFS/astar/Bidirectional.h
(BidirectionalOptions, BiNode, BiQueue, BiFronts, ReverseDomain,
BlindDomain), BiBestFirst.h (BiBestFirst, bidijkstra,
mm, mme, fmm, bae), NBS.h (NBS, nbs),
DVCBS.h (DVCBS, dvcbs), GBFHS.h (GBFHS,
gbfhs, bibfs), ParallelBidirectional.h
(ParallelBidirectional, pnba), PEMSearch.h (PEMSearch,
PEMOptions), IDDAStar.h (IDDAStar, IDDOptions,
idd_astar), include/PBeFS/astar/Domain.h
(BidirectionalDomain, BackwardOperatorDomain, MinCostDomain,
for_each_parent); the tests bidir, bidir-thread, pem-thread and idd
of test/bidirectional.cpp]
We are concerned in this chapter with two ways of reducing what a search must hold to find a path of least cost. The first is to search from both ends: a front-to-end bidirectional search grows a forward search from the initial state \(s\) and a backward search from the goal \(t\), along the edges reversed, each guided by a heuristic towards the root of the other, and it stops when the two have met and a lower bound on the optimal cost \(C^*\), drawn from their open lists, proves that no cheaper path joins them. Since the work of a search grows, roughly, exponentially with the depth it reaches, two searches of half the depth may cost far less than one of the whole depth (cf. the last row of Table 1.1 in §1.3); the difficulty, which took some decades to settle, is to stop as soon as the two searches meet without giving up optimality, and without letting either of them go beyond the middle. The second way is to keep the lists on the disk, as the delayed duplicate detection of §4.6 does for A\(^*\): here we treat the parallel external-memory bidirectional searches of Siag et al. [57], which combine the two ideas, and the A\(^*\) with immediate duplicate detection on the disk of Lin and Fukunaga [95], whose closed list is a file read at random, as fits a solid state drive.
The structure of the chapter is as follows. Section 7.1 states the interface, i.e., the concepts that a domain has to satisfy to be searched backward, the options of the searches and the two adapters of a domain. Section 7.2 describes the table of the nodes that the two directions share, the meeting of the two fronts and the two lemmas on which every proof of the chapter rests, and section 7.3 the lower bounds on \(C^*\) by which the searches stop. Sections 7.4 to 7.7 give the searches that hold their lists in memory: those that expand one node at a time (the bidirectional Dijkstra's algorithm, MM, MMe, fMM and BAE\(^*\)), NBS with the must-expand graph, DVCBS with its dynamic vertex cover, and GBFHS. Section 7.8 runs the two directions at once on two workers (PNBA\(^*\) and the parallel versions of the others), section 7.9 gives the parallel external-memory searches of the framework PEM-BiHS, and section 7.10 the A\(^*\) with immediate duplicate detection on the disk. Sections 7.11 to 7.13 give the benchmark, the notes and references, and the exercises. We use the notation of Chapter 1, the results on A\(^*\) of Chapter 2, the lazy priority queues and the tables of Chapter 3, and the buckets and files of the external search of §4.6, which we do not repeat.
7.1 The problem and the interface¶
We consider the problem of Chapter 1 with a
single goal state \(t\). A bidirectional search needs, besides a Domain, the
goal itself (from which the backward search starts), the predecessors of a
state (along which that search moves) and a heuristic towards \(s\) (by which
it is guided). These are the requirements of the concept
BidirectionalDomain (Domain.h:476): a Domain that also
has goal_state(), the one state for which is_goal() holds,
backward_heuristic( s ), an estimate of the cost of a path from the
initial state to s, and for_each_predecessor( s , hb_s , f ), which
calls f( t , c , hb_t ) for each state t with an edge \((t, s)\) of cost
c, hb_t being the backward heuristic of t, computed (incrementally, if
the domain can) from that of s. The refinement BackwardOperatorDomain
(Domain.h:496) has, moreover,
for_each_predecessor( s , hb , op , f ), which skips the predecessor that the
inverse of op leads to, op being the operator by which the backward search
generated s, exactly as an OperatorDomain skips the move back to the parent
of a successor (Lemma 1.8); the function template
for_each_parent (Domain.h:773) is the backward counterpart
of for_each_child (Algorithm 1.1), and it calls the form with the operator
when the domain has it, and the plain one otherwise. Finally, MinCostDomain
(Domain.h:512) is a Domain with min_edge_cost(), a lower
bound \(\varepsilon \ge 0\) on the cost of an edge, which several of the bounds
below use. The sliding-tile puzzles (whose predecessors are their successors,
the moves being reversible at the same cost), the grids (whose predecessors are
the moves reversed, at the cost of the cell left) and the explicit graphs
satisfy these concepts, and the test bidir checks, on random grids with
weighted cells, that the edges seen backward are those seen forward, with their
costs.
Definition 7.1 (Notation of the bidirectional searches). We write \(d(u, v)\) for the cost of a cheapest path from \(u\) to \(v\), \(C^* = d(s, t)\), \(F\) and \(B\) for the forward and the backward direction, and \(\bar D\) for the direction other than \(D\). For a state \(n\), \(g_F(n)\) is the cost of the best path found from \(s\) to \(n\) and \(g_B(n)\) that of the best path found from \(n\) to \(t\), each \(\infty\) until its direction reaches \(n\); we write \(d_F(n) = d(s, n)\) and \(d_B(n) = d(n, t)\) for their optimal values. \(h_F(n)\) estimates \(d(n, t)\) and \(h_B(n)\) estimates \(d(s, n)\), and \(f_D = g_D + h_D\). The heuristic \(h_F\) is admissible if \(h_F(n) \le d(n, t)\) and consistent if \(h_F(u) \le c(u, v) + h_F(v)\) for every edge \((u, v)\) (Definitions 2.1 and 2.2), and symmetrically \(h_B\) is admissible if \(h_B(n) \le d(s, n)\) and consistent if \(h_B(v) \le c(u, v) + h_B(u)\). Finally, \(\varepsilon \ge 0\) is a lower bound on the cost of every edge, and \(U\) is the incumbent, the cost of the best path from \(s\) to \(t\) found so far (\(\infty\) if none), i.e., the \(z\) of Table 1.2, which we call \(U\) here as the headers and the literature on bidirectional search do.
Two adapters change a BidirectionalDomain without copying it.
ReverseDomain< D > (Bidirectional.h:640) swaps the
initial and the goal state: its successors are the predecessors of D, its
heuristic is the backward heuristic of D, and the other way round, so that
A\(^*\) on it is the reverse A\(^*\) (rA\(^*\)) of Siag et al.
[57], and a path found on it, reversed, is a
path of D; the operators are kept when D is both an OperatorDomain and
a BackwardOperatorDomain, and min_edge_cost() when D is a
MinCostDomain. BlindDomain< D >
(Bidirectional.h:709) replaces both heuristics by 0,
so that A\(^*\) on it is Dijkstra's algorithm, and MM on it is the brute-force
bidirectional search MM\(_0\) of Holte et al. [61].
Both hold a reference to D, which must outlive them.
The in-memory searches take the options
struct BidirectionalOptions : public SearchOptions {
/// the least cost \f$ \epsilon \f$ of an edge, by which the bound
/// \f$ g_F + g_B + \epsilon \f$ is raised; negative to take
/// min_edge_cost() of a MinCostDomain, and 0 for any other Domain
double epsilon = -1;
/// true if both heuristics are consistent: a search then does not open a
/// node that the other has closed, and BAE* may use its bound; false
/// asks only for admissible heuristics, and BAE* refuses it
bool consistent = true;
/// true to stop at the largest of all the lower bounds valid under the
/// heuristics (those of A*, MM and, with consistent heuristics, BAE*)
/// instead of the one of the algorithm alone
bool all_bounds = false;
/// the direction of the next expansion, for the algorithms that expand
/// one node at a time
SideChoice side = SideChoice::automatic;
/// the fraction \f$ p \in ( 0 , 1 ) \f$ of the optimal path at which
/// fMM( p ) meets, and the share of the forward search in the split of
/// GBFHS
double fraction = 0.5;
/// for NBS and DVCBS, true to make ready at once the nodes whose
/// \f$ f \f$ equals the lower bound, which is the version that covers the
/// pairs needed to find all the optimal paths [Shperberg et al., AAAI
/// 2019], false for the version of Chen et al. (IJCAI 2017), which makes
/// them ready one at a time
bool eager = false;
}; // end( struct( BidirectionalOptions ) )
i.e., those of every search (SearchOptions, of which node_limit bounds
the nodes stored by the two directions together, expected_nodes sizes the
table of the nodes at the start, and a weight other than 1 is refused with
std::invalid_argument) and the following ones. epsilon is the
\(\varepsilon\) of Definition 7.1: a negative value (the default) takes
min_edge_cost() of a MinCostDomain, and 0 for any other domain.
consistent (true by default) asserts that both heuristics are consistent,
which lets a search drop a node that the other direction has closed
(Lemma 7.4) and is required by BAE\(^*\) and by the parallel
searches; it is an assumption on the domain that the in-memory searches do
not check, and a domain whose heuristics are only admissible must set it to
false, or the cost returned may be wrong. all_bounds asks a search to stop
at the largest of the lower bounds of §7.3 that hold under the
heuristics, instead of its own. side chooses the direction of the next
expansion, among the values of
enum class SideChoice {
automatic , ///< the choice of the algorithm as published
priority , ///< the direction whose open list has the least priority
alternate , ///< forward and backward in turn
cardinality ///< the direction with fewer open nodes [Pohl, 1971]
};
where automatic is the choice of each algorithm as published; the
directions themselves are indices into the arrays of a node,
enum Side : unsigned {
forward_side = 0 , ///< the search from the start
backward_side = 1 ///< the search from the goal
};
Finally, fraction is the \(p\) of fMM(\(p\)) and the share of the forward
search in the split of GBFHS, and eager selects the variant of NBS and
DVCBS that covers all the optimal paths (§7.5). Each search of
sections 7.4 to 7.8 is a class template with a constructor that takes the
domain (which must outlive the search) and the options, and a method
solve() that returns a Solution (the path, its cost, the status and the
counters of §2.10); a function of one line,
named after the search, builds it and calls solve().
7.2 The two fronts¶
The searches of sections 7.4 to 7.7 share one table of the nodes, built by
the class template BiFronts (Bidirectional.h:331),
and differ only in the order in which they expand its nodes and in the bound at
which they stop.
The node, the table and the queues¶
A node of the table is a BiNode
(Bidirectional.h:191): the state and, for each
direction \(D\) (the index 0 for \(F\) and 1 for \(B\)), \(g_D\), \(h_D\), the parent on
the path of \(D\) and the operator by which \(D\) generated the node, with a byte
of flags which holds, for each direction, whether the node is closed, whether
it has ever been expanded (to count the reexpansions), whether it is open, and
whether it is ready in the sense of NBS and DVCBS. A node is created by the
first direction that reaches its state, with \(g\) of the other direction
infinite, and \(h\) of the other direction is computed when that direction
reaches it (or at once, for the searches that need both heuristics of every
node, such as BAE\(^*\)). The two directions therefore look up their states in
one table (the open-addressing table of §3.6),
and the lookup by which a direction detects its duplicates also tells whether
the other direction has reached the state: this is the immediate solution
detection of Sturtevant and Chen [94], which costs
nothing beyond the duplicate detection.
The open lists are lazy, as that of A\(^*\) (Lemma
3.1): an open list holds entries
\((n, \mathit{key}, g)\), not the nodes, and an entry is stale when its node
has been closed in that direction or reached again with a smaller \(g\) since
the entry was pushed, or, with consistent, when its node has been closed
in the other direction; a stale entry is dropped when it reaches the top
(Bidirectional.h:476), and the entries that are not
stale are fresh. The class template BiQueue
(Bidirectional.h:239) is such a list, ordered by the
key and then by the larger \(g\); it is the two-level bucket queue of
§3.3 when the key and the cost are the same
integer type (the keys being nonnegative), and the \(d\)-ary heap of
§3.2 otherwise, e.g., for the real keys of
fMM. Neither decreases a key: a node whose key changes is pushed again.
The expansion and the meeting¶
BiFronts::start creates the two roots and opens \(s\) forward and \(t\)
backward; when they are the same state the incumbent is \(U = 0\) at once.
BiFronts::expand( d , n , push )
(Bidirectional.h:391) closes \(n\) in the direction \(d\),
enumerates its successors (forward) or its predecessors (backward) by
for_each_child or for_each_parent, prefetching the place of each in the
table (§3.8), and then, for each state \(m\) so
generated, with \(g = g_d(n) + c\) and its heuristic \(h\) in the direction \(d\),
does the following.
- If \(g \ge U\) or \(g + h \ge U\), it drops \(m\), since no path through it in this direction is cheaper than the incumbent (with an admissible heuristic).
- Otherwise it looks \(m\) up, creating its node if absent; if the node has \(g_d(m) \le g\) it counts a duplicate and drops it, and otherwise it sets \(g_d(m) = g\) and the parent and the operator of \(d\), clears the flag closed of \(d\) (a reopening, if it was set), and, if \(g_{\bar d}(m)\) is finite and \(g + g_{\bar d}(m) < U\), sets \(U = g + g_{\bar d}(m)\) and records \(m\) as the meeting node.
- If
consistentholds and \(m\) is closed in the direction \(\bar d\), it does not open \(m\), since every path through it is known (Lemma 7.4); otherwise it opens \(m\) and callspush, by which the search inserts \(m\) in its own lists.
When the search ends, the path is the chain of the forward parents from the
meeting node back to \(s\), reversed, followed by the chain of the backward
parents from it to \(t\) (Bidirectional.h:497). Figure
7.1 shows the two fronts of the bidirectional Dijkstra's algorithm on a grid,
before and after they meet.
The invariants¶
We now state the facts on the table that all the searches of the chapter
use. The first is that \(U\) is always the cost of a path, and the second, the
main one, is that an optimal path always lies between the two fronts while
\(U > C^*\); it is the argument of Holte et al. (section 4 of
[81]), written for any search that detects the
meetings at once and reopens a node reached by a cheaper path. In what
follows, a search closes a node unexpanded when it pops a node whose \(f\)
in the direction of the pop is not smaller than \(U\), which all the searches
do (e.g., BiBestFirst.h:342), and a step of a search
is an expansion or such a closure.
Lemma 7.2 (Values of \(g\) and of \(U\)). At any time, each finite \(g_F(n)\) is the cost of a path from \(s\) to \(n\) and each finite \(g_B(n)\) that of a path from \(n\) to \(t\), so that \(g_D(n) \ge d_D(n)\); \(U\) is \(\infty\) or the value \(g_F(m) + g_B(m)\) at some time of a node \(m\), hence \(U \ge C^*\); and the parent chains of the meeting node give a path from \(s\) to \(t\) of cost at most \(U\).
Proof. \(g_D\) is set only to \(0\) at the root of \(D\) and to \(g_D(n) + c\) along an edge of \(D\) from a node \(n\), which by induction is the cost of a path. \(U\) is lowered only to \(g_F(m) + g_B(m)\) for the node \(m\) recorded with it, and a later decrease of \(g_F(m)\) or of \(g_B(m)\) lowers \(U\) again through the same test (step 2 above). The parent of \(m\) in \(D\) is set together with \(g_D(m) = g_D(n) + c\), and \(g_D(n)\) can only decrease afterwards, so that the parent pointers of \(D\) form a tree in which the cost of the chain of each node is at most its \(g_D\), as for A\(^*\) (Lemma 2.10). \(\square\)
Hence a search that returns \(U\) when it can prove \(U \le C^*\) returns an
optimal path. Let now \(P = (s = p_0, p_1, \dots, p_k = t)\) be an optimal
path, and say that \(p_l\) is settled forward if it is closed forward with
\(g_F(p_l) = d_F(p_l)\), and settled backward if it is closed backward with
\(g_B(p_l) = d_B(p_l)\). The flag consistent needs the following hypothesis,
which Lemma 7.4 proves for the searches of the chapter.
(H) While \(U > C^*\), every node of an optimal path from \(s\) to \(t\) that is closed in a direction \(D\) has its optimal \(g_D\).
Lemma 7.3 (An optimal path between the fronts).
Let a search expand by the procedure above, and, if it uses the flag
consistent, let (H) hold. Then, between two steps, if \(U > C^*\) there are
indices \(i < j\) such that \(p_i\) is open forward with \(g_F(p_i) = d_F(p_i)\)
and a fresh entry in the forward open list, and \(p_j\) is open backward with
\(g_B(p_j) = d_B(p_j)\) and a fresh entry in the backward open list. In
particular, both open lists have a fresh entry.
Proof. We first remark that no node \(p_l\) of \(P\) ever has both \(g_F(p_l) = d_F(p_l)\) and \(g_B(p_l) = d_B(p_l)\) while \(U > C^*\): the later of the two assignments finds the other \(g\) finite and lowers \(U\) to at most \(d_F(p_l) + d_B(p_l) = C^*\) (step 2, or the start if \(s = t\)), and \(U\) never increases.
Let \(i\) be the least index such that \(p_i\) is not settled forward. It
exists, since otherwise \(t = p_k\) would have \(g_F(t) = C^*\) and \(g_B(t) = 0\).
If \(i = 0\), \(p_0 = s\) has \(g_F(s) = 0\). If \(i > 0\), \(p_{i-1}\) is settled
forward, and it was closed with its present \(g_F\), since a later decrease
would have reopened it; it was not closed unexpanded, since \(f_F(p_{i-1}) \le
d_F(p_{i-1}) + d_B(p_{i-1}) = C^* < U\) by admissibility, \(U\) having been
larger than \(C^*\) then as now. Hence it was expanded with \(g_F(p_{i-1}) =
d_F(p_{i-1})\), and it generated \(p_i\) with \(g = d_F(p_i)\) and \(g + h_F(p_i)
\le C^* < U\), so that step 1 did not drop it, and after that expansion
\(g_F(p_i) = d_F(p_i)\), which by Lemma 7.2 cannot decrease. In both cases
\(p_i\) has its optimal \(g_F\) and is not closed forward, not being settled.
When \(g_F(p_i)\) took its present value, \(p_i\) was either opened and pushed
with it or, under consistent, found closed backward, hence settled
backward by (H), which by the first remark contradicts \(U > C^*\). The entry
pushed then is fresh: \(p_i\) has not been closed forward since (it would be
settled forward), nor backward under consistent (it would be settled
backward by (H)). The symmetric argument gives the largest index \(j\) such
that \(p_j\) is not settled backward, open backward with \(g_B(p_j) =
d_B(p_j)\) and a fresh entry.
Finally, if \(j \le i\) the node \(p_j\) would have both optimal values of \(g\): \(g_B(p_j)\) by the choice of \(j\), and \(g_F(p_j)\) because \(p_j\) is settled forward if \(j < i\), and by the argument above if \(j = i\). By the first remark this contradicts \(U > C^*\), and hence \(i < j\). \(\square\)
We remark that Lemma 7.3 asks nothing of the order of the expansions, and
that without the flag consistent it holds with heuristics that are only
admissible, since a node reached by a cheaper path is then always reopened.
The flag is the "nipping" of the BS\(^*\) of Kwa
[90]: a direction that reaches a node closed by
the other one does not open it, which is sound when the node has its optimal
\(g\) in the other direction, and this is what the order of the expansions
guarantees under consistent heuristics.
Lemma 7.4 (Closed with the optimal \(g\)). Let both
heuristics be consistent, and let each direction \(D\) of a search pop its
nodes by the least key \(\mathrm{pr}_D\), ties broken by the larger \(g_D\),
where \(\mathrm{pr}_D\) is nondecreasing along an edge of \(D\) and strictly
increasing in \(g_D\) at a fixed state. (a) Without the flag consistent,
every node is expanded in each direction with its optimal \(g\), and none is
reexpanded. (b) With the flag, (H) holds. The keys \(f\), \(\max\{f, 2g\}\),
\(\max\{f, 2g + \varepsilon\}\), \(\max\{f, g/p\}\), \(g\) and \(b_D = f_D + g_D -
h_{\bar D}\) have these properties, and (a) and (b) hold also for the orders
of NBS, DVCBS and GBFHS.
Proof. The keys are monotone along an edge of cost \(c\): \(f\) by consistency (Lemma 2.12), \(g\) and \(2g\) trivially, and \(b_D\) because it changes by \(2c + \Delta h_D - \Delta h_{\bar D} \ge 2c - c - c = 0\), both differences of the heuristics being at least \(-c\) along the edge by consistency; each of them is strictly increasing in \(g\) at a fixed state.
(a) Let \(n\) be the first node expanded in \(D\) with \(g_D(n) > d_D(n)\), and \(Q\) an optimal path of \(D\) from the root of \(D\) to \(n\); let \(x\) be the first node of \(Q\) that is not closed in \(D\) with its optimal \(g_D\). The nodes of \(Q\) before \(x\) were expanded, not closed unexpanded: if one, \(q\), had been closed unexpanded, then \(f_D(q) \ge U\) then, and \(f_D(n) > d_D(n) + h_D(n) \ge d_D(q) + h_D(q) = f_D(q)\) by consistency along \(Q\), so that \(n\) too would be closed unexpanded, \(U\) not having increased. Hence the predecessor of \(x\) on \(Q\) (if any) generated \(x\) with \(g_D(x) = d_D(x)\) and \(f_D(x) \le d_D(n) + h_D(n) < f_D(n) < U\), so that \(x\) is open in \(D\) with a fresh entry (no node is dropped as closed by the other direction without the flag), and \(x \ne n\). Along \(Q\), \(\mathrm{pr}_D(x) \le \mathrm{pr}_D(n \text{ at } d_D(n)) < \mathrm{pr}_D(n \text{ at } g_D(n))\), so that \(x\) is popped before \(n\), a contradiction. A node expanded with its optimal \(g\) is never reached again with a smaller one, and is not reexpanded.
(b) Let \(p = p_l\) be the first node, over the run, of an optimal path \(P\) from \(s\) to \(t\) that is closed in a direction while \(U > C^*\) with a \(g\) larger than its optimal one; say \(B\), the forward case being symmetric. As in the proof of Lemma 7.3, let \(a > l\) be the largest index such that \(p_a\) is not settled backward; it exists, since otherwise \(p_{l+1}\) would have been expanded with its optimal \(g_B\) (it is not closed unexpanded, its \(f_B\) being at most \(C^* < U\)) and would have given \(p_l\) its optimal \(g_B\), which cannot then increase. Thus \(p_a\) has its optimal \(g_B\) and is not closed backward; if it was not opened backward, or its entry is stale, because it is closed forward, then by the choice of \(p\) it is closed forward with its optimal \(g_F\), and the first remark of the proof of Lemma 7.3 contradicts \(U > C^*\). Hence \(p_a\) is open backward with a fresh entry and, as in (a), \(\mathrm{pr}_B(p_a) < \mathrm{pr}_B(p_l)\), so that it is popped first, a contradiction.
For NBS and DVCBS, a node is expanded from the ready nodes, by least \(g_D\), and every open node with \(f_D\) below the bound (\(C_{lb}\) or LB) is ready when a pair or a cluster is chosen (Lemma 7.10); since the node \(x\) (or \(p_a\)) has \(f_D\) smaller than that of the node popped, which is at most the bound, it is ready, and its \(g_D\) is smaller, so that it precedes the node popped; it cannot be generated by the cluster being expanded, whose children have a \(g_D\) at least that of the cluster. For GBFHS the nodes of a level are popped by \(f\), and \(x\) (or \(p_a\)) has \(f_D\) and \(g_D\) smaller than those of the node popped, hence within the limits of its level, and it is popped first. \(\square\)
Hence, under the flag consistent, a direction that generates a node of an
optimal path closed by the other direction does not open it: its two values
of \(g\) give the path through it, and the meeting is recorded at the
generation (step 2). We remark that (b) does not extend to the nodes off the
optimal paths: a node may be expanded with a \(g\) larger than its optimal
one when the cheaper path to it goes through a node that the flag did not
open, which costs at most some search, not the correctness. The test bidir
runs every search with this flag on the 8-puzzle, the 15-puzzle, the grids
and the graphs whose heuristics are consistent, and without it on a graph
with an admissible heuristic that is not consistent (that of the test of the
reopenings of §2.7), where all the searches but
BAE\(^*\) return the optimal cost.
7.3 The lower bounds¶
A front-to-end search stops when \(U\) is not larger than a lower bound \(\mathrm{LB}\) on \(C^*\), or when one of its open lists is empty. All the bounds below are computed from the least keys of the open lists, and all of them rest on Lemma 7.3: they need not be lower bounds on \(C^*\) at every time, but only while \(U > C^*\), which is what the stopping rule needs. We write \(f_{\min D}\), \(g_{\min D}\), \(b_{\min D}\) and \(d_{\min D}\) for the least \(f_D\), \(g_D\), \(b_D\) and \(\delta_D = g_D - h_{\bar D}\) over the fresh entries of the open list of \(D\).
Theorem 7.5 (The lower bounds). Under the hypotheses of Lemma 7.3, whenever \(U > C^*\) each of the following is at most \(C^*\):
- \(f_{\min F}\) and \(f_{\min B}\), the bounds of A\(^*\);
- \(g_{\min F} + g_{\min B} + \varepsilon\), the bound of the bidirectional Dijkstra's algorithm;
- for \(p \in (0, 1)\), the least key of fMM(\(p\)), \(C_p = \min\{\min_F \max\{f_F, g_F / p\}, \min_B \max\{f_B, g_B / (1 - p)\}\}\), which for \(p = 1/2\) is the least key \(C\) of MM, and the least key of MMe, \(\min_D \min \max\{f_D, 2 g_D + \varepsilon\}\);
- if both heuristics are consistent, \((b_{\min F} + b_{\min B}) / 2\), the bound of BAE\(^*\);
- if both heuristics are consistent, \(f_{\min F} + d_{\min B}\) and \(d_{\min F} + f_{\min B}\).
With integer costs each of them may be rounded up.
Proof. Let \(n = p_i\) and \(m = p_j\) be the nodes of Lemma 7.3, so that \(C^* = g_F(n) + d(n, m) + g_B(m)\) and \(d(n, m) \ge \varepsilon\), since \(i < j\). (1) \(f_F(n) = g_F(n) + h_F(n) \le d(s, n) + d(n, t) = C^*\) by admissibility, and the same for \(f_B(m)\). (2) \(g_F(n) + g_B(m) + \varepsilon \le C^*\). (3) Since \(g_F(n) + g_B(m) \le C^*\), either \(g_F(n) \le p\, C^*\) or \(g_B(m) \le (1 - p)\, C^*\); in the first case \(\max\{f_F(n), g_F(n)/p\} \le C^*\), by (1), and in the second the same holds for \(m\) in \(B\); for MMe, if \(g_F(n) \le g_B(m)\), then \(2 g_F(n) + \varepsilon \le g_F(n) + g_B(m) + \varepsilon \le C^*\), and symmetrically otherwise. (4) By consistency along the subpath from \(n\) to \(m\) (Lemma 2.3), \(h_F(n) \le d(n, m) + h_F(m)\) and \(h_B(m) \le d(n, m) + h_B(n)\), whence
(5) \(f_F(n) + \delta_B(m) = g_F(n) + g_B(m) + h_F(n) - h_F(m) \le g_F(n) + g_B(m) + d(n, m) = C^*\), and symmetrically. Each least key over the fresh entries is at most the key of \(n\) or of \(m\), which have fresh entries. With integer costs \(C^*\) is an integer, and a lower bound on it may be rounded up. \(\square\)
Theorem 7.6 (The stopping rule). Let a search satisfy the hypotheses of Lemma 7.3, and stop when an open list has no fresh entry, or when \(U < \infty\) and \(U \le \mathrm{LB}\) for a value \(\mathrm{LB}\) that is at most \(C^*\) whenever \(U > C^*\). Then, when it stops (and the node limit has not stopped it first), \(U = C^*\) if \(t\) is reachable from \(s\), and \(U = \infty\) otherwise.
Proof. If \(t\) is not reachable, \(U = \infty\) by Lemma 7.2. Otherwise, if \(U > C^*\) when the search stops, both open lists have a fresh entry by Lemma 7.3, and \(\mathrm{LB} \le C^* < U\); neither condition holds, a contradiction. Hence \(U \le C^*\), and \(U \ge C^*\) by Lemma 7.2. \(\square\)
Each search uses its own bound by default, and with all_bounds the largest
of those that hold under its assumptions: the bounds 1 and 2 always, the
bound 3 for MMe, whose key is never smaller than that of MM, and, with
consistent, the bounds 4 and 5. Of course, all of them are dominated by
the bound of the pairs of NBS of §7.5, which, however, needs a
search over the pairs of open nodes. We remark that the bounds of Theorem
7.5 are lower bounds on \(C^*\) only while \(U > C^*\); once \(U = C^*\) they may
exceed \(C^*\), which is harmless, since they then only stop the search.
7.4 One node at a time: MM, fMM, BAE\(^*\) and the bidirectional Dijkstra's algorithm¶
The class template BiBestFirst< D , P > (BiBestFirst.h)
expands, at each step, the node of least priority in the direction chosen, the
priority being one of
enum class BiPriority {
dijkstra , ///< g, the bidirectional Dijkstra's algorithm
mm , ///< max( f , 2 g ), MM
mme , ///< max( f , 2 g + epsilon ), MMe
fmm , ///< max( f , g / p ) and max( f , g / ( 1 - p ) ), fMM( p )
bae ///< f + g - h of the other direction, BAE*
};
i.e., for a node \(n\) open in \(D\), respectively,
for the bidirectional Dijkstra's algorithm, MM of Holte et al. [61], [81], its variant MMe of Sharon et al. [82], the fractional MM of Shaham et al. [83], with \(p_F = p\) and \(p_B = 1 - p\), and BAE\(^*\) of Sadhukhan [88] as defined by Alcázar et al. [89], whose priority adds to \(f\) the error \(g_D - h_{\bar D}\) of the heuristic of the other direction at the node. Its declarations, without the bodies, are
template< BidirectionalDomain D , BiPriority P >
class BiBestFirst {
public:
using Key = std::conditional_t< P == BiPriority::fmm , double , Cost >;
explicit BiBestFirst( const D & domain ,
const BidirectionalOptions & options = {} );
[[nodiscard]] SolutionT solve( void ) const;
};
template< BidirectionalDomain D >
[[nodiscard]] Solution< state_t< D > , cost_t< D > > mm(
const D & domain , const BidirectionalOptions & options = {} );
and the same for mme, fmm (whose \(p\) is options.fraction), bae and
bidijkstra, the last being BiBestFirst< BlindDomain< D > ,
BiPriority::dijkstra >, i.e., the MM\(_0\) of
[61], which ignores the heuristics. The
constructor throws std::invalid_argument for BAE\(^*\) when consistent is
false, and for fMM when the fraction is not in \((0, 1)\). The key is real for
fMM, whose \(g / p\) is not an integer, and of the cost type otherwise.
Algorithm 7.1 (The searches one node at a time, the pseudocode of the
header BiBestFirst.h:29-40).
1 procedure BiBestFirst(s, t)
2 U ← ∞; OPEN_F ← {s}; OPEN_B ← {t}
3 while OPEN_F ≠ ∅ and OPEN_B ≠ ∅ do
4 if U ≤ LB then return U
5 D ← the direction chosen
6 n ← the node of least pr_D in OPEN_D, of largest g_D among those
7 if f_D(n) < U then expand n in the direction D, and
U ← min(U, g_F(m) + g_B(m)) for each m generated
8 return U
Here OPEN\(_D\) is the open list of \(D\) by \(\mathrm{pr}_D\), its stale entries dropped at the top, and the expansion of line 7 is that of §7.2 (we write \(g_F(m) + g_B(m)\) where the header writes \(g_D(m) + g_{\bar D}(m)\)); a node of \(f_D(n) \ge U\) is closed unexpanded. The bound of line 4 is
\(C\) being the least priority of the two open lists (section 4 of
[81]), and the ceiling applying to integer costs
only; with all_bounds it is the largest of the bounds of Theorem 7.5 that
hold. The direction of line 5 is, for SideChoice::automatic, the one of
least priority (the forward one on a tie, unless the top of the backward
list has a smaller \(g\)) for MM, MMe, fMM and Dijkstra's algorithm, which is
SideChoice::priority, and the alternation of the two for BAE\(^*\), as in its
definition and in PEM-BAE\(^*\) [57]; alternate
and cardinality (the direction with fewer open nodes, the criterion of
Pohl [91]) are available to every priority.
Theorem 7.7 (Correctness, and the meeting in the
middle). Algorithm 7.1 returns \(C^*\) (or reports \(t\) unreachable) for each
priority, with admissible heuristics and consistent false, or with
consistent heuristics; for BAE\(^*\) the heuristics must be consistent. With
the choice of the direction by priority, moreover, MM expands no node with
\(g_D(n) > C^*/2\), MMe none with \(2 g_D(n) + \varepsilon > C^*\), and fMM(\(p\))
none with \(g_F(n) > p\, C^*\) or \(g_B(n) > (1 - p)\, C^*\).
Proof. The priorities of the five searches satisfy Lemma 7.4,
so that (H) holds under the flag consistent, and with it Lemma 7.3; the
bound of each is one of Theorem 7.5 (the bound \(C\) of MM, MMe and fMM is
the bound 3, and that of BAE\(^*\) the bound 4, which needs consistency), and
Theorem 7.6 gives the first claim. For the second, let \(n\) be expanded in
\(D\). If \(U > C^*\) at that time, with the direction of least priority
\(\mathrm{pr}_D(n) = C \le C^*\) by Theorem 7.5. If \(U \le C^*\), then \(U =
C^*\), and the search did not stop at line 4, so that \(C \le \mathrm{LB} < U
= C^*\). In both cases \(\mathrm{pr}_D(n) \le C^*\), i.e., \(2 g_D(n) \le C^*\) for
MM, \(2 g_D(n) + \varepsilon \le C^*\) for MMe, and \(g_D(n) \le p_D\, C^*\) for
fMM. \(\square\)
The meeting in the middle depends on the choice of the direction: with
alternate or cardinality the node popped in the direction chosen may have
a priority larger than \(C\), and then larger than \(C^*\), so that the second
claim of the theorem holds only for SideChoice::priority (the default of
these searches). The test bidir checks it on 10 states of the 8-puzzle,
for MM and for fMM with \(p = 0.25\) and \(p = 0.8\), by recording the states
that each direction expands and comparing their distances from \(s\) and to
\(t\), computed by a breadth-first search, with \(p\, C^*\) and \((1 - p)\,
C^*\); and it checks, with the same distances, that MM, NBS, DVCBS and GBFHS
expand no state whose optimal \(g\) in the direction plus its heuristic
exceeds \(C^*\).
Proposition 7.8 (Termination). On a finite graph with nonnegative costs, Algorithm 7.1 terminates, and so do the searches of sections 7.5 to 7.7.
Proof. Each step pops an entry, and an entry is pushed only after a strict decrease of some \(g_D(n)\), which is then the cost of a path (Lemma 7.2). A path of cost at most a given value \(K\) has at most \(K / \delta\) edges of positive cost, \(\delta\) being the least positive cost of an edge of the finite graph, and therefore the distinct costs of such paths are finitely many; hence each \(g_D(n)\) decreases finitely many times, the entries are finitely many, and so are the steps, as in Theorem 2.11. In the procedure that chooses the pair of NBS (or the cluster of DVCBS) each raise of the bound is followed by a return or by the move of an entry from waiting to ready, since the new bound is the least of the quantities that the two tests compare with it, and an entry is moved at most once; GBFHS raises its bound by one unit at a time, and when the bound and the limits exceed the largest \(f\) and \(g\) of the finitely many paths without repeated states every open node is expandable. \(\square\)
The implementation¶
The search keeps, for each direction, the open list by priority and, for
the bounds, up to five further lazy queues by \(f\), by \(g\), by the priority
of MMe, by \(b\) and by \(\delta = g - h_{\bar D}\), each kept only when the
bound of the algorithm (or, with all_bounds, one that holds) needs it;
e.g., MM keeps the queues by \(f\) and by \(g\), and the bidirectional
Dijkstra's algorithm none. A node is pushed in each queue kept when its \(g\)
changes, and the least key of a queue is read after dropping its stale
entries, so that each bound costs as much as the open list, an amortized
\(O(1)\) per entry on the bucket queue (Proposition
3.5) and \(O(\log n)\) on the heap. Both
heuristics of a node are computed at its creation only for BAE\(^*\) and for
the bounds that need \(h_{\bar D}\); the other searches compute \(h_{\bar D}\)
only when \(\bar D\) reaches the node.
7.5 Expanding pairs: NBS and the must-expand graph¶
For a node \(u\) open forward and a node \(v\) open backward, \(u \ne v\),
is a lower bound on the cost of a path from \(s\) through \(u\) and then \(v\) to \(t\) (the bounds 1 and 2 of Theorem 7.5 for one pair). The Near-Optimal Bidirectional Search (NBS) of Chen, Holte, Zilles and Sturtevant [85] expands both nodes of a pair of least lb, and it is the only search of the chapter with a guarantee on the number of its expansions relative to every other front-to-end search, which we now state.
Definition 7.9 (Must-expand graph). Let both heuristics be consistent. The must-expand graph \(G_{MX}\) is the bipartite graph with a forward copy and a backward copy of each state, in which the forward copy of \(u\) and the backward copy of \(v\) are joined if
i.e., if the pair has \(\mathrm{lb} < C^*\) when both nodes have their optimal \(g\). We write \(\mathrm{VC}\) for the size of a minimum vertex cover of \(G_{MX}\).
Theorem 1 of Eckerle et al. [84], as reported by the headers and by Chen et al. [85], states that every admissible front-to-end bidirectional search (one that knows only the values of \(g\), \(h_F\) and \(h_B\) of its nodes and \(\varepsilon\)) must expand \(u\) forward or \(v\) backward for each edge \((u, v)\) of \(G_{MX}\), since otherwise a path of cost \(\mathrm{lb} < C^*\) joining them could exist on an instance indistinguishable from the given one; hence VC is a lower bound on the expansions of every such search.
Algorithm 7.2 (The choice of the pair of NBS, the pseudocode of the
header NBS.h:35-45).
1 procedure PrepareBest
2 move from waiting_D to ready_D every node with f_D < C_lb
3 loop
4 if ready_D ∪ waiting_D = ∅ for some D then return none
5 if ready_F.g + ready_B.g + ε ≤ C_lb then return the two tops
6 if waiting_D.f ≤ C_lb for some D then
move the top of waiting_D to ready_D (for each such D)
7 else C_lb ← min(waiting_F.f, waiting_B.f,
ready_F.g + ready_B.g + ε)
The pair is found as in section 7 of [85], with a
lower bound \(C_{lb}\) on the least lb raised until a pair reaches it: in each
direction \(D\), a queue waiting\(_D\) of the open nodes by \(f_D\), the larger
\(g_D\) first on a tie, and a queue ready\(_D\) of those with \(f_D \le C_{lb}\),
by \(g_D\) and then by the smaller \(f_D\); ready_D.g is the least \(g\) of
ready\(_D\) and waiting_D.f the least \(f\) of waiting\(_D\), both over the
fresh entries. The search calls PrepareBest, stops if it returns none or if
\(U \le C_{lb}\), and otherwise expands the top of ready\(_F\) and then that of
ready\(_B\), each closed unexpanded if its \(f\) is not below \(U\)
(NBS.h:234-246). With eager, line 2 moves the nodes with
\(f_D \le C_{lb}\), which is the NBS\(_A\) of Shperberg et al.
[86], whose pairs cover those with \(\mathrm{lb}
\le C^*\), needed to find all the optimal paths, and line 6 is then never
taken; with \(\varepsilon = 0\) the bound is that of Chen et al. without it
(the base case of Shperberg et al.). The declarations are those of
BiBestFirst without the parameter P, i.e., NBS< D >( domain , options )
with solve(), and nbs( domain , options ).
Lemma 7.10 (The bound of the pairs). (a) Within a
call of PrepareBest, after line 2, every node of waiting\(_D\) has \(f_D \ge
C_{lb}\) (with eager, \(f_D > C_{lb}\)), so that every open node with \(f_D <
C_{lb}\) is ready, and \(C_{lb}\) strictly increases at each execution of
line 7. (b) Each time \(C_{lb}\) is set at line 7, it is at most the least lb of the
pairs of open nodes, and hence at most \(C^*\) if \(U > C^*\). (c) A pair
returned at line 5 has \(\mathrm{lb}(u, v) \le C_{lb}\).
Proof. (a) Line 2 leaves in waiting\(_D\) the nodes with \(f_D \ge C_{lb}\), and line 7 is reached only when the tops of waiting have \(f > C_{lb}\) (line 6) and the ready tops have \(g_F + g_B + \varepsilon > C_{lb}\) (line 5), so that the new value is larger and is again at most the least \(f\) of waiting; no node enters waiting within the call. (b) Let \(u\) be open forward and \(v\) open backward, each with a fresh entry in ready or in waiting. If \(u\) or \(v\) is waiting, \(\mathrm{lb}(u, v)\) is at least its \(f\), which is at least the least \(f\) of its waiting queue; if both are ready, \(\mathrm{lb}(u, v) \ge g_F(u) + g_B(v) + \varepsilon\), which is at least the sum of the least values of \(g\) of the two ready queues plus \(\varepsilon\). The new \(C_{lb}\) is the minimum of these quantities. If \(U > C^*\), the pair \((p_i, p_j)\) of Lemma 7.3 has \(\mathrm{lb} \le C^*\) (Theorem 7.5, bounds 1 and 2), whence \(C_{lb} \le C^*\). (c) A node enters ready\(_D\) with \(f_D \le C_{lb}\), \(C_{lb}\) only grows, and the \(f\) of a ready node does not change while its entry is fresh; the condition of line 5 bounds the third term of lb. \(\square\)
Theorem 7.11 (Correctness and near-optimality of
NBS). NBS returns \(C^*\) (or reports \(t\) unreachable) under the hypotheses of
Theorem 7.7. If both heuristics are consistent and no node is reexpanded
(which holds with consistent false, by Lemma 7.4(a)), the
pairs that it expands with \(\mathrm{lb} < C^*\) form a matching of \(G_{MX}\),
so that it expands at most \(2\, \mathrm{VC}\) nodes in them; the other pairs
expanded have \(\mathrm{lb} = C^*\).
Proof. NBS satisfies Lemma 7.4, so (H) and Lemma 7.3 hold, and by Lemma 7.10(b) the value of \(C_{lb}\) at the test \(U \le C_{lb}\) is at most \(C^*\) whenever \(U > C^*\), since \(U\) only decreases after \(C_{lb}\) is set; Theorem 7.6 gives the correctness. Let the heuristics be consistent, and \((u, v)\) be a pair expanded. Since \(g_F(u) \ge d_F(u)\) and \(g_B(v) \ge d_B(v)\), the quantity of Definition 7.9 is at most \(\mathrm{lb}(u, v)\), and \((u, v)\) is an edge of \(G_{MX}\) if \(\mathrm{lb}(u, v) < C^*\). If no node is reexpanded, each state is expanded at most once in each direction, and two pairs expanded share no forward copy and no backward copy: they form a matching \(M\). Every vertex cover of \(G_{MX}\) contains an end of each edge of \(M\), which are disjoint, hence \(|M| \le \mathrm{VC}\), and the pairs of \(M\) make at most \(2 |M| \le 2\, \mathrm{VC}\) expansions. Finally, a pair is expanded only if \(U > C_{lb} \ge \mathrm{lb}(u, v)\) by Lemma 7.10(c); if \(U = C^*\) this gives \(\mathrm{lb} < C^*\), and if \(U > C^*\) it gives \(\mathrm{lb} \le C_{lb} \le C^*\). \(\square\)
This is theorem 3 of [85], and their theorem 5
shows that no admissible front-to-end search can guarantee less than
\(2\, \mathrm{VC}\) in the worst case. With the flag consistent, a node off
the optimal paths may be expanded with a \(g\) larger than its optimal one
(see the remark after Lemma 7.4) and later reexpanded, which the counter
reexpanded of the Solution reports; the bound of the theorem holds for
the runs in which it is 0. We also remark that the two expansions of a step
are those of the two tops returned by PrepareBest: the forward expansion
cannot make the backward top stale, since \(u \ne v\) (if \(u = v\), the node
would have both values of \(g\), and \(U \le g_F(u) + g_B(u) \le C_{lb}\) would
have stopped the search), and it writes only the forward fields.
7.6 Expanding clusters: DVCBS¶
NBS expands both ends of one edge of \(G_{MX}\) at a time, which is optimal
only up to the factor 2; the Dynamic Vertex Cover Bidirectional Search
(DVCBS) of Shperberg, Felner, Sturtevant, Shimony and Hayoun
[86] instead expands, at each step, one vertex of
a minimum vertex cover of the part of the must-expand graph that it knows.
The class template DVCBS< D > (DVCBS.h), with the function
dvcbs( domain , options ), keeps the high level of NBS: a lower bound LB on
\(C^*\), raised until \(U \le \mathrm{LB}\), the queues waiting\(_D\) by \(f_D\),
and the ready nodes, those with \(f_D < \mathrm{LB}\) (\(\le\) with eager).
The nodes move from waiting\(_D\) to ready\(_D\) one value of \(f_D\) at a time,
and the ready nodes are grouped in clusters, one per value of \(g_D\). The
clusters are the vertices of the dynamic must-expand graph DGMX, a forward
cluster of \(g_F = a\) and a backward one of \(g_B = b\) being joined if
\(a + b + \varepsilon \le \mathrm{LB}\), which makes every pair of their nodes have
\(\mathrm{lb} \le \mathrm{LB}\); and DVCBS expands one cluster of a minimum
vertex cover of DGMX, weighted by the sizes of the clusters (algorithm 3 of
[86]). The header has no pseudocode of its own:
the choice of the clusters is that of Algorithm 7.2 with the moves of whole
values of \(f\) and the test of line 5 on the least \(g\) of the clusters
(DVCBS.h:235-272), and the cover is computed as follows.
Let \(a_0 < a_1 < \dots < a_{m-1}\) be the values of \(g\) of the forward clusters with an edge and \(b_0 < \dots < b_{n-1}\) those of the backward ones, with weights \(w(a_i)\) and \(w(b_j)\), and let \(N(a_i) = \{b_j : a_i + b_j + \varepsilon \le \mathrm{LB}\}\), a prefix of the backward clusters.
Lemma 7.12 (The covers of DGMX). For \(0 \le i \le m\), the set \(K_i = \{a_0, \dots, a_{i-1}\} \cup N(a_i)\) (with \(N(a_m) = \emptyset\)) is a vertex cover of DGMX, and every vertex cover \(K\) contains some \(K_i\); hence a minimum cover is a \(K_i\) of least weight \(\sum_{l < i} w(a_l) + \sum_{b \in N(a_i)} w(b)\).
Proof. The neighbourhoods are nested: \(N(a_{i'}) \subseteq N(a_i)\) for \(i' > i\), since \(b \le \mathrm{LB} - \varepsilon - a_{i'} \le \mathrm{LB} - \varepsilon - a_i\). An edge \((a_l, b)\) is covered by \(K_i\) through \(a_l\) if \(l < i\), and through \(b \in N(a_l) \subseteq N(a_i)\) if \(l \ge i\); hence \(K_i\) is a cover. Given a cover \(K\), let \(i\) be the least index with \(a_i \notin K\) (\(i = m\) if there is none); then \(a_0, \dots, a_{i-1} \in K\), and every edge of \(a_i\) is covered by its backward end, i.e., \(N(a_i) \subseteq K\), so that \(K_i \subseteq K\), and the weight of \(K_i\) is at most that of \(K\). \(\square\)
The structure of the covers was shown by Shaham et al.
[83] for the must-expand graph, and it makes the
minimum cover a pass over \(i = 0, \dots, m\), with a pointer to the end of
\(N(a_i)\) that only moves down and the prefix sums of the backward weights,
in time linear in the number of clusters
(DVCBS.h:199-232). Among the minimum covers, the cluster
expanded is the forward \(a_0\) or the backward \(b_0\) that lies in one of them,
the one with fewer nodes and the backward one on a tie, which is the variant
reported by Shperberg et al. (section 5.1 of [86]);
its nodes are expanded in the order in which they became ready, each closed
unexpanded if its \(f\) is not below \(U\), and the expansion of the cluster stops
as soon as \(U \le \mathrm{LB}\). Figure 7.2 shows the clusters, the edges of
DGMX and a minimum cover.
Proposition 7.13 (Correctness of DVCBS). DVCBS returns \(C^*\) (or reports \(t\) unreachable) under the hypotheses of Theorem 7.7.
Proof. Lemma 7.10 holds for LB with the clusters in place of the ready queues, with the same proof, since the moves of a whole value of \(f\) keep the nodes of waiting at \(f \ge \mathrm{LB}\); the cluster expanded is a cluster of least \(g\) of its direction, so that Lemma 7.4 holds, and with it Lemma 7.3; the test \(U \le \mathrm{LB}\) is made after each node of a cluster, and Theorem 7.6 applies. \(\square\)
DVCBS has no bound of the kind of Theorem 7.11 on its expansions (section
5.2 of [86]), but it expanded fewer nodes than
NBS on every domain of their table 1. The test bidir runs it, as NBS, with
each variant of the options (all the bounds, eager, \(\varepsilon = 0\), and
the choices of the direction, which these two searches ignore), and checks
that it never expands a node of \(f\) above \(C^*\).
The implementation¶
A cluster is a vector of nodes in the order in which they became ready, with
a count of its live nodes, and the clusters of a direction are a map by \(g\)
(DVCBS.h:123-134). A ready node whose \(g\) decreases leaves
its cluster (the count is decremented, and the cluster erased when it reaches
0) and goes back to waiting; under consistent a node expanded in \(D\) leaves
its cluster of \(\bar D\) as well. Since a node may also die in its cluster by a
closure in the other direction, whose leaving is not counted, the cluster
expanded is erased as a whole at the end. The weights used by the cover are the
live counts, i.e., the sizes of the clusters up to these dead nodes.
7.7 GBFHS and the bidirectional breadth-first search¶
The Generalized Breadth-First Heuristic Search (GBFHS) of Barley et al. [87] works with integer costs and raises a bound \(f_{Lim}\) on \(C^*\) one unit at a time; at each value it splits \(f_{Lim} - \varepsilon + 1\) into two limits \(g_{Lim F} + g_{Lim B}\) on the depths of the two searches, and it expands, in each direction \(D\), every open node with \(f_D \le f_{Lim}\) and \(g_D < g_{Lim D}\).
Algorithm 7.3 (GBFHS, the pseudocode of the header
GBFHS.h:16-27).
1 procedure GBFHS(s, t)
2 U ← ∞; f_Lim ← max(h_F(s), h_B(t), ε); g_LimF ← g_LimB ← 0
3 while OPEN_F ≠ ∅ and OPEN_B ≠ ∅ do
4 if U ≤ f_Lim then return U
5 raise g_LimF and g_LimB so that g_LimF + g_LimB = f_Lim − ε + 1
6 while some n in OPEN_D has f_D(n) ≤ f_Lim and g_D(n) < g_LimD do
7 expand the one of least f_D, of largest g_D among those,
of the direction of the least such f
8 if U ≤ f_Lim then return U
9 f_Lim ← f_Lim + 1
The class template GBFHS< D > requires std::is_integral_v< cost_t< D > >,
as do gbfhs( domain , options ) and bibfs( domain , options ), the
latter being GBFHS on the BlindDomain with each unit of depth given to the
direction with fewer open nodes, i.e., the bidirectional breadth-first
search with the criterion of Pohl [91]. The split
of line 5 is chosen by side: alternate, and also automatic, the
default, give each new unit to the smaller limit (the backward one on a tie)
after a first split in halves; cardinality gives it to the direction with
fewer open nodes; and priority gives the forward limit the share
fraction of the sum, \(\lfloor p\,(f_{Lim} - \varepsilon + 1) \rfloor\),
clamped so that no limit decreases, as fMM(\(p\)) does
(GBFHS.h:177-206).
Lemma 7.14 (A level finds its paths). Let the costs be integers, \(\varepsilon\) a lower bound on them, and the hypotheses of Lemma 7.3 hold. When the loop of lines 6 to 8 ends at the level \(f_{Lim}\), every path \(P\) from \(s\) to \(t\) of cost \(C \le f_{Lim}\) has \(U \le C\).
Proof. Let \(P = (p_0, \dots, p_k)\), and suppose \(U > C\). Let \(a\) be the least index such that \(p_a\) is not closed forward with \(g_F(p_a)\) at most the cost of the prefix of \(P\) up to \(p_a\), and \(b\) the largest index such that \(p_b\) is not closed backward with \(g_B(p_b)\) at most the cost of the suffix of \(P\) from \(p_b\). As in the proof of Lemma 7.3, with the costs of the prefixes in place of the optimal values of \(g\) and \(C < U\) in place of \(C^* < U\), \(p_a\) has \(g_F(p_a)\) at most the cost of its prefix, is not closed forward and is open forward with a fresh entry, and symmetrically for \(p_b\); and if \(a \ge b\) the node \(p_b\) has both values of \(g\) within the costs of its prefix and of its suffix, whose sum, at most \(C\), was offered to \(U\). Hence \(a < b\). Then \(f_F(p_a) \le g_F(p_a) + d(p_a, t) \le C \le f_{Lim}\) by admissibility, and since the level ended, \(g_F(p_a) \ge g_{Lim F}\); symmetrically \(g_B(p_b) \ge g_{Lim B}\); and since \(P\) has at least one edge between \(p_a\) and \(p_b\),
a contradiction. \(\square\)
Theorem 7.15 (Correctness of GBFHS). Under the hypotheses of Lemma 7.14, GBFHS returns \(C^*\) (or reports \(t\) unreachable), \(f_{Lim} \le C^*\) at every expansion, and hence it expands no node with \(f_D > C^*\).
Proof. If \(s = t\), \(U = 0\) stops it at once. Otherwise \(f_{Lim} \le C^*\) at the start, since \(h_F(s) \le C^*\), \(h_B(t) \le C^*\) and \(\varepsilon \le C^*\). While \(f_{Lim} < C^*\), \(U \ge C^* > f_{Lim}\) (Lemma 7.2) and the search does not stop at lines 4 or 8; at the end of the level \(f_{Lim} = C^*\), if it is reached, Lemma 7.14 gives \(U \le C^*\), i.e., \(U = C^*\), and the search returns it at line 4 of the next iteration, or earlier, within the level \(C^*\), with \(U \le f_{Lim} = C^*\). Hence every expansion happens at a level \(f_{Lim} \le C^*\), of a node with \(f_D \le f_{Lim}\). An empty open list stops it with \(U = C^*\) or \(U = \infty\) by Lemma 7.3 and Theorem 7.6. \(\square\)
The order of line 7 is ours: Barley et al. leave free the order of the
expandable nodes of a level, and the order of A\(^*\) (least \(f\), then largest
\(g\)) reaches the meeting point within the last level much earlier than the
order of \(g\); the header reports 2.5 times fewer expansions on the
15-puzzle, a measure that we have not repeated here. Under consistent
heuristics this order satisfies Lemma 7.4, which makes the flag consistent
sound.
The implementation¶
Each direction has three lazy queues: waiting, the nodes with \(f > f_{Lim}\)
by \(f\); ready, those with \(f \le f_{Lim}\) by \(f\) and then by the larger \(g\);
and deep, those of ready whose \(g\) reached the limit, by \(g\). A node at the
top of ready with \(g_D \ge g_{Lim D}\) goes to deep, and comes back to ready
when the limit passes it (GBFHS.h:163-174); thus a level
is a sequence of moves between the queues and of expansions, each move being
paid once per entry and per change of the limits. We remark that \(f_{Lim}\)
grows by one unit even when no open node has its \(f\) near it, so that on a
domain with large costs a run may pass through many empty levels, each of a
constant cost.
7.8 The two directions in parallel¶
The class template ParallelBidirectional< D , K , Executor >
(ParallelBidirectional.h) runs the two directions
at once, each on a worker of an executor (the executors of
§1.6), sharing the table of the nodes and the
incumbent. The search of a worker is one of
enum class ParallelBiKind {
nba , ///< NBA*: by f, with the two rejections (PNBA*)
dijkstra , ///< by g, the bound g_F + g_B + epsilon
mm , ///< by max( f , 2 g ), the bound of MM
bae ///< by b, the bound of BAE*
};
where nba is the NBA\(^*\) of Pijls and Post [92],
which expands by \(f\) and rejects some nodes as described below, so that the
search is PNBA\(^*\) of Rios and Chaimowicz [93],
and the other three are the parallel versions of the bidirectional
Dijkstra's algorithm, of MM and of BAE\(^*\). Its declarations are
template< BidirectionalDomain D , ParallelBiKind K ,
ADS::WorkerExecutor Executor = ADS::ThreadPool >
class ParallelBidirectional {
public:
explicit ParallelBidirectional( const D & domain ,
const BidirectionalOptions & options = {} );
void set_executor( Executor & ex ) noexcept;
[[nodiscard]] SolutionT solve( void ) const;
};
template< BidirectionalDomain D >
[[nodiscard]] Solution< state_t< D > , cost_t< D > > pnba(
const D & domain , const BidirectionalOptions & options = {} );
The constructor refuses consistent false and a weight other than 1 with
std::invalid_argument, since the scheme needs consistent heuristics;
without set_executor each search builds an executor of two threads. The
counters expanded_by and stored_by have one entry per direction, and the
node limit is checked every 64 expansions, a worker stopping both when twice
the nodes it has created reach it.
Each worker runs the best-first search of its direction on its own open
list, writes only the fields of its direction in the nodes (\(g_D\), the
parent, the operator and the flag closed\(_D\)), and reads those of the other;
the values of \(g\) and the flags closed are accessed through atomic
references, with sequentially consistent operations, and both workers lower
\(U\), with its meeting node, under a lock
(ParallelBidirectional.h:264). After each
expansion a worker publishes the least key of its open list and, for MM, its
least \(f\) and its least \(g\), each as the maximum of the value published before
and the present one
(ParallelBidirectional.h:392); it stops both
workers when its open list is empty, or when \(U\) is not larger than the bound
of the algorithm computed from the two published records
(ParallelBidirectional.h:275), which is the
bound of BiBestFirst for Dijkstra's algorithm, MM and BAE\(^*\), and
\(\max\{f_{\min F}, f_{\min B}\}\) for NBA\(^*\). Three facts make the scheme
exact.
Lemma 7.16 (No meeting is missed). If both directions set \(g_F(m)\) and \(g_B(m)\) of a node \(m\) to finite values, then at least one of the two workers reads the value set by the other, and offers their sum to \(U\).
Proof. When the worker of \(D\) sets \(g_D(m)\) it then reads \(g_{\bar D}(m)\),
and the worker of \(\bar D\) does the converse
(ParallelBidirectional.h:445-449). With
sequentially consistent accesses there is a total order of the four operations
compatible with the order of each worker; the worker whose write comes second
in that order reads after both writes, and hence reads the value of the other.
A node created by one worker with its \(g\) is published by its insertion in the
concurrent table, so that the other worker that finds it sees its fields. This
is the argument of the mutual exclusion of Dekker. \(\square\)
Lemma 7.17 (The published keys). With consistent heuristics, the least key of the nodes open or being expanded in a direction never decreases, and so each value published by a worker, however old, is at most the least key of the nodes open in its direction at any later time.
Proof. Each worker is a sequential best-first search of its direction whose key satisfies Lemma 7.4. A node popped has the least key of the open list, and its children have keys not smaller than its own, by the monotonicity along an edge; the nodes that the other worker closes, or that \(U\) prunes, only leave the list. Hence the least key over the open nodes and the node being expanded never decreases, and a published value, which is a least key at the time of its publication (or an earlier one, by the maximum), stays below it. \(\square\)
Lemma 7.18 (The rejections of NBA\(^*\)). Let the heuristics be consistent, \(F_{\bar D}\) be a value published by the other direction, and \(x\) be popped in \(D\) with \(g_D(x) + F_{\bar D} - h_{\bar D}(x) \ge U\). Then no path from the root of \(D\) to \(x\) of cost \(g_D(x)\), continued through a node open in \(\bar D\), costs less than \(U\).
Proof. Let \(y\) be open in \(\bar D\), and \(d(x, y)\) the cost of the subpath between them; by consistency \(h_{\bar D}(y) \le d(x, y) + h_{\bar D}(x)\), so that a path through \(x\) and \(y\) costs at least
since \(f_{\bar D}(y) \ge F_{\bar D}\) by Lemma 7.17. \(\square\)
NBA\(^*\) closes unexpanded the node \(x\) popped in \(D\) when \(f_D(x) \ge U\) or
when \(g_D(x) + F_{\bar D} - h_{\bar D}(x) \ge U\) (section 3 of
[92]), the second being the rejection of Lemma
7.18 (ParallelBidirectional.h:472-476).
Theorem 7.19 (Correctness of the parallel
searches). With consistent heuristics, ParallelBidirectional returns \(C^*\)
for each kind, or reports \(t\) unreachable, unless the node limit stops it.
Proof. By Lemma 7.16, every node that gets both values of \(g\) lowers \(U\) to at most their sum, which is the first remark of the proof of Lemma 7.3; each direction pops by a key of Lemma 7.4, so that (H) holds, its proof being the same with the two workers interleaved; and a node of an optimal path is neither pruned nor rejected while \(U > C^*\), since \(f_D \le C^* < U\) and, by Lemma 7.18 with the node of the other direction given by Lemma 7.3, \(g_D(x) + F_{\bar D} - h_{\bar D}(x) \le C^* < U\). Hence Lemma 7.3 holds at any time at which a worker reads its open list: if \(U > C^*\), the open list of each direction has a node of \(P\) with its optimal \(g\). A worker that finds its list empty thus has \(U \le C^*\). A worker that finds \(U \le \mathrm{LB}\), LB being computed from the published values, has by Lemma 7.17 an LB that is at most the bound of Theorem 7.5 computed from the present open lists (each bound being a nondecreasing function of the least keys), and hence at most \(C^*\) if \(U > C^*\); Theorem 7.6 concludes. \(\square\)
The test bidir-thread (and bidir-openmp, bidir-fastflow on the other
executors) runs the four kinds on 50 states of the 8-puzzle, on two instances
of the 15-puzzle of Korf, on random grids with 8 moves and on random directed
graphs, half of the runs on the 8-puzzle with an executor of their own and
the others with one given. A parallel bidirectional search has two workers,
so that its speedup is at most 2, and it pays the overheads of
§8.2: the search overhead of a bound read late
(a worker may expand nodes that a sequential search would have pruned by a
bound already reached) and the coordination overhead of the atomic accesses
to the shared nodes.
7.9 Parallel external-memory bidirectional search¶
The class template PEMSearch< D , K , Executor >
(PEMSearch.h) is the framework PEM-BiHS of Siag, Shperberg,
Felner and Sturtevant [57], whose open and closed
lists are files on the disk, the nodes of one bucket being loaded, checked for
duplicates and expanded by the workers of an executor. The search is one of
i.e., PEM-A\(^*\) (forward only), PEMM, the external MM of Sturtevant and Chen
[94], and PEM-BAE\(^*\); the reverse PEM-rA\(^*\) is
PEM-A\(^*\) on a ReverseDomain. The domain must be a DiskDomain of
§4.6 (integer costs and trivially copyable
states), and a BidirectionalDomain for PEMM and PEM-BAE\(^*\). The
declarations are
template< DiskDomain D , PEMKind K ,
ADS::WorkerExecutor Executor = ADS::ThreadPool >
requires( ( K == PEMKind::astar ) || BidirectionalDomain< D > )
class PEMSearch {
public:
PEMSearch( const D & domain , unsigned threads = 1 ,
const SearchOptions & options = {} , PEMOptions pem = {} );
void set_executor( Executor & ex ) noexcept;
[[nodiscard]] SolutionT solve( void ) const;
};
with the options of the disk
struct PEMOptions {
/// the partitions of a bucket by the hash of the state
std::size_t partitions = 16;
/// where the files go, in a directory of their own removed at the end;
/// the temporary directory of the system if empty
std::filesystem::path directory;
/// the bytes of the buffer of each file being written
std::size_t buffer_bytes = std::size_t( 1 ) << 16;
/// the most bytes the files may hold on the disk (0 = no cap)
std::uint64_t disk_limit = 0;
}; // end( struct( PEMOptions ) )
i.e., the number \(P\) of partitions of a bucket (16 by default, 0 being
refused), the directory of the files (a directory of their own is made in
it, or in the temporary directory of the system, and removed at the end,
also when the search stops at a limit or throws), the bytes of the buffer of
each file being written, and a cap on the bytes held on the disk, at which
the search stops with Status::disk_limit. The number of workers is
threads; of the SearchOptions, node_limit bounds the states written to
the closed files, and a weight other than 1 is refused. The counters are
expanded (the states expanded, and expanded_by by direction),
generated, duplicates (the copies dropped), stored (the states written
to the closed files), sent (the bytes written to the disk) and messages
(here the most bytes held on the disk at once).
The buckets and the meetings¶
A node of the direction \(D\) is kept in the bucket \((D, g_D, h_F, h_B)\) (with \(h_B = 0\) for PEM-A\(^*\)), which carries all that the priorities and the bounds need, and the bucket is split into \(P\) partitions by the hash of the state, a partition being a file per worker that writes to it. Two copies of a state, in either direction, have the same \(h_F\) and \(h_B\) and the same partition, so that the duplicates of a partition are in the same partition of the buckets with the same heuristics, and so are the copies of the state in the other direction.
Algorithm 7.4 (PEM-BiHS, the pseudocode of the header
PEMSearch.h:23-39).
1 procedure PEM-BiHS(s, t)
2 U ← ∞; OPEN_F ← {s}; OPEN_B ← {t}
3 while OPEN_F ≠ ∅ ∧ OPEN_B ≠ ∅ ∧ U > LB do
4 D ← the direction chosen; b ← the best bucket of OPEN_D
5 for each partition p of b, in parallel, do
6 T ← the states of the files of p, without copies
7 T ← T ∖ the partition p of the closed buckets of D with the
same h_F and h_B and a smaller g
8 write T to the partition p of CLOSED_D(b)
9 U ← min(U, g + g') for each state of T found, with g', in
the partition p of the buckets of the other direction
with the same h_F and h_B
10 for each u in T and each child v of u in D do
append v to the partition of v of its bucket of OPEN_D
11 return U
Lines 6 to 8 are the processing of a file of DDD-A\(^*\) (Algorithm 4.6), here
for a partition made of the files of all the workers; line 9 is the delayed
solution detection of Sturtevant and Chen [94]:
a meeting is found when one of its two copies is expanded, by a scan of the
open and the closed buckets of the other direction with the same heuristics,
in the same partition (Figure 7.3). PEM-A\(^*\) instead tests the goal when a
node is generated, as Siag et al. do. The best bucket of a direction is the
one of least priority (\(f\) for PEM-A\(^*\), \(\max\{f, 2g\}\) for PEMM, \(b\) for
PEM-BAE\(^*\)), of least \(g\) among those, and then of least \(h\) of the
direction, the lower-\(g\)-first order of Siag et al. (section 3.3 of
[57]); PEMM takes the direction of least
priority, the forward one on a tie, and PEM-BAE\(^*\) alternates them. The
partitions of a bucket are taken by the workers from a shared counter, and
each worker writes the children through a buffer per file of the buckets it
fills, the new buckets being added to the open ones when the bucket is done
(PEMSearch.h:519-684). The path is traced back at the
end through the hashes of the parents, as by Algorithm 4.7, from each of the
two records of the meeting.
Since a meeting is found only when one of its copies is expanded, two open copies of a state on an optimal path may be unknown to each other, and the bound \(g_{\min F} + g_{\min B} + \varepsilon\) is not valid (section 3.3 of [94]). The bound of line 3 is therefore \(f_{\min F}\) for PEM-A\(^*\),
for PEMM, and, for PEM-BAE\(^*\), the largest of \(\lceil (b_{\min F} + b_{\min
B}) / 2 \rceil\), \(g_{\min F} + g_{\min B}\), \(f_{\min F} + d_{\min B}\) and
\(d_{\min F} + f_{\min B}\) (the bounds of Alcázar et al.
[89], which the PEM-BAE\(^*\) of Siag et al.
computes), all from the keys of the open buckets
(PEMSearch.h:380-406).
Lemma 7.20 (The order of the buckets). Let the costs be positive and the key of a bucket be nondecreasing along every edge generated, which the search checks. Then, in each direction, no bucket gets a record after its expansion, and the copy of a state with its optimal \(g\) in that direction, if generated, is expanded before every other copy of it, all the later ones being dropped at line 7.
Proof. Let the bucket \(b\) of \(D\) be expanded. The children of \(b\) and of every later bucket of \(D\) have keys not smaller than their parents and, for equal keys, a larger \(g\) (the costs being positive); since the best bucket is the one of least key and then of least \(g\), the pairs \((\mathrm{key}, g)\) of the buckets expanded in \(D\) never decrease, and a child of a later bucket \(b'\) has either a key larger than that of \(b\) or the same key and \(g > g(b') \ge g(b)\), so that it is not in \(b\). For the second claim, the copies of a state \(v\) have the same heuristics, so that in its buckets the key is a strictly increasing function of \(g\) (as in Lemma 7.4); the copy with the optimal \(g\) is in the bucket of least key among them, and, by the induction along an optimal path of Lemma 4.14, whose argument applies to any key monotone along the edges, it is there when that bucket is expanded. A later copy, of larger \(g\), is in a later bucket of the same heuristics and the same partition, and line 7 finds \(v\) in the closed partition. \(\square\)
The search throws std::logic_error on an edge of a cost that is not
positive and on a child whose bucket has a smaller key than its parent
(PEMSearch.h:638): for PEM-A\(^*\) the second is a heuristic
that is not consistent, and the test pem-thread checks the refusal on the
graph of §2.7. For PEMM and PEM-BAE\(^*\) the check
is on their key, \(\max\{f, 2g\}\) or \(b\), and a heuristic that is not consistent
but keeps the key monotone on the edges generated is not refused; for
PEM-BAE\(^*\) its bounds then need not hold, and the consistency of both
heuristics is an assumption of the search, as the header states.
Lemma 7.21 (Delayed meetings). Let the hypotheses of Lemma 7.20 hold, \(P = (p_0, \dots, p_k)\) be an optimal path, and \(U > C^*\) between two buckets. Then there are \(i \le j\) such that \(p_i\) has a copy in an open forward bucket with \(g_F = d_F(p_i)\), and \(p_j\) one in an open backward bucket with \(g_B = d_B(p_j)\).
Proof. Say that \(p_l\) is settled in \(D\) if its copy with the optimal \(g\) has been expanded in \(D\). If \(p_l\) is settled in both directions, the later of the two expansions scanned the closed partition that holds the earlier one, and set \(U \le C^*\). As in Lemma 7.3, the first node \(p_i\) not settled forward has its optimal copy in an open forward bucket (generated by \(p_{i-1}\) with \(g + h_F \le C^* < U\), and not dropped at line 7 by Lemma 7.20), and the last node \(p_j\) not settled backward has its optimal copy in an open backward bucket. Suppose \(j < i\): then \(p_j\) is settled forward and, if \(j + 1 < i\), \(p_{j+1}\) is settled in both directions, which is excluded; so \(j = i - 1\), \(p_{i-1}\) is settled forward and open backward, and \(p_i\) is settled backward and open forward. The forward expansion of \(p_{i-1}\) generated the forward copy of \(p_i\), and the backward expansion of \(p_i\) generated the backward copy of \(p_{i-1}\); whichever of the two expansions came later found, in an open bucket of the other direction with the same heuristics and partition, the copy generated by the earlier one (the forward copy of \(p_i\), or the backward copy of \(p_{i-1}\), both still open), and set \(U \le C^*\). Hence \(i \le j\). \(\square\)
Theorem 7.22 (Correctness of PEM-BiHS). Under the
hypotheses of Lemma 7.20, and with consistent heuristics for PEM-BAE\(^*\), the
searches of PEMSearch return \(C^*\), or report \(t\) unreachable, unless a
limit stops them first; each state is expanded at most once in each
direction.
Proof. With \(n = p_i\) and \(m = p_j\) of Lemma 7.21, \(g_F(n) + g_B(m) \le C^*\) (now possibly with \(n = m\)), which proves the bound \(g_{\min F} + g_{\min B}\); the bounds of \(f\) and \(C\) follow as in Theorem 7.5 (1 and 3), whose proofs use only \(g_F(n) + g_B(m) \le C^*\), and those of BAE\(^*\) as in Theorem 7.5 (4 and 5), whose proofs use \(d(n, m) \ge 0\). Every key of an open bucket is the key of the copies in it, so the least keys of the buckets are at most those of the copies of \(n\) and \(m\). Theorem 7.6, with Lemma 7.21 in place of Lemma 7.3, gives the result for PEMM and PEM-BAE\(^*\); PEM-A\(^*\) is DDD-A\(^*\) with the goal tested at the generation and the stop at \(U \le f_{\min F}\), which is correct by the same argument with \(j = k\). A state is written to a closed file of \(D\) only once by Lemma 7.20, and it is expanded only from there. \(\square\)
The implementation¶
The closed buckets are indexed by \((D, h_F, h_B)\), each with the list of the
values of \(g\) that have a closed file, so that the scan of line 7 reads only
the closed partitions of the same heuristics and of a smaller \(g\), and that
of line 9 those of the other direction with the same heuristics; the open
buckets are a set, scanned linearly to choose the best and to compute the
bound, at a cost proportional to their number, which is small relative to
the records. The memory holds, for each worker, the hash table of the
partition it is processing and a buffer of buffer_bytes for each file it
writes, i.e., at most \(P\) for each distinct bucket of the children of the
current one; the disk holds every closed file to the end, as for DDD-A\(^*\)
(Proposition 4.16), since a duplicate may be
in any closed bucket of the same heuristics and the path is traced through
them. The test pem-thread (and pem-openmp, pem-fastflow) runs
PEM-A\(^*\), PEMM, PEM-BAE\(^*\) and PEM-rA\(^*\) with 1, 2 and 4 workers and 5
partitions on 3 states of the 8-puzzle, on random grids with 4 moves and on
the map of Romania, and with 2 workers on random walks of 40 moves of the
15-puzzle, against the cost of A\(^*\); it checks the stop at a cap of 4096
bytes on the disk and at a node limit of 1000, the refusal of an
inconsistent heuristic, and that no file is left when the searches end, stop
or throw.
7.10 A\(^*\) with immediate duplicate detection on the disk¶
The external searches above, and DDD-A\(^*\) of
§4.6, detect the duplicates in batches by
scanning files, which suits a disk read sequentially. On a solid state drive
a random read costs much less, and Lin and Fukunaga
[95] revisited the immediate duplicate
detection on the disk: their A\(^*\)-IDD keeps the closed list in a file read
at random, and in memory only a compact table of the positions of its
records. The class template IDDAStar< D > (IDDAStar.h)
implements it for a DiskDomain, with the declarations
template< DiskDomain D >
class IDDAStar {
public:
explicit IDDAStar( const D & domain , const SearchOptions & options = {} ,
IDDOptions idd = {} );
[[nodiscard]] SolutionT solve( void ) const;
};
template< DiskDomain D >
[[nodiscard]] Solution< state_t< D > , cost_t< D > > idd_astar(
const D & domain , const SearchOptions & options = {} ,
const IDDOptions & idd = {} );
and the options
struct IDDOptions {
/// where the files go, in a directory of their own removed at the end;
/// the temporary directory of the system if empty
std::filesystem::path directory;
/// the places S of the table of the positions in memory, which bound
/// the closed states to 7 S / 8; at least 8 blocks
std::size_t slots = std::size_t( 1 ) << 20;
/// the partitions P of the states, one buffer each
std::size_t partitions = 100;
/// the states B of a full buffer, i.e., of a block of the file
std::size_t block = std::size_t( 1 ) << 10;
/// the records of the top of an open bucket kept in memory
std::size_t open_block = std::size_t( 1 ) << 10;
/// the most bytes the files may hold on the disk (0 = no cap)
std::uint64_t disk_limit = 0;
}; // end( struct( IDDOptions ) )
i.e., the directory of the files (as for PEMSearch), the number \(S\) of
places of the table of the positions, which bounds the closed states to
\(7S/8\), the number \(P\) of partitions, the number \(B\) of states of a block of
the closed file, the number of records of the top of an open bucket kept in
memory, and the cap on the bytes on the disk. A zero option, or \(S < 8B\), is
refused with std::invalid_argument, as is a weight other than 1.
The lists¶
OPEN is a set of buckets \((f, g)\), ordered by least \(f\) and then by largest
\(g\), each a stack of records on the disk with its top in memory: a push adds
to the top, and when the top holds twice the records of open_block, its
lower half goes to the file of the bucket; a pop takes from the top, and when
the top is empty the last block of the file is read back
(IDDAStar.h:350-398). A record holds the state, its
\(g\), the state of its parent and, in an OperatorDomain, its operator. CLOSED
has three parts: the records, in a file written only at its end (or rewritten
in place); a table in memory of \(S\) places of \(\lceil \log_2(S + 1) \rceil\)
bits each, packed in words, each holding the position plus one of a record in
the file (0 for an empty place), probed linearly from the hash of the state;
and \(P\) buffers in memory, one per partition of the states by a second hash,
which collect the states closed until a buffer holds \(B\) of them and is written
to the file as one block, its positions then being put in the table. Since
each block holds the states of one partition, a vector of one partition
number per block tells whether the record that a place points to may be the
state looked for, and the file is read only when it may (section 4 of
[95]).
Algorithm 7.5 (A\(^*\)-IDD, the pseudocode of the header
IDDAStar.h:25-39).
1 procedure A*-IDD(s₀)
2 push (s₀, g = 0) in OPEN
3 while OPEN ≠ ∅ do
4 n ← pop the top of the bucket of least f and largest g
5 if n is in the buffer of its partition or, probing the table
and reading only the records of blocks of its partition,
in the file, with a g not larger, then continue
6 put n in the buffer of its partition (or update its record)
7 if the buffer has B states, append them to the file as a
block, and put their positions in the table
8 if n is a goal then return the path, traced by the parents
9 push each successor of n, with its g and parent, in OPEN
10 return unsolvable
The duplicates are thus detected when a node is popped, before its expansion, and not when it is generated: OPEN holds every copy generated, as the lazy list of §3.1, and a state popped with a smaller \(g\) than its closed record is reopened, its record rewritten in the buffer or in place in the file. The path is traced from the goal by looking up the parent of each record among the closed states, down to the root, whose parent is itself.
Lemma 7.23 (The lookup is exact). At each pop, (a) every closed state is either in the buffer of its partition or in the file, at a position \(a\) such that the place holding \(a + 1\) is reached by the linear probing from its hash before an empty place, and not both; (b) the block \(\lfloor a / B \rfloor\) of the file holds only states of one partition, the one recorded for it; (c) the table has an empty place. Hence the probe of line 5 terminates, and it finds the closed record of \(n\) if there is one, reading from the disk only records of the partition of \(n\).
Proof. (b) A buffer is written only when it holds exactly \(B\) states, all
of its partition, so that each block is full and of one partition, and its
partition is appended to the vector at the same time
(IDDAStar.h:327-348). (a) A state is put in the buffer
only when it is found neither there nor in the file, and it leaves the buffer
only when the buffer is written, each record of the block getting a place found
by the linear probing from its hash; the places are never cleared, so that the
probing from the hash of a state reaches its place before any empty one
(Lemma 3.9), and a reopening rewrites the
record at the same position. (c) The search stops when \(8\, \mathit{used}
\ge 7S\) after a step, so that before a flush fewer than \(7S/8\) places are
taken, and a flush adds \(B \le S/8\) of them (the constructor requires \(S \ge
8B\)); hence fewer than \(S\) places are ever taken, the stop coming right
after the flush that reaches \(7S/8\). Thus the probe meets an empty place,
and a place whose block has another partition is skipped without reading the
record, which cannot be that of \(n\) by (b). \(\square\)
Theorem 7.24 (Correctness of A\(^*\)-IDD). With an admissible heuristic and positive costs, A\(^*\)-IDD returns a path of cost \(C^*\), or reports the instance unsolvable on a finite graph, unless a limit stops it; with a consistent heuristic each state is expanded once, and \(\mathit{expanded} = \mathit{stored}\).
Proof. By Lemma 7.23 the test of line 5 is exact, and the search is A\(^*\) with the duplicates of OPEN dropped at the selection rather than at the generation, the reopening of a closed state popped with a smaller \(g\), and the goal tested at the selection. Every state popped and not dropped has a \(g\) smaller than that of every earlier closure of it, so that the invariant of OPEN of Lemma 2.7 holds (an optimal path has a copy of one of its nodes in OPEN with its optimal \(g\), all its predecessors on the path being closed with the optimal one), and the argument of Theorem 2.9 gives that the first goal popped has \(g = C^*\); the path traced through the records of the parents has a cost at most \(g\), each parent having been closed with a \(g\) that only decreased since, and it ends at the root, since \(g\) strictly decreases along it. With a consistent heuristic the order by \(f\) closes each state with its optimal \(g\) (Theorem 2.13), so that no reopening occurs, and each closed state is stored and expanded once. On a finite graph the closures are finitely many, as in Theorem 2.11. \(\square\)
Proposition 7.25 (Memory and accesses of A\(^*\)-IDD). The memory holds the table, \(S \lceil \log_2(S+1) \rceil / 8\) bytes, the \(P\) buffers, fewer than \(P B\) records, the vector of the partitions of the blocks, and the tops of the open buckets, fewer than \(2\, \mathit{open\_block}\) records each; the disk holds the closed records and the bottoms of the open buckets. A lookup in the file reads at most one record for each place of its partition that the probe visits.
Proof. The bounds follow from the construction above and from Lemma 7.23. \(\square\)
Hence, for \(S = 2^{20}\) (the default), a place takes 21 bits and the table
about 2.75 MB, for up to 917 504 closed states. The counter messages counts the
records read at random from the closed file, i.e., the probes that reach the
disk, and sent the bytes written. The search stops with
Status::node_limit when the table is \(7/8\) full or when the closed states
reach node_limit, and with Status::disk_limit when the files exceed the
cap. The test idd runs A\(^*\)-IDD with \(S = 2^{19}\), \(B = 16\), 7 partitions
and open blocks of 8 records (so that most of the closed list is on the
disk) on 50 states of the 8-puzzle against their exact distances, on the
instance 55 of the 15-puzzle of Korf, where it checks that
\(\mathit{expanded} = \mathit{stored}\) and that the closed file is read, on
random grids and on the map of Romania; it checks the reopening on the graph
with an inconsistent heuristic of §2.7, the stop
when the table of 1024 places is full and at a cap of 4096 bytes on the
disk, the removal of the files, and the refusal of a table smaller than 8
blocks.
We remark that a duplicate found in the file is read twice, once by the probe
and once to compare its \(g\) (IDDAStar.h:429-435), so
that messages counts two reads for it; and that the table is never cleared,
so that a state that is closed once keeps its place for the rest of the search,
which is why the closed states are bounded by \(7S/8\) rather than by the disk.
7.11 Benchmark¶
We compare the bidirectional searches with A\(^*\) and with the reverse A\(^*\)
(A\(^*\) on the ReverseDomain) on the instances of the 15-puzzle of Korf with
the Manhattan distance in both directions, and on random grids with 8 moves
and the octile heuristic, both domains having consistent heuristics and
reversible moves; and the external searches with DDD-A\(^*\) of
§4.6 on the same instances of the
15-puzzle. The runs are made by AStarBench, whose option --algo names
the searches of this chapter (ra, bidij, mm, mme, fmm, bae,
nbs, dvcbs, gbfhs, bibfs, pnba, pdij, pmm, pbae, pema,
pemra, pemm, pembae and idd), each run twice in separate processes
on an idle machine, the gap between the two runs being the A/A noise given
in the note of the tables.
Table 7.1. The in-memory bidirectional searches. For each set of instances and each search, the expansions in the forward and in the backward direction, the nodes stored, and the seconds summed over the instances (each the median of its two runs). The machine and the compiler are given in the note of the table.
| instances | search | expanded forward | expanded backward | stored | seconds |
|---|---|---|---|---|---|
Placeholder: the results of this table are to be measured on an idle machine and written here by manual/build/tables.py; no number is given until then.
Table 7.2. The external searches on the 15-puzzle. For each search and number of workers, the states expanded, the states stored in the closed files, the bytes written to the disk, the most bytes held on the disk at once, and the seconds summed over the instances; the directory of the files is on the local drive of the machine named in the note.
| search | workers | expanded | stored | bytes written | bytes on disk at most | seconds |
|---|---|---|---|---|---|---|
Placeholder: the results of this table are to be measured on an idle machine and written here by manual/build/tables.py; no number is given until then.
The clock is the timer of the Solution: it includes the creation of the
table, the start of the threads of the executor when none is lent, the
search, the writing and the reading of the files and the rebuilding of the
path, and it does not include the construction of the domain nor the
removal of the directory of the files. We leave the tables as placeholders
until the campaign is run on an idle machine.
7.12 Notes and references¶
Bidirectional search is due to Pohl [91], who
also proposed to expand in the direction with fewer open nodes; the
"nipping" of the nodes closed by the other direction is from the BS\(^*\) of
Kwa [90]. The front-to-end searches of this
chapter come from a line of work started by MM of Holte, Felner, Sharon and
Sturtevant [61], whose journal version
[81] gives the bounds and the proof of the
meeting in the middle that we followed in sections 7.2 to 7.4; the improved
priority of MMe is from Sharon et al. [82], and
fMM and the structure of the minimum covers of the must-expand graph are from
Shaham et al. [83]. The sufficient conditions for
node expansion and the must-expand graph are due to Eckerle et al.
[84]; NBS to Chen et al.
[85], whose section 7 gives the queues waiting
and ready that we use; DVCBS, NBS\(_A\) and the eager variants to Shperberg et
al. [86]; and GBFHS to Barley et al.
[87]. BAE\(^*\) was introduced by Sadhukhan
[88], whose paper we could not consult, and
Alcázar, Riddle and Barley [89] derived its
bound, and the individual bounds used with all_bounds, from a unified view
of the errors of the heuristics; we followed their definition. The immediate
and the delayed solution detection, and the external MM, are due to
Sturtevant and Chen [94], and the framework
PEM-BiHS, with PEM-BAE\(^*\) and the reverse A\(^*\), to Siag et al.
[57]. NBA\(^*\) is due to Pijls and Post
[92], and its parallel version PNBA\(^*\) to Rios
and Chaimowicz [93], whose paper we know only
from its abstract; the argument of Lemma 7.16, by which no meeting is missed,
is that of the mutual exclusion of Dekker, and we give it for the atomic
accesses of the library rather than for the scheme of their paper. A\(^*\)-IDD
is due to Lin and Fukunaga [95], and the
hash-based delayed duplicate detection on which the external searches rest
to Korf (see §4.6).
The library implements only front-to-end searches, i.e., searches whose heuristics estimate the distance to the root of the other direction; the front-to-front searches, which estimate the distance to the nodes of the other front, are not treated here. Also, the searches of sections 7.4 to 7.7 are sequential, and the only parallelism over the two directions is that of §7.8, with two workers, while the parallelism within a direction is that of the external searches of §7.9, over the partitions of a bucket. A comparison of the expansions of MM, NBS, DVCBS, GBFHS and BAE\(^*\) across domains is in [86] (table 1) and in [89]; Table 7.1 is to give our own counts, on our instances.
7.13 Exercises¶
Exercise 7.1 (ctest -R PBeFS.bidir). Show that the predecessors of a
cell of a grid with weighted cells, as defined by the domain, are the moves
reversed at the cost of the cell left, and hence that the forward and the
backward graph are the same graph with the edges reversed. The test checks
it on 4 random grids of \(11 \times 7\) cells with 8 moves.
Exercise 7.2 (ctest -R PBeFS.bidir). Prove the bound of MMe, \(\min_D
\max\{f_D, 2 g_D + \varepsilon\} \le C^*\) while \(U > C^*\), directly from
Lemma 7.3, and show that it is never smaller than the bound \(C\) of MM. Then
build a graph of three nodes on which MM expands a node that MMe does not.
The test runs both on 20 states of the 8-puzzle with 6 variants of the
options.
Exercise 7.3 (ctest -R PBeFS.bidir). Theorem 7.7 assumes the choice
of the direction by priority. Build a small instance on which MM with
SideChoice::alternate expands a node with \(g_D > C^*/2\), and explain why
the cost returned is still \(C^*\). The test checks the meeting in the middle
only with the default choice.
Exercise 7.4 (ctest -R PBeFS.bidir). On the graph of five nodes of
the test, with the admissible but inconsistent heuristic \(h = (0, 3, 0, 1,
0)\), run MM by hand with consistent false, and show where a node is
reopened. Then find the step of the proof of Lemma 7.4 that fails with this
heuristic, and explain why bae refuses consistent false.
Exercise 7.5 (ctest -R PBeFS.bidir). Prove that, with eager, every
pair with \(\mathrm{lb} \le C^*\) has an end expanded by NBS before the search
stops. Which line of Algorithm 7.2 is then never executed, and why?
Exercise 7.6 (ctest -R PBeFS.bidir). In Figure 7.2, change the size
of the cluster \(a_0\) to 1 and recompute the weights of the covers \(K_0,
\dots, K_4\) of Lemma 7.12; which cluster does DVCBS expand? Show that NBS,
on the same clusters, may expand nodes of the four clusters \(a_0\), \(a_1\),
\(b_0\) and \(b_1\) before it expands any of \(b_2\).
Exercise 7.7 (ctest -R PBeFS.bidir). Show that GBFHS with
\(\varepsilon = 0\) is still correct, and that each level then raises the sum
of the two limits by one. The test runs GBFHS and the bidirectional
breadth-first search on random directed graphs with arcs of cost 0 to 9, and
with the option \(\varepsilon = 0\) on the 8-puzzle and the grids; which bound
of the other searches becomes weaker with \(\varepsilon = 0\)?
Exercise 7.8 (ctest -R PBeFS.bidir-thread). In Lemma 7.16, replace
the sequentially consistent accesses by a store with release order and a
load with acquire order, and give an execution of the two workers on a path
of three nodes in which neither reads the \(g\) written by the other. Then show
that the published keys of Lemma 7.17 may be read late without harm, but
that a published key that could decrease would break Theorem 7.19.
Exercise 7.9 (ctest -R PBeFS.pem-thread). Lemma 7.21 allows \(i = j\),
which makes the bound \(g_{\min F} + g_{\min B} + \varepsilon\) invalid for the
delayed detection. Build an instance with two open copies of a state on an
optimal path, one per direction, on which that bound exceeds \(C^*\) while
\(U > C^*\), and check that PEMM uses the bound without \(\varepsilon\). The test
runs PEMM, PEM-BAE\(^*\), PEM-A\(^*\) and PEM-rA\(^*\) with 1, 2 and 4 workers.
Exercise 7.10 (ctest -R PBeFS.pem-thread). Show that the bytes on the
disk of PEMSearch never fall below the bytes of the closed files, and
estimate them, for the 15-puzzle, from the number of states stored and the
size of a record (the state, the hash of the parent and the operator). The
test checks the stop at a cap of 4096 bytes.
Exercise 7.11 (ctest -R PBeFS.idd). With \(S = 2^{19}\) places, how
many bits does a place of the table of A\(^*\)-IDD take, and how many closed
states can the search hold? Show that, with 1024 places and blocks of 64
states as in the test, the search stops before the probing of Lemma 7.23
could find the table full, and count the places taken at the stop.
Exercise 7.12 (ctest -R PBeFS.idd). On the graph of five nodes with
the inconsistent heuristic, follow Algorithm 7.5, show which state is
reopened, and whether its record is rewritten in the buffer or in the file
with the options of the test (\(B = 16\), 7 partitions). Then explain why the
test checks \(\mathit{expanded} = \mathit{stored}\) on the 15-puzzle, whose
heuristic is consistent, and not on this graph.