|
| | VacuumWorld (int n, int start, std::uint32_t dirty) |
| | constructor of the row of n cells, with the robot in the cell start and the dirty cells given by the bits of dirty
|
| std::uint64_t | initial_state (void) const noexcept |
| bool | is_goal (std::uint64_t s) const noexcept |
| std::uint64_t | hash (std::uint64_t s) const noexcept |
| int | heuristic (std::uint64_t s) const noexcept |
| template<class F> |
| void | for_each_successor (std::uint64_t s, int h, F &&f) const |
| | calls f( t , 1 , h( t ) ) for Suck, Left and Right, if possible
|
| std::size_t | num_features (void) const noexcept |
| | the number of features: the dirty cells and the cells of the robot
|
| template<class F> |
| void | for_each_feature (std::uint64_t s, F &&f) const |
| | calls f( i ) for each dirty cell i and f( n + r ) for the robot in r
|
| std::size_t | num_abstract_features (void) const noexcept |
| | the number of abstract features: the dirty cells and the robot
|
| std::size_t | abstract_feature (std::size_t i) const noexcept |
| | the abstract feature of a feature: the dirty cell, or n for the robot
|
| std::uint64_t | abstract_state (std::uint64_t s) const noexcept |
| | the abstract state of AHDA*: the dirty cells
|
| std::size_t | num_nblocks (void) const noexcept |
| | the number of nblocks: the cells
|
| std::size_t | nblock (std::uint64_t s) const noexcept |
| | the nblock of PBNF: the cell of the robot
|
| template<class F> |
| void | for_each_nblock_successor (std::size_t b, F &&f) const |
| | calls f( b' ) for each cell b' next to the cell b
|
| int | pairwise_heuristic (std::uint64_t s, std::uint64_t t) const noexcept |
| | the heuristic of PA*SE: the cells dirty in s and clean in t
|
| std::uint64_t | perfect_hash (std::uint64_t s) const noexcept |
| | the perfect hash: the packed state
|
| int | size (void) const noexcept |
| | the number of cells
|
the vacuum world on a row of at most 32 cells
The robot moves Left or Right, or Sucks the dirt of its cell, each action costing 1, and the goal is a clean row; the heuristic, the number of the dirty cells, is consistent. A state packs the dirty cells in the bits \( 0 , \ldots , 31 \) and the cell of the robot in the bits \( 32 , \ldots , 37 \), and the word is also its perfect hash.
The features of Zobrist hashing are the dirt of the cell \( i \), for \( i < n \), and the robot in the cell \( r \), numbered \( n + r \). The abstraction keeps the dirt and forgets the robot: the abstract features of Abstract Zobrist hashing are the dirty cells (the \( n \) features of the robot being one abstract feature, which every state has), and the abstract state of AHDA* is the set of the dirty cells, so that a move keeps the owner and only a Suck changes it. The nblocks of PBNF are the cells of the robot, the neighbours of a cell being its abstract successors, and the heuristic of PA*SE between two states is the number of the cells dirty in the first and clean in the second.
1.15.0