A conceptual representation of samples as an edge-implicit random geometric graph. More...
#include <ompl/geometric/planners/informedtrees/bitstar/ImplicitGraph.h>
Public Member Functions | |
ImplicitGraph (NameFunc nameFunc) | |
Construct an implicit graph. | |
virtual | ~ImplicitGraph ()=default |
Destruct the graph using default destruction. | |
void | setup (const ompl::base::SpaceInformationPtr &spaceInformation, const ompl::base::ProblemDefinitionPtr &problemDefinition, CostHelper *costHelper, SearchQueue *searchQueue, const ompl::base::Planner *plannerPtr, ompl::base::PlannerInputStates &inputStates) |
Setup the ImplicitGraph, must be called before use. Does not take a copy of the PlannerInputStates, but checks it for starts/goals. | |
void | reset () |
Reset the graph to the state of construction. | |
bool | hasAStart () const |
Gets whether the graph contains a start or not. | |
bool | hasAGoal () const |
Gets whether the graph contains a goal or not. | |
VertexPtrVector::const_iterator | startVerticesBeginConst () const |
Returns a const-iterator to the front of the start-vertex vector. | |
VertexPtrVector::const_iterator | startVerticesEndConst () const |
Returns a const-iterator to the end of the start-vertex vector. | |
VertexPtrVector::const_iterator | goalVerticesBeginConst () const |
Returns a const-iterator to the front of the goal-vertex vector. | |
VertexPtrVector::const_iterator | goalVerticesEndConst () const |
Returns a const-iterator to the end of the goal-vertex vector. | |
ompl::base::Cost | minCost () const |
Get the minimum cost solution possible for this problem. | |
bool | hasInformedMeasure () const |
Query whether the underlying state sampler can provide an informed measure. | |
double | getInformedMeasure (const ompl::base::Cost &cost) const |
Query the underlying state sampler for the informed measure of the problem. | |
double | distance (const VertexConstPtr &a, const VertexConstPtr &b) const |
Computes the distance between two states. | |
double | distance (const VertexConstPtrPair &vertices) const |
Computes the distance between two states. | |
void | nearestSamples (const VertexPtr &vertex, VertexPtrVector *neighbourSamples) |
Get the nearest unconnected samples using the appropriate "near" definition (i.e., k or r). | |
void | getGraphAsPlannerData (ompl::base::PlannerData &data) const |
Adds the graph to the given PlannerData struct. | |
VertexConstPtr | closestVertexToGoal () const |
IF BEING TRACKED, returns the closest vertex in the tree to the goal. | |
double | smallestDistanceToGoal () const |
IF BEING TRACKED, returns the how close vertices in the tree are to the goal. | |
unsigned int | getConnectivityK () const |
Get the k of this k-nearest RGG. | |
double | getConnectivityR () const |
Get the radius of this r-disc RGG. | |
VertexPtrVector | getCopyOfSamples () const |
Get a copy of all samples. | |
void | registerSolutionCost (const ompl::base::Cost &solutionCost) |
Mark that a solution has been found and that the graph should be limited to the given heuristic value. | |
void | updateStartAndGoalStates (ompl::base::PlannerInputStates &inputStates, const base::PlannerTerminationCondition &terminationCondition) |
Adds any new goals or starts that have appeared in the problem definition to the vector of vertices and the queue. Creates a new informed sampler if necessary. | |
void | addNewSamples (const unsigned int &numSamples) |
Increase the resolution of the graph-based approximation of the continuous search domain by adding a batch of new samples. | |
std::pair< unsigned int, unsigned int > | prune (double prunedMeasure) |
Prune the samples to the subproblem of the given measure. Returns the number of vertices disconnected and the number of samples removed. | |
void | addToSamples (const VertexPtr &sample) |
Add an unconnected sample. | |
void | addToSamples (const VertexPtrVector &samples) |
Add a vector of unconnected samples. | |
void | removeFromSamples (const VertexPtr &sample) |
Remove a sample from the sample set. | |
void | pruneSample (const VertexPtr &sample) |
Remove an unconnected sample. | |
void | recycleSample (const VertexPtr &sample) |
Insert a sample into the set for recycled samples. | |
void | registerAsVertex (const VertexPtr &vertex) |
Add a vertex to the tree, optionally moving it from the set of unconnected samples. | |
unsigned int | removeFromVertices (const VertexPtr &sample, bool moveToFree) |
Remove a vertex from the tree, can optionally be allowed to move it to the set of unconnected samples if may still be useful. | |
std::pair< unsigned int, unsigned int > | pruneVertex (const VertexPtr &vertex) |
Remove a vertex and mark as pruned. | |
void | removeEdgeBetweenVertexAndParent (const VertexPtr &child, bool cascadeCostUpdates) |
Disconnect a vertex from its parent by removing the edges stored in itself, and its parents. Cascades cost updates if requested. | |
void | setRewireFactor (double rewireFactor) |
Set the rewiring scale factor, s, such that r_rrg = s \times r_rrg*. | |
double | getRewireFactor () const |
Get the rewiring scale factor. | |
void | setUseKNearest (bool useKNearest) |
Enable a k-nearest search for instead of an r-disc search. | |
bool | getUseKNearest () const |
Get whether a k-nearest search is being used. | |
void | setJustInTimeSampling (bool useJit) |
bool | getJustInTimeSampling () const |
Get whether we're using just-in-time sampling. | |
void | setDropSamplesOnPrune (bool dropSamples) |
Set whether unconnected samples are dropped on pruning. | |
void | setPruning (bool usePruning) |
Set whether samples that are provably not beneficial should be kept around. | |
bool | getDropSamplesOnPrune () const |
Get whether unconnected samples are dropped on pruning. | |
void | setTrackApproximateSolutions (bool findApproximate) |
Set whether to track approximate solutions during the search. | |
bool | getTrackApproximateSolutions () const |
Get whether approximate solutions are tracked during the search. | |
void | setAverageNumOfAllowedFailedAttemptsWhenSampling (std::size_t number) |
Set the average number of allowed failed attempts when sampling. | |
std::size_t | getAverageNumOfAllowedFailedAttemptsWhenSampling () const |
Get the average number of allowed failed attempts when sampling. | |
template<template< typename T > class NN> | |
void | setNearestNeighbors () |
Set a different nearest neighbours datastructure. | |
unsigned int | numSamples () const |
The number of samples. | |
unsigned int | numVertices () const |
The number of vertices in the search tree. | |
unsigned int | numStatesGenerated () const |
The total number of states generated. | |
unsigned int | numVerticesConnected () const |
The total number of vertices added to the graph. | |
unsigned int | numFreeStatesPruned () const |
The number of states pruned. | |
unsigned int | numVerticesDisconnected () const |
The number of tree vertices disconnected. | |
unsigned int | numNearestLookups () const |
The number of nearest neighbour calls. | |
unsigned int | numStateCollisionChecks () const |
The number of state collision checks. | |
bool | canVertexBeDisconnected (const VertexPtr &vertex) const |
Returns whether the vertex can be pruned, i.e., whether it could provide a better solution given. the current graph. The check should always be g_t(v) + h^(v) >= g_t(x_g). | |
bool | canSampleBePruned (const VertexPtr &sample) const |
Returns whether the sample can be pruned, i.e., whether it could ever provide a better solution. The check should always be g^(v) + h^(v) >= g_t(x_g). | |
Detailed Description
A conceptual representation of samples as an edge-implicit random geometric graph.
- Short Description
- An edge-implicit representation of a random geometric graph. TODO(Marlin): Separating the search tree from the RGG seems conceptually cleaner. Think about its implications.
Definition at line 56 of file ImplicitGraph.h.
Constructor & Destructor Documentation
◆ ImplicitGraph()
ompl::geometric::BITstar::ImplicitGraph::ImplicitGraph | ( | NameFunc | nameFunc | ) |
Construct an implicit graph.
Definition at line 86 of file ImplicitGraph.cpp.
Member Function Documentation
◆ addNewSamples()
void ompl::geometric::BITstar::ImplicitGraph::addNewSamples | ( | const unsigned int & | numSamples | ) |
Increase the resolution of the graph-based approximation of the continuous search domain by adding a batch of new samples.
Definition at line 599 of file ImplicitGraph.cpp.
◆ addToSamples() [1/2]
void ompl::geometric::BITstar::ImplicitGraph::addToSamples | ( | const VertexPtr & | sample | ) |
Add an unconnected sample.
Definition at line 651 of file ImplicitGraph.cpp.
◆ addToSamples() [2/2]
void ompl::geometric::BITstar::ImplicitGraph::addToSamples | ( | const VertexPtrVector & | samples | ) |
Add a vector of unconnected samples.
Definition at line 664 of file ImplicitGraph.cpp.
◆ canSampleBePruned()
bool ompl::geometric::BITstar::ImplicitGraph::canSampleBePruned | ( | const VertexPtr & | sample | ) | const |
Returns whether the sample can be pruned, i.e., whether it could ever provide a better solution. The check should always be g^(v) + h^(v) >= g_t(x_g).
Definition at line 1243 of file ImplicitGraph.cpp.
◆ canVertexBeDisconnected()
bool ompl::geometric::BITstar::ImplicitGraph::canVertexBeDisconnected | ( | const VertexPtr & | vertex | ) | const |
Returns whether the vertex can be pruned, i.e., whether it could provide a better solution given. the current graph. The check should always be g_t(v) + h^(v) >= g_t(x_g).
Definition at line 1231 of file ImplicitGraph.cpp.
◆ closestVertexToGoal()
BITstar::VertexConstPtr ompl::geometric::BITstar::ImplicitGraph::closestVertexToGoal | ( | ) | const |
IF BEING TRACKED, returns the closest vertex in the tree to the goal.
Definition at line 1474 of file ImplicitGraph.cpp.
◆ distance() [1/2]
double ompl::geometric::BITstar::ImplicitGraph::distance | ( | const VertexConstPtr & | a, |
const VertexConstPtr & | b ) const |
Computes the distance between two states.
Definition at line 259 of file ImplicitGraph.cpp.
◆ distance() [2/2]
double ompl::geometric::BITstar::ImplicitGraph::distance | ( | const VertexConstPtrPair & | vertices | ) | const |
Computes the distance between two states.
Definition at line 280 of file ImplicitGraph.cpp.
◆ getAverageNumOfAllowedFailedAttemptsWhenSampling()
std::size_t ompl::geometric::BITstar::ImplicitGraph::getAverageNumOfAllowedFailedAttemptsWhenSampling | ( | ) | const |
Get the average number of allowed failed attempts when sampling.
Definition at line 1666 of file ImplicitGraph.cpp.
◆ getConnectivityK()
unsigned int ompl::geometric::BITstar::ImplicitGraph::getConnectivityK | ( | ) | const |
Get the k of this k-nearest RGG.
Definition at line 1496 of file ImplicitGraph.cpp.
◆ getConnectivityR()
double ompl::geometric::BITstar::ImplicitGraph::getConnectivityR | ( | ) | const |
Get the radius of this r-disc RGG.
Definition at line 1507 of file ImplicitGraph.cpp.
◆ getCopyOfSamples()
BITstar::VertexPtrVector ompl::geometric::BITstar::ImplicitGraph::getCopyOfSamples | ( | ) | const |
Get a copy of all samples.
Definition at line 1518 of file ImplicitGraph.cpp.
◆ getDropSamplesOnPrune()
bool ompl::geometric::BITstar::ImplicitGraph::getDropSamplesOnPrune | ( | ) | const |
Get whether unconnected samples are dropped on pruning.
Definition at line 1622 of file ImplicitGraph.cpp.
◆ getGraphAsPlannerData()
void ompl::geometric::BITstar::ImplicitGraph::getGraphAsPlannerData | ( | ompl::base::PlannerData & | data | ) | const |
Adds the graph to the given PlannerData struct.
Definition at line 305 of file ImplicitGraph.cpp.
◆ getInformedMeasure()
double ompl::geometric::BITstar::ImplicitGraph::getInformedMeasure | ( | const ompl::base::Cost & | cost | ) | const |
Query the underlying state sampler for the informed measure of the problem.
Definition at line 1469 of file ImplicitGraph.cpp.
◆ getJustInTimeSampling()
bool ompl::geometric::BITstar::ImplicitGraph::getJustInTimeSampling | ( | ) | const |
Get whether we're using just-in-time sampling.
Definition at line 1596 of file ImplicitGraph.cpp.
◆ getRewireFactor()
double ompl::geometric::BITstar::ImplicitGraph::getRewireFactor | ( | ) | const |
Get the rewiring scale factor.
Definition at line 1538 of file ImplicitGraph.cpp.
◆ getTrackApproximateSolutions()
bool ompl::geometric::BITstar::ImplicitGraph::getTrackApproximateSolutions | ( | ) | const |
Get whether approximate solutions are tracked during the search.
Definition at line 1656 of file ImplicitGraph.cpp.
◆ getUseKNearest()
bool ompl::geometric::BITstar::ImplicitGraph::getUseKNearest | ( | ) | const |
Get whether a k-nearest search is being used.
Definition at line 1566 of file ImplicitGraph.cpp.
◆ goalVerticesBeginConst()
BITstar::VertexPtrVector::const_iterator ompl::geometric::BITstar::ImplicitGraph::goalVerticesBeginConst | ( | ) | const |
Returns a const-iterator to the front of the goal-vertex vector.
Definition at line 1449 of file ImplicitGraph.cpp.
◆ goalVerticesEndConst()
BITstar::VertexPtrVector::const_iterator ompl::geometric::BITstar::ImplicitGraph::goalVerticesEndConst | ( | ) | const |
Returns a const-iterator to the end of the goal-vertex vector.
Definition at line 1454 of file ImplicitGraph.cpp.
◆ hasAGoal()
bool ompl::geometric::BITstar::ImplicitGraph::hasAGoal | ( | ) | const |
Gets whether the graph contains a goal or not.
Definition at line 1434 of file ImplicitGraph.cpp.
◆ hasAStart()
bool ompl::geometric::BITstar::ImplicitGraph::hasAStart | ( | ) | const |
Gets whether the graph contains a start or not.
Definition at line 1429 of file ImplicitGraph.cpp.
◆ hasInformedMeasure()
bool ompl::geometric::BITstar::ImplicitGraph::hasInformedMeasure | ( | ) | const |
Query whether the underlying state sampler can provide an informed measure.
Definition at line 1464 of file ImplicitGraph.cpp.
◆ minCost()
ompl::base::Cost ompl::geometric::BITstar::ImplicitGraph::minCost | ( | ) | const |
Get the minimum cost solution possible for this problem.
Definition at line 1459 of file ImplicitGraph.cpp.
◆ nearestSamples()
void ompl::geometric::BITstar::ImplicitGraph::nearestSamples | ( | const VertexPtr & | vertex, |
VertexPtrVector * | neighbourSamples ) |
Get the nearest unconnected samples using the appropriate "near" definition (i.e., k or r).
Definition at line 285 of file ImplicitGraph.cpp.
◆ numFreeStatesPruned()
unsigned int ompl::geometric::BITstar::ImplicitGraph::numFreeStatesPruned | ( | ) | const |
The number of states pruned.
Definition at line 1712 of file ImplicitGraph.cpp.
◆ numNearestLookups()
unsigned int ompl::geometric::BITstar::ImplicitGraph::numNearestLookups | ( | ) | const |
The number of nearest neighbour calls.
Definition at line 1722 of file ImplicitGraph.cpp.
◆ numSamples()
unsigned int ompl::geometric::BITstar::ImplicitGraph::numSamples | ( | ) | const |
The number of samples.
Definition at line 1689 of file ImplicitGraph.cpp.
◆ numStateCollisionChecks()
unsigned int ompl::geometric::BITstar::ImplicitGraph::numStateCollisionChecks | ( | ) | const |
The number of state collision checks.
Definition at line 1727 of file ImplicitGraph.cpp.
◆ numStatesGenerated()
unsigned int ompl::geometric::BITstar::ImplicitGraph::numStatesGenerated | ( | ) | const |
The total number of states generated.
Definition at line 1702 of file ImplicitGraph.cpp.
◆ numVertices()
unsigned int ompl::geometric::BITstar::ImplicitGraph::numVertices | ( | ) | const |
The number of vertices in the search tree.
Definition at line 1694 of file ImplicitGraph.cpp.
◆ numVerticesConnected()
unsigned int ompl::geometric::BITstar::ImplicitGraph::numVerticesConnected | ( | ) | const |
The total number of vertices added to the graph.
Definition at line 1707 of file ImplicitGraph.cpp.
◆ numVerticesDisconnected()
unsigned int ompl::geometric::BITstar::ImplicitGraph::numVerticesDisconnected | ( | ) | const |
The number of tree vertices disconnected.
Definition at line 1717 of file ImplicitGraph.cpp.
◆ prune()
std::pair< unsigned int, unsigned int > ompl::geometric::BITstar::ImplicitGraph::prune | ( | double | prunedMeasure | ) |
Prune the samples to the subproblem of the given measure. Returns the number of vertices disconnected and the number of samples removed.
Definition at line 628 of file ImplicitGraph.cpp.
◆ pruneSample()
void ompl::geometric::BITstar::ImplicitGraph::pruneSample | ( | const VertexPtr & | sample | ) |
Remove an unconnected sample.
Definition at line 685 of file ImplicitGraph.cpp.
◆ pruneVertex()
std::pair< unsigned int, unsigned int > ompl::geometric::BITstar::ImplicitGraph::pruneVertex | ( | const VertexPtr & | vertex | ) |
Remove a vertex and mark as pruned.
Definition at line 806 of file ImplicitGraph.cpp.
◆ recycleSample()
void ompl::geometric::BITstar::ImplicitGraph::recycleSample | ( | const VertexPtr & | sample | ) |
Insert a sample into the set for recycled samples.
Definition at line 726 of file ImplicitGraph.cpp.
◆ registerAsVertex()
void ompl::geometric::BITstar::ImplicitGraph::registerAsVertex | ( | const VertexPtr & | vertex | ) |
Add a vertex to the tree, optionally moving it from the set of unconnected samples.
Definition at line 733 of file ImplicitGraph.cpp.
◆ registerSolutionCost()
void ompl::geometric::BITstar::ImplicitGraph::registerSolutionCost | ( | const ompl::base::Cost & | solutionCost | ) |
Mark that a solution has been found and that the graph should be limited to the given heuristic value.
Definition at line 350 of file ImplicitGraph.cpp.
◆ removeEdgeBetweenVertexAndParent()
void ompl::geometric::BITstar::ImplicitGraph::removeEdgeBetweenVertexAndParent | ( | const VertexPtr & | child, |
bool | cascadeCostUpdates ) |
Disconnect a vertex from its parent by removing the edges stored in itself, and its parents. Cascades cost updates if requested.
Definition at line 882 of file ImplicitGraph.cpp.
◆ removeFromSamples()
void ompl::geometric::BITstar::ImplicitGraph::removeFromSamples | ( | const VertexPtr & | sample | ) |
Remove a sample from the sample set.
Definition at line 677 of file ImplicitGraph.cpp.
◆ removeFromVertices()
unsigned int ompl::geometric::BITstar::ImplicitGraph::removeFromVertices | ( | const VertexPtr & | sample, |
bool | moveToFree ) |
Remove a vertex from the tree, can optionally be allowed to move it to the set of unconnected samples if may still be useful.
Definition at line 755 of file ImplicitGraph.cpp.
◆ reset()
void ompl::geometric::BITstar::ImplicitGraph::reset | ( | ) |
Reset the graph to the state of construction.
Definition at line 190 of file ImplicitGraph.cpp.
◆ setAverageNumOfAllowedFailedAttemptsWhenSampling()
void ompl::geometric::BITstar::ImplicitGraph::setAverageNumOfAllowedFailedAttemptsWhenSampling | ( | std::size_t | number | ) |
Set the average number of allowed failed attempts when sampling.
Definition at line 1661 of file ImplicitGraph.cpp.
◆ setDropSamplesOnPrune()
void ompl::geometric::BITstar::ImplicitGraph::setDropSamplesOnPrune | ( | bool | dropSamples | ) |
Set whether unconnected samples are dropped on pruning.
Definition at line 1601 of file ImplicitGraph.cpp.
◆ setJustInTimeSampling()
void ompl::geometric::BITstar::ImplicitGraph::setJustInTimeSampling | ( | bool | useJit | ) |
Enable sampling "just-in-time", i.e., only when necessary for a nearest-neighbour search.
Definition at line 1571 of file ImplicitGraph.cpp.
◆ setNearestNeighbors()
void ompl::geometric::BITstar::ImplicitGraph::setNearestNeighbors | ( | ) |
Set a different nearest neighbours datastructure.
Definition at line 1672 of file ImplicitGraph.cpp.
◆ setPruning()
void ompl::geometric::BITstar::ImplicitGraph::setPruning | ( | bool | usePruning | ) |
Set whether samples that are provably not beneficial should be kept around.
Definition at line 1617 of file ImplicitGraph.cpp.
◆ setRewireFactor()
void ompl::geometric::BITstar::ImplicitGraph::setRewireFactor | ( | double | rewireFactor | ) |
Set the rewiring scale factor, s, such that r_rrg = s \times r_rrg*.
Definition at line 1525 of file ImplicitGraph.cpp.
◆ setTrackApproximateSolutions()
void ompl::geometric::BITstar::ImplicitGraph::setTrackApproximateSolutions | ( | bool | findApproximate | ) |
Set whether to track approximate solutions during the search.
Definition at line 1627 of file ImplicitGraph.cpp.
◆ setup()
void ompl::geometric::BITstar::ImplicitGraph::setup | ( | const ompl::base::SpaceInformationPtr & | spaceInformation, |
const ompl::base::ProblemDefinitionPtr & | problemDefinition, | ||
CostHelper * | costHelper, | ||
SearchQueue * | searchQueue, | ||
const ompl::base::Planner * | plannerPtr, | ||
ompl::base::PlannerInputStates & | inputStates ) |
Setup the ImplicitGraph, must be called before use. Does not take a copy of the PlannerInputStates, but checks it for starts/goals.
Definition at line 91 of file ImplicitGraph.cpp.
◆ setUseKNearest()
void ompl::geometric::BITstar::ImplicitGraph::setUseKNearest | ( | bool | useKNearest | ) |
Enable a k-nearest search for instead of an r-disc search.
Definition at line 1543 of file ImplicitGraph.cpp.
◆ smallestDistanceToGoal()
double ompl::geometric::BITstar::ImplicitGraph::smallestDistanceToGoal | ( | ) | const |
IF BEING TRACKED, returns the how close vertices in the tree are to the goal.
Definition at line 1485 of file ImplicitGraph.cpp.
◆ startVerticesBeginConst()
BITstar::VertexPtrVector::const_iterator ompl::geometric::BITstar::ImplicitGraph::startVerticesBeginConst | ( | ) | const |
Returns a const-iterator to the front of the start-vertex vector.
Definition at line 1439 of file ImplicitGraph.cpp.
◆ startVerticesEndConst()
BITstar::VertexPtrVector::const_iterator ompl::geometric::BITstar::ImplicitGraph::startVerticesEndConst | ( | ) | const |
Returns a const-iterator to the end of the start-vertex vector.
Definition at line 1444 of file ImplicitGraph.cpp.
◆ updateStartAndGoalStates()
void ompl::geometric::BITstar::ImplicitGraph::updateStartAndGoalStates | ( | ompl::base::PlannerInputStates & | inputStates, |
const base::PlannerTerminationCondition & | terminationCondition ) |
Adds any new goals or starts that have appeared in the problem definition to the vector of vertices and the queue. Creates a new informed sampler if necessary.
Definition at line 365 of file ImplicitGraph.cpp.
The documentation for this class was generated from the following files:
- ompl/geometric/planners/informedtrees/bitstar/ImplicitGraph.h
- ompl/geometric/planners/informedtrees/bitstar/src/ImplicitGraph.cpp