37 #include "ompl/tools/config/SelfConfig.h"
38 #include "ompl/geometric/planners/pdst/PDST.h"
40 ompl::geometric::PDST::PDST(
const base::SpaceInformationPtr &si)
41 : base::Planner(si,
"PDST"), bsp_(NULL), goalBias_(0.05),
42 goalSampler_(NULL), iteration_(1), lastGoalMotion_(NULL)
47 ompl::geometric::PDST::~PDST(
void)
76 double distanceToGoal, closestDistanceToGoal = std::numeric_limits<double>::infinity();
82 if (hasSolution && !isApproximate)
107 motionSelected->updatePriority();
117 closestDistanceToGoal = distanceToGoal;
119 isApproximate =
false;
122 else if (distanceToGoal < closestDistanceToGoal)
124 closestDistanceToGoal = distanceToGoal;
131 Cell *cellSelected = motionSelected->
cell_;
132 std::vector<Motion*> motions;
134 motions.swap(cellSelected->
motions_);
135 for (std::vector<Motion*>::iterator m = motions.begin() ; m != motions.end() ; ++m)
136 addMotion(*m, cellSelected, tmpState1, tmpProj);
158 for (std::vector<base::State*>::reverse_iterator rIt = spath.rbegin(); rIt != spath.rend(); ++rIt)
163 si_->freeState(tmpState1);
164 si_->freeState(tmpState2);
182 std::pair<base::State*, double> lastValid = std::make_pair(rnd, 0.);
183 si_->checkMotion(start, rnd, lastValid);
202 startCell = bsp->
stab(proj);
204 while (startCell != motion->
cell_ && numSegments > 1)
206 Cell *nextStartCell = motion->
cell_, *cell;
207 int i = 0, j = numSegments, k = 1;
215 (
double)k / (
double)numSegments, state);
217 cell = bsp->
stab(proj);
218 if (cell == startCell)
223 nextStartCell = cell;
234 startCell = nextStartCell;
248 void ompl::geometric::PDST::freeMemory(
void)
251 std::vector<Motion*> motions;
254 for (std::vector<Motion*>::iterator it = motions.begin(); it < motions.end(); ++it)
256 if ((*it)->startState_ != (*it)->endState_)
257 si_->freeState((*it)->startState_);
258 if (!(*it)->isSplit_)
259 si_->freeState((*it)->endState_);
275 throw Exception(
"PDST requires a projection evaluator that specifies bounds for the projected space");
286 std::vector<Motion*> motions;
293 for (std::vector<Motion*>::iterator it = motions.begin(); it < motions.end(); ++it)
294 if (!(*it)->isSplit_)
296 Motion *cur = *it, *ancestor = cur->ancestor();
304 if (ancestor->parent_)
313 double childVolume = .5 * volume_;
314 unsigned int nextSplitDimension = (splitDimension_ + 1) % spaceDimension;
315 splitValue_ = .5 * (bounds_.low[splitDimension_] + bounds_.high[splitDimension_]);
317 left_ =
new Cell(childVolume, bounds_, nextSplitDimension);
318 left_->bounds_.high[splitDimension_] = splitValue_;
319 left_->motions_.reserve(motions_.size());
320 right_ =
new Cell(childVolume, bounds_, nextSplitDimension);
321 right_->bounds_.low[splitDimension_] = splitValue_;
322 right_->motions_.reserve(motions_.size());
ompl::base::State * endState_
The state reached by this motion.
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...
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...
Motion * propagateFrom(Motion *motion, base::State *, base::State *)
Select a state along motion and propagate a new motion from there. Return NULL if no valid motion cou...
Class representing the tree of motions exploring the state space.
unsigned int iteration_
Iteration number and priority of the next Motion that will be generated.
virtual void setup(void)
Perform extra configuration steps, if needed. This call will also issue a call to ompl::base::SpaceIn...
Cell * bsp_
Binary Space Partition.
Motion * parent_
Parent motion from which this one started.
unsigned int size() const
Number of cells.
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...
ompl::base::State * startState_
The starting point of this motion.
Abstract definition of goals.
std::vector< Motion * > motions_
The motions contained in this cell. Motions are stored only in leaf nodes.
const std::string & getName(void) const
Get the name of the planner.
Encapsulate a termination condition for a motion planner. Planners will call operator() to decide whe...
ompl::BinaryHeap< Motion *, MotionCompare > priorityQueue_
Priority queue of motions.
void addMotion(Motion *motion, Cell *cell, base::State *, base::EuclideanProjection &)
Inserts the motion into the appropriate cell.
void append(const base::State *state)
Append state to the end of this path. The memory for state is copied.
virtual void clear(void)
Clear all internal datastructures. Planner settings are not affected. Subsequent calls to solve() wil...
Cell is a Binary Space Partition.
ProblemDefinitionPtr pdef_
The user set problem definition.
virtual void sampleGoal(State *st) const =0
Sample a state in the goal region.
ompl::base::StateSamplerPtr sampler_
State sampler.
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.
Motion * lastGoalMotion_
Closest motion to the goal.
Abstract definition of a goal region that can be sampled.
ompl::base::ProjectionEvaluatorPtr projectionEvaluator_
Projection evaluator for the problem.
virtual void checkValidity(void)
Check to see if the planner is in a working state (setup has been called, a goal was set...
#define OMPL_ERROR(fmt,...)
Log a formatted error string.
The planner found an exact solution.
void updateHeapElement(Motion *motion)
Either update heap after motion's priority has changed or insert motion into heap.
void addMotion(Motion *motion, Cell *cell, base::State *, base::State *, base::EuclideanProjection &, base::EuclideanProjection &)
Inserts the motion into the appropriate cells, splitting the motion as necessary. motion is assumed t...
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...
ompl::base::RealVectorBounds bounds_
A bounding box for this cell.
boost::numeric::ublas::vector< double > EuclideanProjection
The datatype for state projections. This class contains a real vector.
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.
void addMotion(Motion *motion)
Add a motion.
void subdivide(unsigned int spaceDimension)
Subdivides this cell.
void addMotion(Motion *motion)
Add a motion.
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.
Motion * propagateFrom(Motion *motion, base::State *, base::State *)
Select a state along motion and propagate a new motion from there. Return NULL if no valid motion cou...
The exception type for ompl.
virtual void getPlannerData(base::PlannerData &data) const
Extracts the planner data from the priority queue into data.
double uniform01(void)
Generate a random real between 0 and 1.
virtual void getPlannerData(PlannerData &data) const
Get information about the current run of the motion planner. Repeated calls to this function will upd...
double getGoalBias(void) const
Get the goal bias the planner is using */.
ompl::base::GoalSampleableRegion * goalSampler_
Objected used to sample the goal.
Cell * stab(const ompl::base::EuclideanProjection &projection) const
Locates the cell that this motion begins in.
Definition of a geometric path.
SpaceInformationPtr si_
The space information for which planning is done.
ompl::BinaryHeap< Motion *, MotionCompare >::Element * heapElement_
Handle to the element of the priority queue for this Motion.
Cell * cell_
pointer to the cell that contains this path
ompl::base::State * endState_
The state reached by this motion.
double priority_
Priority for selecting this path to extend from in the future.
A boost shared pointer wrapper for ompl::base::Path.
double goalBias_
Number between 0 and 1 specifying the probability with which the goal should be sampled.
*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.
#define OMPL_INFORM(fmt,...)
Log a formatted information string.