PDST.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 the 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: Jonathan Sobieski, Mark Moll */
36 
37 
38 #ifndef OMPL_CONTROL_PLANNERS_PDST_PDST_
39 #define OMPL_CONTROL_PLANNERS_PDST_PDST_
40 
41 #include "ompl/base/Planner.h"
42 #include "ompl/base/goals/GoalSampleableRegion.h"
43 #include "ompl/control/PathControl.h"
44 #include "ompl/control/PlannerData.h"
45 #include "ompl/datastructures/BinaryHeap.h"
46 
47 
48 namespace ompl
49 {
50 
51  namespace control
52  {
53 
81  class PDST : public base::Planner
83  {
84  public:
85 
86  PDST(const SpaceInformationPtr &si);
87 
88  virtual ~PDST();
89 
90  virtual base::PlannerStatus solve(const base::PlannerTerminationCondition &ptc);
91  virtual void clear();
92  virtual void setup();
93 
95  virtual void getPlannerData(base::PlannerData &data) const;
96 
98  void setProjectionEvaluator(const base::ProjectionEvaluatorPtr &projectionEvaluator)
99  {
100  projectionEvaluator_ = projectionEvaluator;
101  }
102 
104  void setProjectionEvaluator(const std::string &name)
105  {
106  projectionEvaluator_ = si_->getStateSpace()->getProjection(name);
107  }
108 
111  {
112  return projectionEvaluator_;
113  }
114 
122  void setGoalBias(double goalBias)
123  {
124  goalBias_ = goalBias;
125  }
127  double getGoalBias() const
128  {
129  return goalBias_;
130  }
131 
132  protected:
133  struct Cell;
134  struct Motion;
135 
138  {
140  bool operator() (Motion *p1, Motion *p2) const
141  {
142  // lowest priority means highest score
143  return p1->score() < p2->score();
144  }
145  };
146 
148  struct Motion
149  {
150  public:
151  Motion(base::State *startState, base::State *endState, Control *control,
152  unsigned int controlDuration, double priority, Motion *parent)
153  : startState_(startState), endState_(endState), control_(control),
154  controlDuration_(controlDuration), priority_(priority), parent_(parent),
155  cell_(NULL), heapElement_(NULL), isSplit_(false)
156  {
157  }
160  : startState_(state), endState_(state), control_(NULL), controlDuration_(0),
161  priority_(0.), parent_(NULL), cell_(NULL), heapElement_(NULL), isSplit_(false)
162  {
163  }
165  double score() const
166  {
167  return priority_ / cell_->volume_;
168  }
169  void updatePriority()
170  {
171  priority_ = priority_ * 2. + 1.;
172  }
173 
181  unsigned int controlDuration_;
183  double priority_;
192  bool isSplit_;
193  };
194 
196  struct Cell
197  {
198  Cell(double volume, const base::RealVectorBounds &bounds,
199  unsigned int splitDimension = 0)
200  : volume_(volume), splitDimension_(splitDimension), splitValue_(0.0),
201  left_(NULL), right_(NULL), bounds_(bounds)
202  {
203  }
204 
205  ~Cell()
206  {
207  if (left_)
208  {
209  delete left_;
210  delete right_;
211  }
212  }
213 
215  void subdivide(unsigned int spaceDimension);
216 
218  Cell* stab(const base::EuclideanProjection& projection) const
219  {
220  Cell *containingCell = const_cast<Cell*>(this);
221  while (containingCell->left_ != NULL)
222  {
223  if (projection[containingCell->splitDimension_] <= containingCell->splitValue_)
224  containingCell = containingCell->left_;
225  else
226  containingCell = containingCell->right_;
227  }
228  return containingCell;
229  }
231  void addMotion(Motion *motion)
232  {
233  motions_.push_back(motion);
234  motion->cell_ = this;
235  }
236 
238  unsigned int size() const
239  {
240  unsigned int sz = 1;
241  if (left_)
242  sz += left_->size() + right_->size();
243  return sz;
244  }
245 
247  double volume_;
249  unsigned int splitDimension_;
251  double splitValue_;
259  std::vector<Motion*> motions_;
260  };
261 
262 
265  void addMotion(Motion *motion, Cell *cell,
268  void updateHeapElement(Motion *motion)
269  {
270  if (motion->heapElement_)
272  else
273  motion->heapElement_ = priorityQueue_.insert(motion);
274  }
285  unsigned int findDurationAndAncestor(Motion *motion, base::State *state,
286  base::State *scratch, Motion*& ancestor) const;
287 
288  void freeMemory();
289 
296  // Random number generator
297  RNG rng_;
300  std::vector<Motion*> startMotions_;
308  double goalBias_;
312  unsigned int iteration_;
315  };
316  }
317 }
318 
319 #endif
base::RealVectorBounds bounds_
A bounding box for this cell.
Definition: PDST.h:257
unsigned int controlDuration_
The duration that the control was applied to arrive at this state from the parent.
Definition: PDST.h:181
base::StateSamplerPtr sampler_
State sampler.
Definition: PDST.h:291
virtual void setup()
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Definition: PDST.cpp:318
unsigned int size() const
Number of cells.
Definition: PDST.h:238
Motion * propagateFrom(Motion *motion, base::State *, base::State *)
Select a state along motion and propagate a new motion from there. Return NULL if no valid motion cou...
Definition: PDST.cpp:174
unsigned int iteration_
Iteration number and priority of the next Motion that will be generated.
Definition: PDST.h:312
double priority_
Priority for selecting this path to extend from in the future.
Definition: PDST.h:183
void setProjectionEvaluator(const base::ProjectionEvaluatorPtr &projectionEvaluator)
Set the projection evaluator. This class is able to compute the projection of a given state...
Definition: PDST.h:98
Cell * bsp_
Binary Space Partition.
Definition: PDST.h:304
DirectedControlSamplerPtr controlSampler_
Directed control sampler.
Definition: PDST.h:293
Definition of an abstract control.
Definition: Control.h:48
const SpaceInformation * siC_
SpaceInformation convenience pointer.
Definition: PDST.h:295
virtual void getPlannerData(base::PlannerData &data) const
Extracts the planner data from the priority queue into data.
Definition: PDST.cpp:333
A boost shared pointer wrapper for ompl::base::StateSampler.
void setProjectionEvaluator(const std::string &name)
Set the projection evaluator (select one from the ones registered with the state space).
Definition: PDST.h:104
Class representing the tree of motions exploring the state space.
Definition: PDST.h:148
base::State * startState_
The starting point of this motion.
Definition: PDST.h:175
double splitValue_
The midpoint between the bounds_ at the splitDimension_.
Definition: PDST.h:251
Cell * stab(const base::EuclideanProjection &projection) const
Locates the cell that this motion begins in.
Definition: PDST.h:218
base::GoalSampleableRegion * goalSampler_
Objected used to sample the goal.
Definition: PDST.h:310
double getGoalBias() const
Get the goal bias the planner is using */.
Definition: PDST.h:127
Motion(base::State *state)
constructor for start states
Definition: PDST.h:159
void update(Element *element)
Update an element in the heap.
Definition: BinaryHeap.h:181
Motion * lastGoalMotion_
Closest motion to the goal.
Definition: PDST.h:314
This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome...
Definition: BinaryHeap.h:53
Abstract definition of a goal region that can be sampled.
Main namespace. Contains everything in this library.
Definition: Cost.h:42
BinaryHeap< Motion *, MotionCompare >::Element * heapElement_
Handle to the element of the priority queue for this Motion.
Definition: PDST.h:189
Cell * right_
The right child cell (NULL for a leaf cell)
Definition: PDST.h:255
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
Definition: RandomNumbers.h:54
double volume_
Volume of the cell.
Definition: PDST.h:247
BinaryHeap< Motion *, MotionCompare > priorityQueue_
Priority queue of motions.
Definition: PDST.h:302
A boost shared pointer wrapper for ompl::control::DirectedControlSampler.
Cell * cell_
Pointer to the cell that contains this path.
Definition: PDST.h:187
virtual void clear()
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Definition: PDST.cpp:284
void updateHeapElement(Motion *motion)
Either update heap after motion&#39;s priority has changed or insert motion into heap.
Definition: PDST.h:268
const base::ProjectionEvaluatorPtr & getProjectionEvaluator() const
Get the projection evaluator.
Definition: PDST.h:110
void addMotion(Motion *motion, Cell *cell, base::State *, base::State *, base::EuclideanProjection &, base::EuclideanProjection &)
Inserts the motion into the appropriate cells, splitting the motion as necessary. motion is assumed t...
Definition: PDST.cpp:203
A boost shared pointer wrapper for ompl::base::ProjectionEvaluator.
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 addMotion(Motion *motion)
Add a motion.
Definition: PDST.h:231
bool operator()(Motion *p1, Motion *p2) const
returns true if m1 is lower priority than m2
Definition: PDST.h:140
control::Control * control_
The control that was applied to arrive at this state from the parent.
Definition: PDST.h:179
std::vector< Motion * > motions_
The motions contained in this cell. Motions are stored only in leaf nodes.
Definition: PDST.h:259
Cell is a Binary Space Partition.
Definition: PDST.h:196
The lower and upper bounds for an Rn space.
unsigned int findDurationAndAncestor(Motion *motion, base::State *state, base::State *scratch, Motion *&ancestor) const
Find the max. duration that the control_ in motion can be applied s.t. the trajectory passes through ...
Definition: PDST.cpp:244
std::vector< Motion * > startMotions_
Vector holding all of the start states supplied for the problem Each start motion is the root of its ...
Definition: PDST.h:300
Comparator used to order motions in the priority queue.
Definition: PDST.h:137
base::ProjectionEvaluatorPtr projectionEvaluator_
Projection evaluator for the problem.
Definition: PDST.h:306
SpaceInformationPtr si_
The space information for which planning is done.
Definition: Planner.h:397
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: PDST.cpp:52
Cell * left_
The left child cell (NULL for a leaf cell)
Definition: PDST.h:253
Space information containing necessary information for planning with controls. setup() needs to be ca...
unsigned int splitDimension_
Dimension along which the cell is split into smaller cells.
Definition: PDST.h:249
Element * insert(const _T &data)
Add a new element.
Definition: BinaryHeap.h:135
Motion * parent_
Parent motion from which this one started.
Definition: PDST.h:185
double score() const
The score is used to order motions in a priority queue.
Definition: PDST.h:165
double goalBias_
Number between 0 and 1 specifying the probability with which the goal should be sampled.
Definition: PDST.h:308
base::State * endState_
The state reached by this motion.
Definition: PDST.h:177
*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: PDST.h:122