All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
LazyRRT.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/rrt/LazyRRT.h"
38 #include "ompl/base/goals/GoalSampleableRegion.h"
39 #include "ompl/tools/config/SelfConfig.h"
40 #include <cassert>
41 
42 ompl::geometric::LazyRRT::LazyRRT(const base::SpaceInformationPtr &si) : base::Planner(si, "LazyRRT")
43 {
44  specs_.directed = true;
45  goalBias_ = 0.05;
46  maxDistance_ = 0.0;
47  lastGoalMotion_ = NULL;
48 
49  Planner::declareParam<double>("range", this, &LazyRRT::setRange, &LazyRRT::getRange, "0.:1.:10000.");
50  Planner::declareParam<double>("goal_bias", this, &LazyRRT::setGoalBias, &LazyRRT::getGoalBias, "0.:.05:1.");
51 }
52 
53 ompl::geometric::LazyRRT::~LazyRRT(void)
54 {
55  freeMemory();
56 }
57 
59 {
60  Planner::setup();
61  tools::SelfConfig sc(si_, getName());
62  sc.configurePlannerRange(maxDistance_);
63 
64  if (!nn_)
65  nn_.reset(tools::SelfConfig::getDefaultNearestNeighbors<Motion*>(si_->getStateSpace()));
66  nn_->setDistanceFunction(boost::bind(&LazyRRT::distanceFunction, this, _1, _2));
67 }
68 
70 {
71  Planner::clear();
72  sampler_.reset();
73  freeMemory();
74  if (nn_)
75  nn_->clear();
76  lastGoalMotion_ = NULL;
77 }
78 
80 {
81  if (nn_)
82  {
83  std::vector<Motion*> motions;
84  nn_->list(motions);
85  for (unsigned int i = 0 ; i < motions.size() ; ++i)
86  {
87  if (motions[i]->state)
88  si_->freeState(motions[i]->state);
89  delete motions[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  motion->valid = true;
105  nn_->add(motion);
106  }
107 
108  if (nn_->size() == 0)
109  {
110  OMPL_ERROR("%s: There are no valid initial states!", getName().c_str());
112  }
113 
114  if (!sampler_)
115  sampler_ = si_->allocStateSampler();
116 
117  OMPL_INFORM("%s: Starting with %u states", getName().c_str(), nn_->size());
118 
119  Motion *solution = NULL;
120  double distsol = -1.0;
121  Motion *rmotion = new Motion(si_);
122  base::State *rstate = rmotion->state;
123  base::State *xstate = si_->allocState();
124 
125  bool solutionFound = false;
126 
127  while (ptc == false && !solutionFound)
128  {
129  /* sample random state (with goal biasing) */
130  if (goal_s && rng_.uniform01() < goalBias_ && goal_s->canSample())
131  goal_s->sampleGoal(rstate);
132  else
133  sampler_->sampleUniform(rstate);
134 
135  /* find closest state in the tree */
136  Motion *nmotion = nn_->nearest(rmotion);
137  assert(nmotion != rmotion);
138  base::State *dstate = rstate;
139 
140  /* find state to add */
141  double d = si_->distance(nmotion->state, rstate);
142  if (d > maxDistance_)
143  {
144  si_->getStateSpace()->interpolate(nmotion->state, rstate, maxDistance_ / d, xstate);
145  dstate = xstate;
146  }
147 
148  /* create a motion */
149  Motion *motion = new Motion(si_);
150  si_->copyState(motion->state, dstate);
151  motion->parent = nmotion;
152  nmotion->children.push_back(motion);
153  nn_->add(motion);
154 
155  double dist = 0.0;
156  if (goal->isSatisfied(motion->state, &dist))
157  {
158  distsol = dist;
159  solution = motion;
160  solutionFound = true;
161  lastGoalMotion_ = solution;
162 
163  // Check that the solution is valid:
164  // construct the solution path
165  std::vector<Motion*> mpath;
166  while (solution != NULL)
167  {
168  mpath.push_back(solution);
169  solution = solution->parent;
170  }
171 
172  // check each segment along the path for validity
173  for (int i = mpath.size() - 1 ; i >= 0 && solutionFound; --i)
174  if (!mpath[i]->valid)
175  {
176  if (si_->checkMotion(mpath[i]->parent->state, mpath[i]->state))
177  mpath[i]->valid = true;
178  else
179  {
180  removeMotion(mpath[i]);
181  solutionFound = false;
182  lastGoalMotion_ = NULL;
183  }
184  }
185 
186  if (solutionFound)
187  {
188  // set the solution path
189  PathGeometric *path = new PathGeometric(si_);
190  for (int i = mpath.size() - 1 ; i >= 0 ; --i)
191  path->append(mpath[i]->state);
192 
193  pdef_->addSolutionPath(base::PathPtr(path), false, distsol);
194  }
195  }
196  }
197 
198  si_->freeState(xstate);
199  si_->freeState(rstate);
200  delete rmotion;
201 
202  OMPL_INFORM("%s: Created %u states", getName().c_str(), nn_->size());
203 
205 }
206 
208 {
209  nn_->remove(motion);
210 
211  /* remove self from parent list */
212 
213  if (motion->parent)
214  {
215  for (unsigned int i = 0 ; i < motion->parent->children.size() ; ++i)
216  if (motion->parent->children[i] == motion)
217  {
218  motion->parent->children.erase(motion->parent->children.begin() + i);
219  break;
220  }
221  }
222 
223  /* remove children */
224  for (unsigned int i = 0 ; i < motion->children.size() ; ++i)
225  {
226  motion->children[i]->parent = NULL;
227  removeMotion(motion->children[i]);
228  }
229 
230  if (motion->state)
231  si_->freeState(motion->state);
232  delete motion;
233 }
234 
236 {
237  Planner::getPlannerData(data);
238 
239  std::vector<Motion*> motions;
240  if (nn_)
241  nn_->list(motions);
242 
243  if (lastGoalMotion_)
244  data.addGoalVertex(base::PlannerDataVertex(lastGoalMotion_->state, 1));
245 
246  for (unsigned int i = 0 ; i < motions.size() ; ++i)
247  {
248  if (motions[i]->parent == NULL)
249  data.addStartVertex(base::PlannerDataVertex(motions[i]->state));
250  else
251  data.addEdge(base::PlannerDataVertex(motions[i]->parent ? motions[i]->parent->state : NULL),
252  base::PlannerDataVertex(motions[i]->state));
253 
254  data.tagState(motions[i]->state, motions[i]->valid ? 1 : 0);
255  }
256 }
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
The planner failed to find a solution.
Definition: PlannerStatus.h:62
void setGoalBias(double goalBias)
Set the goal biasing.
Definition: LazyRRT.h:102
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: LazyRRT.cpp:94
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
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: LazyRRT.cpp:235
Encapsulate a termination condition for a motion planner. Planners will call operator() to decide whe...
void append(const base::State *state)
Append state to the end of this path. The memory for state is copied.
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.
void freeMemory(void)
Free the memory allocated by this planner.
Definition: LazyRRT.cpp:79
void removeMotion(Motion *motion)
Remove a motion from the tree datastructure.
Definition: LazyRRT.cpp:207
double getGoalBias(void) const
Get the goal bias the planner is using.
Definition: LazyRRT.h:108
std::vector< Motion * > children
The set of motions that descend from this one.
Definition: LazyRRT.h:168
double maxDistance_
The maximum length of a motion to be added to a tree.
Definition: LazyRRT.h:193
Representation of a motion.
Definition: LazyRRT.h:141
Base class for a vertex in the PlannerData structure. All derived classes must implement the clone an...
Definition: PlannerData.h:60
Invalid start state or no start state specified.
Definition: PlannerStatus.h:56
Abstract definition of a goal region that can be sampled.
Motion * lastGoalMotion_
The most recent goal motion. Used for PlannerData computation.
Definition: LazyRRT.h:199
void setRange(double distance)
Set the range the planner is supposed to use.
Definition: LazyRRT.h:118
#define OMPL_ERROR(fmt,...)
Log a formatted error string.
Definition: Console.h:64
bool tagState(const State *st, int tag)
Set the integer tag associated with the given state. If the given state does not exist in a vertex...
double goalBias_
The fraction of time the goal is picked as the state to expand towards (if such a state is available)...
Definition: LazyRRT.h:190
The planner found an exact solution.
Definition: PlannerStatus.h:66
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 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.
double distanceFunction(const Motion *a, const Motion *b) const
Compute distance between motions (actually distance between contained states)
Definition: LazyRRT.h:178
base::State * state
The state contained by the motion.
Definition: LazyRRT.h:159
PlannerSpecs specs_
The specifications of the planner (its capabilities)
Definition: Planner.h:404
double getRange(void) const
Get the range the planner is using.
Definition: LazyRRT.h:124
bool valid
Flag indicating whether this motion has been validated.
Definition: LazyRRT.h:165
virtual void setup(void)
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Definition: LazyRRT.cpp:58
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
LazyRRT(const base::SpaceInformationPtr &si)
Constructor.
Definition: LazyRRT.cpp:42
virtual void clear(void)
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Definition: LazyRRT.cpp:69
Definition of a geometric path.
Definition: PathGeometric.h:55
Motion * parent
The parent motion in the exploration tree.
Definition: LazyRRT.h:162
A boost shared pointer wrapper for ompl::base::Path.
#define OMPL_INFORM(fmt,...)
Log a formatted information string.
Definition: Console.h:68