lrtdp.h

#ifndef PROBFD_ALGORITHMS_LRTDP_H
#define PROBFD_ALGORITHMS_LRTDP_H
 
#include "probfd/algorithms/heuristic_search_base.h"
 
#include <deque>
 
// Forward Declarations
namespace utils {
class CountdownTimer;
}
 
namespace probfd::algorithms {
template <typename>
class SuccessorSampler;
}
 
namespace probfd::algorithms::lrtdp {
 
enum class TrialTerminationCondition {
    TERMINAL,
    CONSISTENT,
    INCONSISTENT,
    REVISITED
};
 
namespace internal {
 
struct Statistics {
    unsigned long long trials = 0;
    unsigned long long trial_bellman_backups = 0;
    unsigned long long check_and_solve_bellman_backups = 0;
 
    void print(std::ostream& out) const;
};
 
template <typename Action, bool UseInterval>
struct PerStateInformation
    : public heuristic_search::
          PerStateBaseInformation<Action, true, UseInterval> {
private:
    using Base = typename heuristic_search::PerStateBaseInformation<Action, true, UseInterval>;
 
public:
    static constexpr uint8_t VISITED = 0b01 << Base::BITS;
    static constexpr uint8_t SOLVED = 0b10 << Base::BITS;
    static constexpr uint8_t BITS = Base::BITS + 2;
    static constexpr uint8_t MASK = 0b11 << Base::BITS;
 
    bool is_solved() const
    {
        return this->info & SOLVED || this->is_goal_or_terminal();
    }
 
    void mark_solved() { this->info |= SOLVED; }
 
    bool is_closed() const { return (this->info & VISITED) != 0; }
 
    void mark_closed()
    {
        assert(!is_solved());
        this->info |= VISITED;
    }
 
    void unmark_closed()
    {
        assert(!is_solved());
        this->info &= ~VISITED;
    }
 
    void clear() { this->info &= ~MASK; }
};
 
} // namespace internal
 
template <typename State, typename Action, bool UseInterval>
class LRTDP
    : public heuristic_search::FRETHeuristicSearchAlgorithm<
          State,
          Action,
          internal::PerStateInformation<Action, UseInterval>> {
    using Base = typename LRTDP::FRETHeuristicSearchAlgorithm;
 
    using AlgorithmValueType = Base::AlgorithmValueType;
 
public:
    using StateInfo = typename Base::StateInfo;
 
private:
    using MDPType = typename Base::MDPType;
    using EvaluatorType = typename Base::EvaluatorType;
    using PolicyPickerType = typename Base::PolicyPicker;
 
    using SuccessorSamplerType = SuccessorSampler<Action>;
 
    using Statistics = internal::Statistics;
 
    // Algorithm parameters
    const TrialTerminationCondition stop_consistent_;
    const std::shared_ptr<SuccessorSamplerType> sample_;
 
    // Algorithm state
    std::vector<StateID> current_trial_;
    std::vector<StateID> policy_queue_;
    std::deque<StateID> visited_;
 
    Statistics statistics_;
 
    // Re-used buffer
    std::vector<Transition<Action>> transitions_;
    std::vector<AlgorithmValueType> qvalues_;
 
public:
    LRTDP(
        std::shared_ptr<PolicyPickerType> policy_chooser,
        TrialTerminationCondition stop_consistent,
        std::shared_ptr<SuccessorSamplerType> succ_sampler);
 
    void reset_search_state() override;
 
protected:
    Interval do_solve(
        MDPType& mdp,
        EvaluatorType& heuristic,
        param_type<State> state,
        ProgressReport& progress,
        double max_time) override;
 
    void print_additional_statistics(std::ostream& out) const override;
 
private:
    void trial(
        MDPType& mdp,
        EvaluatorType& heuristic,
        StateID initial_state,
        utils::CountdownTimer& timer);
 
    bool check_and_solve(
        MDPType& mdp,
        EvaluatorType& heuristic,
        StateID init_state_id,
        utils::CountdownTimer& timer);
};
 
} // namespace probfd::algorithms::lrtdp
 
#define GUARD_INCLUDE_PROBFD_ALGORITHMS_LRTDP_H
#include "probfd/algorithms/lrtdp_impl.h"
#undef GUARD_INCLUDE_PROBFD_ALGORITHMS_LRTDP_H
 
#endif // PROBFD_ALGORITHMS_LRTDP_H