Template Class KStarStrategy

Inheritance Relationships

Base Type

Class Documentation

template<class Milestone>
class KStarStrategy : public ompl::geometric::KStrategy<Milestone>

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.

External documentation

S. Karaman and E. Frazzoli Sampling-based algorithms for optimal motion planning, Int. Journal of Robotics Research Volume 30, Number 7, June 2010

Public Types

using NumNeighborsFn = std::function<unsigned int()>

Public Functions

inline KStarStrategy(const NumNeighborsFn &n, const std::shared_ptr<NearestNeighbors<Milestone>> &nn, const unsigned int d = 1)

Constructor.

Parameters:

  • 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.

inline const std::vector<Milestone> &operator()(const Milestone &m)

Protected Attributes

const NumNeighborsFn n_

Function returning the number of milestones added to the roadmap so far.

const double kPRMConstant_