frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > > Class Template Reference

The Max-Sum Algorithm. More...

Inheritance diagram for frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >:

Classes
class	VarInfo
	Information about an internal variable. More...
class	FunctionInfo
	Information about each neighboring function node. More...

Public Member Functions
	MaxSum (DCOPProblemInterface< V, U > problem, Element parameters)
	Constructor.
	MaxSum (Element parameters, DCOPProblemInterface< V, U > problem)
	The constructor called in "statistics gatherer" mode.
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 final MessageType	FUNCTION_MSG_TYPE = FunctionMsg.FUNCTION_MSG_TYPE
	The type of the messages received from function nodes of the graph.
static final MessageType	VARIABLE_MSG_TYPE = VariableMsg.VARIABLE_MSG_TYPE
	The type of the messages received from variable nodes of the graph.

Private Member Functions
Hypercube< V, U >	zeroSpace (String varName, V[] dom)
	Returns a single-variable space full of zeros.
Hypercube< V, U >	scaledRandSpace (String varName, V[] dom)
	Returns a scaled random space.
void	start ()
	Parses the problem.
void	checkForTermination ()
	Checks if all my variable nodes have finished.

Private Attributes
HashMap< String, VarInfo >	varInfos
	For each internal variable, its VarInfo.
HashMap< String, FunctionInfo >	functionInfos
	For each constraint in the agent's subproblem, its FunctionInfo.
final int	maxNbrIter
	The algorithm will terminate when ALL function nodes have gone through that many iterations.
final boolean	synchronous
	If true, then round-based execution; if false, then each function/variable node immediately responds to each message.
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.
final boolean	maximize
	Whether to maximize utility or minimize cost.
final U	infeasibleUtil
	The infeasible utility.
final boolean	randomInit
	Whether to initialize the algorithm with random messages, or with messages full of zeros.
final boolean	convergence
	Whether the listener should record the assignment history or not.
final HashMap< String, ArrayList< CurrentAssignment< V > > >	assignmentHistoriesMap
	For each variable its assignment history.
ArrayList< Message >	pendingMsgs = new ArrayList<Message> ()
	Messages received and waiting to be processed.
String	agentName
	The name of this agent.

Static Private Attributes
static final MessageType	CONV_STATS_MSG_TYPE = new MessageType ("Max-Sum", "ConvStats")
	The type of the messages containing the assignment history.

Detailed Description

The Max-Sum Algorithm.

Max-Sum Implementation mostly based on "Decentralised Coordination of Low-Power Embedded Devices Using the Max-Sum Algorithm" by A. Farinelli, A. Rogers, A. Petcu, N. R. Jennings

Each function node is simulated by the agent owning the first variable in its scope.

Author

Thomas Leaute, remotely based on a preliminary contribution by Sokratis Vavilis and George Vouros (AI-Lab of the University of the Aegean)

Parameters

<V>	the type used for variable values
<U>	the type used for utility values in stats gatherer mode

Constructor & Destructor Documentation

MaxSum() [1/2]

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

Constructor.

Parameters

problem	this agent's problem
parameters	the parameters for this module

References frodo2.solutionSpaces.ProblemInterface< V extends Addable< V >, U extends Addable< U > >.getZeroUtility(), maxNbrIter, and problem.

Here is the call graph for this function:

MaxSum() [2/2]

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

The constructor called in "statistics gatherer" mode.

Parameters

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

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

Here is the call graph for this function:

Member Function Documentation

checkForTermination()

void frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.checkForTermination ( )

private

Checks if all my variable nodes have finished.

References frodo2.algorithms.AgentInterface< V extends Addable< V > >.AGENT_FINISHED, and frodo2.communication.Queue.sendMessageToSelf().

Referenced by notifyIn(), and start().

Here is the call graph for this function:

getAssignmentHistories()

HashMap< String, ArrayList< CurrentAssignment< V > > > frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.getAssignmentHistories

(

)

See also

StatsReporterWithConvergence.getAssignmentHistories()

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

getCurrentSolution()

Map< String, V > frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.getCurrentSolution

(

)

See also

StatsReporterWithConvergence.getCurrentSolution()

Todo

Auto-generated method stub

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

getMsgTypes()

Collection< MessageType > frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.getMsgTypes

(

)

See also

StatsReporterWithConvergence.getMsgTypes()

Implements frodo2.communication.MessageListener< T >.

References frodo2.algorithms.AgentInterface< V extends Addable< V > >.ALL_AGENTS_IDLE, FUNCTION_MSG_TYPE, frodo2.algorithms.varOrdering.factorgraph.FactorGraphGen< V extends Addable< V >, U extends Addable< U > >.OUTPUT_MSG_TYPE, and VARIABLE_MSG_TYPE.

getStatsFromQueue()

void frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.getStatsFromQueue

(

Queue

queue

)

See also

StatsReporterWithConvergence.getStatsFromQueue(Queue)

Implements frodo2.algorithms.StatsReporter.

References CONV_STATS_MSG_TYPE, and queue.

notifyIn()

void frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.notifyIn

(

Message

msg

)

See also

StatsReporterWithConvergence.notifyIn(Message)

Implements frodo2.communication.IncomingMsgPolicyInterface< T >.

References frodo2.solutionSpaces.AddableDelayed< T extends Addable< T > >.addDelayed(), frodo2.algorithms.AgentInterface< V extends Addable< V > >.AGENT_FINISHED, frodo2.algorithms.AgentInterface< V extends Addable< V > >.ALL_AGENTS_IDLE, assignmentHistoriesMap, frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.blindProject(), checkForTermination(), CONV_STATS_MSG_TYPE, convergence, frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FunctionInfo.doIrespond(), frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.doIrespond(), frodo2.communication.MessageType.equals(), FUNCTION_MSG_TYPE, frodo2.algorithms.varOrdering.factorgraph.FunctionNode< V extends Addable< V >, U extends Addable< U > >.getAgent(), frodo2.algorithms.varOrdering.factorgraph.VariableNode< V extends Addable< V >, U extends Addable< U > >.getAgent(), frodo2.solutionSpaces.ProblemInterface< V extends Addable< V >, U extends Addable< U > >.getAgent(), frodo2.algorithms.varOrdering.factorgraph.VariableNode< V extends Addable< V >, U extends Addable< U > >.getDom(), frodo2.algorithms.maxsum.FunctionMsg< V extends Addable< V >, U extends Addable< U > >.getFunctionNode(), frodo2.algorithms.maxsum.VariableMsg< V extends Addable< V >, U extends Addable< U > >.getFunctionNode(), frodo2.algorithms.varOrdering.factorgraph.VariableNode< V extends Addable< V >, U extends Addable< U > >.getFunctions(), frodo2.algorithms.maxsum.FunctionMsg< V extends Addable< V >, U extends Addable< U > >.getMarginalUtil(), frodo2.algorithms.maxsum.VariableMsg< V extends Addable< V >, U extends Addable< U > >.getMarginalUtil(), frodo2.algorithms.varOrdering.factorgraph.FunctionNode< V extends Addable< V >, U extends Addable< U > >.getName(), frodo2.communication.MessageWith2Payloads< T1 extends Serializable, T2 extends Serializable >.getPayload1(), frodo2.communication.MessageWith2Payloads< T1 extends Serializable, T2 extends Serializable >.getPayload2(), frodo2.algorithms.varOrdering.factorgraph.FunctionNode< V extends Addable< V >, U extends Addable< U > >.getSpace(), frodo2.communication.Message.getType(), frodo2.algorithms.varOrdering.factorgraph.VariableNode< V extends Addable< V >, U extends Addable< U > >.getVarName(), frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.join(), frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FunctionInfo.lastMsgsIn, frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.lastMsgsIn, frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FunctionInfo.nbrIter, frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.nbrIter, frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.nbrNeighbors, frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.optVal, frodo2.algorithms.varOrdering.factorgraph.FactorGraphGen< V extends Addable< V >, U extends Addable< U > >.OUTPUT_MSG_TYPE, queue, frodo2.solutionSpaces.AddableDelayed< T extends Addable< T > >.resolve(), frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.resolve(), frodo2.communication.Queue.sendMessage(), frodo2.communication.Queue.sendMessageToSelf(), start(), frodo2.algorithms.AgentInterface< V extends Addable< V > >.STATS_MONITOR, VARIABLE_MSG_TYPE, and zeroSpace().

Referenced by start().

Here is the call graph for this function:

reset()

void frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.reset

(

)

See also

StatsReporterWithConvergence.reset()

Todo

To be implemented

Implements frodo2.algorithms.StatsReporter.

scaledRandSpace()

Hypercube< V, U > frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.scaledRandSpace ( String varName, V[] dom )

private

Returns a scaled random space.

Parameters

varName	the name of the (only) variable
dom	the domain of the variable

Returns

a scaled random space over the variable

References frodo2.solutionSpaces.AddableDelayed< T extends Addable< T > >.addDelayed(), infeasibleUtil, scaledRandSpace(), and zero.

Referenced by scaledRandSpace(), and start().

Here is the call graph for this function:

setQueue()

void frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.setQueue

(

Queue

queue

)

See also

StatsReporterWithConvergence.setQueue(Queue)

Implements frodo2.communication.MessageListener< T >.

References queue.

setSilent()

void frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.setSilent

(

boolean

silent

)

See also

StatsReporterWithConvergence.setSilent(boolean)

Implements frodo2.algorithms.StatsReporter.

start()

void frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.start ( )

private

Parses the problem.

References checkForTermination(), CONV_STATS_MSG_TYPE, convergence, notifyIn(), queue, scaledRandSpace(), frodo2.communication.Queue.sendMessage(), frodo2.algorithms.AgentInterface< V extends Addable< V > >.STATS_MONITOR, and zeroSpace().

Referenced by notifyIn().

Here is the call graph for this function:

zeroSpace()

Hypercube< V, U > frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.zeroSpace ( String varName, V[] dom )

private

Returns a single-variable space full of zeros.

Parameters

varName	the name of the variable
dom	the variable domain

Returns

the space

References infeasibleUtil, zero, and zeroSpace().

Referenced by frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FunctionInfo.addVariable(), notifyIn(), start(), frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.VarInfo(), and zeroSpace().

Here is the call graph for this function:

Member Data Documentation

agentName

String frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.agentName

private

The name of this agent.

assignmentHistoriesMap

final HashMap< String, ArrayList< CurrentAssignment<V> > > frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.assignmentHistoriesMap

private

For each variable its assignment history.

Referenced by notifyIn().

CONV_STATS_MSG_TYPE

final MessageType frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.CONV_STATS_MSG_TYPE = new MessageType ("Max-Sum", "ConvStats")

staticprivate

The type of the messages containing the assignment history.

Referenced by getStatsFromQueue(), notifyIn(), and start().

convergence

final boolean frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.convergence

private

Whether the listener should record the assignment history or not.

Referenced by notifyIn(), and start().

FUNCTION_MSG_TYPE

final MessageType frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FUNCTION_MSG_TYPE = FunctionMsg.FUNCTION_MSG_TYPE

static

The type of the messages received from function nodes of the graph.

Referenced by getMsgTypes(), and notifyIn().

functionInfos

HashMap<String, FunctionInfo> frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.functionInfos

private

For each constraint in the agent's subproblem, its FunctionInfo.

infeasibleUtil

final U frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.infeasibleUtil

private

The infeasible utility.

Referenced by scaledRandSpace(), and zeroSpace().

maximize

final boolean frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.maximize

private

Whether to maximize utility or minimize cost.

maxNbrIter

final int frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.maxNbrIter

private

The algorithm will terminate when ALL function nodes have gone through that many iterations.

Referenced by frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FunctionInfo.FunctionInfo(), MaxSum(), and frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.VarInfo().

pendingMsgs

ArrayList<Message> frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.pendingMsgs = new ArrayList<Message> ()

private

Messages received and waiting to be processed.

problem

DCOPProblemInterface<V, U> frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.problem

private

The problem.

Referenced by frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FunctionInfo.FunctionInfo(), MaxSum(), MaxSum(), and frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.VarInfo().

queue

Queue frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.queue

private

This module's queue.

Referenced by getStatsFromQueue(), notifyIn(), setQueue(), and start().

randomInit

final boolean frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.randomInit

private

Whether to initialize the algorithm with random messages, or with messages full of zeros.

started

boolean frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.started = false

private

Whether the module has already started the algorithm.

synchronous

final boolean frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.synchronous

private

If true, then round-based execution; if false, then each function/variable node immediately responds to each message.

Referenced by frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FunctionInfo.doIrespond(), frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.doIrespond(), frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.FunctionInfo.FunctionInfo(), and frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VarInfo.VarInfo().

VARIABLE_MSG_TYPE

final MessageType frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.VARIABLE_MSG_TYPE = VariableMsg.VARIABLE_MSG_TYPE

static

The type of the messages received from variable nodes of the graph.

Referenced by getMsgTypes(), and notifyIn().

varInfos

HashMap<String, VarInfo> frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.varInfos

private

For each internal variable, its VarInfo.

zero

U frodo2.algorithms.maxsum.MaxSum< V extends Addable< V >, U extends Addable< U > >.zero

private

The 0 cost.

Referenced by scaledRandSpace(), and zeroSpace().

---

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

• src/frodo2/algorithms/maxsum/MaxSum.java