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

A queue of edges, sorted according to a sort key. More...

#include <ompl/geometric/planners/informedtrees/bitstar/SearchQueue.h>

Public Types

using SortKey = std::array<ompl::base::Cost, 3u>
 A triplet of costs, i.e., the edge queue sorting key.
using SortKeyAndVertexPtrPair = std::pair<SortKey, VertexPtrPair>
 The data stored in the edge-queue binary heap.
using EdgeComparisonFunction = std::function<bool(const SortKeyAndVertexPtrPair &, const SortKeyAndVertexPtrPair &)>
 The function signature of the sorting function for the Edge Queue.
using EdgeQueue = ompl::BinaryHeap<SortKeyAndVertexPtrPair, EdgeComparisonFunction>
 The underlying edge queue. Using static keys for the same reason as the Vertex Queue.
using EdgeQueueElemPtr = EdgeQueue::Element*
 An element pointer into the edge queue binary heap.
using EdgeQueueElemPtrVector = std::vector<EdgeQueueElemPtr>
 A vector of edge queue pointers.

Public Member Functions

 SearchQueue (NameFunc nameFunc)
 Construct a search queue. It must be setup before use.
virtual ~SearchQueue ()=default
 Destruct the search queue using the default deconstructor.
void setup (CostHelper *costHelpPtr, ImplicitGraph *graphPtr)
 Setup the SearchQueue, must be called before use.
void reset ()
 Reset the queue to the state of construction.
void enableCascadingRewirings (bool enable)
 Set whether cascading of rewirings is enabled.
void insertOutgoingEdges (const VertexPtr &vertex)
 Update the edge queue by adding all the potential edges from the vertex to nearby states.
void insertOutgoingEdgesOfStartVertices ()
 Insert the outgoing edges of all start vertices.
void insertOutgoingEdgesOfInconsistentVertices ()
 Insert the outgoing edges of all inconsistent vertices.
void addToInconsistentSet (const VertexPtr &vertex)
 Add a vertex to the set of inconsistent vertices.
VertexPtrPair getFrontEdge ()
 Get the best edge on the queue, leaving it at the front of the edge queue.
SortKey getFrontEdgeValue ()
 Get the value of the best edge on the queue, leaving it at the front of the edge queue.
VertexPtrPair popFrontEdge ()
 Pop the best edge off the queue, removing it from the front of the edge queue in the process.
void clear ()
 Finish the queue if it is sorted, if not resort the queue. Finishing the queue clears all the edge containers and moves the vertex expansion token to the end. After calling finish() ON A SORTED QUEUE, isEmpty() will return true. Keeps threshold, etc.
void clearInconsistentSet ()
 Clear the set of inconsistent vertices.
void rebuildEdgeQueue ()
 Update all the sort keys of the edges in the queue and resort.
void update (const EdgeQueueElemPtr elementPtr)
 Update the sort key of a particular edge and its position in the queue.
void setInflationFactor (double factor)
 Set the cost-to-go inflation factor.
void registerSolutionCost (const ompl::base::Cost &solutionCost)
 Mark that a solution has been found.
void removeInEdgesConnectedToVertexFromQueue (const VertexPtr &vertex)
 Erase all edges in the edge queue that lead to the given vertex.
void removeOutEdgesConnectedToVertexFromQueue (const VertexPtr &vertex)
 Erase all edges in the edge queue that leave from the given vertex.
void removeAllEdgesConnectedToVertexFromQueue (const VertexPtr &vertex)
 Erase all edges in the edge queue that are connected to the given vertex.
void removeFromInconsistentSet (const VertexPtr &vertex)
 Remove a vertex from the set of inconsistent vertices.
double getInflationFactor () const
 Get the cost-to-go inflation factor.
std::shared_ptr< const unsigned int > getSearchId () const
 Allow access to the current search id.
bool canPossiblyImproveCurrentSolution (const VertexPtr &state) const
 The condition used to insert vertices into the queue. Compares lowerBoundHeuristicVertex to the given threshold. Returns true if the vertex's best cost is lower than the internally set threshold.
bool canPossiblyImproveCurrentSolution (const VertexPtrPair &edge) const
 The condition used to insert edges into the queue. Compares lowerBoundHeuristicEdge to the given threshold. Returns true if the edge's best cost is lower than the internally set threshold.
unsigned int numEdges ()
 Returns the number of edges in the queue. Will resort/expand the queue if necessary.
bool isEmpty ()
 Returns true if the queue is empty. In the case where the edge queue is empty but the vertex queue is not, this function will expand vertices until the edge queue is not empty or there are no vertices to expand.
void getEdges (VertexConstPtrPairVector *edgeQueue)
 Get a copy of the edge queue. This is expensive and is only meant for animations/debugging.
unsigned int numEdgesPopped () const
 The number of edges popped off the queue for processing (numEdgesPopped_).

Detailed Description

A queue of edges, sorted according to a sort key.

Short Description
A search queue holding edges ordered on a sort key, i.e., a cost triple with a lexicographical comparison. The queue is implemented as a binary heap.

Definition at line 64 of file SearchQueue.h.

Member Typedef Documentation

◆ EdgeComparisonFunction

The function signature of the sorting function for the Edge Queue.

Definition at line 78 of file SearchQueue.h.

◆ EdgeQueue

The underlying edge queue. Using static keys for the same reason as the Vertex Queue.

Definition at line 81 of file SearchQueue.h.

◆ EdgeQueueElemPtr

An element pointer into the edge queue binary heap.

Definition at line 84 of file SearchQueue.h.

◆ EdgeQueueElemPtrVector

A vector of edge queue pointers.

Definition at line 87 of file SearchQueue.h.

◆ SortKey

A triplet of costs, i.e., the edge queue sorting key.

Definition at line 72 of file SearchQueue.h.

◆ SortKeyAndVertexPtrPair

The data stored in the edge-queue binary heap.

Definition at line 75 of file SearchQueue.h.

Constructor & Destructor Documentation

◆ SearchQueue()

ompl::geometric::BITstar::SearchQueue::SearchQueue ( NameFunc nameFunc)

Construct a search queue. It must be setup before use.

Definition at line 79 of file SearchQueue.cpp.

Member Function Documentation

◆ addToInconsistentSet()

void ompl::geometric::BITstar::SearchQueue::addToInconsistentSet ( const VertexPtr & vertex)

Add a vertex to the set of inconsistent vertices.

Definition at line 538 of file SearchQueue.cpp.

◆ canPossiblyImproveCurrentSolution() [1/2]

bool ompl::geometric::BITstar::SearchQueue::canPossiblyImproveCurrentSolution ( const VertexPtr & state) const

The condition used to insert vertices into the queue. Compares lowerBoundHeuristicVertex to the given threshold. Returns true if the vertex's best cost is lower than the internally set threshold.

Definition at line 376 of file SearchQueue.cpp.

◆ canPossiblyImproveCurrentSolution() [2/2]

bool ompl::geometric::BITstar::SearchQueue::canPossiblyImproveCurrentSolution ( const VertexPtrPair & edge) const

The condition used to insert edges into the queue. Compares lowerBoundHeuristicEdge to the given threshold. Returns true if the edge's best cost is lower than the internally set threshold.

Definition at line 396 of file SearchQueue.cpp.

◆ clear()

void ompl::geometric::BITstar::SearchQueue::clear ( )

Finish the queue if it is sorted, if not resort the queue. Finishing the queue clears all the edge containers and moves the vertex expansion token to the end. After calling finish() ON A SORTED QUEUE, isEmpty() will return true. Keeps threshold, etc.

Definition at line 333 of file SearchQueue.cpp.

◆ clearInconsistentSet()

void ompl::geometric::BITstar::SearchQueue::clearInconsistentSet ( )

Clear the set of inconsistent vertices.

Definition at line 489 of file SearchQueue.cpp.

◆ enableCascadingRewirings()

void ompl::geometric::BITstar::SearchQueue::enableCascadingRewirings ( bool enable)

Set whether cascading of rewirings is enabled.

Definition at line 135 of file SearchQueue.cpp.

◆ getEdges()

void ompl::geometric::BITstar::SearchQueue::getEdges ( VertexConstPtrPairVector * edgeQueue)

Get a copy of the edge queue. This is expensive and is only meant for animations/debugging.

Definition at line 434 of file SearchQueue.cpp.

◆ getFrontEdge()

BITstar::VertexPtrPair ompl::geometric::BITstar::SearchQueue::getFrontEdge ( )

Get the best edge on the queue, leaving it at the front of the edge queue.

Definition at line 188 of file SearchQueue.cpp.

◆ getFrontEdgeValue()

BITstar::SearchQueue::SortKey ompl::geometric::BITstar::SearchQueue::getFrontEdgeValue ( )

Get the value of the best edge on the queue, leaving it at the front of the edge queue.

Definition at line 203 of file SearchQueue.cpp.

◆ getInflationFactor()

double ompl::geometric::BITstar::SearchQueue::getInflationFactor ( ) const

Get the cost-to-go inflation factor.

Definition at line 366 of file SearchQueue.cpp.

◆ getSearchId()

std::shared_ptr< const unsigned int > ompl::geometric::BITstar::SearchQueue::getSearchId ( ) const

Allow access to the current search id.

Definition at line 371 of file SearchQueue.cpp.

◆ insertOutgoingEdges()

void ompl::geometric::BITstar::SearchQueue::insertOutgoingEdges ( const VertexPtr & vertex)

Update the edge queue by adding all the potential edges from the vertex to nearby states.

Definition at line 452 of file SearchQueue.cpp.

◆ insertOutgoingEdgesOfInconsistentVertices()

void ompl::geometric::BITstar::SearchQueue::insertOutgoingEdgesOfInconsistentVertices ( )

Insert the outgoing edges of all inconsistent vertices.

Definition at line 473 of file SearchQueue.cpp.

◆ insertOutgoingEdgesOfStartVertices()

void ompl::geometric::BITstar::SearchQueue::insertOutgoingEdgesOfStartVertices ( )

Insert the outgoing edges of all start vertices.

Definition at line 344 of file SearchQueue.cpp.

◆ isEmpty()

bool ompl::geometric::BITstar::SearchQueue::isEmpty ( )

Returns true if the queue is empty. In the case where the edge queue is empty but the vertex queue is not, this function will expand vertices until the edge queue is not empty or there are no vertices to expand.

Definition at line 427 of file SearchQueue.cpp.

◆ numEdges()

unsigned int ompl::geometric::BITstar::SearchQueue::numEdges ( )

Returns the number of edges in the queue. Will resort/expand the queue if necessary.

Definition at line 420 of file SearchQueue.cpp.

◆ numEdgesPopped()

unsigned int ompl::geometric::BITstar::SearchQueue::numEdgesPopped ( ) const

The number of edges popped off the queue for processing (numEdgesPopped_).

Definition at line 665 of file SearchQueue.cpp.

◆ popFrontEdge()

BITstar::VertexPtrPair ompl::geometric::BITstar::SearchQueue::popFrontEdge ( )

Pop the best edge off the queue, removing it from the front of the edge queue in the process.

Definition at line 218 of file SearchQueue.cpp.

◆ rebuildEdgeQueue()

void ompl::geometric::BITstar::SearchQueue::rebuildEdgeQueue ( )

Update all the sort keys of the edges in the queue and resort.

Definition at line 494 of file SearchQueue.cpp.

◆ registerSolutionCost()

void ompl::geometric::BITstar::SearchQueue::registerSolutionCost ( const ompl::base::Cost & solutionCost)

Mark that a solution has been found.

Definition at line 253 of file SearchQueue.cpp.

◆ removeAllEdgesConnectedToVertexFromQueue()

void ompl::geometric::BITstar::SearchQueue::removeAllEdgesConnectedToVertexFromQueue ( const VertexPtr & vertex)

Erase all edges in the edge queue that are connected to the given vertex.

Definition at line 312 of file SearchQueue.cpp.

◆ removeFromInconsistentSet()

void ompl::geometric::BITstar::SearchQueue::removeFromInconsistentSet ( const VertexPtr & vertex)

Remove a vertex from the set of inconsistent vertices.

Definition at line 318 of file SearchQueue.cpp.

◆ removeInEdgesConnectedToVertexFromQueue()

void ompl::geometric::BITstar::SearchQueue::removeInEdgesConnectedToVertexFromQueue ( const VertexPtr & vertex)

Erase all edges in the edge queue that lead to the given vertex.

Definition at line 264 of file SearchQueue.cpp.

◆ removeOutEdgesConnectedToVertexFromQueue()

void ompl::geometric::BITstar::SearchQueue::removeOutEdgesConnectedToVertexFromQueue ( const VertexPtr & vertex)

Erase all edges in the edge queue that leave from the given vertex.

Definition at line 288 of file SearchQueue.cpp.

◆ reset()

void ompl::geometric::BITstar::SearchQueue::reset ( )

Reset the queue to the state of construction.

Definition at line 101 of file SearchQueue.cpp.

◆ setInflationFactor()

void ompl::geometric::BITstar::SearchQueue::setInflationFactor ( double factor)

Set the cost-to-go inflation factor.

Definition at line 361 of file SearchQueue.cpp.

◆ setup()

void ompl::geometric::BITstar::SearchQueue::setup ( CostHelper * costHelpPtr,
ImplicitGraph * graphPtr )

Setup the SearchQueue, must be called before use.

Definition at line 88 of file SearchQueue.cpp.

◆ update()

void ompl::geometric::BITstar::SearchQueue::update ( const EdgeQueueElemPtr elementPtr)

Update the sort key of a particular edge and its position in the queue.

Definition at line 527 of file SearchQueue.cpp.


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