PrioritizedSweeping.hpp

Go to the documentation of this file.

#ifndef AI_TOOLBOX_MDP_PRIORITIZED_SWEEPING_HEADER_FILE
#define AI_TOOLBOX_MDP_PRIORITIZED_SWEEPING_HEADER_FILE
 
#include <tuple>
#include <unordered_map>
 
#include <boost/heap/fibonacci_heap.hpp>
 
#include <AIToolbox/MDP/Types.hpp>
#include <AIToolbox/MDP/TypeTraits.hpp>
#include <AIToolbox/MDP/Utils.hpp>
 
#include <AIToolbox/Utils/Probability.hpp>
 
namespace AIToolbox::MDP {
    template <IsModel M>
    class PrioritizedSweeping {
        public:
            PrioritizedSweeping(const M & m, double theta = 0.5, unsigned n = 50);
 
            void stepUpdateQ(size_t s, size_t a);
 
            void batchUpdateQ();
 
            void setQueueThreshold(double t);
 
            double getQueueThreshold() const;
 
            void setN(unsigned n);
 
            unsigned getN() const;
 
            size_t getQueueLength() const;
 
            const M & getModel() const;
 
            const QFunction & getQFunction() const;
 
            void setQFunction(const QFunction & q);
 
            const ValueFunction & getValueFunction() const;
 
        private:
            size_t S, A;
            unsigned N;
            double theta_;
 
            const M & model_;
            QFunction qfun_;
            ValueFunction vfun_;
 
            struct PriorityQueueElement {
                double priority;
                std::pair<size_t, size_t> stateAction;
                bool operator<(const PriorityQueueElement& arg2) const {
                    return priority < arg2.priority;
                }
            };
 
            using QueueType = boost::heap::fibonacci_heap<PriorityQueueElement>;
 
            QueueType queue_;
 
            std::unordered_map<std::pair<size_t, size_t>, typename QueueType::handle_type, boost::hash<std::pair<size_t, size_t>>> queueHandles_;
    };
 
    template <IsModel M>
    PrioritizedSweeping<M>::PrioritizedSweeping(const M & m, const double theta, const unsigned n) :
            S(m.getS()), A(m.getA()), N(n), theta_(theta), model_(m),
            qfun_(makeQFunction(S,A)), vfun_(makeValueFunction(S)) {}
 
    template <IsModel M>
    void PrioritizedSweeping<M>::stepUpdateQ(const size_t s, const size_t a) {
        auto & values = vfun_.values;
 
        // Update q[s][a]
        if constexpr(IsModelEigen<M>) {
            qfun_(s,a) = model_.getRewardFunction().coeff(s, a) + model_.getTransitionFunction(a).row(s).dot(values * model_.getDiscount());
        } else {
            double newQValue = 0;
            for ( size_t s1 = 0; s1 < S; ++s1 ) {
                const double probability = model_.getTransitionProbability(s,a,s1);
                if ( checkDifferentSmall( probability, 0.0 ) )
                    newQValue += probability * ( model_.getExpectedReward(s,a,s1) + model_.getDiscount() * values[s1] );
            }
            qfun_(s, a) = newQValue;
        }
 
        double p = values[s];
        {
            // Update value and action
            values[s] = qfun_.row(s).maxCoeff(&(vfun_.actions[s]));
        }
 
        p = std::fabs(values[s] - p);
 
        for ( size_t ss = 0; ss < S; ++ss ) {
            for ( size_t a = 0; a < A; ++a ) {
                const double delta = p * model_.getTransitionProbability(ss,a,s);
                // If it changed enough, we're going to update its parents.
                if ( delta > theta_ ) {
                    const auto pair = std::make_pair(ss, a);
                    auto it = queueHandles_.find(pair);
 
                    if (it != std::end(queueHandles_)) {
                        if ((*it->second).priority < delta) {
                            (*it->second).priority = delta;
                            queue_.increase(it->second);
                        }
                    } else {
                        queueHandles_[pair] = queue_.emplace(PriorityQueueElement{delta, pair});
                    }
                }
            }
        }
    }
 
    template <IsModel M>
    void PrioritizedSweeping<M>::batchUpdateQ() {
        for ( unsigned i = 0; i < N; ++i ) {
            if ( queue_.empty() ) return;
 
            // The state we extract has been processed already
            // So it is the future we have to backtrack from.
            auto [p, pair] = queue_.top();
            (void)p;
 
            queue_.pop();
            queueHandles_.erase(pair);
 
            stepUpdateQ(pair.first, pair.second);
        }
    }
 
    template <IsModel M>
    void PrioritizedSweeping<M>::setN(const unsigned n) {
        N = n;
    }
 
    template <IsModel M>
    unsigned PrioritizedSweeping<M>::getN() const {
        return N;
    }
 
    template <IsModel M>
    void PrioritizedSweeping<M>::setQueueThreshold(const double t) {
        if ( t < 0.0 ) throw std::invalid_argument("Theta parameter must be >= 0");
        theta_ = t;
    }
 
    template <IsModel M>
    double PrioritizedSweeping<M>::getQueueThreshold() const {
        return theta_;
    }
 
    template <IsModel M>
    size_t PrioritizedSweeping<M>::getQueueLength() const {
        return queue_.size();
    }
 
    template <IsModel M>
    const M & PrioritizedSweeping<M>::getModel() const {
        return model_;
    }
 
    template <IsModel M>
    const QFunction & PrioritizedSweeping<M>::getQFunction() const {
        return qfun_;
    }
 
    template <IsModel M>
    void PrioritizedSweeping<M>::setQFunction(const QFunction & qfun) {
        qfun_ = qfun;
    }
 
    template <IsModel M>
    const ValueFunction & PrioritizedSweeping<M>::getValueFunction() const {
        return vfun_;
    }
}
 
#endif