37 #include "ompl/geometric/planners/rrt/RRTstar.h"
38 #include "ompl/base/goals/GoalSampleableRegion.h"
39 #include "ompl/tools/config/SelfConfig.h"
40 #include "ompl/base/objectives/PathLengthOptimizationObjective.h"
44 #include <boost/math/constants/constants.hpp>
46 ompl::geometric::RRTstar::RRTstar(
const base::SpaceInformationPtr &si) : base::Planner(si,
"RRTstar")
54 lastGoalMotion_ = NULL;
58 bestCost_ = base::Cost(std::numeric_limits<double>::quiet_NaN());
59 distanceDirection_ = FROM_NEIGHBORS;
66 boost::bind(&RRTstar::getIterationCount,
this));
68 boost::bind(&RRTstar::getCollisionCheckCount,
this));
70 boost::bind(&RRTstar::getBestCost,
this));
73 ompl::geometric::RRTstar::~RRTstar(
void)
85 nn_.reset(tools::SelfConfig::getDefaultNearestNeighbors<Motion*>(si_->getStateSpace()));
94 if (pdef_->hasOptimizationObjective())
95 opt_ = pdef_->getOptimizationObjective();
98 OMPL_INFORM(
"%s: No optimization objective specified. Defaulting to optimizing path length for the allowed planning time.", getName().c_str());
111 lastGoalMotion_ = NULL;
112 goalMotions_.clear();
115 collisionChecks_ = 0;
116 bestCost_ =
base::Cost(std::numeric_limits<double>::quiet_NaN());
126 bool symDist = si_->getStateSpace()->hasSymmetricDistance();
127 bool symInterp = si_->getStateSpace()->hasSymmetricInterpolate();
128 bool symCost = opt_->isSymmetric();
133 si_->copyState(motion->
state, st);
134 motion->
cost = opt_->identityCost();
138 if (nn_->size() == 0)
140 OMPL_ERROR(
"%s: There are no valid initial states!", getName().c_str());
145 sampler_ = si_->allocStateSampler();
147 OMPL_INFORM(
"%s: Starting with %u states", getName().c_str(), nn_->size());
149 Motion *solution = lastGoalMotion_;
155 Motion *approximation = NULL;
156 double approximatedist = std::numeric_limits<double>::infinity();
157 bool sufficientlyShort =
false;
164 double k_rrg = boost::math::constants::e<double>() + (boost::math::constants::e<double>()/(double)si_->getStateSpace()->getDimension());
166 std::vector<Motion*> nbh;
168 std::vector<base::Cost> costs;
169 std::vector<base::Cost> incCosts;
170 std::vector<std::size_t> sortedCostIndices;
172 std::vector<int> valid;
173 unsigned int rewireTest = 0;
174 unsigned int statesGenerated = 0;
177 OMPL_INFORM(
"%s: Starting with existing solution of cost %.5f", getName().c_str(), solution->cost.v);
178 OMPL_INFORM(
"%s: Initial k-nearest value of %u", getName().c_str(), (
unsigned int)std::ceil(k_rrg *
log((
double)(nn_->size()+1))));
189 if (goal_s && goalMotions_.size() < goal_s->
maxSampleCount() && rng_.uniform01() < goalBias_ && goal_s->
canSample())
192 sampler_->sampleUniform(rstate);
197 distanceDirection_ = FROM_NEIGHBORS;
200 Motion *nmotion = nn_->nearest(rmotion);
205 double d = si_->distance(nmotion->
state, rstate);
206 if (d > maxDistance_)
208 si_->getStateSpace()->interpolate(nmotion->
state, rstate, maxDistance_ / d, xstate);
214 if (si_->checkMotion(nmotion->
state, dstate))
218 si_->copyState(motion->
state, dstate);
224 unsigned int k = std::ceil(k_rrg *
log((
double)(nn_->size()+1)));
225 nn_->nearestK(motion, k, nbh);
227 rewireTest += nbh.size();
234 if (costs.size() < nbh.size())
236 costs.resize(nbh.size());
237 incCosts.resize(nbh.size());
238 sortedCostIndices.resize(nbh.size());
245 if (symDist && symInterp)
247 if (valid.size() < nbh.size())
248 valid.resize(nbh.size());
249 std::fill(valid.begin(), valid.begin()+nbh.size(), 0);
258 for (std::size_t i = 0 ; i < nbh.size(); ++i)
260 incCosts[i] = opt_->motionCost(nbh[i]->state, motion->
state);
261 costs[i] = opt_->combineCosts(nbh[i]->cost, incCosts[i]);
268 for (std::size_t i = 0; i < nbh.size(); ++i)
269 sortedCostIndices[i] = i;
270 std::sort(sortedCostIndices.begin(), sortedCostIndices.begin()+nbh.size(),
279 for (std::vector<std::size_t>::const_iterator i = sortedCostIndices.begin();
280 i != sortedCostIndices.begin()+nbh.size();
283 if (nbh[*i] != nmotion)
285 if (nbh[*i] == nmotion || si_->checkMotion(nbh[*i]->state, motion->
state))
287 motion->
incCost = incCosts[*i];
288 motion->
cost = costs[*i];
290 if (symDist && symInterp)
294 else if (symDist && symInterp)
303 for (std::size_t i = 0 ; i < nbh.size(); ++i)
305 if (nbh[i] != nmotion)
307 incCosts[i] = opt_->motionCost(nbh[i]->state, motion->
state);
308 costs[i] = opt_->combineCosts(nbh[i]->cost, incCosts[i]);
309 if (opt_->isCostBetterThan(costs[i], motion->
cost))
312 if (si_->checkMotion(nbh[i]->state, motion->
state))
315 motion->
cost = costs[i];
317 if (symDist && symInterp)
320 else if (symDist && symInterp)
327 costs[i] = motion->
cost;
328 if (symDist && symInterp)
338 bool checkForSolution =
false;
346 distanceDirection_ = TO_NEIGHBORS;
347 nn_->nearestK(motion, k, nbh);
348 rewireTest += nbh.size();
351 for (std::size_t i = 0; i < nbh.size(); ++i)
353 if (nbh[i] != motion->
parent)
356 if (symDist && symCost)
357 nbhIncCost = incCosts[i];
359 nbhIncCost = opt_->motionCost(motion->
state, nbh[i]->state);
360 base::Cost nbhNewCost = opt_->combineCosts(motion->
cost, nbhIncCost);
361 if (opt_->isCostBetterThan(nbhNewCost, nbh[i]->cost))
364 if (symDist && symInterp)
369 motionValid = si_->checkMotion(motion->
state, nbh[i]->state);
372 motionValid = (valid[i] == 1);
378 motionValid = si_->checkMotion(motion->
state, nbh[i]->state);
383 removeFromParent (nbh[i]);
386 nbh[i]->parent = motion;
388 nbh[i]->cost = nbhNewCost;
389 nbh[i]->parent->children.push_back(nbh[i]);
392 updateChildCosts(nbh[i]);
394 checkForSolution =
true;
401 double distanceFromGoal;
404 goalMotions_.push_back(motion);
405 checkForSolution =
true;
409 if (checkForSolution)
411 for (
size_t i = 0; i < goalMotions_.size(); ++i)
413 if (opt_->isCostBetterThan(goalMotions_[i]->cost, bestCost))
415 bestCost = goalMotions_[i]->cost;
416 bestCost_ = bestCost;
419 sufficientlyShort = opt_->isSatisfied(goalMotions_[i]->cost);
420 if (sufficientlyShort)
422 solution = goalMotions_[i];
425 else if (!solution ||
426 opt_->isCostBetterThan(goalMotions_[i]->cost,solution->cost))
427 solution = goalMotions_[i];
432 if (goalMotions_.size() == 0 && distanceFromGoal < approximatedist)
434 approximation = motion;
435 approximatedist = distanceFromGoal;
440 if (solution && sufficientlyShort)
444 bool approximate = (solution == 0);
445 bool addedSolution =
false;
447 solution = approximation;
449 lastGoalMotion_ = solution;
454 std::vector<Motion*> mpath;
455 while (solution != 0)
457 mpath.push_back(solution);
458 solution = solution->parent;
463 for (
int i = mpath.size() - 1 ; i >= 0 ; --i)
464 geoPath->
append(mpath[i]->state);
473 pdef_->addSolutionPath (psol);
475 addedSolution =
true;
478 si_->freeState(xstate);
480 si_->freeState(rmotion->
state);
483 OMPL_INFORM(
"%s: Created %u new states. Checked %u rewire options. %u goal states in tree.", getName().c_str(), statesGenerated, rewireTest, goalMotions_.size());
505 for (std::size_t i = 0; i < m->
children.size(); ++i)
516 std::vector<Motion*> motions;
518 for (std::size_t i = 0 ; i < motions.size() ; ++i)
520 if (motions[i]->state)
521 si_->freeState(motions[i]->state);
529 Planner::getPlannerData(data);
531 std::vector<Motion*> motions;
538 for (std::size_t i = 0 ; i < motions.size() ; ++i)
540 if (motions[i]->parent == NULL)
546 data.
properties[
"iterations INTEGER"] = boost::lexical_cast<std::string>(iterations_);
548 boost::lexical_cast<std::string>(collisionChecks_);
551 std::string ompl::geometric::RRTstar::getIterationCount(
void)
const
553 return boost::lexical_cast<std::string>(iterations_);
555 std::string ompl::geometric::RRTstar::getCollisionCheckCount(
void)
const
557 return boost::lexical_cast<std::string>(collisionChecks_);
559 std::string ompl::geometric::RRTstar::getBestCost(
void)
const
561 return boost::lexical_cast<std::string>(bestCost_.v);
bool approximateSolutions
Flag indicating whether the planner is able to compute approximate solutions.
void addPlannerProgressProperty(const std::string &progressPropertyName, const PlannerProgressProperty &prop)
Add a planner progress property called progressPropertyName with a property querying function prop to...
bool canSample(void) const
Return true if maxSampleCount() > 0, since in this case samples can certainly be produced.
bool getDelayCC(void) const
Get the state of the delayed collision checking option.
Object containing planner generated vertex and edge data. It is assumed that all vertices are unique...
void log(const char *file, int line, LogLevel level, const char *m,...)
Root level logging function. This should not be invoked directly, but rather used via a logging macro...
void setDelayCC(bool delayCC)
Option that delays collision checking procedures. When it is enabled, all neighbors are sorted by cos...
bool optimized_
True of the solution was optimized to meet the specified optimization criterion.
Representation of a solution to a planning problem.
void updateChildCosts(Motion *m)
Updates the cost of the children of this node if the cost up to this node has changed.
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.
base::Cost cost
The cost up to this motion.
Encapsulate a termination condition for a motion planner. Planners will call operator() to decide whe...
void setRange(double distance)
Set the range the planner is supposed to use.
double getGoalBias(void) const
Get the goal bias the planner is using.
void append(const base::State *state)
Append state to the end of this path. The memory for state is copied.
Representation of a motion.
virtual void sampleGoal(State *st) const =0
Sample a state in the goal region.
double maxDistance_
The maximum length of a motion to be added to a tree.
base::State * state
The state contained by the motion.
Base class for a vertex in the PlannerData structure. All derived classes must implement the clone an...
Invalid start state or no start state specified.
Abstract definition of a goal region that can be sampled.
Definition of a cost value. Can represent the cost of a motion or the cost of a state.
double getRange(void) const
Get the range the planner is using.
#define OMPL_ERROR(fmt,...)
Log a formatted error string.
virtual void getPlannerData(base::PlannerData &data) const
Get information about the current run of the motion planner. Repeated calls to this function will upd...
A class to store the exit status of Planner::solve()
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...
An optimization objective which corresponds to optimizing path length.
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.
virtual unsigned int maxSampleCount(void) const =0
Return the maximum number of samples that can be asked for before repeating.
virtual bool isSatisfied(const State *st) const =0
Return true if the state satisfies the goal constraints.
std::vector< Motion * > children
The set of motions descending from the current motion.
PlannerSpecs specs_
The specifications of the planner (its capabilities)
void freeMemory(void)
Free the memory allocated by this planner.
Motion * parent
The parent motion in the exploration tree.
bool optimizingPaths
Flag indicating whether the planner attempts to optimize the path and reduce its length until the max...
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...
void removeFromParent(Motion *m)
Removes the given motion from the parent's child list.
void setGoalBias(double goalBias)
Set the goal bias.
Definition of a geometric path.
virtual void clear(void)
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
virtual void setup(void)
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
base::Cost incCost
The incremental cost of this motion's parent to this motion (this is stored to save distance computat...
A boost shared pointer wrapper for ompl::base::Path.
std::map< std::string, std::string > properties
Any extra properties (key-value pairs) the planner can set.
double distanceFunction(const Motion *a, const Motion *b) const
Compute distance between motions (actually distance between contained states)
#define OMPL_INFORM(fmt,...)
Log a formatted information string.