Header file for the class template DDDAStar, the A* search with delayed duplicate detection, whose OPEN and CLOSED lists are files on the disk: the External A* of Edelkamp, Jabbar and Schrödl (2004), with the hash-based delayed duplicate detection of Korf (2008) in place of the external sorts. More...

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <filesystem>
#include <map>
#include <memory>
#include <set>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
#include "ADS/dictionary/FlatHashTable.h"
#include "ADS/external/RecordFile.h"
#include "PBeFS/astar/Domain.h"
#include "PBeFS/core/SearchUtils.h"
#include "PBeFS/astar/Solution.h"

Classes
struct	DDDOptions
	the options of DDDAStar, besides those of all the searches More...
class	DDDAStar< D >
	the A* search of a Domain with delayed duplicate detection on the disk More...

Namespaces
namespace	PBeFS_di_unipi_it
	namespace for the Parallel Best-First Search library

Concepts
concept	PBeFS_di_unipi_it::DiskDomain
	a Domain that DDDAStar can search: integer costs, since a bucket is a pair of values, and states that are trivially copyable, since they are written to the disk as their bytes

Functions
template<DiskDomain D>
Solution< state_t< D >, cost_t< D > >	ddd_astar (const D &domain, const SearchOptions &options={}, const DDDOptions &ddd={})
	searches a Domain with A* and delayed duplicate detection on the disk

Detailed Description

Header file for the class template DDDAStar, the A* search with delayed duplicate detection, whose OPEN and CLOSED lists are files on the disk: the External A* of Edelkamp, Jabbar and Schrödl (2004), with the hash-based delayed duplicate detection of Korf (2008) in place of the external sorts.

The nodes are kept in buckets \( ( g , h ) \), one per pair of values, each bucket split into \( P \) files by the hash of the state, so that two copies of a state are always in the same file of their buckets. With a consistent \( h \) and positive integer costs, the buckets are expanded by increasing \( f = g + h \) and, for equal \( f \), by increasing \( g \) (the successors of a bucket of the same \( f \) have a larger \( g \)), and a state reached again has the same \( h \) and a \( g \) not smaller than that of its first copy; hence its duplicates are within its bucket or in the closed buckets of the same \( h \), and nowhere else:

procedure DDD-A*(s₀)
   OPEN(0, h(s₀)) ← {s₀}
   while some OPEN(g, h) is not empty do
      (g, h) ← the bucket of least g + h, and then of least g
      for p ← 0 to P − 1 do
         T ← the states of the file p of OPEN(g, h), without copies
         for each closed bucket (g', h) with g' < g do
            T ← T ∖ the file p of CLOSED(g', h)
         the file p of CLOSED(g, h) ← T
         if T has a goal then return the path to it, of cost g
         for each u in T and each successor v of u do
            append (v, hash(u)) to the file hash(v) mod P of
                OPEN(g + c(u, v), h(v))
   return unsolvable

Only one file of one bucket is in memory at a time (line 6), in a hash table, while the closed files are scanned (line 8) and the successors are appended through a buffer per file of the buckets they go to (line 12), so that the memory of the search is that of the largest file, about \( 1 / P \) of the largest bucket, and not that of the states generated. The files of the closed buckets are kept to the end, since a duplicate may be in any of them with the same \( h \); a domain whose duplicates are only a few layers back (the undirected graphs with unit costs, as in the frontier search of Korf et al.) could drop the older ones, which is not done here. Each record carries the hash of the parent of its state and, in an OperatorDomain, the operator that generated it, so that the move back to the parent is not generated [see OperatorDomain]; the hash is the one by which the path is traced back from the goal at the end: the parent is looked for in the closed files of its partition, with a smaller \( g \), and checked to have the state as a successor at the cost of the difference of the two \( g \).

The states must be trivially copyable, since they are written to the files as their bytes, and the costs integers, since a bucket is a pair of values (the concept DiskDomain); a successor of a smaller \( f \) than its parent (a heuristic that is not consistent) or an edge of a cost that is not positive throws std::logic_error, since the order of the buckets would no longer make the first goal optimal.

Author: Donato Meoli
Dipartimento di Informatica
Università di Pisa

Classes

Namespaces

Concepts

Functions

Detailed Description