heuristic_search_base.h

#ifndef PROBFD_ALGORITHMS_HEURISTIC_SEARCH_BASE_H
#define PROBFD_ALGORITHMS_HEURISTIC_SEARCH_BASE_H
 
#include "probfd/algorithms/heuristic_search_state_information.h"
#include "probfd/algorithms/types.h"
 
#include "probfd/mdp_algorithm.h"
#include "probfd/progress_report.h"
 
#if defined(EXPENSIVE_STATISTICS)
#include "downward/utils/timer.h"
#endif
 
#include <algorithm>
#include <iostream>
#include <limits>
#include <type_traits>
#include <vector>
 
// Forward Declarations
namespace probfd {
template <typename>
class Distribution;
template <typename>
struct Transition;
template <typename, typename>
class CostFunction;
} // namespace probfd
 
namespace probfd::algorithms {
template <typename, typename>
class PolicyPicker;
template <typename>
class SuccessorSampler;
} // namespace probfd::algorithms
 
namespace probfd::algorithms::fret {
template <typename, typename, typename, typename>
class FRET;
template <typename, typename, typename>
class PolicyGraph;
template <typename, typename, typename>
class ValueGraph;
} // namespace probfd::algorithms::fret
 
namespace probfd::algorithms::heuristic_search {
 
namespace internal {
 
struct Statistics {
    unsigned long long evaluated_states = 0;
    unsigned long long pruned_states = 0;
    unsigned long long goal_states = 0;
 
    unsigned long long expanded_states = 0;
    unsigned long long terminal_states = 0;
    unsigned long long self_loop_states = 0;
 
    unsigned long long value_changes = 0;
    unsigned long long policy_changes = 0;
    unsigned long long value_updates = 0;
    unsigned long long policy_updates = 0;
 
    value_t initial_state_estimate = 0;
    bool initial_state_found_terminal = false;
 
#if defined(EXPENSIVE_STATISTICS)
    utils::Timer update_time = utils::Timer(true);
    utils::Timer policy_selection_time = utils::Timer(true);
#endif
 
    void print(std::ostream& out) const;
};
 
template <typename StateInfo>
class StateInfos : public StateProperties {
    storage::PerStateStorage<StateInfo> state_infos_;
 
public:
    StateInfo& operator[](StateID sid) { return state_infos_[sid]; }
    const StateInfo& operator[](StateID sid) const { return state_infos_[sid]; }
 
    value_t lookup_value(StateID state_id) override
    {
        return state_infos_[state_id].get_value();
    }
 
    Interval lookup_bounds(StateID state_id) override
    {
        return state_infos_[state_id].get_bounds();
    }
 
    void reset() { std::ranges::for_each(state_infos_, &StateInfo::clear); }
};
 
} // namespace internal
 
template <typename State, typename Action, typename StateInfoT>
class HeuristicSearchBase {
    template <bool b, typename T>
    using const_if = std::conditional_t<b, const T, T>;
 
protected:
    using MDPType = MDP<State, Action>;
    using CostFunctionType = CostFunction<State, Action>;
    using EvaluatorType = Evaluator<State>;
    using TransitionType = Transition<Action>;
 
    using PolicyPickerType = PolicyPicker<State, Action>;
 
    // Fret implementation has access to the internals of this base class.
    template <typename, typename, typename, typename>
    friend class fret::FRET;
 
    template <typename, typename, typename>
    friend class fret::PolicyGraph;
 
    template <typename, typename, typename>
    friend class fret::ValueGraph;
 
public:
    using StateInfo = StateInfoT;
 
    static constexpr bool StorePolicy = StateInfo::StorePolicy;
    static constexpr bool UseInterval = StateInfo::UseInterval;
 
    using AlgorithmValueType = AlgorithmValue<UseInterval>;
 
private:
    // Algorithm parameters
    const std::shared_ptr<PolicyPickerType> policy_chooser_;
 
protected:
    // Algorithm state
    internal::StateInfos<StateInfo> state_infos_;
 
    internal::Statistics statistics_;
 
    struct BellmanResult {
        AlgorithmValueType best_value;
        std::optional<TransitionType> transition;
    };
 
public:
    explicit HeuristicSearchBase(
        std::shared_ptr<PolicyPickerType> policy_chooser);
 
    [[nodiscard]]
    Interval lookup_bounds(StateID state_id) const;
 
    [[nodiscard]]
    bool was_visited(StateID state_id) const;
 
    AlgorithmValueType compute_bellman(
        CostFunctionType& cost_function,
        StateID state_id,
        const std::vector<TransitionType>& transitions,
        value_t termination_cost) const;
 
    AlgorithmValueType compute_bellman_and_greedy(
        CostFunctionType& cost_function,
        StateID state_id,
        std::vector<TransitionType>& transitions,
        value_t termination_cost,
        std::vector<AlgorithmValueType>& qvalues,
        value_t epsilon = g_epsilon) const;
 
    std::optional<TransitionType> select_greedy_transition(
        MDPType& mdp,
        std::optional<Action> previous_greedy_action,
        std::vector<TransitionType>& greedy_transitions);
 
    bool update_value(
        StateInfo& state_info,
        AlgorithmValueType other,
        value_t epsilon = g_epsilon);
 
    bool update_policy(
        StateInfo& state_info,
        const std::optional<TransitionType>& transition)
        requires(StorePolicy);
 
protected:
    void initialize_initial_state(
        MDPType& mdp,
        EvaluatorType& h,
        param_type<State> state);
 
    void expand_and_initialize(
        MDPType& mdp,
        EvaluatorType& h,
        param_type<State> state,
        StateInfo& state_info,
        std::vector<TransitionType>& transitions);
 
    void generate_non_tip_transitions(
        MDPType& mdp,
        param_type<State> state,
        std::vector<TransitionType>& transitions) const;
 
    void print_statistics(std::ostream& out) const;
 
private:
    void initialize(
        MDPType& mdp,
        EvaluatorType& h,
        param_type<State> state,
        StateInfo& state_info);
 
    AlgorithmValueType compute_qvalue(
        value_t action_cost,
        StateID state_id,
        const TransitionType& transition) const;
 
    AlgorithmValueType compute_q_values(
        CostFunctionType& cost_function,
        StateID state_id,
        std::vector<TransitionType>& transitions,
        value_t termination_cost,
        std::vector<AlgorithmValueType>& qvalues) const;
 
    AlgorithmValueType filter_greedy_transitions(
        std::vector<TransitionType>& transitions,
        std::vector<AlgorithmValueType>& qvalues,
        const AlgorithmValueType& best_value,
        value_t epsilon = g_epsilon) const;
};
 
template <typename State, typename Action, typename StateInfoT>
class HeuristicSearchAlgorithm
    : public MDPAlgorithm<State, Action>
    , public HeuristicSearchBase<State, Action, StateInfoT> {
    using AlgorithmBase = typename HeuristicSearchAlgorithm::MDPAlgorithm;
    using HSBase = typename HeuristicSearchAlgorithm::HeuristicSearchBase;
 
public:
    using TransitionType = HSBase::TransitionType;
    using AlgorithmValueType = HSBase::AlgorithmValueType;
 
protected:
    using PolicyType = typename AlgorithmBase::PolicyType;
 
    using MDPType = typename AlgorithmBase::MDPType;
    using EvaluatorType = typename AlgorithmBase::EvaluatorType;
 
    using StateInfo = typename HSBase::StateInfo;
    using PolicyPicker = typename HSBase::PolicyPickerType;
 
public:
    // Inherited constructor
    using HSBase::HSBase;
 
    Interval solve(
        MDPType& mdp,
        EvaluatorType& h,
        param_type<State> state,
        ProgressReport progress,
        double max_time) final;
 
    std::unique_ptr<PolicyType> compute_policy(
        MDPType& mdp,
        EvaluatorType& h,
        param_type<State> state,
        ProgressReport progress,
        double max_time) final;
 
    void print_statistics(std::ostream& out) const final;
 
    virtual Interval do_solve(
        MDPType& mdp,
        EvaluatorType& h,
        param_type<State> state,
        ProgressReport& progress,
        double max_time) = 0;
 
    virtual void print_additional_statistics(std::ostream& out) const = 0;
};
 
template <typename State, typename Action, typename StateInfoT>
class FRETHeuristicSearchAlgorithm
    : public HeuristicSearchAlgorithm<State, Action, StateInfoT> {
    using AlgorithmBase = typename FRETHeuristicSearchAlgorithm::MDPAlgorithm;
    using HSBase =
        typename FRETHeuristicSearchAlgorithm::HeuristicSearchAlgorithm;
 
protected:
    using PolicyType = typename AlgorithmBase::PolicyType;
 
    using MDPType = typename AlgorithmBase::MDPType;
    using EvaluatorType = typename AlgorithmBase::EvaluatorType;
 
    using StateInfo = typename HSBase::StateInfo;
    using PolicyPicker = typename HSBase::PolicyPickerType;
 
public:
    // Inherited constructor
    using HSBase::HSBase;
 
    virtual void reset_search_state() {}
};
 
} // namespace probfd::algorithms::heuristic_search
 
#define GUARD_INCLUDE_PROBFD_ALGORITHMS_HEURISTIC_SEARCH_BASE_H
#include "probfd/algorithms/heuristic_search_base_impl.h"
#undef GUARD_INCLUDE_PROBFD_ALGORITHMS_HEURISTIC_SEARCH_BASE_H
 
#endif // __HEURISTIC_SEARCH_BASE_H__