All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
EST.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: Ioan Sucan */
36 
37 #include "ompl/geometric/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::geometric::EST::EST(const base::SpaceInformationPtr &si) : base::Planner(si, "EST")
44 {
46  specs_.directed = true;
47  goalBias_ = 0.05;
48  maxDistance_ = 0.0;
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::geometric::EST::~EST(void)
56 {
57  freeMemory();
58 }
59 
61 {
62  Planner::setup();
63  tools::SelfConfig sc(si_, getName());
64  sc.configureProjectionEvaluator(projectionEvaluator_);
65  sc.configurePlannerRange(maxDistance_);
66 
67  tree_.grid.setDimension(projectionEvaluator_->getDimension());
68 }
69 
71 {
72  Planner::clear();
73  sampler_.reset();
74  freeMemory();
75  tree_.grid.clear();
76  tree_.size = 0;
77  pdf_.clear();
78  lastGoalMotion_ = NULL;
79 }
80 
82 {
83  for (Grid<MotionInfo>::iterator it = tree_.grid.begin(); it != tree_.grid.end() ; ++it)
84  {
85  for (unsigned int i = 0 ; i < it->second->data.size() ; ++i)
86  {
87  if (it->second->data[i]->state)
88  si_->freeState(it->second->data[i]->state);
89  delete it->second->data[i];
90  }
91  }
92 }
93 
95 {
96  checkValidity();
97  base::Goal *goal = pdef_->getGoal().get();
98  base::GoalSampleableRegion *goal_s = dynamic_cast<base::GoalSampleableRegion*>(goal);
99 
100  while (const base::State *st = pis_.nextStart())
101  {
102  Motion *motion = new Motion(si_);
103  si_->copyState(motion->state, st);
104  addMotion(motion);
105  }
106 
107  if (tree_.grid.size() == 0)
108  {
109  OMPL_ERROR("%s: There are no valid initial states!", getName().c_str());
111  }
112 
113  if (!sampler_)
114  sampler_ = si_->allocValidStateSampler();
115 
116  OMPL_INFORM("%s: Starting with %u states", getName().c_str(), tree_.size);
117 
118  Motion *solution = NULL;
119  Motion *approxsol = NULL;
120  double approxdif = std::numeric_limits<double>::infinity();
121  base::State *xstate = si_->allocState();
122 
123  while (ptc == false)
124  {
125  /* Decide on a state to expand from */
126  Motion *existing = selectMotion();
127  assert(existing);
128 
129  /* sample random state (with goal biasing) */
130  if (goal_s && rng_.uniform01() < goalBias_ && goal_s->canSample())
131  goal_s->sampleGoal(xstate);
132  else
133  if (!sampler_->sampleNear(xstate, existing->state, maxDistance_))
134  continue;
135 
136  if (si_->checkMotion(existing->state, xstate))
137  {
138  /* create a motion */
139  Motion *motion = new Motion(si_);
140  si_->copyState(motion->state, xstate);
141  motion->parent = existing;
142 
143  addMotion(motion);
144  double dist = 0.0;
145  bool solved = goal->isSatisfied(motion->state, &dist);
146  if (solved)
147  {
148  approxdif = dist;
149  solution = motion;
150  break;
151  }
152  if (dist < approxdif)
153  {
154  approxdif = dist;
155  approxsol = motion;
156  }
157  }
158  }
159 
160  bool solved = false;
161  bool approximate = false;
162  if (solution == NULL)
163  {
164  solution = approxsol;
165  approximate = true;
166  }
167 
168  if (solution != NULL)
169  {
170  lastGoalMotion_ = solution;
171 
172  /* construct the solution path */
173  std::vector<Motion*> mpath;
174  while (solution != NULL)
175  {
176  mpath.push_back(solution);
177  solution = solution->parent;
178  }
179 
180  /* set the solution path */
181  PathGeometric *path = new PathGeometric(si_);
182  for (int i = mpath.size() - 1 ; i >= 0 ; --i)
183  path->append(mpath[i]->state);
184  pdef_->addSolutionPath(base::PathPtr(path), approximate, approxdif);
185  solved = true;
186  }
187 
188  si_->freeState(xstate);
189 
190  OMPL_INFORM("%s: Created %u states in %u cells", getName().c_str(), tree_.size, tree_.grid.size());
191 
192  return base::PlannerStatus(solved, approximate);
193 }
194 
196 {
197  GridCell* cell = pdf_.sample(rng_.uniform01());
198  return cell && !cell->data.empty() ? cell->data[rng_.uniformInt(0, cell->data.size() - 1)] : NULL;
199 }
200 
202 {
204  projectionEvaluator_->computeCoordinates(motion->state, coord);
205  GridCell* cell = tree_.grid.getCell(coord);
206  if (cell)
207  {
208  cell->data.push_back(motion);
209  pdf_.update(cell->data.elem_, 1.0/cell->data.size());
210  }
211  else
212  {
213  cell = tree_.grid.createCell(coord);
214  cell->data.push_back(motion);
215  tree_.grid.add(cell);
216  cell->data.elem_ = pdf_.add(cell, 1.0);
217  }
218  tree_.size++;
219 }
220 
222 {
223  Planner::getPlannerData(data);
224 
225  std::vector<MotionInfo> motions;
226  tree_.grid.getContent(motions);
227 
228  if (lastGoalMotion_)
229  data.addGoalVertex(base::PlannerDataVertex(lastGoalMotion_->state));
230 
231  for (unsigned int i = 0 ; i < motions.size() ; ++i)
232  for (unsigned int j = 0 ; j < motions[i].size() ; ++j)
233  {
234  if (motions[i][j]->parent == NULL)
235  data.addStartVertex(base::PlannerDataVertex(motions[i][j]->state));
236  else
237  data.addEdge(base::PlannerDataVertex(motions[i][j]->parent->state),
238  base::PlannerDataVertex(motions[i][j]->state));
239  }
240 }
bool approximateSolutions
Flag indicating whether the planner is able to compute approximate solutions.
Definition: Planner.h:212
bool canSample(void) const
Return true if maxSampleCount() > 0, since in this case samples can certainly be produced.
Object containing planner generated vertex and edge data. It is assumed that all vertices are unique...
Definition: PlannerData.h:164
Motion * lastGoalMotion_
The most recent goal motion. Used for PlannerData computation.
Definition: EST.h:252
std::vector< int > Coord
Definition of a coordinate within this grid.
Definition: Grid.h:56
double maxDistance_
The maximum length of a motion to be added to a tree.
Definition: EST.h:243
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
Encapsulate a termination condition for a motion planner. Planners will call operator() to decide whe...
_T data
The data we store in the cell.
Definition: Grid.h:62
void append(const base::State *state)
Append state to the end of this path. The memory for state is copied.
base::State * state
The state contained by the motion.
Definition: EST.h:165
bool directed
Flag indicating whether the planner is able to account for the fact that the validity of a motion fro...
Definition: Planner.h:220
virtual void sampleGoal(State *st) const =0
Sample a state in the goal region.
The definition of a motion.
Definition: EST.h:147
Base class for a vertex in the PlannerData structure. All derived classes must implement the clone an...
Definition: PlannerData.h:60
virtual void clear(void)
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Definition: EST.cpp:70
Invalid start state or no start state specified.
Definition: PlannerStatus.h:56
Abstract definition of a goal region that can be sampled.
double getRange(void) const
Get the range the planner is using.
Definition: EST.h:115
#define OMPL_ERROR(fmt,...)
Log a formatted error string.
Definition: Console.h:64
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:221
double getGoalBias(void) const
Get the goal bias the planner is using.
Definition: EST.h:99
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...
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:94
void freeMemory(void)
Free the memory allocated by this planner.
Definition: EST.cpp:81
A boost 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:50
virtual bool isSatisfied(const State *st) const =0
Return true if the state satisfies the goal constraints.
void setRange(double distance)
Set the range the planner is supposed to use.
Definition: EST.h:109
PlannerSpecs specs_
The specifications of the planner (its capabilities)
Definition: Planner.h:404
Definition of a cell in this grid.
Definition: Grid.h:59
void configureProjectionEvaluator(base::ProjectionEvaluatorPtr &proj)
If proj is undefined, it is set to the default projection reported by base::StateSpace::getDefaultPro...
Definition: SelfConfig.cpp:232
virtual void setup(void)
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Definition: EST.cpp:60
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:93
void configurePlannerRange(double &range)
Compute what a good length for motion segments is.
Definition: SelfConfig.cpp:226
This class contains methods that automatically configure various parameters for motion planning...
Definition: SelfConfig.h:56
EST(const base::SpaceInformationPtr &si)
Constructor.
Definition: EST.cpp:43
Motion * parent
The parent motion in the exploration tree.
Definition: EST.h:168
void addMotion(Motion *motion)
Add a motion to the exploration tree.
Definition: EST.cpp:201
Motion * selectMotion(void)
Select a motion to continue the expansion of the tree from.
Definition: EST.cpp:195
Definition of a geometric path.
Definition: PathGeometric.h:55
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:240
A boost shared pointer wrapper for ompl::base::Path.
CoordHash::const_iterator iterator
We only allow const iterators.
Definition: Grid.h:374
#define OMPL_INFORM(fmt,...)
Log a formatted information string.
Definition: Console.h:68