The SynchBB algorithm for DCOPs. More...

Inheritance diagram for frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >:

[legend]

Classes
class	ConvergenceMessage
	A message reporting the convergence for a given component. More...
class	ClusterInfo
	Information about a cluster of variables owned by this agent. More...
class	ComponentInfo
	The information about a particular component of the constraint graph. More...

Public Member Functions
	SynchBB (Element parameters, DCOPProblemInterface< V, U > problem)
	The constructor called in "statistics gatherer" mode.
	SynchBB (DCOPProblemInterface< V, U > problem, Element parameters)
	Constructor.
void	reset ()
Collection< MessageType >	getMsgTypes ()
void	getStatsFromQueue (Queue queue)
void	setSilent (boolean silent)
void	setQueue (Queue queue)
void	notifyIn (Message msg)
HashMap< String, ArrayList< CurrentAssignment< V > > >	getAssignmentHistories ()
Map< String, V >	getCurrentSolution ()
Public Member Functions inherited from frodo2.communication.IncomingMsgPolicyInterface< T >
default void	notifyIn (Message msg, Object toAgent)
	Notifies the listener of an incoming message.

Static Public Attributes
static MessageType	START_MSG_TYPE = AgentInterface.START_AGENT
	The type of the message telling the module to start.
static MessageType	ORDER_MSG_TYPE = OrderMsg.ORDER_MSG_TYPE
	The types of the messages containing the chosen linear order of (clusters of) variables.
static MessageType	ORDER_STATS_MSG_TYPE = OrderMsg.STATS_MSG_TYPE
	The types of the messages containing the chosen linear order of (clusters of) variables sent to the stats gatherer.
static final MessageType	BACKTRACK_MSG_TYPE = new MessageType ("SynchBB", "Backtrack")
	The type of the backtrack messages.
static final MessageType	PATH_MSG_TYPE = new MessageType ("SynchBB", "Path")
	The type of the messages containing the current partial assignment.
static final MessageType	OUTPUT_MSG_TYPE = new MessageType ("SynchBB", "Solution")
	The type of the message containing the optimal solution found.
static final MessageType	UB_MSG_TYPE = new MessageType ("SynchBB", "UB")
	The type of the messages broadcast by the last variable containing the current upper bound.

Private Member Functions
void	start ()
	Parses the problem.
boolean	checkAllCostsNonNeg ()
void	initiate (Comparable<?> compID, ComponentInfo compInfo)
	Chooses a first value for the first cluster of variables and starts the algorithm.
void	terminate (Comparable<?> compID, ComponentInfo compInfo)
	Sends output and termination messages.
void	received_from_prev (PathMsg< V, U > msg)
	Reacts to the reception of a path message from the previous cluster in the ordering.
void	received_from_next (BTmsg msg)
	Reacts to the reception of a backtrack message.
void	send_token (Comparable<?> compID, ComponentInfo compInfo, final int clusterIndex, ClusterInfo info, V[] next)
	Sends the next message.
V[]	get_next (ComponentInfo compInfo, final int clusterIndex, ClusterInfo info)
	Chooses the next assignment for the current cluster of variables.

Private Attributes
final boolean	convergence
	`true` when the convergence history is to be stored
HashMap< String, ArrayList< CurrentAssignment< V > > >	assignmentHistoriesMap
	For each variable, its assignment history.
HashMap< Comparable<?>, ComponentInfo >	compInfos
	The information about each component in the constraint graph.
HashMap< String, Comparable<?> >	compOfCluster
	For each cluster, its component ID.
Queue	queue
	This module's queue.
DCOPProblemInterface< V, U >	problem
	The problem.
boolean	started = false
	Whether the module has already started the algorithm.
U	zero
	The 0 cost.
HashMap< String, V >	solution
	The solution.
Class< V >	valClass
	The class of V.
Class< V[]>	valArrayClass
	The class of V[].
LinkedList< SolutionMsg< V, U > >	pendingSolMsgs
	Used to store solution messages received by the stats gatherer before their corresponding linear order.
LinkedList< ConvergenceMessage< V > >	pendingConvMsgs
	Used to store convergence messages received by the stats gatherer before their corresponding linear order.
HashMap< String, PathMsg< V, U > >	pendingPathMsgs
	For some clusters, a PathMsg that was received before the var order message.

Static Private Attributes
static final MessageType	CONV_STATS_MSG_TYPE = new MessageType ("SynchBB", "Convergence")
	The type of the message reporting the convergence for a given component.
static final boolean	DEBUG = false
	Whether the algorithm should print out debugging information.

Detailed Description

The SynchBB algorithm for DCOPs.

This is the original SynchBB algorithm by Hirayama & Yokoo (CP'97), adapted to solve DCOPs as proposed by Meisels (Springer Verlag, 2008), with two additional performance improvements:

BACKTRACK messages do not include the path
PATH messages strip the first part of the path that has not changed

Author: Thomas Leaute

Parameters

<V>	the type used for variable values
<U>	the type used for utility values

Constructor & Destructor Documentation

◆ SynchBB() [1/2]

frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable< U > >.SynchBB	(	Element	parameters,
		DCOPProblemInterface< V, U >	problem )

The constructor called in "statistics gatherer" mode.

Parameters

problem	the overall problem
parameters	the description of what statistics should be reported (currently unused)

References problem.

◆ SynchBB() [2/2]

frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable< U > >.SynchBB	(	DCOPProblemInterface< V, U >	problem,
		Element	parameters )

Constructor.

Parameters

problem	this agent's problem
parameters	the parameters for SynchBB

References problem.

Member Function Documentation

◆ checkAllCostsNonNeg()

boolean frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.checkAllCostsNonNeg ( )

private

Returns: true if all utilities in all spaces are non-negative, false otherwise

References frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.getSolutionSpaces(), frodo2.solutionSpaces.SolutionSpace< V extends Addable< V > >.Iterator< V >.hasNext(), and zero.

Referenced by start().

Here is the call graph for this function:

◆ get_next()

V[] frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable< U > >.get_next	(	ComponentInfo	compInfo,
		final int	clusterIndex,
		ClusterInfo	info )

private

Chooses the next assignment for the current cluster of variables.

Parameters

compInfo	the information about the component in the constraint graph
clusterIndex	index of the current cluster in the cluster ordering
info	information about the current cluster

Returns: the next assignment for the current cluster, or null if the domain is exhausted

Todo: can we move a part of this computation at the creation of the clusterInfo object to avoid searching for these variables that are fixed in the order too many times? Yes, we can!(R)

References get_next(), and valArrayClass.

Referenced by get_next(), received_from_next(), and send_token().

Here is the call graph for this function:

◆ getAssignmentHistories()

HashMap< String, ArrayList< CurrentAssignment< V > > > frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.getAssignmentHistories ( )

See also: StatsReporterWithConvergence.getAssignmentHistories()

Implements frodo2.algorithms.StatsReporterWithConvergence< Val extends Addable< Val > >.

Referenced by frodo2.algorithms.synchbb.test.SynchBBagentTest< V extends Addable< V >, U extends Addable >.checkOutput().

◆ getCurrentSolution()

Map< String, V > frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.getCurrentSolution ( )

See also: StatsReporterWithConvergence.getCurrentSolution()

Todo: Auto-generated method stub

Implements frodo2.algorithms.StatsReporterWithConvergence< Val extends Addable< Val > >.

◆ getMsgTypes()

Collection< MessageType > frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.getMsgTypes ( )

See also: StatsReporterWithConvergence.getMsgTypes()

Implements frodo2.communication.MessageListener< T >.

References frodo2.algorithms.AgentInterface< V extends Addable< V > >.AGENT_FINISHED, BACKTRACK_MSG_TYPE, ORDER_MSG_TYPE, OUTPUT_MSG_TYPE, PATH_MSG_TYPE, START_MSG_TYPE, and UB_MSG_TYPE.

◆ getStatsFromQueue()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.getStatsFromQueue ( Queue queue )

See also: StatsReporterWithConvergence.getStatsFromQueue(Queue)

Implements frodo2.algorithms.StatsReporter.

References CONV_STATS_MSG_TYPE, ORDER_STATS_MSG_TYPE, and queue.

Referenced by frodo2.algorithms.synchbb.test.SynchBBagentTest< V extends Addable< V >, U extends Addable >.setUp().

◆ initiate()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable< U > >.initiate	(	Comparable<?>	compID,
		ComponentInfo	compInfo )

private

Chooses a first value for the first cluster of variables and starts the algorithm.

Parameters

compID	the ID of the component in the constraint graph
compInfo	the information about the component in the constraint graph

References initiate(), frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ClusterInfo.nextAgent, terminate(), valArrayClass, and valClass.

Referenced by initiate().

Here is the call graph for this function:

◆ notifyIn()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.notifyIn ( Message msg )

See also: StatsReporterWithConvergence.notifyIn(Message)

Implements frodo2.communication.IncomingMsgPolicyInterface< T >.

References frodo2.communication.MessageType.equals(), notifyIn(), and ORDER_STATS_MSG_TYPE.

Referenced by notifyIn().

Here is the call graph for this function:

◆ received_from_next()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.received_from_next ( BTmsg msg )

private

Reacts to the reception of a backtrack message.

Parameters

msg	the received backtrack message

References frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.clusterIndexes, frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.clusterInfos, frodo2.algorithms.synchbb.BTmsg.dest, get_next(), and send_token().

Here is the call graph for this function:

◆ received_from_prev()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.received_from_prev ( PathMsg< V, U > msg )

private

Reacts to the reception of a path message from the previous cluster in the ordering.

Parameters

msg	the received path message

References frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.clusterIndexes, and received_from_prev().

Referenced by received_from_prev().

Here is the call graph for this function:

◆ reset()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.reset ( )

See also: StatsReporterWithConvergence.reset()

Implements frodo2.algorithms.StatsReporter.

◆ send_token()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable< U > >.send_token	(	Comparable<?>	compID,
		ComponentInfo	compInfo,
		final int	clusterIndex,
		ClusterInfo	info,
		V[]	next )

private

Sends the next message.

Parameters

compID	the ID of the component in the constraint graph
compInfo	the information about the component in the constraint graph
clusterIndex	index of the current cluster in the cluster ordering
info	information on the current cluster
next	next assignment chosen for the current cluster

References convergence, DEBUG, get_next(), frodo2.solutionSpaces.ProblemInterface< V extends Addable< V >, U extends Addable >.getAgent(), frodo2.communication.Queue.getCurrentTime(), send_token(), frodo2.communication.Queue.sendMessage(), frodo2.communication.Queue.sendMessageToMulti(), terminate(), UB_MSG_TYPE, and valArrayClass.

Referenced by received_from_next(), and send_token().

Here is the call graph for this function:

◆ setQueue()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.setQueue ( Queue queue )

See also: StatsReporterWithConvergence.setQueue(Queue)

Implements frodo2.communication.MessageListener< T >.

References queue.

◆ setSilent()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.setSilent ( boolean silent )

See also: StatsReporterWithConvergence.setSilent(boolean)

Implements frodo2.algorithms.StatsReporter.

Referenced by frodo2.algorithms.synchbb.test.SynchBBagentTest< V extends Addable< V >, U extends Addable >.setUp().

◆ start()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.start ( )

private

Parses the problem.

References checkAllCostsNonNeg(), frodo2.solutionSpaces.ProblemInterface< V extends Addable< V >, U extends Addable >.getZeroUtility(), and frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.maximize().

Here is the call graph for this function:

◆ terminate()

void frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable< U > >.terminate	(	Comparable<?>	compID,
		ComponentInfo	compInfo )

private

Sends output and termination messages.

Parameters

compID	the ID of the component in the constraint graph
compInfo	the information about the component in the constraint graph

Todo: Terminate all components prematurely if the optimal cost is already infinite

References frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.agents, frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.bestSol, frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.history, OUTPUT_MSG_TYPE, frodo2.communication.Queue.sendMessage(), frodo2.communication.Queue.sendMessageToMulti(), frodo2.algorithms.AgentInterface< V extends Addable< V > >.STATS_MONITOR, and frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.ub.

Referenced by initiate(), and send_token().

Here is the call graph for this function:

Member Data Documentation

◆ assignmentHistoriesMap

HashMap< String, ArrayList< CurrentAssignment<V> > > frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.assignmentHistoriesMap

private

For each variable, its assignment history.

◆ BACKTRACK_MSG_TYPE

final MessageType frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.BACKTRACK_MSG_TYPE = new MessageType ("SynchBB", "Backtrack")

static

The type of the backtrack messages.

Referenced by frodo2.algorithms.synchbb.BTmsg.BTmsg(), frodo2.algorithms.synchbb.BTmsg.BTmsg(), and getMsgTypes().

◆ compInfos

HashMap<Comparable<?>, ComponentInfo> frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.compInfos

private

The information about each component in the constraint graph.

◆ compOfCluster

HashMap< String, Comparable<?> > frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.compOfCluster

private

For each cluster, its component ID.

◆ CONV_STATS_MSG_TYPE

final MessageType frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.CONV_STATS_MSG_TYPE = new MessageType ("SynchBB", "Convergence")

staticprivate

The type of the message reporting the convergence for a given component.

Todo: Do not include the solution?

Referenced by frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ConvergenceMessage< V extends Addable< V > >.ConvergenceMessage(), frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ConvergenceMessage< V extends Addable< V > >.ConvergenceMessage(), and getStatsFromQueue().

◆ convergence

final boolean frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.convergence

private

true when the convergence history is to be stored

Referenced by frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.ComponentInfo(), frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ComponentInfo.ComponentInfo(), and send_token().

◆ DEBUG

final boolean frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.DEBUG = false

staticprivate

Whether the algorithm should print out debugging information.

Referenced by send_token().

◆ ORDER_MSG_TYPE

MessageType frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ORDER_MSG_TYPE = OrderMsg.ORDER_MSG_TYPE

static

The types of the messages containing the chosen linear order of (clusters of) variables.

Referenced by getMsgTypes().

◆ ORDER_STATS_MSG_TYPE

MessageType frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.ORDER_STATS_MSG_TYPE = OrderMsg.STATS_MSG_TYPE

static

The types of the messages containing the chosen linear order of (clusters of) variables sent to the stats gatherer.

Referenced by getStatsFromQueue(), and notifyIn().

◆ OUTPUT_MSG_TYPE

final MessageType frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.OUTPUT_MSG_TYPE = new MessageType ("SynchBB", "Solution")

static

The type of the message containing the optimal solution found.

Referenced by getMsgTypes(), and terminate().

◆ PATH_MSG_TYPE

final MessageType frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.PATH_MSG_TYPE = new MessageType ("SynchBB", "Path")

static

The type of the messages containing the current partial assignment.

Referenced by getMsgTypes(), frodo2.algorithms.synchbb.PathMsg< V extends Addable< V >, U extends Addable >.PathMsg(), and frodo2.algorithms.synchbb.PathMsg< V extends Addable< V >, U extends Addable >.PathMsg().

◆ pendingConvMsgs

LinkedList< ConvergenceMessage<V> > frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.pendingConvMsgs

private

Used to store convergence messages received by the stats gatherer before their corresponding linear order.

◆ pendingPathMsgs

HashMap< String, PathMsg<V, U> > frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.pendingPathMsgs

private

For some clusters, a PathMsg that was received before the var order message.

◆ pendingSolMsgs

LinkedList< SolutionMsg<V, U> > frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.pendingSolMsgs

private

Used to store solution messages received by the stats gatherer before their corresponding linear order.

◆ problem

DCOPProblemInterface<V, U> frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.problem

private

The problem.

Referenced by SynchBB(), and SynchBB().

◆ queue

Queue frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.queue

private

This module's queue.

Referenced by getStatsFromQueue(), and setQueue().

◆ solution

HashMap<String, V> frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.solution

private

The solution.

◆ START_MSG_TYPE

MessageType frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.START_MSG_TYPE = AgentInterface.START_AGENT

static

The type of the message telling the module to start.

Referenced by getMsgTypes().

◆ started

boolean frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.started = false

private

Whether the module has already started the algorithm.

◆ UB_MSG_TYPE

final MessageType frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.UB_MSG_TYPE = new MessageType ("SynchBB", "UB")

static

The type of the messages broadcast by the last variable containing the current upper bound.

Referenced by getMsgTypes(), and send_token().

◆ valArrayClass

Class<V[]> frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.valArrayClass

private

The class of V[].

Referenced by get_next(), initiate(), and send_token().

◆ valClass

Class<V> frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.valClass

private

The class of V.

Referenced by initiate().

◆ zero

U frodo2.algorithms.synchbb.SynchBB< V extends Addable< V >, U extends Addable >.zero

private

The 0 cost.

Referenced by checkAllCostsNonNeg().

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

src/frodo2/algorithms/synchbb/SynchBB.java

Classes

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SynchBB() [1/2]

◆ SynchBB() [2/2]

Member Function Documentation

◆ checkAllCostsNonNeg()

◆ get_next()

◆ getAssignmentHistories()

◆ getCurrentSolution()

◆ getMsgTypes()

◆ getStatsFromQueue()

◆ initiate()

◆ notifyIn()

◆ received_from_next()

◆ received_from_prev()

◆ reset()

◆ send_token()

◆ setQueue()

◆ setSilent()

◆ start()

◆ terminate()

Member Data Documentation

◆ assignmentHistoriesMap

◆ BACKTRACK_MSG_TYPE

◆ compInfos

◆ compOfCluster

◆ CONV_STATS_MSG_TYPE

◆ convergence

◆ DEBUG

◆ ORDER_MSG_TYPE

◆ ORDER_STATS_MSG_TYPE

◆ OUTPUT_MSG_TYPE

◆ PATH_MSG_TYPE

◆ pendingConvMsgs

◆ pendingPathMsgs

◆ pendingSolMsgs

◆ problem

◆ queue

◆ solution

◆ START_MSG_TYPE

◆ started

◆ UB_MSG_TYPE

◆ valArrayClass

◆ valClass

◆ zero