AtlasStateSpace.h

/*********************************************************************
* Software License Agreement (BSD License)
*
*  Copyright (c) 2014, Rice University
*  All rights reserved.
*
*  Redistribution and use in source and binary forms, with or without
*  modification, are permitted provided that the following conditions
*  are met:
*
*   * Redistributions of source code must retain the above copyright
*     notice, this list of conditions and the following disclaimer.
*   * Redistributions in binary form must reproduce the above
*     copyright notice, this list of conditions and the following
*     disclaimer in the documentation and/or other materials provided
*     with the distribution.
*   * Neither the name of the Rice University nor the names of its
*     contributors may be used to endorse or promote products derived
*     from this software without specific prior written permission.
*
*  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
*  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
*  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
*  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
*  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
*  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
*  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
*  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
*  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
*  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
*  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
*  POSSIBILITY OF SUCH DAMAGE.
*********************************************************************/

/* Author: Zachary Kingston, Caleb Voss */

#ifndef OMPL_BASE_SPACES_ATLAS_STATE_SPACE_
#define OMPL_BASE_SPACES_ATLAS_STATE_SPACE_

#include "ompl/base/StateSampler.h"
#include "ompl/base/ValidStateSampler.h"
#include "ompl/base/Constraint.h"
#include "ompl/datastructures/NearestNeighborsGNAT.h"
#include "ompl/datastructures/PDF.h"

#include "ompl/base/spaces/constraint/ConstrainedStateSpace.h"

#include <boost/math/constants/constants.hpp>
#include <Eigen/Core>

namespace ompl
{
    namespace magic
    {
        static const unsigned int ATLAS_STATE_SPACE_SAMPLES = 50;
        static const double ATLAS_STATE_SPACE_EPSILON = 0.05;
        static const double ATLAS_STATE_SPACE_RHO_MULTIPLIER = 5;
        static const double ATLAS_STATE_SPACE_ALPHA = boost::math::constants::pi<double>() / 8.0;
        static const double ATLAS_STATE_SPACE_EXPLORATION = 0.75;
        static const unsigned int ATLAS_STATE_SPACE_MAX_CHARTS_PER_EXTENSION = 200;
        static const double ATLAS_STATE_SPACE_BACKOFF = 0.75;
    }

    namespace base
    {

        OMPL_CLASS_FORWARD(AtlasChart);


        OMPL_CLASS_FORWARD(AtlasStateSpace);

        class AtlasStateSampler : public StateSampler
        {
        public:
            AtlasStateSampler(const AtlasStateSpace *space);

            void sampleUniform(State *state) override;

            void sampleUniformNear(State *state, const State *near, double distance) override;

            void sampleGaussian(State *state, const State *mean, double stdDev) override;

        private:
            const AtlasStateSpace *atlas_;

            mutable RNG rng_;
        };

        class AtlasStateSpace : public ConstrainedStateSpace
        {
        public:
            typedef std::function<double(AtlasChart *)> AtlasChartBiasFunction;
            using NNElement = std::pair<const StateType *, std::size_t>;

            class StateType : public ConstrainedStateSpace::StateType
            {
            public:
                StateType(const ConstrainedStateSpace *space) : ConstrainedStateSpace::StateType(space)
                {
                }

                AtlasChart *getChart() const
                {
                    return chart_;
                }

                void setChart(AtlasChart *c) const
                {
                    chart_ = c;
                }

            private:
                mutable AtlasChart *chart_{nullptr};
            };

            AtlasStateSpace(const StateSpacePtr &ambientSpace, const ConstraintPtr &constraint, bool separate = true);

            ~AtlasStateSpace() override;

            void clear() override;

            StateSamplerPtr allocDefaultStateSampler() const override
            {
                return std::make_shared<AtlasStateSampler>(this);
            }

            StateSamplerPtr allocStateSampler() const override
            {
                return std::make_shared<AtlasStateSampler>(this);
            }

            void copyState(State *destination, const State *source) const override
            {
                ConstrainedStateSpace::copyState(destination, source);
                destination->as<StateType>()->setChart(source->as<StateType>()->getChart());
            }

            State *allocState() const override
            {
                return new StateType(this);
            }

            void setEpsilon(double epsilon)
            {
                if (epsilon <= 0)
                    throw ompl::Exception("ompl::base::AtlasStateSpace::setEpsilon(): "
                                          "epsilon must be positive.");
                epsilon_ = epsilon;
            }

            void setRho(double rho)
            {
                if (rho <= 0)
                    throw ompl::Exception("ompl::base::AtlasStateSpace::setRho(): "
                                          "rho must be positive.");
                rho_ = rho;
                rho_s_ = rho_ / std::pow(1 - exploration_, 1.0 / k_);
            }

            void setAlpha(double alpha)
            {
                if (alpha <= 0 || alpha >= boost::math::constants::pi<double>() / 2.)
                    throw ompl::Exception("ompl::base::AtlasStateSpace::setAlpha(): "
                                          "alpha must be in (0, pi/2).");
                cos_alpha_ = std::cos(alpha);
            }

            void setExploration(double exploration)
            {
                if (exploration >= 1)
                    throw ompl::Exception("ompl::base::AtlasStateSpace::setExploration(): "
                                          "exploration must be in [0, 1).");
                exploration_ = exploration;

                // Update sampling radius
                setRho(rho_);
            }

            void setMaxChartsPerExtension(unsigned int charts)
            {
                maxChartsPerExtension_ = charts;
            }

            void setBiasFunction(const AtlasChartBiasFunction &biasFunction)
            {
                biasFunction_ = biasFunction;
            }

            void setSeparated(bool separate)
            {
                separate_ = separate;
            }

            void setBackoff(double backoff)
            {
                backoff_ = backoff;
            }

            double getEpsilon() const
            {
                return epsilon_;
            }

            double getRho() const
            {
                return rho_;
            }

            double getAlpha() const
            {
                return std::acos(cos_alpha_);
            }

            double getExploration() const
            {
                return exploration_;
            }

            double getRho_s() const
            {
                return rho_s_;
            }

            unsigned int getMaxChartsPerExtension() const
            {
                return maxChartsPerExtension_;
            }

            bool isSeparated() const
            {
                return separate_;
            }

            std::size_t getChartCount() const
            {
                return charts_.size();
            }

            double getBackoff() const
            {
                return backoff_;
            }

            AtlasChart *newChart(const StateType *state) const;

            AtlasChart *sampleChart() const;

            AtlasChart *owningChart(const StateType *state) const;

            AtlasChart *getChart(const StateType *state, bool force = false, bool *created = nullptr) const;

            AtlasChart *anchorChart(const State *state) const;

            bool discreteGeodesic(const State *from, const State *to, bool interpolate = false,
                                  std::vector<State *> *geodesic = nullptr) const override;

            double estimateFrontierPercent() const;

            void printPLY(std::ostream &out) const;

        protected:
            mutable std::vector<StateType *> anchors_;

            mutable std::vector<AtlasChart *> charts_;

            mutable PDF<AtlasChart *> chartPDF_;

            mutable NearestNeighborsGNAT<NNElement> chartNN_;

            double epsilon_{ompl::magic::ATLAS_STATE_SPACE_EPSILON};

            double rho_;

            double cos_alpha_;

            double exploration_;

            mutable double rho_s_;

            double backoff_{ompl::magic::ATLAS_STATE_SPACE_BACKOFF};

            unsigned int maxChartsPerExtension_{ompl::magic::ATLAS_STATE_SPACE_MAX_CHARTS_PER_EXTENSION};

            AtlasChartBiasFunction biasFunction_;

            bool separate_;

            mutable RNG rng_;
        };
    }
}

#endif