DDDAStar.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*---------------------------- File DDDAStar.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_DDDAStar
 #define __PBeFS_DDDAStar
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <algorithm>
 
#include <cstddef>
 
#include <cstdint>
 
#include <filesystem>
 
#include <map>
 
#include <memory>
 
#include <set>
 
#include <stdexcept>
 
#include <string>
 
#include <tuple>
 
#include <type_traits>
 
#include <utility>
 
#include <vector>
 
#include "ADS/dictionary/FlatHashTable.h"
 
#include "ADS/external/RecordFile.h"
 
#include "PBeFS/astar/Domain.h"
 
#include "PBeFS/core/SearchUtils.h"
 
#include "PBeFS/astar/Solution.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- CONCEPTS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
template< class D >
concept DiskDomain = Domain< D > && std::is_integral_v< cost_t< D > > &&
 std::is_trivially_copyable_v< state_t< D > >;
 
/*--------------------------------------------------------------------------*/
/*--------------------------------- TYPES ----------------------------------*/
/*--------------------------------------------------------------------------*/
 
struct DDDOptions {
 std::size_t partitions = 64;
 std::filesystem::path directory;
 std::size_t buffer_bytes = std::size_t( 1 ) << 16;
 };  // end( struct( DDDOptions ) )
 
/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS DDDAStar ------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< DiskDomain D >
class DDDAStar {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using State = state_t< D >;                       
 using Cost = cost_t< D >;                         
 using SolutionT = Solution< State , Cost >;       
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 explicit DDDAStar( const D & domain , const SearchOptions & options = {} ,
                    DDDOptions ddd = {} )
  : f_domain( domain ) , f_options( options ) , f_ddd( std::move( ddd ) )
 {
  if( f_ddd.partitions == 0 )
   throw( std::invalid_argument( "DDDAStar: no partition" ) );
  }
 
/*-------------------------------- SOLVING ---------------------------------*/
 
 [[nodiscard]] SolutionT solve( void ) const
 {
  Stopwatch clock;
  Run r( f_domain , f_options , f_ddd );
  SolutionT sol = r.search();
  sol.stats = std::move( r.st );
  sol.stats.expanded_by = { sol.stats.expanded };
  sol.stats.stored_by = { sol.stats.stored };
  sol.stats.seconds = clock.seconds();
  return( sol );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:

 struct Rec {
  State s;
  std::uint64_t parent;
  [[no_unique_address]] OperatorOf< D > o;
  };

 struct Val {
  std::uint64_t parent;
  [[no_unique_address]] OperatorOf< D > o;
  };

 struct Hash {
  const D * d;
  std::uint64_t operator()( const State & s ) const {
   return( d->hash( s ) );
   }
  };
 
 using Table = ADS::FlatHashTable< State , Val , Hash >;

 struct Key {
  Cost f;
  Cost g;
  bool operator<( const Key & o ) const {
   return( ( f < o.f ) || ( ( f == o.f ) && ( g < o.g ) ) );
   }
  };

 struct Run {
 
  const D & d;                                    
  const SearchOptions & opt;                      
  const DDDOptions & ddd;                         
  ADS::TempDirectory dir;                         
  std::size_t buffer;                             
  std::set< Key > open;                           
  std::map< Cost , std::vector< Cost > > closed;  
  SearchStats st;                                 
 
  Run( const D & domain , const SearchOptions & o , const DDDOptions & x )
   : d( domain ) , opt( o ) , ddd( x ) , dir( x.directory , "pbefs-ddd-" ) ,
     buffer( std::max< std::size_t >( 1 , x.buffer_bytes / sizeof( Rec ) ) )
   {}
 
  // the file p of the open (o) or closed (c) bucket ( g , h )
  [[nodiscard]] ADS::RecordFile< Rec > file( char kind , Cost g , Cost h ,
                                             std::size_t p ) const {
   return( ADS::RecordFile< Rec >( dir / ( std::string( 1 , kind ) + "_" +
                                           std::to_string( g ) + "_" +
                                           std::to_string( h ) + "_" +
                                           std::to_string( p ) ) ) );
   }
 
  [[nodiscard]] std::size_t part( const State & s ) const {
   return( std::size_t( d.hash( s ) % ddd.partitions ) );
   }
 
  SolutionT search( void ) {
   SolutionT sol;
   const State s0 = d.initial_state();
   const Cost h0 = d.heuristic( s0 );
   {
    const Rec root{ s0 , d.hash( s0 ) , {} };
    file( 'o' , Cost( 0 ) , h0 , part( s0 ) ).append( &root , 1 );
    open.insert( Key{ h0 , Cost( 0 ) } );
    }
 
   while( ! open.empty() ) {
    const Key k = *open.begin();
    open.erase( open.begin() );
    const Cost g = k.g , h = k.f - k.g;
    // the files of the buckets ( g' , h' ) that the successors go to, by
    // ( g' , h' , p ), with their writers, kept for this bucket only
    std::map< std::tuple< Cost , Cost , std::size_t > ,
              std::pair< std::unique_ptr< ADS::RecordFile< Rec > > ,
                         std::unique_ptr< ADS::RecordWriter< Rec > > > > out;
    const auto writer = [ & ]( Cost gv , Cost hv , std::size_t p )
     -> ADS::RecordWriter< Rec > & {
     auto & slot = out[ { gv , hv , p } ];
     if( ! slot.second ) {
      slot.first = std::make_unique< ADS::RecordFile< Rec > >(
                                               file( 'o' , gv , hv , p ) );
      slot.second = std::make_unique< ADS::RecordWriter< Rec > >(
                                               *slot.first , buffer );
      }
     return( *slot.second );
     };
    for( std::size_t p = 0 ; p < ddd.partitions ; ++p ) {
     auto in = file( 'o' , g , h , p );
     if( in.empty() ) {
      in.remove();
      continue;
      }
     Table t( in.size() , Hash{ &d } );
     in.forEach( [ & ]( const Rec & x ) {
      if( ! t.insert( x.s , Val{ x.parent , x.o } ) )
       ++st.duplicates;                           // a copy in the file
      } );
     in.remove();
     const auto cl = closed.find( h );
     if( cl != closed.end() )
      for( Cost gc : cl->second )
       file( 'c' , gc , h , p ).forEach( [ & ]( const Rec & x ) {
        if( t.remove( x.s ) )
         ++st.duplicates;                         // closed already
        } );
     if( t.empty() )
      continue;
 
     std::vector< Rec > fresh;                    // the closed file p
     fresh.reserve( t.size() );
     t.forEach( [ & ]( const State & s , const Val & v ) {
      fresh.push_back( Rec{ s , v.parent , v.o } );
      } );
     file( 'c' , g , h , p ).append( fresh.data() , fresh.size() );
     st.stored += fresh.size();
     closed[ h ];                                 // the list of this h
 
     for( const Rec & x : fresh )
      if( d.is_goal( x.s ) ) {
       mark_closed( g , h );
       sol.status = Status::solved;
       sol.cost = g;
       sol.path = trace( x , g );
       return( sol );
       }
 
     for( const Rec & x : fresh ) {
      ++st.expanded;
      const std::uint64_t hu = d.hash( x.s );
      for_each_child( d , x.s , h , x.o.op , [ & ]( const State & v , Cost c ,
                                                    Cost hv ,
                                                    std::uint8_t ov ) {
       ++st.generated;
       if( c <= Cost( 0 ) )
        throw( std::logic_error( "DDDAStar: an edge of a cost that is not"
                                 " positive" ) );
       if( g + c + hv < k.f )
        throw( std::logic_error( "DDDAStar: the heuristic is not"
                                 " consistent" ) );
       writer( g + c , hv , part( v ) ).push( Rec{ v , hu , ov } );
       } );
      }
 
     if( opt.node_limit && ( st.stored >= opt.node_limit ) ) {
      mark_closed( g , h );
      sol.status = Status::node_limit;
      return( sol );
      }
     }
 
    for( auto & [ key , fw ] : out ) {
     fw.second->flush();
     const auto [ gv , hv , p ] = key;
     open.insert( Key{ gv + hv , gv } );
     }
    mark_closed( g , h );
    }
   sol.status = Status::unsolvable;
   return( sol );
   }
 
  // the bucket ( g , h ) among the closed ones of h, if it has a file
  void mark_closed( Cost g , Cost h ) {
   auto it = closed.find( h );
   if( ( it != closed.end() ) &&
       ( std::find( it->second.begin() , it->second.end() , g ) ==
         it->second.end() ) )
    it->second.push_back( g );
   }
 
  // the path from s0 to the goal x, of cost g: each parent
  // is looked for in the closed files of its partition, among the states
  // of smaller g whose hash is the one recorded and that have the child as
  // a successor at the cost of the difference
  std::vector< State > trace( Rec x , Cost g ) {
   std::vector< State > path{ x.s };
   const State s0 = d.initial_state();
   while( ! ( ( g == Cost( 0 ) ) && ( x.s == s0 ) ) ) {
    const std::size_t p = std::size_t( x.parent % ddd.partitions );
    bool found = false;
    for( const auto & e : closed ) {
     const Cost hc = e.first;
     for( Cost gc : e.second ) {
      if( gc >= g )
       continue;
      file( 'c' , gc , hc , p ).forEach( [ & ]( const Rec & y ) {
       if( found || ( d.hash( y.s ) != x.parent ) )
        return;
       d.for_each_successor( y.s , hc , [ & ]( const State & v , Cost c ,
                                               Cost ) {
        if( ! found && ( v == x.s ) && ( gc + c == g ) ) {
         found = true;
         x = y;
         g = gc;
         }
        } );
       } );
      if( found )
       break;
      }
     if( found )
      break;
     }
    if( ! found )
     throw( std::logic_error( "DDDAStar: the parent of a state is not in"
                              " the closed files" ) );
    path.push_back( x.s );
    }
   std::reverse( path.begin() , path.end() );
   return( path );
   }
 
  };  // end( struct( Run ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const D & f_domain;                                 
 SearchOptions f_options;                            
 DDDOptions f_ddd;                                   
 
 };  // end( class( DDDAStar ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
template< DiskDomain D >
[[nodiscard]] Solution< state_t< D > , cost_t< D > > ddd_astar(
 const D & domain , const SearchOptions & options = {} ,
 const DDDOptions & ddd = {} )
{
 return( DDDAStar< D >( domain , options , ddd ).solve() );
 }
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_DDDAStar */
 
/*--------------------------------------------------------------------------*/
/*-------------------------- End File DDDAStar.h ---------------------------*/
/*--------------------------------------------------------------------------*/