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.
 
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()

template<template< typename T > class NN>
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: