ProjEST.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/ProjEST.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::ProjEST::ProjEST(const base::SpaceInformationPtr &si) : base::Planner(si, "ProjEST")
44 {
46  specs_.directed = true;
47  goalBias_ = 0.05;
48  maxDistance_ = 0.0;
49  lastGoalMotion_ = nullptr;
50 
51  Planner::declareParam<double>("range", this, &ProjEST::setRange, &ProjEST::getRange, "0.:1.:10000.");
52  Planner::declareParam<double>("goal_bias", this, &ProjEST::setGoalBias, &ProjEST::getGoalBias, "0.:.05:1.");
53 }
54 
55 ompl::geometric::ProjEST::~ProjEST()
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  freeMemory();
75  tree_.grid.clear();
76  tree_.size = 0;
77  pdf_.clear();
78  lastGoalMotion_ = nullptr;
79 }
80 
82 {
83  for (const auto &it : tree_.grid)
84  {
85  for (auto &motion : it.second->data.motions_)
86  {
87  if (motion->state)
88  si_->freeState(motion->state);
89  delete motion;
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  auto *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 planning with %u states already in datastructure", getName().c_str(), tree_.size);
117 
118  Motion *solution = nullptr;
119  Motion *approxsol = nullptr;
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 if (!sampler_->sampleNear(xstate, existing->state, maxDistance_))
133  continue;
134 
135  if (si_->checkMotion(existing->state, xstate))
136  {
137  /* create a motion */
138  auto *motion = new Motion(si_);
139  si_->copyState(motion->state, xstate);
140  motion->parent = existing;
141 
142  addMotion(motion);
143  double dist = 0.0;
144  bool solved = goal->isSatisfied(motion->state, &dist);
145  if (solved)
146  {
147  approxdif = dist;
148  solution = motion;
149  break;
150  }
151  if (dist < approxdif)
152  {
153  approxdif = dist;
154  approxsol = motion;
155  }
156  }
157  }
158 
159  bool solved = false;
160  bool approximate = false;
161  if (solution == nullptr)
162  {
163  solution = approxsol;
164  approximate = true;
165  }
166 
167  if (solution != nullptr)
168  {
169  lastGoalMotion_ = solution;
170 
171  /* construct the solution path */
172  std::vector<Motion *> mpath;
173  while (solution != nullptr)
174  {
175  mpath.push_back(solution);
176  solution = solution->parent;
177  }
178 
179  /* set the solution path */
180  auto path(std::make_shared<PathGeometric>(si_));
181  for (int i = mpath.size() - 1; i >= 0; --i)
182  path->append(mpath[i]->state);
183  pdef_->addSolutionPath(path, approximate, approxdif, getName());
184  solved = true;
185  }
186 
187  si_->freeState(xstate);
188 
189  OMPL_INFORM("%s: Created %u states in %u cells", getName().c_str(), tree_.size, tree_.grid.size());
190 
191  return base::PlannerStatus(solved, approximate);
192 }
193 
195 {
196  GridCell *cell = pdf_.sample(rng_.uniform01());
197  return cell && !cell->data.empty() ? cell->data[rng_.uniformInt(0, cell->data.size() - 1)] : nullptr;
198 }
199 
201 {
203  projectionEvaluator_->computeCoordinates(motion->state, coord);
204  GridCell *cell = tree_.grid.getCell(coord);
205  if (cell)
206  {
207  cell->data.push_back(motion);
208  pdf_.update(cell->data.elem_, 1.0 / cell->data.size());
209  }
210  else
211  {
212  cell = tree_.grid.createCell(coord);
213  cell->data.push_back(motion);
214  tree_.grid.add(cell);
215  cell->data.elem_ = pdf_.add(cell, 1.0);
216  }
217  tree_.size++;
218 }
219 
221 {
222  Planner::getPlannerData(data);
223 
224  std::vector<MotionInfo> motionInfo;
225  tree_.grid.getContent(motionInfo);
226 
227  if (lastGoalMotion_)
229 
230  for (auto &m : motionInfo)
231  for (auto &motion : m.motions_)
232  {
233  if (motion->parent == nullptr)
234  data.addStartVertex(base::PlannerDataVertex(motion->state));
235  else
236  data.addEdge(base::PlannerDataVertex(motion->parent->state), base::PlannerDataVertex(motion->state));
237  }
238 }
Grid< MotionInfo > grid
A grid where each cell contains an array of motions.
Definition: ProjEST.h:208
bool approximateSolutions
Flag indicating whether the planner is able to compute approximate solutions.
Definition: Planner.h:212
ProjEST(const base::SpaceInformationPtr &si)
Constructor.
Definition: ProjEST.cpp:43
Object containing planner generated vertex and edge data. It is assumed that all vertices are unique...
Definition: PlannerData.h:174
unsigned int size
The total number of motions in the grid.
Definition: ProjEST.h:211
double getGoalBias() const
Get the goal bias the planner is using.
Definition: ProjEST.h:97
RNG rng_
The random number generator.
Definition: ProjEST.h:241
void clear()
Clears the PDF.
Definition: PDF.h:242
Motion * parent
The parent motion in the exploration tree.
Definition: ProjEST.h:162
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:62
Motion * selectMotion()
Select a motion to continue the expansion of the tree from.
Definition: ProjEST.cpp:194
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: ProjEST.cpp:94
Encapsulate a termination condition for a motion planner. Planners will call operator() to decide whe...
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: ProjEST.h:91
void clear() override
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Definition: ProjEST.cpp:70
_T data
The data we store in the cell.
Definition: Grid.h:60
double getRange() const
Get the range the planner is using.
Definition: ProjEST.h:113
ProblemDefinitionPtr pdef_
The user set problem definition.
Definition: Planner.h:418
bool directed
Flag indicating whether the planner is able to account for the fact that the validity of a motion fro...
Definition: Planner.h:222
virtual void sampleGoal(State *st) const =0
Sample a state in the goal region.
std::vector< int > Coord
Definition of a coordinate within this grid.
Definition: Grid.h:54
base::State * state
The state contained by the motion.
Definition: ProjEST.h:159
void setRange(double distance)
Set the range the planner is supposed to use.
Definition: ProjEST.h:107
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
Invalid start state or no start state specified.
Definition: PlannerStatus.h:56
base::ProjectionEvaluatorPtr projectionEvaluator_
This algorithm uses a discretization (a grid) to guide the exploration. The exploration is imposed on...
Definition: ProjEST.h:231
Abstract definition of a goal region that can be sampled.
void addMotion(Motion *motion)
Add a motion to the exploration tree.
Definition: ProjEST.cpp:200
#define OMPL_ERROR(fmt,...)
Log a formatted error string.
Definition: Console.h:64
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: ProjEST.cpp:220
bool canSample() const
Return true if maxSampleCount() > 0, since in this case samples can certainly be produced.
void setup() override
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Definition: ProjEST.cpp:60
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
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
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
Definition of a cell in this grid.
Definition: Grid.h:57
The definition of a motion.
Definition: ProjEST.h:144
CellPDF pdf_
The PDF used for selecting a cell from which to sample a motion.
Definition: ProjEST.h:244
void update(Element *elem, const double w)
Updates the data in the given Element with a new weight value.
Definition: PDF.h:155
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
_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
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
const std::string & getName() const
Get the name of the planner.
Definition: Planner.cpp:56
double maxDistance_
The maximum length of a motion to be added to a tree.
Definition: ProjEST.h:238
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
SpaceInformationPtr si_
The space information for which planning is done.
Definition: Planner.h:415
double goalBias_
The fraction of time the goal is picked as the state to expand towards (if such a state is available)...
Definition: ProjEST.h:235
void freeMemory()
Free the memory allocated by this planner.
Definition: ProjEST.cpp:81
Motion * lastGoalMotion_
The most recent goal motion. Used for PlannerData computation.
Definition: ProjEST.h:247
int uniformInt(int lower_bound, int upper_bound)
Generate a random integer within given bounds: [lower_bound, upper_bound].
Definition: RandomNumbers.h:81
base::ValidStateSamplerPtr sampler_
Valid state sampler.
Definition: ProjEST.h:224
TreeData tree_
The exploration tree constructed by this algorithm.
Definition: ProjEST.h:227
#define OMPL_INFORM(fmt,...)
Log a formatted information string.
Definition: Console.h:68