PASE.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*------------------------------ File PASE.h -------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_PASE
 #define __PBeFS_PASE
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <algorithm>
 
#include <cmath>
 
#include <compare>
 
#include <condition_variable>
 
#include <cstdint>
 
#include <memory>
 
#include <mutex>
 
#include <tuple>
 
#include <type_traits>
 
#include <utility>
 
#include <vector>
 
#include "PBeFS/astar/HDAStar.h"
 
#include "ADS/tree/BTreeMap.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS PASEOptions ----------------------------*/
/*--------------------------------------------------------------------------*/
 
struct PASEOptions : public ParallelOptions {

 double eps = 1;
 
 };  // end( struct( PASEOptions ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------------- CLASS PASE -------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< PairwiseDomain D , ADS::WorkerExecutor Executor = ADS::ThreadPool >
class PASE {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using State = state_t< D >;                       
 using Cost = cost_t< D >;                         
 using NodeT = Node< State , Cost >;               
 using SolutionT = Solution< State , Cost >;       
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 explicit PASE( const D & domain , const PASEOptions & options = {} )
  : f_domain( domain ) , f_options( options ) {
  f_options.normalize();
  if( f_options.eps < 1 )
   f_options.eps = 1;
  }
 
/*------------------------- OTHER INITIALIZATIONS --------------------------*/
 
 void set_executor( Executor & ex ) noexcept { f_ex = &ex; }
 
/*-------------------------------- SOLVING ---------------------------------*/
 
 [[nodiscard]] SolutionT solve( void ) const
 {
  const unsigned p = f_options.threads;
  Stopwatch clock;
  Shared sh;
  std::vector< std::unique_ptr< Worker > > w( p );
  for( unsigned i = 0 ; i < p ; ++i )
   w[ i ] = std::make_unique< Worker >( *this , sh );
 
  {
   const State s0 = f_domain.initial_state();
   NodeT * root = w[ 0 ]->f_pool.allocate();
   *root = NodeT{ s0 , Cost( 0 ) , Cost( f_domain.heuristic( s0 ) ) ,
                  nullptr , false , false };
   sh.table.find_or_insert( s0 , f_domain.hash( s0 ) ,
                            [ & ] { return( root ); } );
   sh.open.insert( Key( root ) , true );
   }
 
  run_workers( f_ex , p , [ & ]( unsigned i ) { w[ i ]->run(); } );
 
  SolutionT sol;
  SearchStats & st = sol.stats;
  for( auto & x : w ) {
   st.expanded += x->f_st.expanded;
   st.generated += x->f_st.generated;
   st.duplicates += x->f_st.duplicates;
   st.stored += x->f_pool.size();
   st.expanded_by.push_back( x->f_st.expanded );
   st.stored_by.push_back( x->f_pool.size() );
   }
  if( sh.limit_hit )
   sol.status = Status::node_limit;
  else
   if( sh.goal ) {
    sol.status = Status::solved;
    sol.cost = sh.goal->g;
    sol.path = trace_path( sh.goal );
    }
  st.seconds = clock.seconds();
  return( sol );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 using Lock = typename Executor::lock_type;
 
 // OPEN: by f, then by larger g, then by address; with integer costs f
 // and g are one word [see packed_fg], compared at once
 struct Key {
  std::conditional_t< std::is_integral_v< Cost > , std::uint64_t ,
                      std::pair< Cost , Cost > > fg{};
  std::uintptr_t node = 0;
 
  Key( void ) = default;
 
  explicit Key( const NodeT * x )
   : node( reinterpret_cast< std::uintptr_t >( x ) ) {
   if constexpr( std::is_integral_v< Cost > )
    fg = packed_fg( x->g , x->h );
   else
    fg = { x->f() , - x->g };
   }
 
  NodeT * get( void ) const { return( reinterpret_cast< NodeT * >( node ) ); }
 
  friend auto operator<=>( const Key & , const Key & ) = default;
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the data shared by the workers, all protected by lock
 
 struct Shared {
  Lock lock;                                    // protects everything
  std::condition_variable_any changed;          // OPEN or BE changed
  ADS::BTreeMap< Key , bool > open;            // OPEN
  std::vector< NodeT * > be;                    // being expanded
  NodeTable< NodeT > table;                     // all the states
  bool done = false;                            // the search is over
  bool limit_hit = false;                       // the node limit is hit
  NodeT * goal = nullptr;                       // the goal, once safe
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // a worker: its pool of nodes and its counters
 
 struct alignas( cache_line ) Worker {
 
  Worker( const PASE & a , Shared & s ) : f_a( a ) , f_sh( s ) {}
 
  // the states of OPEN that a worker examines for a safe one
  static constexpr std::size_t c_candidates = 64;
 
  // true if s is independent of t: g( s ) - g( t ) <= eps h( t , s ), up
  // to a relative 1e-9 for real costs, whose rounding would otherwise make
  // the goal dependent on the states with f = f( goal )
  bool independent( const NodeT * s , const NodeT * t ) const {
   const double lhs = double( s->g - t->g );
   const double rhs = f_a.f_options.eps *
    double( f_a.f_domain.pairwise_heuristic( t->state , s->state ) );
   if constexpr( std::is_floating_point_v< Cost > )
    return( lhs <= rhs + 1e-9 * std::max( 1.0 ,
                                          std::abs( double( s->g ) ) ) );
   else
    return( lhs <= rhs );
   }
 
  // true if s is safe to expand (lock held): independent of BE and of the
  // states of OPEN with a smaller f, which come first in OPEN, as in the
  // definition of safety of the paper; the states of equal f are not
  // checked, so that a layer of equal f costs a scan of BE per state
  // instead of a scan of the layer
  bool safe( const NodeT * s ) const {
   for( const NodeT * t : f_sh.be )
    if( ! independent( s , t ) )
     return( false );
   const Cost fs = s->f();
   for( const auto & k : f_sh.open ) {
    const NodeT * t = k.first.get();
    if( ! ( t->f() < fs ) )
     break;
    if( ! independent( s , t ) )
     return( false );
    }
   return( true );
   }
 
  // Algorithm 1 of the paper
  void run( void ) {
   std::vector< std::tuple< State , Cost , Cost , std::uint64_t ,
                            std::uint8_t > > succ;
   std::unique_lock< Lock > guard( f_sh.lock );
   while( ! f_sh.done ) {
    // the safe state of smallest f among the first c_candidates of OPEN,
    // if any: further down, each candidate would have to be checked
    // against the larger and larger part of OPEN before it, under the lock;
    // with BE empty the first state is safe, and the search goes on
    NodeT * s = nullptr;
    std::size_t n = 0;
    for( const auto & k : f_sh.open ) {
     if( n++ == c_candidates )
      break;
     if( safe( k.first.get() ) ) {
      s = k.first.get();
      break;
      }
     }
    if( ! s ) {
     if( f_sh.open.empty() && f_sh.be.empty() ) {
      f_sh.done = true;
      f_sh.changed.notify_all();
      break;
      }
     f_sh.changed.wait( guard );
     continue;
     }
    f_sh.open.remove( Key( s ) );
    if( f_a.f_domain.is_goal( s->state ) ) {
     f_sh.goal = s;               // safe, hence of optimal g
     f_sh.done = true;
     f_sh.changed.notify_all();
     break;
     }
    f_sh.be.push_back( s );
    s->closed = s->expanded = true;
    const State st = s->state;
    const Cost g = s->g , h = s->h;
    const std::uint8_t op = s->op;
    guard.unlock();
 
    ++f_st.expanded;
    succ.clear();
    for_each_child( f_a.f_domain , st , h , op ,
                    [ & ]( const State & t , Cost c , Cost ht ,
                           std::uint8_t ot ) {
     succ.emplace_back( t , g + c , ht , f_a.f_domain.hash( t ) , ot );
     } );
 
    // the hashes computed without the lock, and the places of all the
    // successors prefetched under it before any lookup, so that their
    // misses overlap and the lock is held for about one of them
    guard.lock();
    for( const auto & sc : succ )
     f_sh.table.prefetch( std::get< 3 >( sc ) );
    for( const auto & sc : succ ) {    // no structured binding: OpenMP
     const State & t = std::get< 0 >( sc );     // cannot capture one
     const Cost gt = std::get< 1 >( sc ) , ht = std::get< 2 >( sc );
     ++f_st.generated;
     auto [ x , fresh ] = f_sh.table.find_or_insert( t ,
                                                     std::get< 3 >( sc ) ,
                                                     [ & ] {
      NodeT * y = f_pool.allocate();
      *y = NodeT{ t , gt , ht , s , false , false , std::get< 4 >( sc ) };
      return( y );
      } );
     if( fresh )
      f_sh.open.insert( Key( x ) , true );
     else
      if( ! x->closed && ( gt < x->g ) ) {
       f_sh.open.remove( Key( x ) );
       x->g = gt;
       x->parent = s;
       x->op = std::get< 4 >( sc );
       f_sh.open.insert( Key( x ) , true );
       }
      else
       ++f_st.duplicates;
     }
    f_sh.be.erase( std::find( f_sh.be.begin() , f_sh.be.end() , s ) );
    if( f_a.f_options.node_limit &&
        ( f_pool.size() >= f_a.f_options.node_limit ) ) {
     f_sh.limit_hit = true;
     f_sh.done = true;
     }
    f_sh.changed.notify_all();
    }
   }
 
  const PASE & f_a;                             // the search
  Shared & f_sh;                                // the shared data
  NodePool< NodeT > f_pool;                     // the nodes it allocated
  SearchStats f_st;                             // its counters
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const D & f_domain;                                   
 PASEOptions f_options;                                
 Executor * f_ex = nullptr;                            
 
 };  // end( class( PASE ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_PASE */
 
/*--------------------------------------------------------------------------*/
/*---------------------------- End File PASE.h -----------------------------*/
/*--------------------------------------------------------------------------*/