ompl::geometric::BITstar::IntegratedQueue Class Reference
A queue of edges to be processed that integrates both the expansion of Vertices and the ordering of the resulting edges. More...
#include <ompl/geometric/planners/bitstar/datastructures/IntegratedQueue.h>
Public Types | |
| typedef std::pair< ompl::base::Cost, ompl::base::Cost > | CostPair |
| A typedef for a pair of costs, i.e., the edge sorting key. | |
| typedef std::function< ompl::base::Cost(const VertexConstPtr &)> | VertexHeuristicFunc |
| A std::function definition of a heuristic function for a vertex. | |
| typedef std::function< ompl::base::Cost(const VertexConstPtrPair &)> | EdgeHeuristicFunc |
| A std::function definition of a heuristic function for an edge. | |
| typedef std::function< double(const VertexConstPtr &, const VertexConstPtr &)> | DistanceFunc |
| A std::function definition for the distance between two vertices. | |
| typedef std::function< unsigned int(const VertexPtr &, std::vector< VertexPtr > *)> | NeighbourhoodFunc |
| A std::function definition for the neighbourhood of a vertex . | |
Public Member Functions | |
| IntegratedQueue (const ompl::base::OptimizationObjectivePtr &opt, const DistanceFunc &distanceFunc, const NeighbourhoodFunc &nearSamplesFunc, const NeighbourhoodFunc &nearVerticesFunc, const VertexHeuristicFunc &lowerBoundHeuristicVertex, const VertexHeuristicFunc ¤tHeuristicVertex, const EdgeHeuristicFunc &lowerBoundHeuristicEdge, const EdgeHeuristicFunc ¤tHeuristicEdge, const EdgeHeuristicFunc ¤tHeuristicEdgeTarget) | |
| Construct an integrated queue. | |
| void | setDelayedRewiring (bool delayRewiring) |
| Delay considering rewiring edges until an initial solution is found. This improves the time required to find an initial solution when doing so requires multiple batches and has no effects on theoretical asymptotic optimality (as the rewiring edges are eventually considered). | |
| bool | getDelayedRewiring () const |
| Get whether BIT* is delaying rewiring until a solution is found. | |
| void | insertVertex (const VertexPtr &newVertex) |
| Insert a vertex into the vertex expansion queue. Vertices remain in the vertex queue until pruned or manually removed. A moving token marks the line between expanded and not expanded vertices. | |
| void | insertEdge (const VertexPtrPair &newEdge) |
| Insert an edge into the edge processing queue. Edges are removed from the processing queue. This is only valid if the source vertex is already in the expansion queue (though it may already be expanded). | |
| void | eraseVertex (const VertexPtr &oldVertex, bool disconnectParent, const VertexPtrNNPtr &vertexNN, const VertexPtrNNPtr &freeStateNN, std::vector< VertexPtr > *recycledVertices) |
| Erase a vertex from the vertex expansion queue. Will disconnect the vertex from its parent and remove the associated incoming and outgoing edges from the edge queue as requested. | |
| VertexPtr | frontVertex () |
| Get the best vertex on the queue without incrementing the vertex queue. | |
| VertexPtrPair | frontEdge () |
| Get the best edge on the queue, leaving it on the edge queue. | |
| ompl::base::Cost | frontVertexValue () |
| Get the value of the best vertex on the queue without incrementing the vertex queue. | |
| CostPair | frontEdgeValue () |
| Get the value of the best edge on the queue, leaving it on the edge queue. | |
| void | popFrontEdge (VertexPtrPair *bestEdge) |
| Pop the best edge off the queue, removing it from the edge queue in the process. | |
| VertexPtrPair | popFrontEdge () |
| Pop the best edge off the queue, removing it from the edge queue in the process. | |
| void | hasSolution () |
| Mark that a solution has been found. | |
| void | setThreshold (const ompl::base::Cost &costThreshold) |
| Set the threshold of the queue. | |
| ompl::base::Cost | getThreshold () const |
| Get the threshold of the queue. | |
| void | removeEdgesTo (const VertexPtr &cVertex) |
| Erase all edges in the edge queue that lead to the given vertex. | |
| void | removeEdgesFrom (const VertexPtr &pVertex) |
| Erase all edges in the edge queue that leave from the given vertex. | |
| void | pruneEdgesTo (const VertexPtr &cVertex) |
| Prune edges in the edge queue that lead to the given vertex using the prune function. | |
| void | pruneEdgesFrom (const VertexPtr &pVertex) |
| Prune edges in the edge queue that leave from the given vertex using the prune function. | |
| void | markVertexUnsorted (const VertexPtr &vertex) |
| Mark the queue as requiring resorting downstream of the specified vertex. | |
| std::pair< unsigned int, unsigned int > | prune (const VertexPtr &pruneStartPtr, const VertexPtrNNPtr &vertexNN, const VertexPtrNNPtr &freeStateNN, std::vector< VertexPtr > *recycledVertices) |
| Prune the vertex queue of vertices whose their lower-bound heuristic is greater then the threshold. Descendents of pruned vertices that are not pruned themselves are returned to the set of free states. Returns the number of vertices pruned (either removed completely or moved to the set of free states). | |
| std::pair< unsigned int, unsigned int > | resort (const VertexPtrNNPtr &vertexNN, const VertexPtrNNPtr &freeStateNN, std::vector< VertexPtr > *recycledVertices) |
| Resort the queue, only reinserting edges/vertices if their lower-bound heuristic is less then the threshold. Descendents of pruned vertices that are not pruned themselves are returned to the set of free states. Requires first marking the queue as unsorted. Returns the number of vertices pruned (either removed completely or moved to the set of free states). | |
| void | finish () |
| Finish the queue, clearing all the edge containers and moving the vertex expansion token to the end. After a call to finish, isEmpty() will return true. Keeps threshold, list of unsorted vertices, etc. | |
| void | reset () |
| Reset the queue, clearing all the edge containers and moving the vertex expansion token to the start. After a call to reset, isEmpty() will return false (unless there is no data in the queue of course). Keeps threshold, list of unsorted vertices, etc. | |
| void | clear () |
| Clear the queue to the state of construction. | |
| bool | vertexPruneCondition (const VertexPtr &vertex) const |
| The condition used to prune vertices out of the queue. Compares lowerBoundHeuristicVertex to the given threshold. Returns true if the vertex's best cost is greater than the internally set threshold. Used internally during resort() | |
| bool | samplePruneCondition (const VertexPtr &vertex) const |
| The condition used to prune disconnected samples from the free set. Compares lowerBoundHeuristicVertex to the given threshold. Returns true if the vertex's best cost is greater than or equal to the internally set threshold. Used internally during resort() | |
| bool | edgePruneCondition (const VertexPtrPair &edge) const |
| The condition used to prune edge (i.e., vertex-pair) out of the queue. Compares lowerBoundHeuristicEdge to the given threshold. Returns true if the edge's best cost is greater than the internally set threshold. Used internally during resort() | |
| unsigned int | numEdges () const |
| Returns the number of edges in the queue. | |
| unsigned int | numVertices () const |
| Returns the number of vertices left to expand. This has nontrivial cost, as the token must be moved through the list to count. | |
| unsigned int | numEdgesTo (const VertexPtr &cVertex) const |
| Get the number of edges in the queue pointing to a specific vertex. | |
| unsigned int | numEdgesFrom (const VertexPtr &pVertex) const |
| Get the number of edges in the queue coming from a specific vertex. | |
| bool | isSorted () const |
| Return whether the queue is still sorted. | |
| bool | isReset () const |
| Returns true if the queue is reset. This means that no edges have been expanded and the vertex expansion token is pointing at the start. | |
| 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. | |
| bool | isVertexExpanded (const VertexConstPtr &vertex) const |
| Returns whether a given vertex has been expanded or not. | |
| void | listVertices (std::vector< VertexConstPtr > *vertexQueue) |
| Get a copy of the vertices in the vertex queue that are left to be expanded. This is expensive and is only meant for animations/debugging. | |
| void | listEdges (std::vector< std::pair< VertexConstPtr, VertexConstPtr > > *edgeQueue) |
| Get a copy of the edge queue. This is expensive and is only meant for animations/debugging. | |
Detailed Description
A queue of edges to be processed that integrates both the expansion of Vertices and the ordering of the resulting edges.
- Short Description
- An integrated two-stage queue that consists of vertices expanded into edges to be processed. The integrated queue consists of a vertex expansion queue and an edge processing queue. Vertices are expanded as needed from the vertex queue into edges places in the edge queue. Edges are removed from the edge queue for processing by BIT*. The vertex queue is implemented as a static ordered list of the vertices in the graph with a token (i.e., an iterator) pointing to the next vertex that needs to be expanded. This is specifically a multimap ordered on ompl::base::Cost The edge queue is implemented as an ordered list of potential edges. It is filled by the vertex queue and emptied by popping the best value off the front. It is specifically a multimap ordered on std::pair<ompl::base::Cost, ompl::base::Cost>
- Notes:
- An eraseEdge() function could be made by mimicking the vertex -> vertexQueue_::iterator lookup datastructure for the edgeQueue_
Definition at line 90 of file IntegratedQueue.h.
The documentation for this class was generated from the following files:
- ompl/geometric/planners/bitstar/datastructures/IntegratedQueue.h
- ompl/geometric/planners/bitstar/datastructures/src/IntegratedQueue.cpp