astar/Domain.h
Header of the layer astar, in the group Domains; the same header on the site of Doxygen, its source on GitHub.
Classes
Class |
Description |
|---|---|
The operator that generated a state, kept in a message [see OperatorDomain]; an empty type, with op always no_op, when D is not an OperatorDomain, so that a message with [[no_unique_address]] on it does not grow |
|
Concepts
-
template<class D>
concept Domain - #include <PBeFS/astar/Domain.h>
a search domain
A type D is a Domain if it provides:
the type state_type, a regular value type compared with ==;
the type cost_type, an arithmetic type for g, h and the edge costs;
initial_state(), the root of the search;
is_goal( s ), the goal predicate;
heuristic( s ), the estimate h( s ) of the cost from s to a goal;
hash( s ), a well spread 64-bit hash of s, used by the closed list;
for_each_successor( s , h_s , f ), which calls f( t , c , h_t ) for every successor t of s, c being the cost of the edge ( s , t ) and h_t = h( t ); the value h_s = h( s ) is passed in so that h_t can be computed incrementally.
-
template<class D>
concept FeatureDomain - #include <PBeFS/astar/Domain.h>
a Domain whose states are described by a set of features
A state is a set of propositions x_0 , … , x_n taken from a universe of num_features() features, and for_each_feature( s , f ) calls f( i ) for every feature i that holds in s. This is what Zobrist hashing needs [see Kishimoto, Fukunaga and Botea, AIJ 2013].
-
template<class D>
concept IncrementalFeatureDomain - #include <PBeFS/astar/Domain.h>
a FeatureDomain that also gives the features changed by a move
for_each_feature_change( s , t , f ) calls f( i ) for every feature i that holds in exactly one of s and of t, a successor of s: since a Zobrist hash is the exclusive or of the entries of the features, the hash of t is that of s with the entries of these features added, and it costs as many lookups as the features that the move changes rather than as the features of t [see Zobrist, 1970].
-
template<class D>
concept AbstractFeatureDomain - #include <PBeFS/astar/Domain.h>
a FeatureDomain that also provides a feature projection
abstract_feature( i ) maps the feature i to an abstract feature in [ 0 , num_abstract_features() ): this is the projection A of Abstract Zobrist hashing [see Jinnai and Fukunaga, JAIR 2017].
-
template<class D>
concept AbstractStateDomain - #include <PBeFS/astar/Domain.h>
a Domain with a state abstraction
abstract_state( s ) returns the image of s in an abstract space, coded as an integer: it is the projection by which AHDA* keeps the successors of a state on the same processor [see Burns et al., JAIR 2010].
-
template<class D>
concept NBlockDomain - #include <PBeFS/astar/Domain.h>
a Domain whose state space is partitioned into nblocks
Besides an abstraction with num_nblocks() abstract states, given by nblock( s ), the Domain enumerates with for_each_nblock_successor( b , f ) the abstract successors of the nblock b, which define the duplicate detection scope of Parallel Best-NBlock-First search [see Burns et al., JAIR 2010].
-
template<class D>
concept PairwiseDomain - #include <PBeFS/astar/Domain.h>
a Domain with a heuristic between any two states
pairwise_heuristic( s , t ) estimates the cost of a path from s to t; it has to be forward-backward consistent, as required by PA*SE [see Phillips, Likhachev and Koenig, ICAPS 2014].
-
template<class D>
concept OperatorDomain - #include <PBeFS/astar/Domain.h>
a Domain that knows the operator by which a state was generated
for_each_successor( s , h_s , op , f ) calls f( t , c , h_t , op_t ) for every successor t of s except the one that the inverse of op leads to, op being the operator that generated s (no_op at the root) and op_t < no_op the one that generates t. Since the inverse move costs as much as the move, going back to the parent never gives a cheaper path, and the searches skip it without looking it up [see Burns et al., SoCS 2012].
-
template<class D>
concept PerfectHashDomain - #include <PBeFS/astar/Domain.h>
a Domain with a perfect hash of its states
perfect_hash( s ) is an injective map of the states to integers, used by the HDA*[P] work distribution of Burns et al. (JAIR 2010).
Functions
-
template<Domain D, class F>
void PBeFS_di_unipi_it::for_each_child(
) the successors of s but its parent, when D knows the operators
Calls f( t , c , h_t , op_t ) for every successor t of s, s having been generated by the operator op: without the one that the inverse of op leads to and with op_t the operator of t if D is an OperatorDomain, with all of them and op_t = no_op otherwise.
Types
-
template<Domain D>
using PBeFS_di_unipi_it::state_t = typename D::state_type the state type of a Domain
-
template<Domain D>
using PBeFS_di_unipi_it::cost_t = typename D::cost_type the cost type of a Domain
Variables
-
constexpr std::uint8_t PBeFS_di_unipi_it::no_op = 0xFF
the operator of the root, which no state was generated by
Description of the header
Header file for the concepts a search problem has to satisfy in order to be searched by the algorithms of the library, and for the few type helpers built upon them.
A domain describes an implicit state-space graph in the sense of Edelkamp and Schroedl: an initial state, a goal predicate, and an expansion procedure that enumerates the successors of a state together with the cost of the edge and the heuristic value of the successor. All the searches are templates over the domain, so that no virtual call is paid in the inner loop [see Burns et al., SoCS 2012].
- Author
Donato Meoli
Dipartimento di Informatica
Università di Pisa
- Copyright
© by Donato Meoli