VacuumWorld
Declared in astar/VacuumWorld.h; the same class on the site of Doxygen.
-
class VacuumWorld
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.
Public Types
-
using state_type = std::uint64_t
the packed state
-
using cost_type = int
the cost type
Public Functions
-
inline 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
-
inline std::uint64_t initial_state(void) const noexcept
-
inline bool is_goal(std::uint64_t s) const noexcept
-
inline std::uint64_t hash(std::uint64_t s) const noexcept
-
inline int heuristic(std::uint64_t s) const noexcept
-
template<class F>
inline 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
-
inline std::size_t num_features(void) const noexcept
the number of features: the dirty cells and the cells of the robot
-
template<class F>
inline 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
-
inline std::size_t num_abstract_features(void) const noexcept
the number of abstract features: the dirty cells and the robot
-
inline 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
-
inline std::uint64_t abstract_state(std::uint64_t s) const noexcept
the abstract state of AHDA*: the dirty cells
-
inline std::size_t num_nblocks(void) const noexcept
the number of nblocks: the cells
-
inline std::size_t nblock(std::uint64_t s) const noexcept
the nblock of PBNF: the cell of the robot
-
template<class F>
inline void for_each_nblock_successor(std::size_t b, F &&f) const calls f( b’ ) for each cell b’ next to the cell b
-
inline 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
-
inline std::uint64_t perfect_hash(std::uint64_t s) const noexcept
the perfect hash: the packed state
-
inline int size(void) const noexcept
the number of cells
-
using state_type = std::uint64_t