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
	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

using ompl::geometric::BITstar::SearchQueue::EdgeComparisonFunction

Initial value:

std::function<bool(const SortKeyAndVertexPtrPair &, const SortKeyAndVertexPtrPair &)>

ompl::geometric::BITstar::SearchQueue::SortKeyAndVertexPtrPair

std::pair< SortKey, VertexPtrPair > SortKeyAndVertexPtrPair

The data stored in the edge-queue binary heap.

Definition SearchQueue.h:75

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

Definition at line 78 of file SearchQueue.h.

◆ EdgeQueue

using ompl::geometric::BITstar::SearchQueue::EdgeQueue = ompl::BinaryHeap<SortKeyAndVertexPtrPair, EdgeComparisonFunction>

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

Definition at line 82 of file SearchQueue.h.

◆ EdgeQueueElemPtr

using ompl::geometric::BITstar::SearchQueue::EdgeQueueElemPtr = EdgeQueue::Element *

An element pointer into the edge queue binary heap.

Definition at line 85 of file SearchQueue.h.

◆ EdgeQueueElemPtrVector

using ompl::geometric::BITstar::SearchQueue::EdgeQueueElemPtrVector = std::vector<EdgeQueueElemPtr>

A vector of edge queue pointers.

Definition at line 88 of file SearchQueue.h.

◆ SortKey

using ompl::geometric::BITstar::SearchQueue::SortKey = std::array<ompl::base::Cost, 3u>

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

Definition at line 72 of file SearchQueue.h.

◆ SortKeyAndVertexPtrPair

using ompl::geometric::BITstar::SearchQueue::SortKeyAndVertexPtrPair = std::pair<SortKey, VertexPtrPair>

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 539 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 377 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 397 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 334 of file SearchQueue.cpp.

◆ clearInconsistentSet()

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

Clear the set of inconsistent vertices.

Definition at line 490 of file SearchQueue.cpp.

◆ enableCascadingRewirings()

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

Set whether cascading of rewirings is enabled.

Definition at line 136 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 435 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 189 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 204 of file SearchQueue.cpp.

◆ getInflationFactor()

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

Get the cost-to-go inflation factor.

Definition at line 367 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 372 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 453 of file SearchQueue.cpp.

◆ insertOutgoingEdgesOfInconsistentVertices()

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

Insert the outgoing edges of all inconsistent vertices.

Definition at line 474 of file SearchQueue.cpp.

◆ insertOutgoingEdgesOfStartVertices()

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

Insert the outgoing edges of all start vertices.

Definition at line 345 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 428 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 421 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 219 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 495 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 254 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 313 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 319 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 265 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 289 of file SearchQueue.cpp.

◆ reset()

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

Reset the queue to the state of construction.

Definition at line 102 of file SearchQueue.cpp.

◆ setInflationFactor()

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

Set the cost-to-go inflation factor.

Definition at line 362 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 89 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 528 of file SearchQueue.cpp.

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

ompl/geometric/planners/informedtrees/bitstar/SearchQueue.h
ompl/geometric/planners/informedtrees/bitstar/src/SearchQueue.cpp

Public Types

Public Member Functions