Public Types | Public Member Functions | List of all members
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 &currentHeuristicVertex, const EdgeHeuristicFunc &lowerBoundHeuristicEdge, const EdgeHeuristicFunc &currentHeuristicEdge, const EdgeHeuristicFunc &currentHeuristicEdgeTarget)
 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: