E[DPOP]'s UTIL propagation phase. More...

Inheritance diagram for frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >:

[legend]

Classes
enum	Method
	The method to use to choose the optimal value for a variable. More...

Public Member Functions
	ExpectedUTIL (DCOPProblemInterface< Val, U > problem, Element parameters)
	Constructor.
	ExpectedUTIL (Element parameters, DCOPProblemInterface< Val, U > problem)
	The constructor called in "statistics gatherer" mode.
void	reset ()
Collection< MessageType >	getMsgTypes ()
void	getStatsFromQueue (Queue queue)
U	getWorstUtil ()
U	getExpectedUtil ()
U	getProbOfOptimality ()
void	notifyIn (Message msg)
HashMap< String, Val >	getSolution ()
Public Member Functions inherited from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >
MessageType	getStartMsgType ()
MessageType	getDFSMsgType ()
	UTILpropagation ()
	Default constructor.
	UTILpropagation (DCOPProblemInterface< Val, U > problem)
	Constructor.
	UTILpropagation (DCOPProblemInterface< Val, U > problem, Element parameters)
	Constructor from XML descriptions.
	UTILpropagation (Element parameters, DCOPProblemInterface< Val, U > problem)
	The constructor called in "statistics gatherer" mode.
void	setQueue (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	RAND_VARS_PROJ_MSG_TYPE = SamplingPhase.RAND_VARS_PROJ_MSG_TYPE
	The type of the messages containing information about the where random variables should be projected out.
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
void	parseMethod (Element parameters)
	Parses the method to use.
ProjOutput< Val, U >	project (UtilitySolutionSpace< Val, U > space, String[] vars)
void	sendToParent (String var, String parentVar, String parentAgent, UtilitySolutionSpace< Val, U > space)
	Before sending the UTIL message, projects out the relevant random variables.
void	sendOutput (UtilitySolutionSpace< Val, U > space, String root)
void	sendSeparator (String sender, String senderAgent, String dest, String[] separator)
Protected Member Functions inherited from frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable< U > >
void	init ()
	Parses the problem.
ClusterInfo	newClusterInfo ()
void	record (String senderVar, UtilitySolutionSpace< Val, U > space, ClusterInfo info)
	Records the input space until spaces from all children have been received.
void	projectAndSend (ClusterInfo info)
	Projects out a variable and sends the result to its parent (if any) or to itself (to initiate VALUE propagation).

Protected Attributes
HashMap< String, HashSet< String > >	randVarsProj = new HashMap< String, HashSet<String> > ()
	For each variable, the random variables that should be projected out of its UTIL message.
Method	method = Method.EXPECTATION
	The method to use.
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.

Private Member Functions
void	sliceSpaces (ClusterInfo varInfo)
	Slices the spaces stored for the input variable according to the sampled domains.

Private Attributes
HashMap< String, Val >	solution = new HashMap<String, Val> ()
	For each variable, its optimal value.
int	remainingVars
	The number of variables owned by this agents that still have not sent VALUE messages to all their children.
U	worstUtil
	The worst-case utility.
U	expectedUtil
	The expected utility.
U	zero
	The utility 0.
U	one
	The utility 1.
boolean	measureProbOfOpt = false
	Whether to measure the probability of optimality.
U	probOfOptimality
	The total probability of the scenarios for which the chosen solution is optimal.

Detailed Description

E[DPOP]'s UTIL propagation phase.

The difference with the normal UTILpropagation phase is that it "projects out" the random variables by computing the expectation over these variables.

Author: Thomas Leaute

Parameters

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

Warning: This implementation currently assumes all variables owned by any given agent belong to the same component of the overall constraint graph, and might not work properly if this assumption is violated.

Constructor & Destructor Documentation

◆ ExpectedUTIL() [1/2]

frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable< U > >.ExpectedUTIL	(	DCOPProblemInterface< Val, U >	problem,
		Element	parameters )

Constructor.

Parameters

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

References parseMethod(), frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable >.problem, and frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable >.withAnonymVars.

Here is the call graph for this function:

◆ ExpectedUTIL() [2/2]

frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable< U > >.ExpectedUTIL	(	Element	parameters,
		DCOPProblemInterface< Val, U >	problem )

The constructor called in "statistics gatherer" mode.

Parameters

problem	the overall problem
parameters	the description of what statistics should be reported

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

Member Function Documentation

◆ getExpectedUtil()

U frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.getExpectedUtil ( )

Returns: the expected utility

◆ getMsgTypes()

Collection< MessageType > frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.getMsgTypes ( )

See also: UTILpropagation.getMsgTypes()

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

References RAND_VARS_PROJ_MSG_TYPE.

◆ getProbOfOptimality()

U frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.getProbOfOptimality ( )

Returns: the total probability of the scenarios for which the chosen solution is optimal

◆ getSolution()

HashMap< String, Val > frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.getSolution ( )

Returns: the solution

References solution.

Referenced by frodo2.algorithms.dpop.stochastic.E_DPOPsolver< V extends Addable< V >, U extends Addable >.buildSolution().

◆ getStatsFromQueue()

void frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.getStatsFromQueue ( Queue queue )

See also: UTILpropagation.getStatsFromQueue(Queue)

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

References frodo2.algorithms.SolutionCollector< V extends Addable< V >, U extends Addable >.ASSIGNMENTS_MSG_TYPE, and frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable >.queue.

◆ getWorstUtil()

U frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.getWorstUtil ( )

Returns: the worst-case utility

References worstUtil.

◆ notifyIn()

void frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.notifyIn ( Message msg )

See also: UTILpropagation.notifyIn(Message)

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

Here is the call graph for this function:

◆ parseMethod()

void frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.parseMethod ( Element parameters )

protected

Parses the method to use.

Parameters

parameters the parameters for the module

Todo: Add support for ROBUST method, by merging code from WorstCaseUTIL

Reimplemented in frodo2.algorithms.dpop.stochastic.robust.WorstCaseUTIL< Val extends Addable< Val >, U extends Addable >.

References frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.Method.CONSENSUS, frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.Method.CONSENSUS_ALL_SOLS, frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.Method.EXPECTATION, and frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.Method.EXPECTATION_MONOTONE.

Referenced by ExpectedUTIL().

◆ project()

ProjOutput< Val, U > frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable< U > >.project	(	UtilitySolutionSpace< Val, U >	space,
		String[]	vars )

protected

See also: UTILpropagation.project(UtilitySolutionSpace, java.lang.String[])

Todo: Add support for clusters

Todo: Add support for Method.ROBUST

Todo: call argProjExpectMonotone() instead

Todo: call argProject() instead

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

Reimplemented in frodo2.algorithms.dpop.stochastic.robust.WorstCaseUTIL< Val extends Addable< Val >, U extends Addable >.

Here is the call graph for this function:

◆ reset()

void frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.reset ( )

See also: UTILpropagation.reset()

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

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

◆ sendOutput()

void frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable< U > >.sendOutput	(	UtilitySolutionSpace< Val, U >	space,
		String	root )

protected

See also: UTILpropagation.sendOutput(UtilitySolutionSpace, java.lang.String)

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

Reimplemented in frodo2.algorithms.dpop.stochastic.robust.WorstCaseUTIL< Val extends Addable< Val >, U extends Addable >.

References frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable >.expectation(), and frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable >.problem.

Here is the call graph for this function:

◆ sendSeparator()

void frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable< U > >.sendSeparator	(	String	sender,
		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 >.

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

◆ sendToParent()

void frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable< U > >.sendToParent	(	String	var,
		String	parentVar,
		String	parentAgent,
		UtilitySolutionSpace< Val, U >	space )

protected

Before sending the UTIL message, projects out the relevant random variables.

See also: UTILpropagation.sendToParent(java.lang.String, java.lang.String, String, UtilitySolutionSpace)

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

Reimplemented in frodo2.algorithms.dpop.stochastic.robust.WorstCaseUTIL< Val extends Addable< Val >, U extends Addable >.

References frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable >.expectation(), and frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable >.problem.

Here is the call graph for this function:

◆ sliceSpaces()

void frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.sliceSpaces ( ClusterInfo varInfo )

private

Slices the spaces stored for the input variable according to the sampled domains.

Parameters

varInfo the var info

References frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable >.iterator(), frodo2.algorithms.dpop.UTILpropagation< Val extends Addable< Val >, U extends Addable >.problem, frodo2.solutionSpaces.UtilitySolutionSpace< V extends Addable< V >, U extends Addable >.slice(), and sliceSpaces().

Referenced by notifyIn(), and sliceSpaces().

Here is the call graph for this function:

Member Data Documentation

◆ expectedUtil

U frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.expectedUtil

private

The expected utility.

◆ measureProbOfOpt

boolean frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.measureProbOfOpt = false

private

Whether to measure the probability of optimality.

◆ method

Method frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.method = Method.EXPECTATION

protected

The method to use.

◆ one

U frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.one

private

The utility 1.

◆ probOfOptimality

U frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.probOfOptimality

private

The total probability of the scenarios for which the chosen solution is optimal.

◆ RAND_VARS_PROJ_MSG_TYPE

MessageType frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.RAND_VARS_PROJ_MSG_TYPE = SamplingPhase.RAND_VARS_PROJ_MSG_TYPE

static

The type of the messages containing information about the where random variables should be projected out.

Referenced by getMsgTypes(), and notifyIn().

◆ randVarsProj

HashMap< String, HashSet<String> > frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.randVarsProj = new HashMap< String, HashSet<String> > ()

protected

For each variable, the random variables that should be projected out of its UTIL message.

Referenced by frodo2.algorithms.dpop.stochastic.robust.WorstCaseUTIL< Val extends Addable< Val >, U extends Addable >.project(), and frodo2.algorithms.dpop.stochastic.robust.WorstCaseUTIL< Val extends Addable< Val >, U extends Addable >.sendToParent().

◆ remainingVars

int frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.remainingVars

private

The number of variables owned by this agents that still have not sent VALUE messages to all their children.

◆ solution

HashMap<String, Val> frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.solution = new HashMap<String, Val> ()

private

For each variable, its optimal value.

Referenced by getSolution(), and notifyIn().

◆ worstUtil

U frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.worstUtil

private

The worst-case utility.

Referenced by getWorstUtil().

◆ zero

U frodo2.algorithms.dpop.stochastic.ExpectedUTIL< Val extends Addable< Val >, U extends Addable >.zero

private

The utility 0.

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

src/frodo2/algorithms/dpop/stochastic/ExpectedUTIL.java

Classes

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ExpectedUTIL() [1/2]

◆ ExpectedUTIL() [2/2]

Member Function Documentation

◆ getExpectedUtil()

◆ getMsgTypes()

◆ getProbOfOptimality()

◆ getSolution()

◆ getStatsFromQueue()

◆ getWorstUtil()

◆ notifyIn()

◆ parseMethod()

◆ project()

◆ reset()

◆ sendOutput()

◆ sendSeparator()

◆ sendToParent()

◆ sliceSpaces()

Member Data Documentation

◆ expectedUtil

◆ measureProbOfOpt

◆ method

◆ one

◆ probOfOptimality

◆ RAND_VARS_PROJ_MSG_TYPE

◆ randVarsProj

◆ remainingVars

◆ solution

◆ worstUtil

◆ zero