STRIDE.cpp
1 /*********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2008, Willow Garage, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above
14  * copyright notice, this list of conditions and the following
15  * disclaimer in the documentation and/or other materials provided
16  * with the distribution.
17  * * Neither the name of the Willow Garage nor the names of its
18  * contributors may be used to endorse or promote products derived
19  * from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *********************************************************************/
34 
35 /* Author: Bryant Gipson, Mark Moll, Ioan Sucan */
36 
37 #include "ompl/geometric/planners/stride/STRIDE.h"
38 // enable sampling from the GNAT data structure
39 #define GNAT_SAMPLER
40 #include "ompl/datastructures/NearestNeighborsGNAT.h"
41 #include "ompl/base/goals/GoalSampleableRegion.h"
42 #include "ompl/tools/config/SelfConfig.h"
43 #include <limits>
44 #include <cassert>
45 
46 ompl::geometric::STRIDE::STRIDE(const base::SpaceInformationPtr &si, bool useProjectedDistance, unsigned int degree,
47  unsigned int minDegree, unsigned int maxDegree, unsigned int maxNumPtsPerLeaf,
48  double estimatedDimension)
49  : base::Planner(si, "STRIDE")
50  , goalBias_(0.05)
51  , maxDistance_(0.)
52  , useProjectedDistance_(useProjectedDistance)
53  , degree_(degree)
54  , minDegree_(minDegree)
55  , maxDegree_(maxDegree)
56  , maxNumPtsPerLeaf_(maxNumPtsPerLeaf)
57  , estimatedDimension_(estimatedDimension)
58  , minValidPathFraction_(0.2)
59 {
61 
62  if (estimatedDimension_ < 1.)
63  estimatedDimension_ = si->getStateDimension();
64 
65  Planner::declareParam<double>("range", this, &STRIDE::setRange, &STRIDE::getRange, "0.:1.:10000.");
66  Planner::declareParam<double>("goal_bias", this, &STRIDE::setGoalBias, &STRIDE::getGoalBias, "0.:.05:1.");
67  Planner::declareParam<bool>("use_projected_distance", this, &STRIDE::setUseProjectedDistance,
69  Planner::declareParam<unsigned int>("degree", this, &STRIDE::setDegree, &STRIDE::getDegree, "2:20");
70  Planner::declareParam<unsigned int>("max_degree", this, &STRIDE::setMaxDegree, &STRIDE::getMaxDegree, "2:20");
71  Planner::declareParam<unsigned int>("min_degree", this, &STRIDE::setMinDegree, &STRIDE::getMinDegree, "2:20");
72  Planner::declareParam<unsigned int>("max_pts_per_leaf", this, &STRIDE::setMaxNumPtsPerLeaf,
73  &STRIDE::getMaxNumPtsPerLeaf, "1:200");
74  Planner::declareParam<double>("estimated_dimension", this, &STRIDE::setEstimatedDimension,
76  Planner::declareParam<double>("min_valid_path_fraction", this, &STRIDE::setMinValidPathFraction,
77  &STRIDE::getMinValidPathFraction, "0.:.05:1.");
78 }
79 
80 ompl::geometric::STRIDE::~STRIDE()
81 {
82  freeMemory();
83 }
84 
86 {
87  Planner::setup();
91  setupTree();
92 }
93 
95 {
96  tree_.reset(
99  tree_->setDistanceFunction([this](const Motion *a, const Motion *b)
100  {
101  return projectedDistanceFunction(a, b);
102  });
103  else
104  tree_->setDistanceFunction([this](const Motion *a, const Motion *b)
105  {
106  return distanceFunction(a, b);
107  });
108 }
109 
111 {
112  Planner::clear();
113  sampler_.reset();
114  freeMemory();
115  setupTree();
116 }
117 
119 {
120  if (tree_)
121  {
122  std::vector<Motion *> motions;
123  tree_->list(motions);
124  for (auto &motion : motions)
125  {
126  if (motion->state)
127  si_->freeState(motion->state);
128  delete motion;
129  }
130  tree_.reset();
131  }
132 }
133 
135 {
136  checkValidity();
137  base::Goal *goal = pdef_->getGoal().get();
138  base::GoalSampleableRegion *goal_s = dynamic_cast<base::GoalSampleableRegion *>(goal);
139 
140  while (const base::State *st = pis_.nextStart())
141  {
142  auto *motion = new Motion(si_);
143  si_->copyState(motion->state, st);
144  addMotion(motion);
145  }
146 
147  if (tree_->size() == 0)
148  {
149  OMPL_ERROR("%s: There are no valid initial states!", getName().c_str());
151  }
152 
153  if (!sampler_)
154  sampler_ = si_->allocValidStateSampler();
155 
156  OMPL_INFORM("%s: Starting planning with %u states already in datastructure", getName().c_str(), tree_->size());
157 
158  Motion *solution = nullptr;
159  Motion *approxsol = nullptr;
160  double approxdif = std::numeric_limits<double>::infinity();
161  base::State *xstate = si_->allocState();
162 
163  while (ptc == false)
164  {
165  /* Decide on a state to expand from */
166  Motion *existing = selectMotion();
167  assert(existing);
168 
169  /* sample random state (with goal biasing) */
170  if (goal_s && rng_.uniform01() < goalBias_ && goal_s->canSample())
171  goal_s->sampleGoal(xstate);
172  else if (!sampler_->sampleNear(xstate, existing->state, maxDistance_))
173  continue;
174 
175  std::pair<base::State *, double> fail(xstate, 0.0);
176  bool keep = si_->checkMotion(existing->state, xstate, fail) || fail.second > minValidPathFraction_;
177 
178  if (keep)
179  {
180  /* create a motion */
181  auto *motion = new Motion(si_);
182  si_->copyState(motion->state, xstate);
183  motion->parent = existing;
184 
185  addMotion(motion);
186  double dist = 0.0;
187  bool solved = goal->isSatisfied(motion->state, &dist);
188  if (solved)
189  {
190  approxdif = dist;
191  solution = motion;
192  break;
193  }
194  if (dist < approxdif)
195  {
196  approxdif = dist;
197  approxsol = motion;
198  }
199  }
200  }
201 
202  bool solved = false;
203  bool approximate = false;
204  if (solution == nullptr)
205  {
206  solution = approxsol;
207  approximate = true;
208  }
209 
210  if (solution != nullptr)
211  {
212  /* construct the solution path */
213  std::vector<Motion *> mpath;
214  while (solution != nullptr)
215  {
216  mpath.push_back(solution);
217  solution = solution->parent;
218  }
219 
220  /* set the solution path */
221  auto path(std::make_shared<PathGeometric>(si_));
222  for (int i = mpath.size() - 1; i >= 0; --i)
223  path->append(mpath[i]->state);
224  pdef_->addSolutionPath(path, approximate, approxdif, getName());
225  solved = true;
226  }
227 
228  si_->freeState(xstate);
229 
230  OMPL_INFORM("%s: Created %u states", getName().c_str(), tree_->size());
231 
232  return base::PlannerStatus(solved, approximate);
233 }
234 
236 {
237  tree_->add(motion);
238 }
239 
241 {
242  return tree_->sample(rng_);
243 }
244 
246 {
247  Planner::getPlannerData(data);
248 
249  std::vector<Motion *> motions;
250  tree_->list(motions);
251  for (auto &motion : motions)
252  {
253  if (motion->parent == nullptr)
254  data.addStartVertex(base::PlannerDataVertex(motion->state, 1));
255  else
256  data.addEdge(base::PlannerDataVertex(motion->parent->state, 1), base::PlannerDataVertex(motion->state, 1));
257  }
258 }
void setupTree()
Initialize GNAT data structure.
Definition: STRIDE.cpp:94
bool approximateSolutions
Flag indicating whether the planner is able to compute approximate solutions.
Definition: Planner.h:212
Object containing planner generated vertex and edge data. It is assumed that all vertices are unique...
Definition: PlannerData.h:174
double getEstimatedDimension() const
Get estimated dimension of the free space, which is needed to compute the sampling weight for a node ...
Definition: STRIDE.h:178
base::ProjectionEvaluatorPtr projectionEvaluator_
This algorithm can optionally use a projection to guide the exploration.
Definition: STRIDE.h:291
void freeMemory()
Free the memory allocated by this planner.
Definition: STRIDE.cpp:118
The definition of a motion.
Definition: STRIDE.h:238
double estimatedDimension_
Estimate of the local dimensionality of the free space around a state.
Definition: STRIDE.h:315
base::PlannerStatus solve(const base::PlannerTerminationCondition &ptc) override
Function that can solve the motion planning problem. This function can be called multiple times on th...
Definition: STRIDE.cpp:134
void setMinDegree(unsigned int minDegree)
Set minimum degree of a node in the GNAT.
Definition: STRIDE.h:137
void setEstimatedDimension(double estimatedDimension)
Set estimated dimension of the free space, which is needed to compute the sampling weight for a node ...
Definition: STRIDE.h:171
Abstract definition of goals.
Definition: Goal.h:62
Encapsulate a termination condition for a motion planner. Planners will call operator() to decide whe...
unsigned int minDegree_
Minimum degree of an internal node in the GNAT.
Definition: STRIDE.h:309
void setup() override
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Definition: STRIDE.cpp:85
Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search...
bool useProjectedDistance_
Whether to use distance in the projection (instead of distance in the state space) for the GNAT...
Definition: STRIDE.h:305
ProblemDefinitionPtr pdef_
The user set problem definition.
Definition: Planner.h:418
unsigned int maxDegree_
Maximum degree of an internal node in the GNAT.
Definition: STRIDE.h:311
virtual void sampleGoal(State *st) const =0
Sample a state in the goal region.
double projectedDistanceFunction(const Motion *a, const Motion *b) const
Compute distance between motions (actually distance between projections of contained states) ...
Definition: STRIDE.h:272
base::ValidStateSamplerPtr sampler_
Valid state sampler.
Definition: STRIDE.h:288
double uniform01()
Generate a random real between 0 and 1.
Definition: RandomNumbers.h:68
Base class for a vertex in the PlannerData structure. All derived classes must implement the clone an...
Definition: PlannerData.h:58
double getMinValidPathFraction() const
Get the value of the fraction set by setMinValidPathFraction()
Definition: STRIDE.h:210
Invalid start state or no start state specified.
Definition: PlannerStatus.h:56
Abstract definition of a goal region that can be sampled.
double getRange() const
Get the range the planner is using.
Definition: STRIDE.h:194
double minValidPathFraction_
When extending a motion, the planner can decide to keep the first valid part of it, even if invalid states are found, as long as the valid part represents a sufficiently large fraction from the original motion. This is used only when extendWhileValid_ is true.
Definition: STRIDE.h:321
unsigned int getMaxDegree() const
Set maximum degree of a node in the GNAT.
Definition: STRIDE.h:152
void setDegree(unsigned int degree)
Set desired degree of a node in the GNAT.
Definition: STRIDE.h:127
void setMaxNumPtsPerLeaf(unsigned int maxNumPtsPerLeaf)
Set maximum number of elements stored in a leaf node of the GNAT.
Definition: STRIDE.h:158
double distanceFunction(const Motion *a, const Motion *b) const
Compute distance between motions (actually distance between contained states)
Definition: STRIDE.h:266
#define OMPL_ERROR(fmt,...)
Log a formatted error string.
Definition: Console.h:64
double maxDistance_
The maximum length of a motion to be added to a tree.
Definition: STRIDE.h:301
bool getUseProjectedDistance() const
Return whether nearest neighbors are computed based on distances in a projection of the state rather ...
Definition: STRIDE.h:121
bool canSample() const
Return true if maxSampleCount() > 0, since in this case samples can certainly be produced.
void clear() override
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Definition: STRIDE.cpp:110
A class to store the exit status of Planner::solve()
Definition: PlannerStatus.h:48
virtual bool addEdge(unsigned int v1, unsigned int v2, const PlannerDataEdge &edge=PlannerDataEdge(), Cost weight=Cost(1.0))
Adds a directed edge between the given vertex indexes. An optional edge structure and weight can be s...
A shared pointer wrapper for ompl::base::SpaceInformation.
unsigned int addStartVertex(const PlannerDataVertex &v)
Adds the given vertex to the graph data, and marks it as a start vertex. The vertex index is returned...
Definition of an abstract state.
Definition: State.h:49
void setRange(double distance)
Set the range the planner is supposed to use.
Definition: STRIDE.h:188
virtual void checkValidity()
Check to see if the planner is in a working state (setup has been called, a goal was set...
Definition: Planner.cpp:101
virtual bool isSatisfied(const State *st) const =0
Return true if the state satisfies the goal constraints.
PlannerInputStates pis_
Utility class to extract valid input states.
Definition: Planner.h:421
unsigned int degree_
Desired degree of an internal node in the GNAT.
Definition: STRIDE.h:307
PlannerSpecs specs_
The specifications of the planner (its capabilities)
Definition: Planner.h:427
const State * nextStart()
Return the next valid start state or nullptr if no more valid start states are available.
Definition: Planner.cpp:230
STRIDE(const base::SpaceInformationPtr &si, bool useProjectedDistance=false, unsigned int degree=16, unsigned int minDegree=12, unsigned int maxDegree=18, unsigned int maxNumPtsPerLeaf=6, double estimatedDimension=0.0)
Constructor.
Definition: STRIDE.cpp:46
void configureProjectionEvaluator(base::ProjectionEvaluatorPtr &proj)
If proj is undefined, it is set to the default projection reported by base::StateSpace::getDefaultPro...
Definition: SelfConfig.cpp:231
const std::string & getName() const
Get the name of the planner.
Definition: Planner.cpp:56
Motion * selectMotion()
Select a motion to continue the expansion of the tree from.
Definition: STRIDE.cpp:240
void configurePlannerRange(double &range)
Compute what a good length for motion segments is.
Definition: SelfConfig.cpp:225
This class contains methods that automatically configure various parameters for motion planning...
Definition: SelfConfig.h:59
unsigned int getDegree() const
Get desired degree of a node in the GNAT.
Definition: STRIDE.h:132
double getGoalBias() const
Get the goal bias the planner is using.
Definition: STRIDE.h:106
double goalBias_
The fraction of time the goal is picked as the state to expand towards (if such a state is available)...
Definition: STRIDE.h:298
void getPlannerData(base::PlannerData &data) const override
Get information about the current run of the motion planner. Repeated calls to this function will upd...
Definition: STRIDE.cpp:245
SpaceInformationPtr si_
The space information for which planning is done.
Definition: Planner.h:415
void setMinValidPathFraction(double fraction)
When extending a motion, the planner can decide to keep the first valid part of it, even if invalid states are found, as long as the valid part represents a sufficiently large fraction from the original motion. This function sets the minimum acceptable fraction (between 0 and 1).
Definition: STRIDE.h:204
base::State * state
The state contained by the motion.
Definition: STRIDE.h:253
unsigned int getMinDegree() const
Get minimum degree of a node in the GNAT.
Definition: STRIDE.h:142
unsigned int maxNumPtsPerLeaf_
Maximum number of points stored in a leaf node in the GNAT.
Definition: STRIDE.h:313
unsigned int getMaxNumPtsPerLeaf() const
Get maximum number of elements stored in a leaf node of the GNAT.
Definition: STRIDE.h:164
void setUseProjectedDistance(bool useProjectedDistance)
Set whether nearest neighbors are computed based on distances in a projection of the state rather dis...
Definition: STRIDE.h:114
void setMaxDegree(unsigned int maxDegree)
Set maximum degree of a node in the GNAT.
Definition: STRIDE.h:147
void setGoalBias(double goalBias)
In the process of randomly selecting states in the state space to attempt to go towards, the algorithm may in fact choose the actual goal state, if it knows it, with some probability. This probability is a real number between 0.0 and 1.0; its value should usually be around 0.05 and should not be too large. It is probably a good idea to use the default value.
Definition: STRIDE.h:100
void addMotion(Motion *motion)
Add a motion to the exploration tree.
Definition: STRIDE.cpp:235
#define OMPL_INFORM(fmt,...)
Log a formatted information string.
Definition: Console.h:68
boost::scoped_ptr< NearestNeighborsGNAT< Motion * > > tree_
The exploration tree constructed by this algorithm.
Definition: STRIDE.h:294
RNG rng_
The random number generator.
Definition: STRIDE.h:324