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>
 
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 magic
 
    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:
            using AtlasChartBiasFunction = std::function<double(AtlasChart *)>;
            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_;
        };
    }  // namespace base
}  // namespace ompl
 
#endif