#include <CBSQuery.h>

Inheritance diagram for CBSQuery:

Collaboration diagram for CBSQuery:

[legend]

Public Types
Motion Planning Types
typedef MPBaseObject::RoadmapType	RoadmapType

typedef RoadmapType::VID	VID

typedef RoadmapType::EdgeID	EdgeID

Public Types inherited from MapEvaluatorMethod
typedef std::unordered_map< size_t, std::unordered_map< size_t, std::vector< Range< double > > > >	EdgeIntervals

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
	CBSQuery ()

	CBSQuery (XMLNode &_node)

virtual	~CBSQuery ()=default

MPBaseObject Overrides
virtual void	Initialize () override

MapEvaluator Overrides
virtual bool	operator() () override

Public Member Functions inherited from MapEvaluatorMethod
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...

void	SetActiveRobots (const std::vector< size_t > &_activeRobots)
	Set the active robots. More...

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

	MapEvaluatorMethod ()=default

	MapEvaluatorMethod (XMLNode &_node)

virtual	~MapEvaluatorMethod ()=default

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

	MPBaseObject (XMLNode &_node)

virtual	~MPBaseObject ()

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

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

Protected Member Functions
CBS Functors
Path *	SolveIndividualTask (Robot *const _robot, Node &_node)

std::vector< std::pair< Robot *, Constraint > >	ValidationFunction (Node &_node)

std::vector< Node >	SplitNodeFunction (Node &_node, std::vector< std::pair< Robot *, Constraint >> _constraints, CBSLowLevelPlanner< Robot, Constraint, Path > &_lowlevel, CBSCostFunction< Robot, Constraint, Path > &_cost)

double	CostFunction (Node &_node)

Helpers
void	ComputeIntervals (Robot *_robot, const Node &_node)

std::vector< Range< size_t > >	ConstructSafeIntervals (std::vector< Range< size_t >> &_unsafeIntervals)

bool	OverlappingIntervals (Range< size_t > _interval1, Range< size_t > _interval2)

Range< double >	MergeIntervals (Range< double > _interval1, Range< double > _interval2)

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

const std::string &	GetBaseFilename () const

Protected Attributes
Internal State
std::vector< Robot * >	m_robots
	The robots in the group. More...

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

std::string	m_vcLabel
	Validity checker for conflict detection. More...

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

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

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

VertexIntervals	m_vertexIntervals
	The current set of safe vertex intervals. More...

EdgeIntervals	m_edgeIntervals
	The current set of safe edge intervals. More...

Protected Attributes inherited from MapEvaluatorMethod
std::vector< size_t >	m_activeRobots

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

Detailed Description

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 Typedef Documentation

◆ EdgeID

typedef RoadmapType::EdgeID CBSQuery::EdgeID

◆ RoadmapType

typedef MPBaseObject::RoadmapType CBSQuery::RoadmapType

◆ VID

typedef RoadmapType::VID CBSQuery::VID

Constructor & Destructor Documentation

◆ CBSQuery() [1/2]

CBSQuery::CBSQuery ( )

◆ CBSQuery() [2/2]

CBSQuery::CBSQuery ( XMLNode & _node )

◆ ~CBSQuery()

virtual CBSQuery::~CBSQuery ( )

virtualdefault

Member Function Documentation

◆ ComputeIntervals()

void CBSQuery::ComputeIntervals	(	Robot *	_robot,
		const Node &	_node
	)

protected

Compute the safe intervals for a robot given its constraint set in the node.

Parameters

_robot	The robot to compute safe intervals for.
_node	The node containing the constraint set.

◆ ConstructSafeIntervals()

std::vector< Range< size_t > > CBSQuery::ConstructSafeIntervals ( std::vector< Range< size_t >> & _unsafeIntervals )

protected

Construct the safe intervals that complement the unsafe intervals.

Parameters

_unsafeIntervals The unsafe intervals that define the complement.

Returns: The set of safe intervals.

◆ CostFunction()

double CBSQuery::CostFunction ( Node & _node )

protected

Compute the cost of a CBS node. Can either be makespace or sum-of-cost.

Parameters

_node Node to compute cost for.

Returns: The computed cost.

◆ Initialize()

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

◆ MergeIntervals()

Range< double > CBSQuery::MergeIntervals	(	Range< double >	_interval1,
		Range< double >	_interval2
	)

protected

Merge a pair of intervals into a new interval.

Parameters

_interval1	First interval to check.
_interval2	Second interval to check.

Returns: New merged interval.

◆ operator()()

bool CBSQuery::operator() ( )

overridevirtual

Evaluate a roadmap.

Returns: True if this roadmap meets the evaluation criteria.

Implements MapEvaluatorMethod.

◆ OverlappingIntervals()

bool CBSQuery::OverlappingIntervals	(	Range< size_t >	_interval1,
		Range< size_t >	_interval2
	)

protected

Check if two intervals are overlapping.

Parameters

_interval1	First interval to check.
_interval2	Second interval to check.

Returns: Boolean indicating if they are overlapping.

◆ SolveIndividualTask()

Path * CBSQuery::SolveIndividualTask	(	Robot *const	_robot,
		Node &	_node
	)

protected

Generate a path for a robot given a set of constraints.

Parameters

_robot	The robot to solve the task for.
_node	The CBS node to store the new path in.

Returns: Path pointer to the resulting path. A nullptr indicates failure.

◆ SplitNodeFunction()

std::vector< typename CBSQuery::Node > CBSQuery::SplitNodeFunction	(	Node &	_node,
		std::vector< std::pair< Robot *, Constraint >>	_constraints,
		CBSLowLevelPlanner< Robot, Constraint, Path > &	_lowlevel,
		CBSCostFunction< Robot, Constraint, Path > &	_cost
	)

protected

Create child nodes corresponding to the additional constraints.

Parameters

_node	The parent CBS node to spawn children for.
_constraints	The set of new constraints to spawn new child nodes for.
_lowLevel	The functor to plan new paths for robots with new constraints.
_cost	The functor to compute the cost of new child nodes.

Returns: The set of new child nodes.

◆ ValidationFunction()

std::vector< std::pair< Robot *, typename CBSQuery::Constraint > > CBSQuery::ValidationFunction ( Node & _node )

protected

Validate that the set of paths in the node do not contain conflicts.

Parameters

_node The node to validate

Returns: The set of new robot-constraint pairs to add to the node generated from discovered conflicts.

Field Documentation

◆ m_costLabel

std::string CBSQuery::m_costLabel = "SOC"

protected

The label of the cost function.

◆ m_edgeIntervals

EdgeIntervals CBSQuery::m_edgeIntervals

protected

The current set of safe edge intervals.

◆ m_nodeLimit

size_t CBSQuery::m_nodeLimit {std::numeric_limits<size_t>::max()}

protected

The maximum number of nodes.

◆ m_queryLabel

std::string CBSQuery::m_queryLabel

protected

Query method for making individual plans.

◆ m_robots

std::vector<Robot*> CBSQuery::m_robots

protected

The robots in the group.

◆ m_taskMap

std::unordered_map<Robot*, MPTask*> CBSQuery::m_taskMap

protected

The task for each robot.

◆ m_vcLabel

std::string CBSQuery::m_vcLabel

protected

Validity checker for conflict detection.

◆ m_vertexIntervals

VertexIntervals CBSQuery::m_vertexIntervals

protected

The current set of safe vertex intervals.

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

/opt/actions-runner/_work/open-ppl/open-ppl/src/MPLibrary/MapEvaluators/CBSQuery.h
/opt/actions-runner/_work/open-ppl/open-ppl/src/MPLibrary/MapEvaluators/CBSQuery.cpp

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ EdgeID

◆ RoadmapType

◆ VID

Constructor & Destructor Documentation

◆ CBSQuery() [1/2]

◆ CBSQuery() [2/2]

◆ ~CBSQuery()

Member Function Documentation

◆ ComputeIntervals()

◆ ConstructSafeIntervals()

◆ CostFunction()

◆ Initialize()

◆ MergeIntervals()

◆ operator()()

◆ OverlappingIntervals()

◆ SolveIndividualTask()

◆ SplitNodeFunction()

◆ ValidationFunction()

Field Documentation

◆ m_costLabel

◆ m_edgeIntervals

◆ m_nodeLimit

◆ m_queryLabel

◆ m_robots

◆ m_taskMap

◆ m_vcLabel

◆ m_vertexIntervals