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 128 of file SearchQueue.h.

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

Detailed Description