EST.cpp
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2015, 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/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_ = nullptr;
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()
56 {
57  freeMemory();
58 }
59 
61 {
62  Planner::setup();
65 
66  // Make the neighborhood radius smaller than sampling range to keep probabilities relatively high for rejection
67  // sampling
69 
70  if (!nn_)
71  nn_.reset(tools::SelfConfig::getDefaultNearestNeighbors<Motion *>(this));
72  nn_->setDistanceFunction([this](const Motion *a, const Motion *b)
73  {
74  return distanceFunction(a, b);
75  });
76 }
77 
79 {
80  Planner::clear();
81  sampler_.reset();
82  freeMemory();
83  if (nn_)
84  nn_->clear();
85 
86  motions_.clear();
87  pdf_.clear();
88  lastGoalMotion_ = nullptr;
89 }
90 
92 {
93  for (auto &motion : motions_)
94  {
95  if (motion->state)
96  si_->freeState(motion->state);
97  delete motion;
98  }
99 }
100 
102 {
103  checkValidity();
104  base::Goal *goal = pdef_->getGoal().get();
105  base::GoalSampleableRegion *goal_s = dynamic_cast<base::GoalSampleableRegion *>(goal);
106 
107  std::vector<Motion *> neighbors;
108 
109  while (const base::State *st = pis_.nextStart())
110  {
111  auto *motion = new Motion(si_);
112  si_->copyState(motion->state, st);
113 
114  nn_->nearestR(motion, nbrhoodRadius_, neighbors);
115  addMotion(motion, neighbors);
116  }
117 
118  if (motions_.size() == 0)
119  {
120  OMPL_ERROR("%s: There are no valid initial states!", getName().c_str());
122  }
123 
124  if (!sampler_)
125  sampler_ = si_->allocValidStateSampler();
126 
127  OMPL_INFORM("%s: Starting planning with %u states already in datastructure", getName().c_str(), motions_.size());
128 
129  Motion *solution = nullptr;
130  Motion *approxsol = nullptr;
131  double approxdif = std::numeric_limits<double>::infinity();
132  base::State *xstate = si_->allocState();
133  auto *xmotion = new Motion();
134 
135  while (ptc == false)
136  {
137  // Select a state to expand from
138  Motion *existing = pdf_.sample(rng_.uniform01());
139  assert(existing);
140 
141  // Sample random state in the neighborhood (with goal biasing)
142  if (goal_s && rng_.uniform01() < goalBias_ && goal_s->canSample())
143  {
144  goal_s->sampleGoal(xstate);
145 
146  // Compute neighborhood of candidate motion
147  xmotion->state = xstate;
148  nn_->nearestR(xmotion, nbrhoodRadius_, neighbors);
149  }
150  else
151  {
152  // Sample a state in the neighborhood
153  if (!sampler_->sampleNear(xstate, existing->state, maxDistance_))
154  continue;
155 
156  // Compute neighborhood of candidate state
157  xmotion->state = xstate;
158  nn_->nearestR(xmotion, nbrhoodRadius_, neighbors);
159 
160  // reject state with probability proportional to neighborhood density
161  if (neighbors.size())
162  {
163  double p = 1.0 - (1.0 / neighbors.size());
164  if (rng_.uniform01() < p)
165  continue;
166  }
167  }
168 
169  // Is motion good?
170  if (si_->checkMotion(existing->state, xstate))
171  {
172  // create a motion
173  auto *motion = new Motion(si_);
174  si_->copyState(motion->state, xstate);
175  motion->parent = existing;
176 
177  // add it to everything
178  addMotion(motion, neighbors);
179 
180  // done?
181  double dist = 0.0;
182  bool solved = goal->isSatisfied(motion->state, &dist);
183  if (solved)
184  {
185  approxdif = dist;
186  solution = motion;
187  break;
188  }
189  if (dist < approxdif)
190  {
191  approxdif = dist;
192  approxsol = motion;
193  }
194  }
195  }
196 
197  bool solved = false;
198  bool approximate = false;
199  if (solution == nullptr)
200  {
201  solution = approxsol;
202  approximate = true;
203  }
204 
205  if (solution != nullptr)
206  {
207  lastGoalMotion_ = solution;
208 
209  // construct the solution path
210  std::vector<Motion *> mpath;
211  while (solution != nullptr)
212  {
213  mpath.push_back(solution);
214  solution = solution->parent;
215  }
216 
217  // set the solution path
218  auto path(std::make_shared<PathGeometric>(si_));
219  for (int i = mpath.size() - 1; i >= 0; --i)
220  path->append(mpath[i]->state);
221  pdef_->addSolutionPath(path, approximate, approxdif, getName());
222  solved = true;
223  }
224 
225  si_->freeState(xstate);
226  delete xmotion;
227 
228  OMPL_INFORM("%s: Created %u states", getName().c_str(), motions_.size());
229 
230  return base::PlannerStatus(solved, approximate);
231 }
232 
233 void ompl::geometric::EST::addMotion(Motion *motion, const std::vector<Motion *> &neighbors)
234 {
235  // Updating neighborhood size counts
236  for (auto neighbor : neighbors)
237  {
238  PDF<Motion *>::Element *elem = neighbor->element;
239  double w = pdf_.getWeight(elem);
240  pdf_.update(elem, w / (w + 1.));
241  }
242 
243  // now add new motion to the data structures
244  motion->element = pdf_.add(motion, 1. / (neighbors.size() + 1.)); // +1 for self
245  motions_.push_back(motion);
246  nn_->add(motion);
247 }
248 
250 {
251  Planner::getPlannerData(data);
252 
253  if (lastGoalMotion_)
255 
256  for (auto motion : motions_)
257  {
258  if (motion->parent == nullptr)
259  data.addStartVertex(base::PlannerDataVertex(motion->state));
260  else
261  data.addEdge(base::PlannerDataVertex(motion->parent->state), base::PlannerDataVertex(motion->state));
262  }
263 }
bool approximateSolutions
Flag indicating whether the planner is able to compute approximate solutions.
Definition: Planner.h:212
RNG rng_
The random number generator.
Definition: EST.h:176
Object containing planner generated vertex and edge data. It is assumed that all vertices are unique...
Definition: PlannerData.h:174
PDF< Motion * >::Element * element
A pointer to the corresponding element in the probability distribution function.
Definition: EST.h:138
Motion * lastGoalMotion_
The most recent goal motion. Used for PlannerData computation.
Definition: EST.h:179
double getGoalBias() const
Get the goal bias the planner is using.
Definition: EST.h:90
double maxDistance_
The maximum length of a motion to be added to a tree.
Definition: EST.h:170
void setup() override
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Definition: EST.cpp:60
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
base::ValidStateSamplerPtr sampler_
Valid state sampler.
Definition: EST.h:163
std::vector< Motion * > motions_
The set of all states in the tree.
Definition: EST.h:151
Encapsulate a termination condition for a motion planner. Planners will call operator() to decide whe...
double nbrhoodRadius_
The radius considered for neighborhood.
Definition: EST.h:173
PDF< Motion * > pdf_
The probability distribution function over states in the tree.
Definition: EST.h:154
ProblemDefinitionPtr pdef_
The user set problem definition.
Definition: Planner.h:418
base::State * state
The state contained by the motion.
Definition: EST.h:132
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.
The definition of a motion.
Definition: EST.h:117
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
Abstract definition of a goal region that can be sampled.
void clear() override
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Definition: EST.cpp:78
double distanceFunction(const Motion *a, const Motion *b) const
Compute distance between motions (actually distance between contained states)
Definition: EST.h:142
#define OMPL_ERROR(fmt,...)
Log a formatted error string.
Definition: Console.h:64
bool canSample() const
Return true if maxSampleCount() > 0, since in this case samples can certainly be produced.
double getRange() const
Get the range the planner is using.
Definition: EST.h:106
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.
void setRange(double distance)
Set the range the planner is supposed to use.
Definition: EST.h:100
PlannerInputStates pis_
Utility class to extract valid input states.
Definition: Planner.h:421
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: EST.cpp:101
A class that will hold data contained in the PDF.
Definition: PDF.h:52
void addMotion(Motion *motion, const std::vector< Motion *> &neighbors)
Add a motion to the exploration tree.
Definition: EST.cpp:233
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
void freeMemory()
Free the memory allocated by this planner.
Definition: EST.cpp:91
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: EST.cpp:249
const std::string & getName() const
Get the name of the planner.
Definition: Planner.cpp:56
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:84
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
EST(const base::SpaceInformationPtr &si)
Constructor.
Definition: EST.cpp:43
SpaceInformationPtr si_
The space information for which planning is done.
Definition: Planner.h:415
std::shared_ptr< NearestNeighbors< Motion * > > nn_
A nearest-neighbors datastructure containing the tree of motions.
Definition: EST.h:148
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:167
#define OMPL_INFORM(fmt,...)
Log a formatted information string.
Definition: Console.h:68