interval_iteration.h

#ifndef PROBFD_ALGORITHMS_INTERVAL_ITERATION_H
#define PROBFD_ALGORITHMS_INTERVAL_ITERATION_H
 
#include "probfd/algorithms/topological_value_iteration.h"
 
#include "probfd/preprocessing/end_component_decomposition.h"
#include "probfd/preprocessing/qualitative_reachability_analysis.h"
 
#include "probfd/quotients/quotient_system.h"
 
#include "probfd/storage/per_state_storage.h"
 
#include "probfd/mdp_algorithm.h"
 
#include <limits>
 
namespace probfd::algorithms::interval_iteration {
 
struct Statistics {
    preprocessing::ECDStatistics ecd_statistics;
    topological_vi::Statistics tvi_statistics;
 
    void print(std::ostream& out) const
    {
        tvi_statistics.print(out);
        ecd_statistics.print(out);
    }
};
 
template <typename State, typename Action>
class IntervalIteration : public MDPAlgorithm<State, Action> {
    using Base = typename IntervalIteration::MDPAlgorithm;
 
    using MDPType = typename Base::MDPType;
    using EvaluatorType = typename Base::EvaluatorType;
    using PolicyType = typename Base::PolicyType;
 
    using QSystem = quotients::QuotientSystem<State, Action>;
    using QState = quotients::QuotientState<State, Action>;
    using QAction = quotients::QuotientAction<Action>;
 
    using Decomposer = preprocessing::EndComponentDecomposition<State, Action>;
    using QuotientQRAnalysis =
        preprocessing::QualitativeReachabilityAnalysis<QState, QAction>;
    using QuotientValueIteration =
        topological_vi::TopologicalValueIteration<QState, QAction, true>;
 
    // Algorithm parameters
    const bool extract_probability_one_states_;
 
    // Algorithm state
    QuotientQRAnalysis qr_analysis_;
    Decomposer ec_decomposer_;
    QuotientValueIteration vi_;
 
    Statistics statistics_;
 
public:
    explicit IntervalIteration(
        bool extract_probability_one_states,
        bool expand_goals);
 
    Interval solve(
        MDPType& mdp,
        EvaluatorType& heuristic,
        param_type<State> state,
        ProgressReport report,
        double max_time) override;
 
    std::unique_ptr<PolicyType> compute_policy(
        MDPType& mdp,
        EvaluatorType& heuristic,
        param_type<State> state,
        ProgressReport report,
        double max_time) override;
 
    void print_statistics(std::ostream& out) const override;
 
    template <typename ValueStoreT, typename SetLike, typename SetLike2>
    Interval solve(
        MDPType& mdp,
        EvaluatorType& heuristic,
        param_type<State> state,
        ValueStoreT& value_store,
        SetLike& dead_ends,
        SetLike2& one_states,
        double max_time = std::numeric_limits<double>::infinity());
 
private:
    std::unique_ptr<QSystem> create_quotient(
        MDPType& mdp,
        EvaluatorType& heuristic,
        param_type<State> state,
        utils::CountdownTimer& timer);
 
    template <typename ValueStoreT, typename SetLike, typename SetLike2>
    Interval mysolve(
        MDPType& mdp,
        EvaluatorType& heuristic,
        param_type<State> state,
        ValueStoreT& value_store,
        SetLike& dead_ends,
        SetLike2& one_states,
        QSystem& sys,
        utils::CountdownTimer& timer);
};
 
} // namespace probfd::algorithms::interval_iteration
 
#define GUARD_INCLUDE_PROBFD_ALGORITHMS_INTERVAL_ITERATION_H
#include "probfd/algorithms/interval_iteration_impl.h"
#undef GUARD_INCLUDE_PROBFD_ALGORITHMS_INTERVAL_ITERATION_H
 
#endif // PROBFD_ALGORITHMS_INTERVAL_ITERATION_H