FRODO Version 2.19.1
An open-source framework for Distributed Constraint Optimization (DCOP)
Loading...
Searching...
No Matches
frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > > Class Template Reference

MB-DPOP's memory-bounded UTIL propagation phase. More...

Inheritance diagram for frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >:
Inheritance graph
[legend]

Classes

class  VarInfo
 The information about a given variable. More...

Public Member Functions

MessageType getStartMsgType ()
MessageType getDFSMsgType ()
 MemoryBoundedUTIL (DCOPProblemInterface< V, U > problem, Element parameters)
 Constructor.
 MemoryBoundedUTIL (Element parameters, DCOPProblemInterface< V, U > problem)
 Constructor in stats gatherer mode.
Collection< MessageType > getMsgTypes ()
void notifyIn (Message msg)
Public Member Functions inherited from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >
 UTILpropagation ()
 Default constructor.
 UTILpropagation (DCOPProblemInterface< Val, U > problem)
 Constructor.
 UTILpropagation (DCOPProblemInterface< Val, U > problem, Element parameters)
 Constructor from XML descriptions.
void reset ()
 UTILpropagation (Element parameters, DCOPProblemInterface< Val, U > problem)
 The constructor called in "statistics gatherer" mode.
void setQueue (Queue queue)
void getStatsFromQueue (Queue queue)
void setSilent (boolean silent)
Integer getMaxMsgDim ()
U getOptUtil ()
long getFinalTime ()
 Returns the time at which this module has finished, determined by looking at the timestamp of the stat messages.
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 DFS_MSG_TYPE = DFSgeneration.OUTPUT_MSG_TYPE
 The type of the messages containing information about the DFS.
Static Public Attributes inherited from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >
static MessageType START_MSG_TYPE = AgentInterface.START_AGENT
 The type of the message telling the module to start.
static MessageType FINISH_MSG_TYPE = AgentInterface.AGENT_FINISHED
 The type of the message telling the agent finished.
static MessageType DFS_MSG_TYPE = DFSgeneration.OUTPUT_MSG_TYPE
 The type of the messages containing information about the DFS.
static final MessageType UTIL_MSG_TYPE = new MessageType ("DPOP", "UTILpropagation", "UTIL")
 The type of the messages containing utilities.
static final MessageType OUTPUT_MSG_TYPE = new MessageType ("DPOP", "UTILpropagation", "UTILoutput")
 The type of the messages containing conditional optimal assignments.
static final MessageType SEPARATOR_MSG_TYPE = new MessageType ("DPOP", "UTILpropagation", "Separator")
 The type of the messages containing separators.
static final MessageType OPT_UTIL_MSG_TYPE = new MessageType ("DPOP", "UTILpropagation", "OptUtil")
 The type of the messages containing optimal utility values sent by roots.
static final MessageType UTIL_STATS_MSG_TYPE = new MessageType ("DPOP", "UTILpropagation", "UTILstats")
 The type of messages sent to the statistics monitor.

Protected Member Functions

VarInfo newClusterInfo ()
void projectAndSend (ClusterInfo info)
void sendSeparator (String senderVar, String senderAgent, String dest, String[] separator)
void record (String senderVar, UtilitySolutionSpace< V, U > space, ClusterInfo info)
Protected Member Functions inherited from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >
void init ()
 Parses the problem.
void record (String senderVar, UtilitySolutionSpace< Val, U > space, ClusterInfo info)
 Records the input space until spaces from all children have been received.
ProjOutput< Val, U > project (UtilitySolutionSpace< Val, U > space, String[] vars)
 Projects the input variable from the input space.
void sendToParent (String var, String parentVar, String parentAgent, UtilitySolutionSpace< Val, U > space)
 Sends a UTIL message.
void sendOutput (UtilitySolutionSpace< Val, U > space, String root)
 Sends the output optimal utility to itself (i.e.

Additional Inherited Members

Protected Attributes inherited from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >
boolean withAnonymVars = false
 Whether the parser should consider variables with no specified owner.
DCOPProblemInterface< Val, U > problem
 The problem.
boolean started = false
 Whether the execution of the algorithm has been started.
boolean maximize = true
 true if we want to maximize utility, false if we want to minimize cost
Queue queue
 The queue on which it should call sendMessage().
Map< String, ClusterInfo > infos
 For each variable this agent owns, its relevant information.
String myID
 This agent's name.
U optUtil
 The optimal utility found to the problem.
boolean reportStats = true
 Whether to report stats.

Detailed Description

MB-DPOP's memory-bounded UTIL propagation phase.

Adrian Petcu and Boi Faltings. MB-DPOP: A new memory-bounded algorithm for distributed optimization. In Manuela M. Veloso, editor, Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07), pages 1452-1457, Hyderabad, India, January 6-12 2007.

Author
Thomas Leaute
Parameters
<V>the type used for variable values
<U>the type used for utility values

Constructor & Destructor Documentation

◆ MemoryBoundedUTIL() [1/2]

frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.MemoryBoundedUTIL ( DCOPProblemInterface< V, U > problem,
Element parameters )

Constructor.

Parameters
problemthe agent's subproblem
parametersthe module parameters

References frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.problem.

◆ MemoryBoundedUTIL() [2/2]

frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.MemoryBoundedUTIL ( Element parameters,
DCOPProblemInterface< V, U > problem )

Constructor in stats gatherer mode.

Parameters
parametersthe module parameters
problemthe overall problem

References frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.problem.

Member Function Documentation

◆ getDFSMsgType()

MessageType frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.getDFSMsgType ( )
Returns
the type of the DFS output

Reimplemented from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.

References DFS_MSG_TYPE.

◆ getMsgTypes()

Collection< MessageType > frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.getMsgTypes ( )
See also
UTILpropagation.getMsgTypes()

Reimplemented from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.

References frodo2.algorithms.dpop.memory.ContextMsg< V extends Addable< V > >.CONTEXT_MSG_TYPE, frodo2.algorithms.dpop.memory.LabelMsg< V extends Addable< V > >.LABEL_MSG_TYPE, frodo2.algorithms.dpop.memory.LabelingPhase< V extends Addable< V > >.OUTPUT_MSG_TYPE, and frodo2.algorithms.dpop.VALUEpropagation< Val extends Addable< Val > >.VALUE_MSG_TYPE.

◆ getStartMsgType()

MessageType frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.getStartMsgType ( )
Returns
the type of the start message

Reimplemented from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.

References START_MSG_TYPE.

◆ newClusterInfo()

VarInfo frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.newClusterInfo ( )
protected
Returns
a new VarInfo

Reimplemented from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.

References frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.ClusterInfo.nbrUTIL.

Referenced by notifyIn().

◆ notifyIn()

void frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.notifyIn ( Message msg)
See also
UTILpropagation.notifyIn(Message)
Todo
Add support for clustered pseudo-trees

Reimplemented from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.

References frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.ccs, frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.ccsByChild, frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.context, frodo2.algorithms.dpop.memory.ContextMsg< V extends Addable< V > >.CONTEXT_MSG_TYPE, frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.contextValues, frodo2.communication.MessageType.equals(), frodo2.algorithms.dpop.memory.ContextMsg< V extends Addable< V > >.getCCs(), frodo2.algorithms.dpop.memory.LabelMsg< V extends Addable< V > >.getCCs(), frodo2.algorithms.dpop.memory.ContextMsg< V extends Addable< V > >.getDest(), frodo2.algorithms.dpop.memory.LabelMsg< V extends Addable< V > >.getDest(), frodo2.algorithms.dpop.VALUEmsg< Val extends Addable< Val > >.getDest(), frodo2.communication.MessageWith2Payloads< T1 extends Serializable, T2 extends Serializable >.getPayload1(), frodo2.communication.MessageWith2Payloads< T1 extends Serializable, T2 extends Serializable >.getPayload2(), frodo2.algorithms.dpop.memory.LabelMsg< V extends Addable< V > >.getSender(), frodo2.algorithms.dpop.memory.LabelMsg< V extends Addable< V > >.getSep(), frodo2.communication.Message.getType(), frodo2.algorithms.dpop.memory.ContextMsg< V extends Addable< V > >.getValues(), frodo2.algorithms.dpop.VALUEmsg< Val extends Addable< Val > >.getValues(), frodo2.algorithms.dpop.VALUEmsg< Val extends Addable< Val > >.getVariables(), frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.infos, frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.iter, frodo2.java, frodo2.algorithms.dpop.memory.LabelMsg< V extends Addable< V > >.LABEL_MSG_TYPE, frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.lastUTIL, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.ClusterInfo.nbrChildren, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.ClusterInfo.nbrUTIL, newClusterInfo(), frodo2.algorithms.dpop.memory.LabelingPhase< V extends Addable< V > >.OUTPUT_MSG_TYPE, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.problem, projectAndSend(), frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.projOutput, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.queue, frodo2.algorithms.dpop.VALUEpropagation< Val extends Addable< Val > >.VALUE_MSG_TYPE, and frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.ClusterInfo.vars.

Here is the call graph for this function:

◆ projectAndSend()

void frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.projectAndSend ( ClusterInfo info)
protected
See also
UTILpropagation.projectAndSend(UTILpropagation.ClusterInfo)
Todo
Add support for clustered pseudo-trees

Reimplemented from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.

References frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.blindProject(), frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.ccs, frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.ccsByChild, frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.context, frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.contextValues, frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.ProjOutput< V extends Addable< V >, U extends Addable< U > >.getAssignments(), frodo2.solutionSpaces.SolutionSpace< V extends Addable< V > >.SparseIterator< V >.getCurrentSolution(), frodo2.solutionSpaces.SolutionSpace< V extends Addable< V > >.Iterator< V >.hasNext(), frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.iter, frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.iterator(), frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.lastUTIL, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.myID, frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.SparseIterator< V, U >.nextUtility(), frodo2.output, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.ClusterInfo.parent, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.problem, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.project(), frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.projOutput, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.queue, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.reportStats, frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.resolve(), frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.sepValues, frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.slice(), frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.sliceIn, frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.ProjOutput< V extends Addable< V >, U extends Addable< U > >.space, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.ClusterInfo.spaces, frodo2.algorithms.AgentInterface< V extends Addable< V > >.STATS_MONITOR, frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.ClusterInfo.vars, and frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable< U > >.ProjOutput< V extends Addable< V >, U extends Addable< U > >.varsOut.

Referenced by notifyIn().

Here is the call graph for this function:

◆ record()

void frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.record ( String senderVar,
UtilitySolutionSpace< V, U > space,
ClusterInfo info )
protected
See also
UTILpropagation.record(java.lang.String, UtilitySolutionSpace, UTILpropagation.ClusterInfo)

References frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.ccsByChild, and frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.VarInfo.sliceIn.

◆ sendSeparator()

void frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.sendSeparator ( String senderVar,
String senderAgent,
String dest,
String[] separator )
protected
See also
UTILpropagation.sendSeparator(java.lang.String, String, java.lang.String, java.lang.String[])

Reimplemented from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >.

Member Data Documentation

◆ DFS_MSG_TYPE

MessageType frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.DFS_MSG_TYPE = DFSgeneration.OUTPUT_MSG_TYPE
static

The type of the messages containing information about the DFS.

Referenced by getDFSMsgType().

◆ START_MSG_TYPE

MessageType frodo2.algorithms.dpop.memory.MemoryBoundedUTIL< V extends Addable< V >, U extends Addable< U > >.START_MSG_TYPE = AgentInterface.START_AGENT
static

The type of the message telling the module to start.

Referenced by getStartMsgType().

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