STRIDE.h
1 /*********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2013, Rice University
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 Rice University 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 */
36 
37 #ifndef OMPL_GEOMETRIC_PLANNERS_STRIDE_STRIDE_
38 #define OMPL_GEOMETRIC_PLANNERS_STRIDE_STRIDE_
39 
40 #include "ompl/datastructures/Grid.h"
41 #include "ompl/geometric/planners/PlannerIncludes.h"
42 #include "ompl/base/ProjectionEvaluator.h"
43 #include "ompl/datastructures/PDF.h"
44 #include <boost/unordered_map.hpp>
45 #include <boost/scoped_ptr.hpp>
46 #include <vector>
47 
48 namespace ompl
49 {
50 
51  template<typename _T>
52  class NearestNeighborsGNAT;
53 
54  namespace geometric
55  {
56 
80  class STRIDE : public base::Planner
81  {
82  public:
83 
85  STRIDE(const base::SpaceInformationPtr &si, bool useProjectedDistance = false,
86  unsigned int degree = 16, unsigned int minDegree = 12, unsigned int maxDegree = 18,
87  unsigned int maxNumPtsPerLeaf = 6, double estimatedDimension = 0.0);
88  virtual ~STRIDE();
89 
90  virtual void setup();
91 
93 
94  virtual void clear();
95 
103  void setGoalBias(double goalBias)
104  {
105  goalBias_ = goalBias;
106  }
107 
109  double getGoalBias() const
110  {
111  return goalBias_;
112  }
113 
117  void setUseProjectedDistance(bool useProjectedDistance)
118  {
119  useProjectedDistance_ = useProjectedDistance;
120  }
125  {
126  return useProjectedDistance_;
127  }
128 
130  void setDegree(unsigned int degree)
131  {
132  degree_ = degree;
133  }
135  unsigned int getDegree() const
136  {
137  return degree_;
138  }
140  void setMinDegree(unsigned int minDegree)
141  {
142  minDegree_ = minDegree;
143  }
145  unsigned int getMinDegree() const
146  {
147  return minDegree_;
148  }
150  void setMaxDegree(unsigned int maxDegree)
151  {
152  maxDegree_ = maxDegree;
153  }
155  unsigned int getMaxDegree() const
156  {
157  return maxDegree_;
158  }
161  void setMaxNumPtsPerLeaf(unsigned int maxNumPtsPerLeaf)
162  {
163  maxNumPtsPerLeaf_ = maxNumPtsPerLeaf;
164  }
167  unsigned int getMaxNumPtsPerLeaf() const
168  {
169  return maxNumPtsPerLeaf_;
170  }
174  void setEstimatedDimension(double estimatedDimension)
175  {
176  estimatedDimension_ = estimatedDimension;
177  }
181  double getEstimatedDimension() const
182  {
183  return estimatedDimension_;
184  }
185 
191  void setRange(double distance)
192  {
193  maxDistance_ = distance;
194  }
195 
197  double getRange() const
198  {
199  return maxDistance_;
200  }
207  void setMinValidPathFraction(double fraction)
208  {
209  minValidPathFraction_ = fraction;
210  }
211 
213  double getMinValidPathFraction() const
214  {
215  return minValidPathFraction_;
216  }
219  void setProjectionEvaluator(const base::ProjectionEvaluatorPtr &projectionEvaluator)
220  {
221  projectionEvaluator_ = projectionEvaluator;
222  }
223 
226  void setProjectionEvaluator(const std::string &name)
227  {
228  projectionEvaluator_ = si_->getStateSpace()->getProjection(name);
229  }
230 
233  {
234  return projectionEvaluator_;
235  }
236 
237  virtual void getPlannerData(base::PlannerData &data) const;
238 
239  protected:
240 
242  class Motion
243  {
244  public:
245  Motion() : state(NULL), parent(NULL)
246  {
247  }
248 
250  Motion(const base::SpaceInformationPtr &si) : state(si->allocState()), parent(NULL)
251  {
252  }
253 
254  ~Motion()
255  {
256  }
257 
260 
263  };
264 
265 
267  void freeMemory();
268 
270  void setupTree();
271 
273  double distanceFunction(const Motion *a, const Motion *b) const
274  {
275  return si_->distance(a->state, b->state);
276  }
277 
279  double projectedDistanceFunction(const Motion *a, const Motion *b) const
280  {
281  unsigned int num_dims = projectionEvaluator_->getDimension();
282  ompl::base::EuclideanProjection aproj(num_dims), bproj(num_dims);
283  projectionEvaluator_->project(a->state, aproj);
284  projectionEvaluator_->project(b->state, bproj);
285  return boost::numeric::ublas::norm_2(aproj - bproj);
286  }
287 
289  void addMotion(Motion *motion);
290 
292  Motion* selectMotion();
293 
296 
299 
301  boost::scoped_ptr<NearestNeighborsGNAT<Motion*> >
303 
305  double goalBias_;
306 
308  double maxDistance_;
309 
313  unsigned int degree_;
315  unsigned int minDegree_;
317  unsigned int maxDegree_;
319  unsigned int maxNumPtsPerLeaf_;
328 
331  };
332 
333  }
334 }
335 
336 #endif
void setupTree()
Initialize GNAT data structure.
Definition: STRIDE.cpp:86
Search Tree with Resolution Independent Density Estimation.
Definition: STRIDE.h:80
bool getUseProjectedDistance() const
Return whether nearest neighbors are computed based on distances in a projection of the state rather ...
Definition: STRIDE.h:124
double getMinValidPathFraction() const
Get the value of the fraction set by setMinValidPathFraction()
Definition: STRIDE.h:213
Object containing planner generated vertex and edge data. It is assumed that all vertices are unique...
Definition: PlannerData.h:164
void setProjectionEvaluator(const std::string &name)
Set the projection evaluator (select one from the ones registered with the state space).
Definition: STRIDE.h:226
unsigned int getMaxNumPtsPerLeaf() const
Get maximum number of elements stored in a leaf node of the GNAT.
Definition: STRIDE.h:167
base::ProjectionEvaluatorPtr projectionEvaluator_
This algorithm can optionally use a projection to guide the exploration.
Definition: STRIDE.h:298
void freeMemory()
Free the memory allocated by this planner.
Definition: STRIDE.cpp:103
A boost shared pointer wrapper for ompl::base::ValidStateSampler.
Motion * parent
The parent motion in the exploration tree.
Definition: STRIDE.h:262
unsigned int getMaxDegree() const
Set maximum degree of a node in the GNAT.
Definition: STRIDE.h:155
double getEstimatedDimension() const
Get estimated dimension of the free space, which is needed to compute the sampling weight for a node ...
Definition: STRIDE.h:181
The definition of a motion.
Definition: STRIDE.h:242
double estimatedDimension_
Estimate of the local dimensionality of the free space around a state.
Definition: STRIDE.h:321
void setMinDegree(unsigned int minDegree)
Set minimum degree of a node in the GNAT.
Definition: STRIDE.h:140
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:174
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:315
bool useProjectedDistance_
Whether to use distance in the projection (instead of distance in the state space) for the GNAT...
Definition: STRIDE.h:311
const base::ProjectionEvaluatorPtr & getProjectionEvaluator() const
Get the projection evaluator.
Definition: STRIDE.h:232
double getRange() const
Get the range the planner is using.
Definition: STRIDE.h:197
unsigned int maxDegree_
Maximum degree of an internal node in the GNAT.
Definition: STRIDE.h:317
base::ValidStateSamplerPtr sampler_
Valid state sampler.
Definition: STRIDE.h:295
Main namespace. Contains everything in this library.
Definition: Cost.h:42
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:327
virtual void setup()
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Definition: STRIDE.cpp:77
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
Definition: RandomNumbers.h:54
Motion(const base::SpaceInformationPtr &si)
Constructor that allocates memory for the state.
Definition: STRIDE.h:250
virtual void clear()
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Definition: STRIDE.cpp:95
void setDegree(unsigned int degree)
Set desired degree of a node in the GNAT.
Definition: STRIDE.h:130
void setMaxNumPtsPerLeaf(unsigned int maxNumPtsPerLeaf)
Set maximum number of elements stored in a leaf node of the GNAT.
Definition: STRIDE.h:161
double maxDistance_
The maximum length of a motion to be added to a tree.
Definition: STRIDE.h:308
Base class for a planner.
Definition: Planner.h:232
boost::scoped_ptr< NearestNeighborsGNAT< Motion * > > tree_
The exploration tree constructed by this algorithm.
Definition: STRIDE.h:302
A boost shared pointer wrapper for ompl::base::ProjectionEvaluator.
A class to store the exit status of Planner::solve()
Definition: PlannerStatus.h:48
A boost shared pointer wrapper for ompl::base::SpaceInformation.
boost::numeric::ublas::vector< double > EuclideanProjection
The datatype for state projections. This class contains a real vector.
Definition of an abstract state.
Definition: State.h:50
void setRange(double distance)
Set the range the planner is supposed to use.
Definition: STRIDE.h:191
unsigned int degree_
Desired degree of an internal node in the GNAT.
Definition: STRIDE.h:313
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
unsigned int getDegree() const
Get desired degree of a node in the GNAT.
Definition: STRIDE.h:135
virtual base::PlannerStatus solve(const base::PlannerTerminationCondition &ptc)
Function that can solve the motion planning problem. This function can be called multiple times on th...
Definition: STRIDE.cpp:119
double projectedDistanceFunction(const Motion *a, const Motion *b) const
Compute distance between motions (actually distance between projections of contained states) ...
Definition: STRIDE.h:279
Motion * selectMotion()
Select a motion to continue the expansion of the tree from.
Definition: STRIDE.cpp:226
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:305
SpaceInformationPtr si_
The space information for which planning is done.
Definition: Planner.h:397
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:207
base::State * state
The state contained by the motion.
Definition: STRIDE.h:259
virtual void getPlannerData(base::PlannerData &data) const
Get information about the current run of the motion planner. Repeated calls to this function will upd...
Definition: STRIDE.cpp:231
unsigned int maxNumPtsPerLeaf_
Maximum number of points stored in a leaf node in the GNAT.
Definition: STRIDE.h:319
unsigned int getMinDegree() const
Get minimum degree of a node in the GNAT.
Definition: STRIDE.h:145
void setUseProjectedDistance(bool useProjectedDistance)
Set whether nearest neighbors are computed based on distances in a projection of the state rather dis...
Definition: STRIDE.h:117
void setMaxDegree(unsigned int maxDegree)
Set maximum degree of a node in the GNAT.
Definition: STRIDE.h:150
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:103
void addMotion(Motion *motion)
Add a motion to the exploration tree.
Definition: STRIDE.cpp:221
double distanceFunction(const Motion *a, const Motion *b) const
Compute distance between motions (actually distance between contained states)
Definition: STRIDE.h:273
double getGoalBias() const
Get the goal bias the planner is using.
Definition: STRIDE.h:109
void setProjectionEvaluator(const base::ProjectionEvaluatorPtr &projectionEvaluator)
Set the projection evaluator. This class is able to compute the projection of a given state...
Definition: STRIDE.h:219
RNG rng_
The random number generator.
Definition: STRIDE.h:330