Classes |
Public Types |
Public Member Functions |
Protected Member Functions |
Protected Attributes |
List of all members
ompl::geometric::BITstar Class Reference
Batch Informed Trees (BIT*) More...
#include <ompl/geometric/planners/bitstar/BITstar.h>
Inheritance diagram for ompl::geometric::BITstar:
Classes | |
| class | IdGenerator |
| An ID generator class for vertex IDs. More... | |
| class | IntegratedQueue |
| A queue of edges to be processed that integrates both the expansion of Vertices and the ordering of the resulting edges. More... | |
| class | Vertex |
| The vertex of the underlying graphs in BIT*. More... | |
Public Types | |
| typedef std::shared_ptr< Vertex > | VertexPtr |
| A vertex shared pointer. | |
| typedef std::shared_ptr< const Vertex > | VertexConstPtr |
| A constant vertex shared pointer. | |
| typedef std::weak_ptr< Vertex > | VertexWeakPtr |
| A vertex weak pointer. | |
| typedef std::shared_ptr< IntegratedQueue > | IntegratedQueuePtr |
| An integrated queue shared pointer. | |
| typedef unsigned int | VertexId |
| The vertex id type. | |
| typedef std::pair< VertexPtr, VertexPtr > | VertexPtrPair |
| A pair of vertices, i.e., an edge. | |
| typedef std::pair< VertexConstPtr, VertexConstPtr > | VertexConstPtrPair |
| A pair of const vertices, i.e., an edge. | |
| typedef std::shared_ptr< NearestNeighbors< VertexPtr > > | VertexPtrNNPtr |
| The OMPL::NearestNeighbors structure. | |
 Public Types inherited from ompl::base::Planner | |
| typedef std::function< std::string()> | PlannerProgressProperty |
| Definition of a function which returns a property about the planner's progress that can be queried by a benchmarking routine. | |
| typedef std::map< std::string, PlannerProgressProperty > | PlannerProgressProperties |
| A dictionary which maps the name of a progress property to the function to be used for querying that property. | |
Public Member Functions | |
| BITstar (const base::SpaceInformationPtr &si, const std::string &name="BITstar") | |
| Construct! | |
| virtual | ~BITstar () |
| Destruct! | |
| virtual void | setup () |
| Setup. | |
| virtual void | clear () |
| Clear. | |
| base::PlannerStatus | solve (const base::PlannerTerminationCondition &ptc) |
| Solve. | |
| virtual void | getPlannerData (base::PlannerData &data) const |
| Get results. | |
| std::pair< const ompl::base::State *, const ompl::base::State * > | getNextEdgeInQueue () |
| Get the next edge to be processed. Causes vertices in the queue to be expanded (if necessary) and therefore effects the run timings of the algorithm, but helpful for some videos and debugging. | |
| ompl::base::Cost | getNextEdgeValueInQueue () |
| Get the value of the next edge to be processed. Causes vertices in the queue to be expanded (if necessary) and therefore effects the run timings of the algorithm, but helpful for some videos and debugging. | |
| void | getEdgeQueue (std::vector< std::pair< VertexConstPtr, VertexConstPtr > > *edgesInQueue) |
| Get the whole messy set of edges in the queue. Expensive but helpful for some videos. | |
| void | getVertexQueue (std::vector< VertexConstPtr > *verticesInQueue) |
| Get the whole set of vertices to be expanded. Expensive but helpful for some videos. | |
| unsigned int | numIterations () const |
| Get the number of iterations completed. | |
| ompl::base::Cost | bestCost () const |
| Retrieve the best exact-solution cost found. | |
| template<template< typename T > class NN> | |
| void | setNearestNeighbors () |
| Set a different nearest neighbours datastructure. | |
| void | setRewireFactor (double rewireFactor) |
| Set the rewiring scale factor, s, such that r_rrg = s r_rrg*. | |
| double | getRewireFactor () const |
| Get the rewiring scale factor. | |
| void | setSamplesPerBatch (unsigned int n) |
| Set the number of samplers per batch. | |
| unsigned int | getSamplesPerBatch () const |
| Get the number of samplers per batch. | |
| void | setKNearest (bool useKNearest) |
| Enable a k-nearest search for instead of an r-disc search. | |
| bool | getKNearest () const |
| Get whether a k-nearest search is being used. | |
| void | setStrictQueueOrdering (bool beStrict) |
| Enable "strict sorting" of the edge queue. Rewirings can change the position in the queue of an edge. When strict sorting is enabled, the effected edges are resorted immediately, while disabling strict sorting delays this resorting until the end of the batch. | |
| bool | getStrictQueueOrdering () const |
| Get whether strict queue ordering is in use. | |
| void | setPruning (bool prune) |
| Enable pruning of vertices/samples that CANNOT improve the current solution. When a vertex in the graph is pruned, it's descendents are also pruned (if they also cannot improve the solution) or placed back in the set of free samples (if they could improve the solution). This assures that a uniform density is maintained. | |
| bool | getPruning () const |
| Get whether graph and sample pruning is in use. | |
| void | setPruneThresholdFraction (double fractionalChange) |
| Set the fractional change in the solution cost necessary for pruning to occur. | |
| double | getPruneThresholdFraction () const |
| Get the fractional change in the solution cost necessary for pruning to occur. | |
| void | setDelayRewiringUntilInitialSolution (bool delayRewiring) |
| Delay the consideration of rewiring edges until an initial solution is found. When multiple batches are required to find an initial solution, this can improve the time required to do so, by delaying improvements in the cost-to-come to a connected vertex. As the rewiring edges are considered once an initial solution is found, this has no effect on the theoretical asymptotic optimality of the planner. More... | |
| bool | getDelayRewiringUntilInitialSolution () const |
| Get whether BIT* is delaying rewiring until a solution is found. | |
| void | setJustInTimeSampling (bool useJit) |
| Delay the generation of samples until they are necessary. This only works when using an r-disc connection scheme, and is currently only implemented for problems seeking to minimize path length. This helps reduce the complexity of nearest-neighbour look ups, and can be particularly beneficial in unbounded planning problems where selecting an appropriate bounding box is difficult. With JIT sampling enabled, BIT* can solve planning problems whose state space has infinite boundaries. When enumerating outgoing edges from a vertex, BIT* uses JIT sampling to assure that the area within r of the vertex has been sampled during this batch. This is done in a way that maintains uniform sample distribution and has no effect on the theoretical asymptotic optimality of the planner. More... | |
| bool | getJustInTimeSampling () const |
| Get whether we're using just-in-time sampling. | |
| void | setDropSamplesOnPrune (bool dropSamples) |
| Drop all unconnected samples when pruning, regardless of their heuristic value. This provides a method for BIT* to remove samples that have not been connected to the graph and may be beneficial in problems where portions of the free space are unreachable (i.e., disconnected). BIT* calculates the connection radius for each batch from the underlying uniform distribution of states. The resulting larger connection radius may be detrimental in areas where the graph is dense, but maintains the theoretical asymptotic optimality of the planner. More... | |
| bool | getDropSamplesOnPrune () const |
| Get whether unconnected samples are dropped on pruning. | |
| void | setStopOnSolnImprovement (bool stopOnChange) |
| Stop the planner each time a solution improvement is found. Useful for examining the intermediate solutions found by BIT*. | |
| bool | getStopOnSolnImprovement () const |
| Get whether BIT* stops each time a solution is found. | |
| Public Member Functions inherited from ompl::base::Planner | |
| Planner (const Planner &)=delete | |
| Planner & | operator= (const Planner &)=delete |
| Planner (const SpaceInformationPtr &si, const std::string &name) | |
| Constructor. | |
| virtual | ~Planner () |
| Destructor. | |
| template<class T > | |
| T * | as () |
| Cast this instance to a desired type. More... | |
| template<class T > | |
| const T * | as () const |
| Cast this instance to a desired type. More... | |
| const SpaceInformationPtr & | getSpaceInformation () const |
| Get the space information this planner is using. | |
| const ProblemDefinitionPtr & | getProblemDefinition () const |
| Get the problem definition the planner is trying to solve. | |
| const PlannerInputStates & | getPlannerInputStates () const |
| Get the planner input states. | |
| virtual void | setProblemDefinition (const ProblemDefinitionPtr &pdef) |
| Set the problem definition for the planner. The problem needs to be set before calling solve(). Note: If this problem definition replaces a previous one, it may also be necessary to call clear(). | |
| PlannerStatus | solve (const PlannerTerminationConditionFn &ptc, double checkInterval) |
| Same as above except the termination condition is only evaluated at a specified interval. | |
| PlannerStatus | solve (double solveTime) |
| Same as above except the termination condition is solely a time limit: the number of seconds the algorithm is allowed to spend planning. | |
| const std::string & | getName () const |
| Get the name of the planner. | |
| void | setName (const std::string &name) |
| Set the name of the planner. | |
| const PlannerSpecs & | getSpecs () const |
| Return the specifications (capabilities of this planner) | |
| virtual void | checkValidity () |
| Check to see if the planner is in a working state (setup has been called, a goal was set, the input states seem to be in order). In case of error, this function throws an exception. | |
| bool | isSetup () const |
| Check if setup() was called for this planner. | |
| ParamSet & | params () |
| Get the parameters for this planner. | |
| const ParamSet & | params () const |
| Get the parameters for this planner. | |
| const PlannerProgressProperties & | getPlannerProgressProperties () const |
| Retrieve a planner's planner progress property map. | |
| virtual void | printProperties (std::ostream &out) const |
| Print properties of the motion planner. | |
| virtual void | printSettings (std::ostream &out) const |
| Print information about the motion planner's settings. | |
Protected Member Functions | |
| void | estimateMeasures () |
| A debug function: Estimate the measure of the free/obstace space via sampling. | |
| virtual void | iterate () |
| A single iteration. | |
| void | newBatch () |
| Initialize variables for a new batch. | |
| void | updateSamples (const VertexConstPtr &vertex) |
| Update the list of free samples. | |
| virtual bool | prune () |
| Prune the problem. Returns true if pruning was done. | |
| virtual bool | resort () |
| Resort the queue. Returns true if any pruning was done. | |
| void | publishSolution () |
| Publish the found solution to the ProblemDefinition. | |
| std::vector< const ompl::base::State * > | bestPathFromGoalToStart () const |
| Extract the best solution, ordered from the goal to the start and including both the goal and the start. Used by both publishSolution and the ProblemDefinition::IntermediateSolutionCallback. | |
| void | updateStartAndGoalStates (const base::PlannerTerminationCondition &ptc) |
| Adds any new goals or starts that have appeared in the problem definition to the list of vertices and the queue. Creates a new informed sampler. Returns true if new starts/goals are created. | |
| void | pruneStartsGoals () |
| Prune the starts and goals that have a solution heuristic that is not less than bestCost_. | |
| void | pruneSamples () |
| Prune all samples with a solution heuristic that is not less than the bestCost_. | |
| bool | checkEdge (const VertexConstPtrPair &edge) |
| Checks an edge for collision. A wrapper to SpaceInformation->checkMotion that tracks number of collision checks. | |
| void | dropSample (VertexPtr oldSample) |
| Actually remove a sample from its NN struct. | |
| void | addEdge (const VertexPtrPair &newEdge, const ompl::base::Cost &edgeCost, const bool &removeFromFree, const bool &updateDescendants) |
| Add an edge from the edge queue to the tree. Will add the state to the vertex queue if it's new to the tree or otherwise replace the parent. Updates solution information if the solution improves. | |
| void | replaceParent (const VertexPtrPair &newEdge, const ompl::base::Cost &edgeCost, const bool &updateDescendants) |
| Replace the parent edge with the given new edge and cost. | |
| void | updateGoalVertex () |
| The special work that needs to be done to update the goal vertex is the solution has changed. | |
| void | addSample (const VertexPtr &newSample) |
| Add a sample. | |
| void | addVertex (const VertexPtr &newVertex, const bool &removeFromFree) |
| Add a vertex to the graph. | |
| unsigned int | nearestSamples (const VertexPtr &vertex, std::vector< VertexPtr > *neighbourSamples) |
| Get the nearest samples from the freeStateNN_ using the appropriate "near" definition (i.e., k or r). If using k-nearest, returns the target k, otherwise returns 0u. | |
| unsigned int | nearestVertices (const VertexPtr &vertex, std::vector< VertexPtr > *neighbourVertices) |
| Get the nearest samples from the vertexNN_ using the appropriate "near" definition (i.e., k or r). If using k-nearest, returns the target k, otherwise returns 0u. | |
| double | nnDistance (const VertexConstPtr &a, const VertexConstPtr &b) const |
| The distance function used for nearest neighbours. Calculates the distance directionally from the given state to all the other states (can be used on states either in our out of the graph). | |
| ompl::base::Cost | lowerBoundHeuristicVertex (const VertexConstPtr &vertex) const |
| Calculates a heuristic estimate of the cost of a solution constrained to pass through a vertex, independent of the current cost-to-come. I.e., combines the heuristic estimates of the cost-to-come and cost-to-go. | |
| ompl::base::Cost | currentHeuristicVertex (const VertexConstPtr &vertex) const |
| Calculates a heuristic estimate of the cost of a solution constrained to pass through a vertex, dependent on the current cost-to-come. I.e., combines the current cost-to-come with a heuristic estimate of the cost-to-go. | |
| ompl::base::Cost | lowerBoundHeuristicEdge (const VertexConstPtrPair &edgePair) const |
| Calculates a heuristic estimate of the cost of a solution constrained to go through an edge, independent of the cost-to-come of the parent state. I.e., combines the heuristic estimates of the cost-to-come, edge cost, and cost-to-go. | |
| ompl::base::Cost | currentHeuristicEdge (const VertexConstPtrPair &edgePair) const |
| Calculates a heuristic estimate of the cost of a solution constrained to go through an edge, dependent on the cost-to-come of the parent state. I.e., combines the current cost-to-come with heuristic estimates of the edge cost, and cost-to-go. | |
| ompl::base::Cost | currentHeuristicEdgeTarget (const VertexConstPtrPair &edgePair) const |
| Calculates a heuristic estimate of the cost of a path to the target of an edge, dependent on the cost-to-come of the parent state. I.e., combines the current cost-to-come with heuristic estimates of the edge cost. | |
| ompl::base::Cost | costToComeHeuristic (const VertexConstPtr &vertex) const |
| Calculate a heuristic estimate of the cost-to-come for a Vertex. | |
| ompl::base::Cost | edgeCostHeuristic (const VertexConstPtrPair &edgePair) const |
| Calculate a heuristic estimate of the cost an edge between two Vertices. | |
| ompl::base::Cost | costToGoHeuristic (const VertexConstPtr &vertex) const |
| Calculate a heuristic estimate of the cost-to-go for a Vertex. | |
| ompl::base::Cost | trueEdgeCost (const VertexConstPtrPair &edgePair) const |
| The true cost of an edge, including collisions. | |
| ompl::base::Cost | neighbourhoodCost (const VertexConstPtr &vertex) const |
| Calculate the max req'd cost to define a neighbourhood around a state. Currently only implemented for path-length problems, for which the neighbourhood cost is the f-value of the vertex plus 2r. | |
| bool | isCostWorseThan (const ompl::base::Cost &a, const ompl::base::Cost &b) const |
| Compare whether cost a is worse than cost b by checking whether b is better than a. | |
| bool | isCostNotEquivalentTo (const ompl::base::Cost &a, const ompl::base::Cost &b) const |
| Compare whether cost a and cost b are not equivalent by checking if either a or b is better than the other. | |
| bool | isCostBetterThanOrEquivalentTo (const ompl::base::Cost &a, const ompl::base::Cost &b) const |
| Compare whether cost a is better or equivalent to cost b by checking that b is not better than a. | |
| bool | isCostWorseThanOrEquivalentTo (const ompl::base::Cost &a, const ompl::base::Cost &b) const |
| Compare whether cost a is worse or equivalent to cost b by checking that a is not better than b. | |
| ompl::base::Cost | combineCosts (const ompl::base::Cost &a, const ompl::base::Cost &b, const ompl::base::Cost &c) const |
| Combine 3 costs. | |
| ompl::base::Cost | combineCosts (const ompl::base::Cost &a, const ompl::base::Cost &b, const ompl::base::Cost &c, const ompl::base::Cost &d) const |
| Combine 4 costs. | |
| double | fractionalChange (const ompl::base::Cost &newCost, const ompl::base::Cost &oldCost) const |
| Calculate the fractional change of cost "newCost" from "oldCost" relative to "oldCost", i.e., (newCost - oldCost)/oldCost. | |
| double | fractionalChange (const ompl::base::Cost &newCost, const ompl::base::Cost &oldCost, const ompl::base::Cost &refCost) const |
| Calculate the fractional change of cost "newCost" from "oldCost" relative to "refCost", i.e., (newCost - oldCost)/refCost. | |
| void | initializeNearestTerms () |
| Initialize the nearest-neighbour terms. | |
| virtual void | updateNearestTerms () |
| Update the appropriate nearest-neighbour terms, r_ and k_. Performs this calculation considering the "future" samples to be added in this batch, except on the first batch. | |
| double | calculateR (unsigned int N) const |
| Calculate the r for r-disc nearest neighbours, a function of the current graph. | |
| unsigned int | calculateK (unsigned int N) const |
| Calculate the k for k-nearest neighours, a function of the current graph. | |
| double | minimumRggR () const |
| Calculate the lower-bounding radius RGG term for asymptotic almost-sure convergence to the optimal path (i.e., r_rrg* in Karaman and Frazzoli IJRR 11). This is a function of the size of the problem domain. | |
| double | minimumRggK () const |
| Calculate the lower-bounding k-nearest RGG term for asymptotic almost-sure convergence to the optimal path (i.e., k_rrg* in Karaman and Frazzoli IJRR 11). This is a function of the state dimension and is left as a double for later accuracy in calculate k. | |
| virtual void | goalMessage () const |
| The message printed when a goal is found/improved. | |
| virtual void | endSuccessMessage () const |
| The message printed when solve finishes successfully. | |
| virtual void | endFailureMessage () const |
| The message printed when solve finishes unsuccessfully. | |
| virtual void | statusMessage (const ompl::msg::LogLevel &msgLevel, const std::string &status) const |
| A debug-level status message for debugging. | |
| std::string | bestCostProgressProperty () const |
| Retrieve the best exact-solution cost found as a planner-progress property. (bestCost_) | |
| std::string | bestLengthProgressProperty () const |
| Retrieve the length of the best exact-solution found as a planner-progress property. (bestLength_) | |
| std::string | currentFreeProgressProperty () const |
| Retrieve the current number of free samples as a planner-progress property. (size of freeStateNN_) | |
| std::string | currentVertexProgressProperty () const |
| Retrieve the current number of vertices in the graph as a planner-progress property. (Size of vertexNN_) | |
| std::string | vertexQueueSizeProgressProperty () const |
| Retrieve the current number of vertices in the expansion queue as a planner-progress property. (The position of the vertex subqueue of intQueue_) | |
| std::string | edgeQueueSizeProgressProperty () const |
| Retrieve the current number of edges in the search queue as a planner-progress property. (The size of the edge subqueue of intQueue_) | |
| std::string | iterationProgressProperty () const |
| Retrieve the number of iterations as a planner-progress property. (numIterations_) | |
| unsigned int | numBatches () const |
| Retrieve the number of batches processed as the raw data. (numBatches_) | |
| std::string | batchesProgressProperty () const |
| Retrieve the number of batches processed as a planner-progress property. (numBatches_) | |
| std::string | pruningProgressProperty () const |
| Retrieve the number of graph prunings performed as a planner-progress property. (numPrunings_) | |
| virtual std::string | totalStatesCreatedProgressProperty () const |
| Retrieve the total number of states generated as a planner-progress property. (numSamples_) | |
| std::string | verticesConstructedProgressProperty () const |
| Retrieve the total number of vertices added to the graph as a planner-progress property. (numVertices_) | |
| std::string | statesPrunedProgressProperty () const |
| Retrieve the number of states pruned from the problem as a planner-progress property. (numFreeStatesPruned_) | |
| std::string | verticesDisconnectedProgressProperty () const |
| Retrieve the number of graph vertices that are disconnected and either returned to the set of free samples or deleted completely as a planner-progress property. (numVerticesDisconnected_) | |
| std::string | rewiringProgressProperty () const |
| Retrieve the number of global-search edges that rewired the graph as a planner-progress property. (numRewirings_) | |
| std::string | stateCollisionCheckProgressProperty () const |
| Retrieve the number of state collisions checks (i.e., calls to SpaceInformation::isValid(...)) as a planner-progress property. (numStateCollisionChecks_) | |
| std::string | edgeCollisionCheckProgressProperty () const |
| Retrieve the number of edge (or motion) collision checks (i.e., calls to SpaceInformation::checkMotion(...)) as a planner-progress property. (numEdgeCollisionChecks_) | |
| std::string | nearestNeighbourProgressProperty () const |
| Retrieve the number of nearest neighbour calls (i.e., NearestNeighbors<T>::nearestK(...) or NearestNeighbors<T>::nearestR(...)) as a planner-progress property. (numNearestNeighbours_) | |
| std::string | edgesProcessedProgressProperty () const |
| Retrieve the total number of edges processed from the queue as a planner-progress property. (numEdgesProcessed_) | |
| Protected Member Functions inherited from ompl::base::Planner | |
| template<typename T , typename PlannerType , typename SetterType , typename GetterType > | |
| void | declareParam (const std::string &name, const PlannerType &planner, const SetterType &setter, const GetterType &getter, const std::string &rangeSuggestion="") |
| This function declares a parameter for this planner instance, and specifies the setter and getter functions. | |
| template<typename T , typename PlannerType , typename SetterType > | |
| void | declareParam (const std::string &name, const PlannerType &planner, const SetterType &setter, const std::string &rangeSuggestion="") |
| This function declares a parameter for this planner instance, and specifies the setter function. | |
| void | addPlannerProgressProperty (const std::string &progressPropertyName, const PlannerProgressProperty &prop) |
| Add a planner progress property called progressPropertyName with a property querying function prop to this planner's progress property map. | |
Protected Attributes | |
| ompl::RNG | rng_ |
| An instance of a random number generator. | |
| ompl::base::InformedSamplerPtr | sampler_ |
| State sampler. | |
| ompl::base::OptimizationObjectivePtr | opt_ |
| Optimization objective copied from ProblemDefinition. | |
| std::list< VertexPtr > | startVertices_ |
| The start states of the problem as vertices. | |
| std::list< VertexPtr > | goalVertices_ |
| The goal states of the problem as vertices. | |
| std::list< VertexPtr > | prunedStartVertices_ |
| Any start states of the problem that have been pruned. | |
| std::list< VertexPtr > | prunedGoalVertices_ |
| Any goal states of the problem that have been pruned. | |
| VertexPtr | curGoalVertex_ |
| The goal vertex of the current best solution. | |
| VertexPtrNNPtr | freeStateNN_ |
| The unconnected samples as a nearest-neighbours datastructure. Sorted by nnDistance. Size accessible via currentFreeProgressProperty. | |
| VertexPtrNNPtr | vertexNN_ |
| The vertices as a nearest-neighbours data structure. Sorted by nnDistance. Size accessible via currentVertexProgressProperty. | |
| IntegratedQueuePtr | intQueue_ |
| The integrated queue of vertices to expand and edges to process ordered on "f-value", i.e., estimated solution cost. Remaining vertex queue "size" and edge queue size are accessible via vertexQueueSizeProgressProperty and edgeQueueSizeProgressProperty, respectively. | |
| std::vector< VertexPtr > | newSamples_ |
| A copy of the new samples from this batch. | |
| std::vector< VertexPtr > | recycledSamples_ |
| A copy of the vertices recycled into samples during this batch. | |
| unsigned int | numUniformStates_ |
| The number of states (vertices or samples) that were generated from a uniform distribution. Only valid when refreshSamplesOnPrune_ is true, in which case it's used to calculate the RGG term of the uniform subgraph. | |
| double | r_ |
| The current r-disc RGG connection radius. | |
| double | k_rgg_ |
| The minimum k-nearest RGG connection term. Only a function of state dimension, so can be calculated once. Left as a double for later accuracy in calculate k. | |
| unsigned int | k_ |
| The current k-nearest RGG connection number. | |
| ompl::base::Cost | bestCost_ |
| The best cost found to date. This is the maximum total-heuristic cost of samples we'll consider. Accessible via bestCostProgressProperty. | |
| unsigned int | bestLength_ |
| The number of vertices in the best solution found to date. Accessible via bestLengthProgressProperty. | |
| ompl::base::Cost | prunedCost_ |
| The cost to which the graph has been pruned. We will only prune the graph if bestCost_ is less than this value. | |
| double | prunedMeasure_ |
| The measure of the problem domain when we pruned the graph. | |
| ompl::base::Cost | minCost_ |
| The minimum possible solution cost. I.e., the heuristic value of the goal. | |
| ompl::base::Cost | costSampled_ |
| The total-heuristic cost up to which we've sampled. | |
| bool | hasSolution_ |
| If we've found a solution yet. | |
| bool | stopLoop_ |
| A manual stop on the solve loop. | |
| bool | approximateSoln_ |
| If the solution is approximate. | |
| double | approximateDiff_ |
| The distance of the approximate solution, set to -1.0 for non approximate solutions. | |
| unsigned int | numIterations_ |
| The number of iterations run. Accessible via iterationProgressProperty. | |
| unsigned int | numBatches_ |
| The number of batches processed. Accessible via batchesProgressProperty. | |
| unsigned int | numPrunings_ |
| The number of times the graph/samples have been pruned. Accessible via pruningProgressProperty. | |
| unsigned int | numSamples_ |
| The number of states generated through sampling. Accessible via statesFromSamplingProgressProperty. | |
| unsigned int | numVertices_ |
| The number of vertices ever added to the graph. Will count vertices twice if they spend any time disconnected. Accessible via verticesConstructedProgressProperty. | |
| unsigned int | numFreeStatesPruned_ |
| The number of free states that have been pruned. Accessible via statesPrunedProgressProperty. | |
| unsigned int | numVerticesDisconnected_ |
| The number of graph vertices that get disconnected. These either return to being free samples or are pruned completely. Accessible via verticesDisconnectedProgressProperty. | |
| unsigned int | numRewirings_ |
| The number of times a state in the graph was rewired. Accessible via rewiringProgressProperty. | |
| unsigned int | numStateCollisionChecks_ |
| The number of state collision checks. Accessible via stateCollisionCheckProgressProperty. | |
| unsigned int | numEdgeCollisionChecks_ |
| The number of edge collision checks. Accessible via edgeCollisionCheckProgressProperty. | |
| unsigned int | numNearestNeighbours_ |
| The number of nearest neighbour calls. Accessible via nearestNeighbourProgressProperty. | |
| unsigned int | numEdgesProcessed_ |
| The number of edges processed, in one way or other, from the queue. Accessible via edgesProcessedProgressProperty. | |
| bool | useStrictQueueOrdering_ |
| Whether to use a strict-queue ordering (param) | |
| double | rewireFactor_ |
| The rewiring factor, s, so that r_rrg = s r_rrg* > r_rrg* (param) | |
| unsigned int | samplesPerBatch_ |
| The number of samples per batch (param) | |
| bool | useKNearest_ |
| Option to use k-nearest search for rewiring (param) | |
| bool | usePruning_ |
| Whether to use graph pruning (param) | |
| double | pruneFraction_ |
| The fractional decrease in solution cost required to trigger pruning (param) | |
| bool | delayRewiring_ |
| Whether to delay rewiring until a solution is found (param) | |
| bool | useJustInTimeSampling_ |
| Whether to use just-in-time sampling (param) | |
| bool | dropSamplesOnPrune_ |
| Whether to refresh (i.e., forget) unconnected samples on pruning (param) | |
| bool | stopOnSolnChange_ |
| Whether to stop the planner as soon as the path changes (param) | |
| Protected Attributes inherited from ompl::base::Planner | |
| SpaceInformationPtr | si_ |
| The space information for which planning is done. | |
| ProblemDefinitionPtr | pdef_ |
| The user set problem definition. | |
| PlannerInputStates | pis_ |
| Utility class to extract valid input states. | |
| std::string | name_ |
| The name of this planner. | |
| PlannerSpecs | specs_ |
| The specifications of the planner (its capabilities) | |
| ParamSet | params_ |
| A map from parameter names to parameter instances for this planner. This field is populated by the declareParam() function. | |
| PlannerProgressProperties | plannerProgressProperties_ |
| A mapping between this planner's progress property names and the functions used for querying those progress properties. | |
| bool | setup_ |
| Flag indicating whether setup() has been called. | |
Detailed Description
Batch Informed Trees (BIT*)
BIT* (Batch Informed Trees) is an anytime almost surely asymptotically optimal sampling-based planning algorithm. It approaches problems by assuming that a simple solution exists and only goes onto consider complex solutions when that proves incorrect. It accomplishes this by using heuristics to search in order of decreasing potential solution quality.
Both a k-nearest and r-disc version are available, with the k-nearest selected by default. It is recommended that you try both variants, with the r-disc version being recommended if it finds an initial solution in a suitable amount of time (which it probably will). In general, both variants work, but for a small number of problems the calculation of the radius in the r-disc version appears to be too small and does not create an implicit graph that is sufficiently dense (hence the default choice). This is a question of the random geometric graph theory underpinning this type of almost surely asymptotically optimal planner and certainly merits further review.
This implementation of BIT* can handle multiple starts, multiple goals, a variety of optimization objectives (e.g., path length), and with just-in-time sampling, infinite problem domains. Note that for some of optimization objectives, the user must specify a suitable heuristic and that when this heuristic is not specified, it will use the conservative/always admissible zero-heuristic.
This implementation also includes some new advancements, including the ability to prioritize exploration until an initial solution is found (Delayed rewiring), the ability to generate samples only when necessary (Just-in-time sampling), and the ability to periodically remove samples that have yet to be connected to the graph (Sample dropping). With just-in-time sampling, BIT* can even solve planning problems with infinite state space boundaries, i.e., (-inf, inf).
- Associated publication:
J D. Gammell, S. S. Srinivasa, T. D. Barfoot, "Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs," In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). Seattle, WA, USA, 26-30 May 2015. DOI: 10.1109/ICRA.2015.7139620. Illustration video.
- Todo:
- Implement approximate solution support.
- Make the k-nearest variant correct. Right now the search considers the k-nearest samples and the k-nearest vertices. It should find the combined k-nearest "samples & vertices".
Member Function Documentation
| void ompl::geometric::BITstar::setDelayRewiringUntilInitialSolution | ( | bool | delayRewiring | ) |
Delay the consideration of rewiring edges until an initial solution is found. When multiple batches are required to find an initial solution, this can improve the time required to do so, by delaying improvements in the cost-to-come to a connected vertex. As the rewiring edges are considered once an initial solution is found, this has no effect on the theoretical asymptotic optimality of the planner.
Definition at line 2176 of file BITstar.cpp.
| void ompl::geometric::BITstar::setDropSamplesOnPrune | ( | bool | dropSamples | ) |
Drop all unconnected samples when pruning, regardless of their heuristic value. This provides a method for BIT* to remove samples that have not been connected to the graph and may be beneficial in problems where portions of the free space are unreachable (i.e., disconnected). BIT* calculates the connection radius for each batch from the underlying uniform distribution of states. The resulting larger connection radius may be detrimental in areas where the graph is dense, but maintains the theoretical asymptotic optimality of the planner.
Definition at line 2222 of file BITstar.cpp.
| void ompl::geometric::BITstar::setJustInTimeSampling | ( | bool | useJit | ) |
Delay the generation of samples until they are necessary. This only works when using an r-disc connection scheme, and is currently only implemented for problems seeking to minimize path length. This helps reduce the complexity of nearest-neighbour look ups, and can be particularly beneficial in unbounded planning problems where selecting an appropriate bounding box is difficult. With JIT sampling enabled, BIT* can solve planning problems whose state space has infinite boundaries. When enumerating outgoing edges from a vertex, BIT* uses JIT sampling to assure that the area within r of the vertex has been sampled during this batch. This is done in a way that maintains uniform sample distribution and has no effect on the theoretical asymptotic optimality of the planner.
Definition at line 2196 of file BITstar.cpp.
The documentation for this class was generated from the following files:
- ompl/geometric/planners/bitstar/BITstar.h
- ompl/geometric/planners/bitstar/src/BITstar.cpp