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
using ompl::geometric::BITstar::SearchQueue::EdgeComparisonFunction = std::function<bool(const SortKeyAndVertexPtrPair &, const SortKeyAndVertexPtrPair &)> |
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 81 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 84 of file SearchQueue.h.
◆ EdgeQueueElemPtrVector
using ompl::geometric::BITstar::SearchQueue::EdgeQueueElemPtrVector = std::vector<EdgeQueueElemPtr> |
A vector of edge queue pointers.
Definition at line 87 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 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:
- ompl/geometric/planners/informedtrees/bitstar/SearchQueue.h
- ompl/geometric/planners/informedtrees/bitstar/src/SearchQueue.cpp