Program Listing for File PRM.h
↰ Return to documentation for file (src/ompl/geometric/planners/prm/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 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()};
};
}
}
#endif