Loading...
Searching...
No Matches
ompl::geometric::BITstar::ImplicitGraph Class Reference

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. More...
 
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. More...
 
void reset ()
 Reset the graph to the state of construction. More...
 
bool hasAStart () const
 Gets whether the graph contains a start or not. More...
 
bool hasAGoal () const
 Gets whether the graph contains a goal or not. More...
 
VertexPtrVector::const_iterator startVerticesBeginConst () const
 Returns a const-iterator to the front of the start-vertex vector. More...
 
VertexPtrVector::const_iterator startVerticesEndConst () const
 Returns a const-iterator to the end of the start-vertex vector. More...
 
VertexPtrVector::const_iterator goalVerticesBeginConst () const
 Returns a const-iterator to the front of the goal-vertex vector. More...
 
VertexPtrVector::const_iterator goalVerticesEndConst () const
 Returns a const-iterator to the end of the goal-vertex vector. More...
 
ompl::base::Cost minCost () const
 Get the minimum cost solution possible for this problem. More...
 
bool hasInformedMeasure () const
 Query whether the underlying state sampler can provide an informed measure. More...
 
double getInformedMeasure (const ompl::base::Cost &cost) const
 Query the underlying state sampler for the informed measure of the problem. More...
 
double distance (const VertexConstPtr &a, const VertexConstPtr &b) const
 Computes the distance between two states. More...
 
double distance (const VertexConstPtrPair &vertices) const
 Computes the distance between two states. More...
 
void nearestSamples (const VertexPtr &vertex, VertexPtrVector *neighbourSamples)
 Get the nearest unconnected samples using the appropriate "near" definition (i.e., k or r). More...
 
void getGraphAsPlannerData (ompl::base::PlannerData &data) const
 Adds the graph to the given PlannerData struct. More...
 
VertexConstPtr closestVertexToGoal () const
 IF BEING TRACKED, returns the closest vertex in the tree to the goal. More...
 
double smallestDistanceToGoal () const
 IF BEING TRACKED, returns the how close vertices in the tree are to the goal. More...
 
unsigned int getConnectivityK () const
 Get the k of this k-nearest RGG. More...
 
double getConnectivityR () const
 Get the radius of this r-disc RGG. More...
 
VertexPtrVector getCopyOfSamples () const
 Get a copy of all samples. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
void addToSamples (const VertexPtr &sample)
 Add an unconnected sample. More...
 
void addToSamples (const VertexPtrVector &samples)
 Add a vector of unconnected samples. More...
 
void removeFromSamples (const VertexPtr &sample)
 Remove a sample from the sample set. More...
 
void pruneSample (const VertexPtr &sample)
 Remove an unconnected sample. More...
 
void recycleSample (const VertexPtr &sample)
 Insert a sample into the set for recycled samples. More...
 
void registerAsVertex (const VertexPtr &vertex)
 Add a vertex to the tree, optionally moving it from the set of unconnected samples. More...
 
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. More...
 
std::pair< unsigned int, unsigned int > pruneVertex (const VertexPtr &vertex)
 Remove a vertex and mark as pruned. More...
 
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. More...
 
void setRewireFactor (double rewireFactor)
 Set the rewiring scale factor, s, such that r_rrg = s \times r_rrg*. More...
 
double getRewireFactor () const
 Get the rewiring scale factor. More...
 
void setUseKNearest (bool useKNearest)
 Enable a k-nearest search for instead of an r-disc search. More...
 
bool getUseKNearest () const
 Get whether a k-nearest search is being used. More...
 
void setJustInTimeSampling (bool useJit)
 
bool getJustInTimeSampling () const
 Get whether we're using just-in-time sampling. More...
 
void setDropSamplesOnPrune (bool dropSamples)
 Set whether unconnected samples are dropped on pruning. More...
 
void setPruning (bool usePruning)
 Set whether samples that are provably not beneficial should be kept around. More...
 
bool getDropSamplesOnPrune () const
 Get whether unconnected samples are dropped on pruning. More...
 
void setTrackApproximateSolutions (bool findApproximate)
 Set whether to track approximate solutions during the search. More...
 
bool getTrackApproximateSolutions () const
 Get whether approximate solutions are tracked during the search. More...
 
void setAverageNumOfAllowedFailedAttemptsWhenSampling (std::size_t number)
 Set the average number of allowed failed attempts when sampling. More...
 
std::size_t getAverageNumOfAllowedFailedAttemptsWhenSampling () const
 Get the average number of allowed failed attempts when sampling. More...
 
template<template< typename T > class NN>
void setNearestNeighbors ()
 Set a different nearest neighbours datastructure. More...
 
unsigned int numSamples () const
 The number of samples. More...
 
unsigned int numVertices () const
 The number of vertices in the search tree. More...
 
unsigned int numStatesGenerated () const
 The total number of states generated. More...
 
unsigned int numVerticesConnected () const
 The total number of vertices added to the graph. More...
 
unsigned int numFreeStatesPruned () const
 The number of states pruned. More...
 
unsigned int numVerticesDisconnected () const
 The number of tree vertices disconnected. More...
 
unsigned int numNearestLookups () const
 The number of nearest neighbour calls. More...
 
unsigned int numStateCollisionChecks () const
 The number of state collision checks. More...
 
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). More...
 
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). More...
 

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 617 of file ImplicitGraph.cpp.

◆ addToSamples() [1/2]

void ompl::geometric::BITstar::ImplicitGraph::addToSamples ( const VertexPtr sample)

Add an unconnected sample.

Definition at line 669 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 682 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 1261 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 1249 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 1492 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 277 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 298 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 1684 of file ImplicitGraph.cpp.

◆ getConnectivityK()

unsigned int ompl::geometric::BITstar::ImplicitGraph::getConnectivityK ( ) const

Get the k of this k-nearest RGG.

Definition at line 1514 of file ImplicitGraph.cpp.

◆ getConnectivityR()

double ompl::geometric::BITstar::ImplicitGraph::getConnectivityR ( ) const

Get the radius of this r-disc RGG.

Definition at line 1525 of file ImplicitGraph.cpp.

◆ getCopyOfSamples()

BITstar::VertexPtrVector ompl::geometric::BITstar::ImplicitGraph::getCopyOfSamples ( ) const

Get a copy of all samples.

Definition at line 1536 of file ImplicitGraph.cpp.

◆ getDropSamplesOnPrune()

bool ompl::geometric::BITstar::ImplicitGraph::getDropSamplesOnPrune ( ) const

Get whether unconnected samples are dropped on pruning.

Definition at line 1640 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 323 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 1487 of file ImplicitGraph.cpp.

◆ getJustInTimeSampling()

bool ompl::geometric::BITstar::ImplicitGraph::getJustInTimeSampling ( ) const

Get whether we're using just-in-time sampling.

Definition at line 1614 of file ImplicitGraph.cpp.

◆ getRewireFactor()

double ompl::geometric::BITstar::ImplicitGraph::getRewireFactor ( ) const

Get the rewiring scale factor.

Definition at line 1556 of file ImplicitGraph.cpp.

◆ getTrackApproximateSolutions()

bool ompl::geometric::BITstar::ImplicitGraph::getTrackApproximateSolutions ( ) const

Get whether approximate solutions are tracked during the search.

Definition at line 1674 of file ImplicitGraph.cpp.

◆ getUseKNearest()

bool ompl::geometric::BITstar::ImplicitGraph::getUseKNearest ( ) const

Get whether a k-nearest search is being used.

Definition at line 1584 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 1467 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 1472 of file ImplicitGraph.cpp.

◆ hasAGoal()

bool ompl::geometric::BITstar::ImplicitGraph::hasAGoal ( ) const

Gets whether the graph contains a goal or not.

Definition at line 1452 of file ImplicitGraph.cpp.

◆ hasAStart()

bool ompl::geometric::BITstar::ImplicitGraph::hasAStart ( ) const

Gets whether the graph contains a start or not.

Definition at line 1447 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 1482 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 1477 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 303 of file ImplicitGraph.cpp.

◆ numFreeStatesPruned()

unsigned int ompl::geometric::BITstar::ImplicitGraph::numFreeStatesPruned ( ) const

The number of states pruned.

Definition at line 1730 of file ImplicitGraph.cpp.

◆ numNearestLookups()

unsigned int ompl::geometric::BITstar::ImplicitGraph::numNearestLookups ( ) const

The number of nearest neighbour calls.

Definition at line 1740 of file ImplicitGraph.cpp.

◆ numSamples()

unsigned int ompl::geometric::BITstar::ImplicitGraph::numSamples ( ) const

The number of samples.

Definition at line 1707 of file ImplicitGraph.cpp.

◆ numStateCollisionChecks()

unsigned int ompl::geometric::BITstar::ImplicitGraph::numStateCollisionChecks ( ) const

The number of state collision checks.

Definition at line 1745 of file ImplicitGraph.cpp.

◆ numStatesGenerated()

unsigned int ompl::geometric::BITstar::ImplicitGraph::numStatesGenerated ( ) const

The total number of states generated.

Definition at line 1720 of file ImplicitGraph.cpp.

◆ numVertices()

unsigned int ompl::geometric::BITstar::ImplicitGraph::numVertices ( ) const

The number of vertices in the search tree.

Definition at line 1712 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 1725 of file ImplicitGraph.cpp.

◆ numVerticesDisconnected()

unsigned int ompl::geometric::BITstar::ImplicitGraph::numVerticesDisconnected ( ) const

The number of tree vertices disconnected.

Definition at line 1735 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 646 of file ImplicitGraph.cpp.

◆ pruneSample()

void ompl::geometric::BITstar::ImplicitGraph::pruneSample ( const VertexPtr sample)

Remove an unconnected sample.

Definition at line 703 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 824 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 744 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 751 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 368 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 900 of file ImplicitGraph.cpp.

◆ removeFromSamples()

void ompl::geometric::BITstar::ImplicitGraph::removeFromSamples ( const VertexPtr sample)

Remove a sample from the sample set.

Definition at line 695 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 773 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 1679 of file ImplicitGraph.cpp.

◆ setDropSamplesOnPrune()

void ompl::geometric::BITstar::ImplicitGraph::setDropSamplesOnPrune ( bool  dropSamples)

Set whether unconnected samples are dropped on pruning.

Definition at line 1619 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 1589 of file ImplicitGraph.cpp.

◆ setNearestNeighbors()

template<template< typename T > class NN>
void ompl::geometric::BITstar::ImplicitGraph::setNearestNeighbors ( )

Set a different nearest neighbours datastructure.

Definition at line 1690 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 1635 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 1543 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 1645 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 1561 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 1503 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 1457 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 1462 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 383 of file ImplicitGraph.cpp.


The documentation for this class was generated from the following files: