EST.cpp
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2011, 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: Ryan Luna */
36 
37 #include "ompl/control/planners/est/EST.h"
38 #include "ompl/base/goals/GoalSampleableRegion.h"
39 #include "ompl/tools/config/SelfConfig.h"
40 #include <limits>
41 #include <cassert>
42 
43 ompl::control::EST::EST(const SpaceInformationPtr &si) : base::Planner(si, "EST")
44 {
46  goalBias_ = 0.05;
47  maxDistance_ = 0.0;
48  siC_ = si.get();
49  lastGoalMotion_ = NULL;
50 
51  Planner::declareParam<double>("range", this, &EST::setRange, &EST::getRange, "0.:1.:10000.");
52  Planner::declareParam<double>("goal_bias", this, &EST::setGoalBias, &EST::getGoalBias, "0.:.05:1.");
53 }
54 
55 ompl::control::EST::~EST()
56 {
57  freeMemory();
58 }
59 
61 {
62  Planner::setup();
66 
67  tree_.grid.setDimension(projectionEvaluator_->getDimension());
68 }
69 
71 {
72  Planner::clear();
73  sampler_.reset();
74  controlSampler_.reset();
75  freeMemory();
76  tree_.grid.clear();
77  tree_.size = 0;
78  pdf_.clear ();
79  lastGoalMotion_ = NULL;
80 }
81 
83 {
84  for (Grid<MotionInfo>::iterator it = tree_.grid.begin(); it != tree_.grid.end() ; ++it)
85  {
86  for (unsigned int i = 0 ; i < it->second->data.size() ; ++i)
87  {
88  if (it->second->data[i]->state)
89  si_->freeState(it->second->data[i]->state);
90  if (it->second->data[i]->control)
91  siC_->freeControl(it->second->data[i]->control);
92  delete it->second->data[i];
93  }
94  }
95 }
96 
98 {
99  checkValidity();
100  base::Goal *goal = pdef_->getGoal().get();
101  base::GoalSampleableRegion *goal_s = dynamic_cast<base::GoalSampleableRegion*>(goal);
102 
103  // Initializing tree with start state(s)
104  while (const base::State *st = pis_.nextStart())
105  {
106  Motion *motion = new Motion(siC_);
107  si_->copyState(motion->state, st);
108  siC_->nullControl(motion->control);
109  addMotion(motion);
110  }
111 
112  if (tree_.grid.size() == 0)
113  {
114  OMPL_ERROR("%s: There are no valid initial states!", getName().c_str());
116  }
117 
118  // Ensure that we have a state sampler AND a control sampler
119  if (!sampler_)
120  sampler_ = si_->allocValidStateSampler();
121  if (!controlSampler_)
123 
124  OMPL_INFORM("%s: Starting planning with %u states already in datastructure", getName().c_str(), tree_.size);
125 
126  Motion *solution = NULL;
127  Motion *approxsol = NULL;
128  double approxdif = std::numeric_limits<double>::infinity();
129  Motion *rmotion = new Motion(siC_);
130  bool solved = false;
131 
132  while (!ptc)
133  {
134  // Select a state to expand the tree from
135  Motion *existing = selectMotion();
136  assert (existing);
137 
138  // sample a random state (with goal biasing) near the state selected for expansion
139  if (goal_s && rng_.uniform01() < goalBias_ && goal_s->canSample())
140  goal_s->sampleGoal(rmotion->state);
141  else
142  {
143  if (!sampler_->sampleNear(rmotion->state, existing->state, maxDistance_))
144  continue;
145  }
146 
147  // Extend a motion toward the state we just sampled
148  unsigned int duration = controlSampler_->sampleTo(rmotion->control, existing->control,
149  existing->state, rmotion->state);
150 
151  // If the system was propagated for a meaningful amount of time, save into the tree
152  if (duration >= siC_->getMinControlDuration())
153  {
154  // create a motion to the resulting state
155  Motion *motion = new Motion(siC_);
156  si_->copyState(motion->state, rmotion->state);
157  siC_->copyControl(motion->control, rmotion->control);
158  motion->steps = duration;
159  motion->parent = existing;
160 
161  // save the state
162  addMotion(motion);
163 
164  // Check if this state is the goal state, or improves the best solution so far
165  double dist = 0.0;
166  solved = goal->isSatisfied(motion->state, &dist);
167  if (solved)
168  {
169  approxdif = dist;
170  solution = motion;
171  break;
172  }
173  if (dist < approxdif)
174  {
175  approxdif = dist;
176  approxsol = motion;
177  }
178  }
179  }
180 
181  bool approximate = false;
182  if (solution == NULL)
183  {
184  solution = approxsol;
185  approximate = true;
186  }
187 
188  // Constructing the solution path
189  if (solution != NULL)
190  {
191  lastGoalMotion_ = solution;
192 
193  std::vector<Motion*> mpath;
194  while (solution != NULL)
195  {
196  mpath.push_back(solution);
197  solution = solution->parent;
198  }
199 
200  PathControl *path = new PathControl(si_);
201  for (int i = mpath.size() - 1 ; i >= 0 ; --i)
202  if (mpath[i]->parent)
203  path->append(mpath[i]->state, mpath[i]->control, mpath[i]->steps * siC_->getPropagationStepSize());
204  else
205  path->append(mpath[i]->state);
206  solved = true;
207  pdef_->addSolutionPath(base::PathPtr(path), approximate, approxdif, getName());
208  }
209 
210  // Cleaning up memory
211  if (rmotion->state)
212  si_->freeState(rmotion->state);
213  if (rmotion->control)
214  siC_->freeControl(rmotion->control);
215  delete rmotion;
216 
217  OMPL_INFORM("%s: Created %u states in %u cells", getName().c_str(), tree_.size, tree_.grid.size());
218 
219  return base::PlannerStatus(solved, approximate);
220 }
221 
223 {
224  GridCell* cell = pdf_.sample(rng_.uniform01());
225  return cell && !cell->data.empty() ? cell->data[rng_.uniformInt(0, cell->data.size() - 1)] : NULL;
226 }
227 
229 {
231  projectionEvaluator_->computeCoordinates(motion->state, coord);
232  GridCell* cell = tree_.grid.getCell(coord);
233  if (cell)
234  {
235  cell->data.push_back(motion);
236  pdf_.update(cell->data.elem_, 1.0/cell->data.size());
237  }
238  else
239  {
240  cell = tree_.grid.createCell(coord);
241  cell->data.push_back(motion);
242  tree_.grid.add(cell);
243  cell->data.elem_ = pdf_.add(cell, 1.0);
244  }
245  tree_.size++;
246 }
247 
249 {
250  Planner::getPlannerData(data);
251 
252  std::vector<MotionInfo> motions;
253  tree_.grid.getContent(motions);
254 
255  double stepSize = siC_->getPropagationStepSize();
256 
257  if (lastGoalMotion_)
259 
260  for (unsigned int i = 0 ; i < motions.size() ; ++i)
261  for (unsigned int j = 0 ; j < motions[i].size() ; ++j)
262  {
263  if (motions[i][j]->parent)
264  {
265  if (data.hasControls())
266  data.addEdge (base::PlannerDataVertex (motions[i][j]->parent->state),
267  base::PlannerDataVertex (motions[i][j]->state),
268  PlannerDataEdgeControl(motions[i][j]->control, motions[i][j]->steps * stepSize));
269  else
270  data.addEdge (base::PlannerDataVertex (motions[i][j]->parent->state),
271  base::PlannerDataVertex (motions[i][j]->state));
272  }
273  else
274  data.addStartVertex (base::PlannerDataVertex (motions[i][j]->state));
275  }
276 }
bool approximateSolutions
Flag indicating whether the planner is able to compute approximate solutions.
Definition: Planner.h:214
Object containing planner generated vertex and edge data. It is assumed that all vertices are unique...
Definition: PlannerData.h:164
unsigned int getMinControlDuration() const
Get the minimum number of steps a control is propagated for.
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: EST.cpp:97
void addMotion(Motion *motion)
Add a motion to the exploration tree.
Definition: EST.cpp:228
base::ProjectionEvaluatorPtr projectionEvaluator_
This algorithm uses a discretization (a grid) to guide the exploration. The exploration is imposed on...
Definition: EST.h:252
Control * control
The control contained by the motion.
Definition: EST.h:172
void append(const base::State *state)
Append state to the end of the path; it is assumed state is the first state, so no control is applied...
DirectedControlSamplerPtr controlSampler_
Directed control sampler.
Definition: EST.h:243
Motion * selectMotion()
Select a motion to continue the expansion of the tree from.
Definition: EST.cpp:222
std::vector< int > Coord
Definition of a coordinate within this grid.
Definition: Grid.h:56
virtual bool hasControls() const
Indicate whether any information about controls (ompl::control::Control) is stored in this instance...
void clear()
Clears the PDF.
Definition: PDF.h:241
unsigned int addGoalVertex(const PlannerDataVertex &v)
Adds the given vertex to the graph data, and marks it as a start vertex. The vertex index is returned...
Abstract definition of goals.
Definition: Goal.h:63
CellPDF pdf_
The PDF used for selecting a cell from which to sample a motion.
Definition: EST.h:264
Encapsulate a termination condition for a motion planner. Planners will call operator() to decide whe...
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: EST.cpp:248
Motion * lastGoalMotion_
The most recent goal motion. Used for PlannerData computation.
Definition: EST.h:267
_T data
The data we store in the cell.
Definition: Grid.h:62
Representation of an edge in PlannerData for planning with controls. This structure encodes a specifi...
Definition: PlannerData.h:60
base::ValidStateSamplerPtr sampler_
Valid state sampler.
Definition: EST.h:240
double goalBias_
The fraction of time the goal is picked as the state to expand towards (if such a state is available)...
Definition: EST.h:255
void freeControl(Control *control) const
Free the memory of a control.
TreeData tree_
The exploration tree constructed by this algorithm.
Definition: EST.h:249
Definition of a control path.
Definition: PathControl.h:60
virtual void setup()
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Definition: EST.cpp:60
ProblemDefinitionPtr pdef_
The user set problem definition.
Definition: Planner.h:400
double uniform01()
Generate a random real between 0 and 1.
Definition: RandomNumbers.h:62
Base class for a vertex in the PlannerData structure. All derived classes must implement the clone an...
Definition: PlannerData.h:60
DirectedControlSamplerPtr allocDirectedControlSampler() const
Allocate an instance of the DirectedControlSampler to use. This will be the default (SimpleDirectedCo...
Invalid start state or no start state specified.
Definition: PlannerStatus.h:56
double getPropagationStepSize() const
Propagation is performed at integer multiples of a specified step size. This function returns the val...
Abstract definition of a goal region that can be sampled.
unsigned int steps
The number of steps the control is applied for.
Definition: EST.h:175
virtual void clear()
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Definition: EST.cpp:70
#define OMPL_ERROR(fmt,...)
Log a formatted error string.
Definition: Console.h:64
Motion * parent
The parent motion in the exploration tree.
Definition: EST.h:178
unsigned int size
The total number of motions in the grid.
Definition: EST.h:227
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...
bool canSample() const
Return true if maxSampleCount() > 0, since in this case samples can certainly be produced.
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:50
Representation of a motion.
Definition: EST.h:151
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:100
PlannerInputStates pis_
Utility class to extract valid input states.
Definition: Planner.h:403
A boost shared pointer wrapper for ompl::control::SpaceInformation.
PlannerSpecs specs_
The specifications of the planner (its capabilities)
Definition: Planner.h:409
const State * nextStart()
Return the next valid start state or NULL if no more valid start states are available.
Definition: Planner.cpp:230
Definition of a cell in this grid.
Definition: Grid.h:59
void update(Element *elem, const double w)
Updates the data in the given Element with a new weight value.
Definition: PDF.h:155
RNG rng_
The random number generator.
Definition: EST.h:261
void configureProjectionEvaluator(base::ProjectionEvaluatorPtr &proj)
If proj is undefined, it is set to the default projection reported by base::StateSpace::getDefaultPro...
Definition: SelfConfig.cpp:238
void setRange(double distance)
Set the range the planner is supposed to use.
Definition: EST.h:110
Element * add(const _T &d, const double w)
Adds a piece of data with a given weight to the PDF. Returns a corresponding Element, which can be used to subsequently update or remove the data from the PDF.
Definition: PDF.h:97
double getGoalBias() const
Get the goal bias the planner is using.
Definition: EST.h:100
base::State * state
The state contained by the motion.
Definition: EST.h:169
void freeMemory()
Free the memory allocated by this planner.
Definition: EST.cpp:82
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: EST.h:94
void configurePlannerRange(double &range)
Compute what a good length for motion segments is.
Definition: SelfConfig.cpp:232
This class contains methods that automatically configure various parameters for motion planning...
Definition: SelfConfig.h:58
void nullControl(Control *control) const
Make the control have no effect if it were to be applied to a state for any amount of time...
double getRange() const
Get the range the planner is using.
Definition: EST.h:116
double maxDistance_
The maximum length of a motion to be added to a tree.
Definition: EST.h:258
SpaceInformationPtr si_
The space information for which planning is done.
Definition: Planner.h:397
int uniformInt(int lower_bound, int upper_bound)
Generate a random integer within given bounds: [lower_bound, upper_bound].
Definition: RandomNumbers.h:75
virtual bool isSatisfied(const State *st) const =0
Return true if the state satisfies the goal constraints.
virtual void sampleGoal(State *st) const =0
Sample a state in the goal region.
_T & sample(double r) const
Returns a piece of data from the PDF according to the input sampling value, which must be between 0 a...
Definition: PDF.h:132
const std::string & getName() const
Get the name of the planner.
Definition: Planner.cpp:55
const SpaceInformation * siC_
The base::SpaceInformation cast as control::SpaceInformation, for convenience.
Definition: EST.h:246
Grid< MotionInfo > grid
A grid where each cell contains an array of motions.
Definition: EST.h:224
A boost shared pointer wrapper for ompl::base::Path.
void copyControl(Control *destination, const Control *source) const
Copy a control to another.
CoordHash::const_iterator iterator
We only allow const iterators.
Definition: Grid.h:374
EST(const SpaceInformationPtr &si)
Constructor.
Definition: EST.cpp:43
#define OMPL_INFORM(fmt,...)
Log a formatted information string.
Definition: Console.h:68