FarmAStar.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*---------------------------- File FarmAStar.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_FarmAStar
 #define __PBeFS_FarmAStar
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <memory>
 
#include <stdexcept>
 
#include <tuple>
 
#include <type_traits>
 
#include <vector>
 
#include "PBeFS/astar/HDAStar.h"
 
#include "ADS/parallel/Farm.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS FarmAStar -----------------------------*/
/*--------------------------------------------------------------------------*/

 
template< Domain D , ADS::WorkerExecutor Executor = ADS::ThreadPool ,
          class Open = std::conditional_t<
           std::is_integral_v< cost_t< D > > ,
           BucketOpenList< Node< state_t< D > , cost_t< D > > > ,
           HeapOpenList< Node< state_t< D > , cost_t< D > > > > >
class FarmAStar {
 
/*------------------------ 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 FarmAStar( const D & domain , const ParallelOptions & options = {} )
  : f_domain( domain ) , f_options( options ) {
  f_options.normalize();
  }
 
/*------------------------- OTHER INITIALIZATIONS --------------------------*/
 
 void set_executor( Executor & ex ) noexcept { f_ex = &ex; }
 
/*-------------------------------- SOLVING ---------------------------------*/
 
 [[nodiscard]] SolutionT solve( void ) const
 {
  Stopwatch clock;
  const unsigned w = f_options.threads;
  Master master( *this );
  std::vector< char > pinned( w , 0 );
  const auto start = [ & ]( auto && emit , std::size_t ) {
   if( ! ADS::isRunCaller() )
    pin_worker( 0 );
   master.start( emit );
   };
  const auto back = [ & ]( Task * t , auto && emit ) {
   return( master.back( t , emit ) );
   };
  const auto work = [ & ]( Task * t , std::size_t i ) {
   if( ! pinned[ i ] ) {                   // each index on one thread
    pinned[ i ] = 1;
    if( ! ADS::isRunCaller() )
     pin_worker( unsigned( i + 1 ) );
    }
   expand( t );
   return( t );
   };
  if( f_ex )
   ADS::feedbackFarm< Task * , Task * >( *f_ex , w , start , back , work );
  else {
   Executor ex( w + 1 );
   ADS::feedbackFarm< Task * , Task * >( ex , w , start , back , work );
   }
 
  SolutionT sol;
  sol.stats = master.f_st;
  sol.stats.stored = master.f_pool.size();
  sol.stats.expanded_by = { sol.stats.expanded };
  sol.stats.stored_by = { sol.stats.stored };
  if( master.f_limit_hit )
   sol.status = Status::node_limit;
  else
   if( master.f_goal ) {
    sol.status = Status::solved;
    sol.cost = master.f_goal->g;
    sol.path = trace_path( master.f_goal );
    }
  sol.stats.seconds = clock.seconds();
  return( sol );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 // a task: nodes to expand, and then their successors
 struct Task {
  std::vector< NodeT * > nodes;                           // the nodes
  std::vector< std::uint8_t > ops;          // their operators, when sent
  std::vector< std::tuple< std::size_t , State , Cost , Cost ,
                           std::uint8_t > > succ;
          // per successor: its node, state, edge cost, h and operator
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the master: OPEN, CLOSED, the nodes and the counters
 
 struct Master {
 
  explicit Master( const FarmAStar & a ) : f_a( a ) {}
 
  Master( const Master & ) = delete;
  Master & operator=( const Master & ) = delete;
 
  ~Master() {
   for( Task * t : v_free )
    delete t;
   }
 
  // the start: the root, and the first tasks
  template< class E >
  void start( E && emit ) {
   const State s0 = f_a.f_domain.initial_state();
   insert( s0 , Cost( 0 ) , Cost( f_a.f_domain.heuristic( s0 ) ) ,
           nullptr , no_op , f_a.f_domain.hash( s0 ) );
   dispatch( emit );
   }
 
  // a task back, with the successors of its nodes; false once nothing is
  // out at the workers and nothing is left to send
  template< class E >
  bool back( Task * t , E && emit ) {
   --f_out;
   v_hash.resize( t->succ.size() );       // prefetch the batch first
   for( std::size_t i = 0 ; i < t->succ.size() ; ++i ) {
    v_hash[ i ] = f_a.f_domain.hash( std::get< 1 >( t->succ[ i ] ) );
    f_table.prefetch( v_hash[ i ] );
    }
   for( std::size_t i = 0 ; i < t->succ.size() ; ++i ) {
    const auto & [ k , s , c , h , o ] = t->succ[ i ];
    ++f_st.generated;
    NodeT * parent = t->nodes[ k ];
    const Cost g = parent->g + c;
    if( g + h < f_incumbent )
     insert( s , g , h , parent , o , v_hash[ i ] );
    }
   if( f_a.f_options.node_limit &&
       ( f_pool.size() >= f_a.f_options.node_limit ) )
    f_limit_hit = true;
   v_free.push_back( t );
   dispatch( emit );
   return( ( f_out > 0 ) || ( ! f_limit_hit && has_work() ) );
   }
 
  // sends tasks while there are nodes and free workers
  template< class E >
  void dispatch( E && emit ) {
   while( ! f_limit_hit && ( f_out < f_a.f_options.threads ) ) {
    Task * t = nullptr;
    while( NodeT * n = next() ) {
     n->closed = true;
     ++f_st.expanded;
     if( n->expanded )
      ++f_st.reexpanded;
     n->expanded = true;
     if( f_a.f_domain.is_goal( n->state ) ) {
      if( n->g < f_incumbent ) {
       f_incumbent = n->g;
       f_goal = n;
       }
      continue;
      }
     if( ! t ) {
      if( v_free.empty() )
       t = new Task;
      else {
       t = v_free.back();
       v_free.pop_back();
       }
      t->nodes.clear();
      t->ops.clear();
      t->succ.clear();
      }
     t->nodes.push_back( n );
     t->ops.push_back( n->op );
     if( t->nodes.size() >= f_a.f_options.batch )
      break;
     }
    if( ! t )
     return;
    ++f_out;
    emit( t );
    }
   }
 
  // true if OPEN has a node with f below the incumbent
  bool has_work( void ) {
   while( ! f_open.empty() && f_open.top().stale() )
    f_open.pop();
   return( ! f_open.empty() && ( f_open.top_f() < f_incumbent ) );
   }
 
  // the best node of OPEN with f below the incumbent, removed, or nullptr
  NodeT * next( void ) {
   return( has_work() ? f_open.pop().node : nullptr );
   }
 
  // the path to s, whose hash is hash, of cost g through parent and op
  void insert( const State & s , Cost g , Cost h , NodeT * parent ,
               std::uint8_t op , std::uint64_t hash ) {
   auto [ x , fresh ] = f_table.find_or_insert( s , hash , [ & ] {
    NodeT * y = f_pool.allocate();
    *y = NodeT{ s , g , h , parent , false , false , op };
    return( y );
    } );
   if( fresh )
    f_open.push( x );
   else
    if( g < x->g ) {
     x->g = g;
     x->parent = parent;
     x->op = op;
     x->closed = false;
     f_open.push( x );
     }
    else
     ++f_st.duplicates;
   }
 
  const FarmAStar & f_a;                        // the search
  NodePool< NodeT > f_pool;                     // the nodes
  NodeTable< NodeT > f_table;                   // CLOSED
  Open f_open;                                  // OPEN
  std::vector< Task * > v_free;                 // tasks to reuse
  std::vector< std::uint64_t > v_hash;          // hashes of a task back
  unsigned f_out = 0;                           // tasks at the workers
  Cost f_incumbent = infinite_cost< Cost >();   // the best cost found
  NodeT * f_goal = nullptr;                     // the best goal found
  bool f_limit_hit = false;                     // the node limit is hit
  SearchStats f_st;                             // the counters
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the work of a worker: the successors of the nodes of a task
 
 void expand( Task * t ) const {
  for( std::size_t k = 0 ; k < t->nodes.size() ; ++k ) {
   const NodeT * n = t->nodes[ k ];
   for_each_child( f_domain , n->state , n->h , t->ops[ k ] ,
                   [ & ]( const State & s , Cost c , Cost h ,
                          std::uint8_t o ) {
    t->succ.emplace_back( k , s , c , h , o );
    } );
   }
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const D & f_domain;                                   
 ParallelOptions f_options;                            
 Executor * f_ex = nullptr;                            
 
 };  // end( class( FarmAStar ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_FarmAStar */
 
/*--------------------------------------------------------------------------*/
/*-------------------------- End File FarmAStar.h --------------------------*/
/*--------------------------------------------------------------------------*/