Public Member Functions
Construction
	CBSQuery ()

	CBSQuery (XMLNode &_node)

virtual	~CBSQuery ()=default

MPBaseObject Overrides
virtual void	Initialize () override

MapEvaluator Overrides
virtual bool	operator() () override

MapEvaluator Interface
virtual void	SetEdgeIntervals (EdgeIntervals _edgeIntervals)
	Set the edge intervals of a roadmap. More...

virtual void	SetMinEndtime (double _minEndtime)
	Set the minimum end time of a path. More...

Active Robots
Todo: This is an artifact of developing robot groups. It should be replaced by using a proper subgroup where each robot within is active.
void	SetActiveRobots (const std::vector< size_t > &_activeRobots)
	Set the active robots.

std::vector< size_t >	GetActiveRobots () const
	Get the active robots.

I/O
virtual void	Print (std::ostream &_os) const

Name and Label Accessors
const std::string &	GetName () const
	Get the class name for this object.

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

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

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

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

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

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

DistanceMetricPointer	GetDistanceMetric (const std::string &) const noexcept
	Get a distance metric by label from the owning MPLibrary.

ValidityCheckerPointer	GetValidityChecker (const std::string &) const noexcept
	Get a validity checker by label from the owning MPLibrary.

NeighborhoodFinderPointer	GetNeighborhoodFinder (const std::string &) const noexcept
	Get a neighborhood finder by label from the owning MPLibrary.

SamplerPointer	GetSampler (const std::string &) const noexcept
	Get a sampler by label from the owning MPLibrary.

LocalPlannerPointer	GetLocalPlanner (const std::string &) const noexcept
	Get a local planner by label from the owning MPLibrary.

ExtenderPointer	GetExtender (const std::string &) const noexcept
	Get an extender by label from the owning MPLibrary.

PathModifierPointer	GetPathModifier (const std::string &) const noexcept
	Get a path modifier by label from the owning MPLibrary.

ConnectorPointer	GetConnector (const std::string &) const noexcept
	Get a connector by label from the owning MPLibrary.

MetricPointer	GetMetric (const std::string &) const noexcept
	Get a metric by label from the owning MPLibrary.

MapEvaluatorPointer	GetMapEvaluator (const std::string &) const noexcept
	Get a map evaluator by label from the owning MPLibrary.

MPStrategyPointer	GetMPStrategy (const std::string &) const noexcept
	Get a strategy by label from the owning MPLibrary.

MPTraits::MPTools *	GetMPTools () const noexcept
	Get the MPTools container from the owning MPLibrary.

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

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

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

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

Solution Accessors
MPSolution *	GetMPSolution () const noexcept

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

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

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

Path *	GetPath (Robot *const _r=nullptr) const noexcept
	Get the current best path.

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

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

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

GoalTracker *	GetGoalTracker () const noexcept
	Get the goal tracker.

Public Types
Motion Planning Types
typedef MPTraits::RoadmapType	RoadmapType

typedef MPTraits::CfgType	CfgType

typedef MPTraits::Path	Path

typedef RoadmapType::VID	VID

typedef RoadmapType::EdgeID	EdgeID

Local Types
typedef MPTraits::GroupRoadmapType	GroupRoadmapType

typedef MPTraits::LocalObstacleMap	LocalObstacleMap

typedef MPTraits::GroupPathType	GroupPath

typedef MPTraits::MPLibrary	MPLibrary

typedef MPTraits::MPSolution	MPSolution

typedef MPTraits::GoalTracker	GoalTracker

typedef MPLibrary::SamplerPointer	SamplerPointer

typedef MPLibrary::LocalPlannerPointer	LocalPlannerPointer

typedef MPLibrary::ExtenderPointer	ExtenderPointer

typedef MPLibrary::PathModifierPointer	PathModifierPointer

typedef MPLibrary::ConnectorPointer	ConnectorPointer

typedef MPLibrary::MetricPointer	MetricPointer

typedef MPLibrary::MapEvaluatorPointer	MapEvaluatorPointer

typedef MPLibrary::MPStrategyPointer	MPStrategyPointer

typedef MPLibrary::DistanceMetricPointer	DistanceMetricPointer

typedef MPLibrary::ValidityCheckerPointer	ValidityCheckerPointer

typedef MPLibrary::NeighborhoodFinderPointer	NeighborhoodFinderPointer

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

const std::string &	GetBaseFilename () const

Protected Attributes
bool	m_debug
	Print debug info?

Internal State
std::vector< size_t >	m_activeRobots

Helpers
std::vector< Robot * >	m_robots
	The robots in the group.

std::string	m_queryLabel
	Query method for making individual plans.

std::string	m_vcLabel
	Validity checker for conflict detection.

std::string	m_safeIntervalLabel
	The Safe Intarval Tool label.

std::string	m_costLabel = "SOC"
	The label of the cost function.

size_t	m_nodeLimit {std::numeric_limits<size_t>::max()}
	The maximum number of nodes.

const ConstraintSet *	m_currentConstraints {nullptr}
	The current constraints.

std::set< ConstraintMap >	m_constraintCache
	The cached constraints.

std::unordered_map< Robot , MPTask >	m_taskMap
	The task for each robot.

GroupConflictsCache	m_groupConflictsCache
	The cache of contraints with cached safe intervals.

EdgeIntervalsMap	m_edgeIntervalsMap
	The cached edge intervals.

size_t	m_cacheIndex {0}
	The size of the cache.

Path *	SolveIndividualTask (Robot *const _robot, const ConstraintMap &_constraintMap={})
	Generate a path for a robot given a set of constraints.

std::pair< std::pair< Robot , Robot >, Conflict >	FindConflict (const SolutionMap &_solution)
	Find a conflict between a pair of robots.

EdgeIntervals	ComputeIntervals (Robot *_robot)
	Compute the safe intervals for a robot's roadmap.

EdgeIntervals	JoinEdgeIntervals (Robot *_robot, std::vector< EdgeIntervals > _edgeIntervals)
	Join the edge intervals for a robot's roadmap.

std::vector< Range< double > >	JoinIntervals (std::vector< std::vector< Range< double > > > _allIntervals)
	Computes joint safe intervals for the intervals in _allIntervals.

std::vector< Range< double > >	InsertIntervals (std::vector< Range< double > > _jointIntervals, std::vector< Range< double > > _newIntervals)
	Inserts _jointIntervals into _newIntervals.

bool	OverlappingIntervals (Range< double > _existingInterval, Range< double > _newInterval)
	Checks if there is overlap between two safe intervals.

Range< double >	MergeIntervals (Range< double > _interval1, Range< double > _interval2)
	Merges two safe intervals.

Detailed Description

template<typename MPTraits>
class CBSQuery< MPTraits >

Generates paths for each robot individually and then finds and resolves conflicts by setting constraints on each robot's path and replanning.

Reference: Guni Sharon, Roni Stern, Ariel Felner, and Nathan Sturtevant. "Conflict- Based Search For Optimal Multi-Agent Path Finding". AAAI 2012.

Member Function Documentation

◆ Initialize()

template<typename MPTraits >

void CBSQuery< MPTraits >::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< MPTraits >.

◆ operator()()

template<typename MPTraits >

bool CBSQuery< MPTraits >::operator() ( )

overridevirtual

Evaluate a roadmap.

Returns: True if this roadmap meets the evaluation criteria.

Implements MapEvaluatorMethod< MPTraits >.

◆ SetEdgeIntervals()

template<typename MPTraits >

virtual void MapEvaluatorMethod< MPTraits >::SetEdgeIntervals ( EdgeIntervals _edgeIntervals )

virtualinherited

Set the edge intervals of a roadmap.

Reimplemented in SIPPMethod< MPTraits >.

◆ SetMinEndtime()

template<typename MPTraits >

virtual void MapEvaluatorMethod< MPTraits >::SetMinEndtime ( double _minEndtime )

virtualinherited

Set the minimum end time of a path.

Reimplemented in SIPPMethod< MPTraits >.

◆ Print()

template<typename MPTraits >

void MPBaseObject< MPTraits >::Print ( std::ostream & _os ) const

virtualinherited

◆ SetName()

template<typename MPTraits >

void MPBaseObject< MPTraits >::SetName ( const std::string & _s )

protectedinherited

Parameters

_s	Class name

◆ GetBaseFilename()

template<typename MPTraits >

const std::string & MPBaseObject< MPTraits >::GetBaseFilename ( ) const

protectedinherited

Returns: base file name from MPProblem

Member Data Documentation

◆ m_activeRobots

template<typename MPTraits >

std::vector<size_t> MapEvaluatorMethod< MPTraits >::m_activeRobots

protectedinherited

The active robots, used only by group map evaluators. Depending on the evaluator, the usage could be different, but the current use case is to set the robot(s) that are being moved, then a clearance check is done only considering those specified bodies (see MinimumClearanceEvaluator).

Todo:: This is an artifact of developing robot groups. It should be replaced by using a proper subgroup where each robot within is active.

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

CBSQuery.h

Public Member Functions

Public Types

Protected Member Functions

Protected Attributes

Helpers

Detailed Description

Member Function Documentation

◆ Initialize()

◆ operator()()

◆ SetEdgeIntervals()

◆ SetMinEndtime()

◆ Print()

◆ SetName()

◆ GetBaseFilename()

Member Data Documentation

◆ m_activeRobots