The approach applies to both shared and distributed memory architectures. No locks for individual states are needed. This parallelization maintains locks only for the abstract space. More formally, let ϕ( u 1) and ϕ( u 2) be the two abstract nodes then the scopes of ϕ( u 1) and ϕ( u 2) are disjoint if S u c c ( ϕ ( u 1 ) ) ∩ S u c c ( ϕ ( u 2 ) ) = ∅. If in one BFS level two abstract nodes together with their successor do not overlap, their expansion can be executed fully independently on different processors. We assume that the parallelization takes care of synchronization after one breadth-first search iteration has been completed, because a concurrent expansion in different depths likely affects the algorithm's optimality. In parallel structured duplicate detection abstract states together with their abstract neighbors are assigned to a process. Structured duplicate detection extends nicely to a parallel implementation. If not, external A* or iterative-deepening breadth-first heuristic search applies. 6), which generates the search space with increasing depth, but prunes it with respect to the f-value, provided that the optimal solution length is known. We assume breadth-first heuristic search as the underlying search algorithm (see Ch. Since all adjacent abstract states were loaded into main memory, duplicate detection for concrete successor states remains in the RAM. Each abstract state represents a file containing every concrete state mapping to it. 6) performs early duplicate detection in the RAM. Stefan Edelkamp, Stefan Schrödl, in Heuristic Search, 2012 9.4.2 Parallel Structured Duplicate Detection The idea is that smaller abstract state space sizes should be preferred but usually lead to larger branching factors. If there are different abstractions to choose from, a suggestion is to take those that have the smallest ratio of maximum node branching factor b max and abstract state space size | ϕ ( S ) |. In difference to the locality for delayed duplicate detection the locality for structured duplicate detection is defined as the maximum node branching factor b max = max v ∈ ϕ ( S ) | S u c c ( v ) | in the abstract state space ϕ ( S ). This gives rise to a different definition of locality, which determines a handle for the duplicate detection scope. Before expanding a bucket, not only the bucket itself, but all buckets that are potentially affected by successor generation have to be loaded and, consequently, fit into main memory. In difference to delayed duplicate detection, structured duplicate detection detects duplicates early, as soon as they are generated. A bucket now corresponds to the set of original states, which all map to the same abstract state. 4), such that for each pair of consecutive abstract nodes the pair of original nodes are also connected. Such hash projections are state space homomorphisms (as introduced in Ch. Structured duplicate detection incorporates a hash function that maps nodes into an abstract problem graph this reduces the successor scope of nodes that have to be kept in main memory. Stefan Edelkamp, Stefan Schrödl, in Heuristic Search, 2012 8.7.2 Structured Duplicate Detection
0 kommentar(er)
