Make the minimal number of connections required to ensure asymptotic optimality. More...
#include <ConnectionStrategy.h>
Public Types | |
typedef boost::function < unsigned int()> | NumNeighborsFn |
Public Member Functions | |
KStarStrategy (const NumNeighborsFn &n, const boost::shared_ptr< NearestNeighbors< Milestone > > &nn, const unsigned int d=1) | |
Constructor. | |
std::vector< Milestone > & | operator() (const Milestone &m) |
Given a milestone m, find the number of nearest neighbors connection attempts that should be made from it, according to the connection strategy. | |
![]() | |
KStrategy (const unsigned int k, const boost::shared_ptr< NearestNeighbors< Milestone > > &nn) | |
Constructor takes the maximum number of nearest neighbors to return (k) and the nearest neighbors datastruture to use (nn) | |
void | setNearestNeighbors (const boost::shared_ptr< NearestNeighbors< Milestone > > &nn) |
Set the nearest neighbors datastructure to use. |
Protected Attributes | |
const NumNeighborsFn | n_ |
Function returning the number of milestones added to the roadmap so far. | |
const double | kPRMConstant_ |
![]() | |
unsigned int | k_ |
Maximum number of nearest neighbors to attempt to connect new milestones to. | |
boost::shared_ptr < NearestNeighbors< Milestone > > | nn_ |
Nearest neighbors data structure. | |
std::vector< Milestone > | neighbors_ |
Scratch space for storing k-nearest neighbors. |
Make the minimal number of connections required to ensure asymptotic optimality.
This connection strategy attempts to connect a milestone to its k-nearest neighbors where k is a function of the number of milestones that have already been added to the roadmap (n).
k(n) = kPRMConstant * log(n)
where
kPRMConstant > kStarPRMConstant = e(1 + 1/d)
and d is the number of dimensions in the state space. Note that kPRMConstant = 2e is a valid choice for any problem instance and so, if d is not provided, this value is used.
The user must provide a function that returns the value of n.
Definition at line 126 of file ConnectionStrategy.h.
|
inline |
Constructor.
n | a function that returns the number of milestones that have already been added to the roadmap |
nn | the nearest neighbors datastruture to use |
d | the dimensionality of the state space. The default is 1, which will make kPRMConstant=2e which is valid for all problem instances. |
Definition at line 139 of file ConnectionStrategy.h.