#include <KdTreeNF.h>

Inheritance diagram for KdTreeNF:

Collaboration diagram for KdTreeNF:

[legend]

Public Types
Motion Planning Types
typedef MPBaseObject::RoadmapType	RoadmapType

typedef RoadmapType::VI	VI

typedef RoadmapType::VID	VID

typedef RoadmapType::VertexSet	VertexSet

typedef RoadmapType::CCTrackerType	CCTrackerType

typedef MPBaseObject::GroupRoadmapType	GroupRoadmapType

typedef MPBaseObject::GroupCfgType	GroupCfgType

Local Types
enum class	Type
	The type of neighbors found. More...

typedef std::back_insert_iterator< std::vector< Neighbor > >	OutputIterator
	Output iterator for writing discovered neighbors to a container. More...

Public Types inherited from NeighborhoodFinderMethod
enum class	Type { K , RADIUS , APPROX , OTHER }
	The type of neighbors found. More...

typedef std::back_insert_iterator< std::vector< Neighbor > >	OutputIterator
	Output iterator for writing discovered neighbors to a container. More...

typedef MPBaseObject::RoadmapType	RoadmapType

typedef RoadmapType::VID	VID

typedef RoadmapType::VertexSet	VertexSet

typedef MPBaseObject::GroupRoadmapType	GroupRoadmapType

typedef MPBaseObject::GroupCfgType	GroupCfgType

Public Types inherited from MPBaseObject
typedef DefaultWeight< Cfg >	WeightType

typedef GenericStateGraph< Cfg, WeightType >	RoadmapType

typedef GroupCfg< RoadmapType >	GroupCfgType

typedef GroupLocalPlan< RoadmapType >	GroupWeightType

typedef GroupRoadmap< GroupCfgType, GroupWeightType >	GroupRoadmapType

Public Member Functions
Construction
	KdTreeNF ()

	KdTreeNF (XMLNode &_node)

virtual	~KdTreeNF ()=default

MPBaseObject Overrides
virtual void	Initialize () override

virtual void	Print (std::ostream &_os) const override

NeighborhoodFinder Functions
virtual void	FindNeighbors (RoadmapType *const _r, const Cfg &_cfg, const VertexSet &_candidates, OutputIterator _out) override

virtual void	FindNeighbors (GroupRoadmapType *const _r, const GroupCfgType &_cfg, const VertexSet &_candidates, OutputIterator _out) override

Public Member Functions inherited from NeighborhoodFinderMethod
	NeighborhoodFinderMethod (const Type _type=Type::OTHER)

	NeighborhoodFinderMethod (XMLNode &_node, const Type _type=Type::OTHER, const bool _requireDM=true)

virtual	~NeighborhoodFinderMethod ()=default

Type	GetType () const noexcept

virtual size_t &	GetK () noexcept

virtual double &	GetRadius () noexcept

virtual void	SetDMLabel (const std::string &_label) noexcept

virtual const std::string &	GetDMLabel () const noexcept

template<typename AbstractRoadmapType >
void	FindNeighbors (AbstractRoadmapType *const _r, const typename AbstractRoadmapType::CfgType &_cfg, OutputIterator _out)

Public Member Functions inherited from MPBaseObject
	MPBaseObject (const std::string &_label="", const std::string &_name="", bool _debug=false)

	MPBaseObject (XMLNode &_node)

virtual	~MPBaseObject ()

const std::string &	GetName () const
	Get the class name for this object. More...

const std::string &	GetLabel () const
	Get the unique label for this object. More...

std::string	GetNameAndLabel () const
	Get the unique string identifier for this object "m_name::m_label". More...

void	SetLabel (const std::string &)
	Set the unique label for this object. More...

void	SetMPLibrary (MPLibrary *) noexcept
	Set the owning MPLibrary. More...

MPLibrary *	GetMPLibrary () const noexcept
	Get the owning MPLibrary. More...

bool	IsRunning () const noexcept
	Check the library's running flag. More...

MPProblem *	GetMPProblem () const noexcept
	Get the library's current MPProblem. More...

Environment *	GetEnvironment () const noexcept
	Get the current environment. More...

MPTask *	GetTask () const noexcept
	Get the current task. More...

GroupTask *	GetGroupTask () const noexcept
	Get the current group task. More...

MPSolutionType *	GetMPSolution () const noexcept

RoadmapType *	GetRoadmap (Robot *const _r=nullptr) const noexcept
	Get the current free-space roadmap. More...

GroupRoadmapType *	GetGroupRoadmap (RobotGroup *const _g=nullptr) const noexcept
	Get the current free-space group roadmap. More...

RoadmapType *	GetBlockRoadmap (Robot *const _r=nullptr) const noexcept
	Get the current obstacle-space roadmap. More...

Path *	GetPath (Robot *const _r=nullptr) const noexcept

GroupPath *	GetGroupPath (RobotGroup *const _g=nullptr) const noexcept
	Get the current best group path. More...

StatClass *	GetStatClass () const noexcept
	Get the current StatClass. More...

LocalObstacleMap *	GetLocalObstacleMap () const noexcept
	Get the local obstacle map. More...

Additional Inherited Members
Protected Member Functions inherited from NeighborhoodFinderMethod
template<typename AbstractRoadmapType >
bool	DirectEdge (const AbstractRoadmapType *_g, const typename AbstractRoadmapType::CfgType &_c, const typename AbstractRoadmapType::VID _v) const noexcept

Protected Member Functions inherited from MPBaseObject
void	SetName (const std::string &_s)

const std::string &	GetBaseFilename () const

Protected Attributes inherited from NeighborhoodFinderMethod
Type	m_nfType {Type::OTHER}
	Type of neighborhood finder. More...

size_t	m_k {0}
	How many closest neighbors to find? More...

double	m_radius {0}
	Maximum distance of closest neighbors. More...

std::string	m_dmLabel
	The distance metric to use. More...

bool	m_unconnected {false}
	Require neighbors with no direct edge. More...

Protected Attributes inherited from MPBaseObject
bool	m_debug
	Print debug info? More...

Detailed Description

Uses a k-d tree to find nearest-neighbors.

This class builds a separate kd tree for each roadmap and each of its components. This is important for avoiding a continuous rebuild from scratch for any candidate set other than the full roadmap.

Todo:: We should be able to use a Search_traits_adaptor to avoid recopying the points and instead put VIDs into the kd tree. However my attempt to do that resulted in bogus runtime behavior within CGAL's Kd_tree::build (dimension is computed incorrectly resulting in a bad array size). Figure out how to finagle this so that we can avoid recopying Cfgs.

Todo:: This is limited to euclidean distance at present, but it should be possible to use any minkowski or mahalonobis distance with the appropriate distance adapter. It can not support arbitrary distances despite the claims in CGAL's documentation because the implementation requires finding the nearest and furthest point to an AABB; this is not tractible unless the geometrically nearest/farthest points (i.e. measured with euclidean) are also the nearest points for our metric.

Member Typedef Documentation

◆ CCTrackerType

typedef RoadmapType::CCTrackerType KdTreeNF::CCTrackerType

◆ GroupCfgType

typedef MPBaseObject::GroupCfgType KdTreeNF::GroupCfgType

◆ GroupRoadmapType

typedef MPBaseObject::GroupRoadmapType KdTreeNF::GroupRoadmapType

◆ OutputIterator

typedef std::back_insert_iterator<std::vector<Neighbor> > NeighborhoodFinderMethod::OutputIterator

Output iterator for writing discovered neighbors to a container.

◆ RoadmapType

typedef MPBaseObject::RoadmapType KdTreeNF::RoadmapType

◆ VertexSet

typedef RoadmapType::VertexSet KdTreeNF::VertexSet

◆ VI

typedef RoadmapType::VI KdTreeNF::VI

◆ VID

typedef RoadmapType::VID KdTreeNF::VID

Member Enumeration Documentation

◆ Type

enum NeighborhoodFinderMethod::Type

strong

The type of neighbors found.

Constructor & Destructor Documentation

◆ KdTreeNF() [1/2]

KdTreeNF::KdTreeNF ( )

◆ KdTreeNF() [2/2]

KdTreeNF::KdTreeNF ( XMLNode & _node )

◆ ~KdTreeNF()

virtual KdTreeNF::~KdTreeNF ( )

virtualdefault

Member Function Documentation

◆ FindNeighbors() [1/2]

void KdTreeNF::FindNeighbors	(	GroupRoadmapType *const	_r,
		const GroupCfgType &	_cfg,
		const VertexSet &	_candidates,
		OutputIterator	_out
	)

overridevirtual

Implements NeighborhoodFinderMethod.

◆ FindNeighbors() [2/2]

void KdTreeNF::FindNeighbors	(	RoadmapType *const	_r,
		const Cfg &	_cfg,
		const VertexSet &	_candidates,
		OutputIterator	_out
	)

overridevirtual

Some methods can be implemented more efficiently if the candidates are provided in a hash set. This function is to support that; the default implementation forwards to the iterator version.

Parameters

_r	The roadmap.
_cfg	The query configuration.
_candidates	The set of candidate VIDs.
_out	Output iterator.

Implements NeighborhoodFinderMethod.

◆ Initialize()

void KdTreeNF::Initialize ( )

overridevirtual

Initialize this object for the current MPProblem. This should reset any internal state of the algorithms so that they are ready for execution. It is also the place to initialize any state that depends on the current problem.

Warning: This member will be called for every compiled algorithm in the planning library - even those that will not be used. If an algorithm needs to do expenisve setup, then this method should only set a flag that tells it to do so on first use. The only exceptions are the MPStrategies, which will only have their initialize called on first use.

Reimplemented from MPBaseObject.

◆ Print()

void KdTreeNF::Print ( std::ostream & _os ) const

overridevirtual

Print internal state of this object.

Parameters

_os	The std::ostream to print to.

Reimplemented from NeighborhoodFinderMethod.

The documentation for this class was generated from the following files:

/opt/actions-runner/_work/open-ppl/open-ppl/src/MPLibrary/NeighborhoodFinders/KdTreeNF.h
/opt/actions-runner/_work/open-ppl/open-ppl/src/MPLibrary/NeighborhoodFinders/KdTreeNF.cpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ CCTrackerType

◆ GroupCfgType

◆ GroupRoadmapType

◆ OutputIterator

◆ RoadmapType

◆ VertexSet

◆ VI

◆ VID

Member Enumeration Documentation

◆ Type

Constructor & Destructor Documentation

◆ KdTreeNF() [1/2]

◆ KdTreeNF() [2/2]

◆ ~KdTreeNF()

Member Function Documentation

◆ FindNeighbors() [1/2]

◆ FindNeighbors() [2/2]

◆ Initialize()

◆ Print()