PRM.h

/*********************************************************************
 * Software License Agreement (BSD License)
 *
 *  Copyright (c) 2011, 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: Ioan Sucan, James D. Marble, Ryan Luna, Henning Kayser */
 
#ifndef OMPL_GEOMETRIC_PLANNERS_PRM_PRM_
#define OMPL_GEOMETRIC_PLANNERS_PRM_PRM_
 
#include "ompl/geometric/planners/PlannerIncludes.h"
#include "ompl/datastructures/NearestNeighbors.h"
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <mutex>
#include <utility>
#include <vector>
#include <map>
 
namespace ompl
{
    namespace base
    {
        // Forward declare for use in implementation
        OMPL_CLASS_FORWARD(OptimizationObjective);
    }  // namespace base
 
    namespace geometric
    {

        class PRM : public base::Planner
        {
        public:
            struct vertex_state_t
            {
                using kind = boost::vertex_property_tag;
            };
 
            struct vertex_total_connection_attempts_t
            {
                using kind = boost::vertex_property_tag;
            };
 
            struct vertex_successful_connection_attempts_t
            {
                using kind = boost::vertex_property_tag;
            };

            using Graph = boost::adjacency_list<
                boost::vecS, boost::vecS, boost::undirectedS,
                boost::property<
                    vertex_state_t, base::State *,
                    boost::property<
                        vertex_total_connection_attempts_t, unsigned long int,
                        boost::property<vertex_successful_connection_attempts_t, unsigned long int,
                                        boost::property<boost::vertex_predecessor_t, unsigned long int,
                                                        boost::property<boost::vertex_rank_t, unsigned long int>>>>>,
                boost::property<boost::edge_weight_t, base::Cost>>;

            using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
            using Edge = boost::graph_traits<Graph>::edge_descriptor;

            using RoadmapNeighbors = std::shared_ptr<NearestNeighbors<Vertex>>;

            using ConnectionStrategy = std::function<const std::vector<Vertex> &(const Vertex)>;

            using ConnectionFilter = std::function<bool(const Vertex &, const Vertex &)>;

            PRM(const base::SpaceInformationPtr &si, bool starStrategy = false);

            PRM(const base::PlannerData &data, bool starStrategy = false);
 
            ~PRM() override;
 
            void setProblemDefinition(const base::ProblemDefinitionPtr &pdef) override;

            void setConnectionStrategy(const ConnectionStrategy &connectionStrategy)
            {
                connectionStrategy_ = connectionStrategy;
                userSetConnectionStrategy_ = true;
            }

            void setDefaultConnectionStrategy();

            void setMaxNearestNeighbors(unsigned int k);

            unsigned int getMaxNearestNeighbors() const;

            void setConnectionFilter(const ConnectionFilter &connectionFilter)
            {
                connectionFilter_ = connectionFilter;
            }
 
            void getPlannerData(base::PlannerData &data) const override;

            void constructRoadmap(const base::PlannerTerminationCondition &ptc);

            void growRoadmap(double growTime);

            void growRoadmap(const base::PlannerTerminationCondition &ptc);

            void expandRoadmap(double expandTime);

            void expandRoadmap(const base::PlannerTerminationCondition &ptc);

            base::PlannerStatus solve(const base::PlannerTerminationCondition &ptc) override;

            void clearQuery() override;
 
            void clear() override;

            template <template <typename T> class NN>
            void setNearestNeighbors()
            {
                if (nn_ && nn_->size() == 0)
                    OMPL_WARN("Calling setNearestNeighbors will clear all states.");
                clear();
                nn_ = std::make_shared<NN<Vertex>>();
                if (!userSetConnectionStrategy_)
                    setDefaultConnectionStrategy();
                if (isSetup())
                    setup();
            }
 
            void setup() override;
 
            const Graph &getRoadmap() const
            {
                return g_;
            }

            unsigned long int milestoneCount() const
            {
                return boost::num_vertices(g_);
            }

            unsigned long int edgeCount() const
            {
                return boost::num_edges(g_);
            }
 
            const RoadmapNeighbors &getNearestNeighbors()
            {
                return nn_;
            }
 
        protected:
            void freeMemory();

            Vertex addMilestone(base::State *state);

            void uniteComponents(Vertex m1, Vertex m2);

            bool sameComponent(Vertex m1, Vertex m2);

            void growRoadmap(const base::PlannerTerminationCondition &ptc, base::State *workState);

            void expandRoadmap(const base::PlannerTerminationCondition &ptc, std::vector<base::State *> &workStates);

            void checkForSolution(const base::PlannerTerminationCondition &ptc, base::PathPtr &solution);

            bool maybeConstructSolution(const std::vector<Vertex> &starts, const std::vector<Vertex> &goals,
                                        base::PathPtr &solution);

            ompl::base::Cost constructApproximateSolution(const std::vector<Vertex> &starts,
                                                          const std::vector<Vertex> &goals, base::PathPtr &solution);

            bool addedNewSolution() const;

            base::PathPtr constructSolution(const Vertex &start, const Vertex &goal);

            base::Cost costHeuristic(Vertex u, Vertex v) const;

            double distanceFunction(const Vertex a, const Vertex b) const
            {
                return si_->distance(stateProperty_[a], stateProperty_[b]);
            }

            // Planner progress property functions
            std::string getIterationCount() const
            {
                return std::to_string(iterations_);
            }
            std::string getBestCost() const
            {
                return std::to_string(bestCost_.value());
            }
            std::string getMilestoneCountString() const
            {
                return std::to_string(milestoneCount());
            }
            std::string getEdgeCountString() const
            {
                return std::to_string(edgeCount());
            }

            bool starStrategy_;

            base::ValidStateSamplerPtr sampler_;

            base::StateSamplerPtr simpleSampler_;

            RoadmapNeighbors nn_;

            Graph g_;

            std::vector<Vertex> startM_;

            std::vector<Vertex> goalM_;

            boost::property_map<Graph, vertex_state_t>::type stateProperty_;

            boost::property_map<Graph, vertex_total_connection_attempts_t>::type totalConnectionAttemptsProperty_;

            boost::property_map<Graph, vertex_successful_connection_attempts_t>::type
                successfulConnectionAttemptsProperty_;

            boost::property_map<Graph, boost::edge_weight_t>::type weightProperty_;

            boost::disjoint_sets<boost::property_map<Graph, boost::vertex_rank_t>::type,
                                 boost::property_map<Graph, boost::vertex_predecessor_t>::type>
                disjointSets_;

            ConnectionStrategy connectionStrategy_;

            ConnectionFilter connectionFilter_;

            bool userSetConnectionStrategy_{false};

            RNG rng_;

            bool addedNewSolution_{false};

            mutable std::mutex graphMutex_;

            base::OptimizationObjectivePtr opt_;

            // Planner progress properties
            unsigned long int iterations_{0};
            base::Cost bestCost_{std::numeric_limits<double>::quiet_NaN()};
        };
    }  // namespace geometric
}  // namespace ompl
 
#endif