FRODO Version 2.19.1
An open-source framework for Distributed Constraint Optimization (DCOP)
Loading...
Searching...
No Matches
frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > > Class Template Reference

This class is designed to store GOODs received by a node from its children, and is used in the ASODPOP algorithm. More...

Inheritance diagram for frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >:

Public Member Functions

 InnerNodeTree (String ownVariable, Val[] ownVariableDomain, UtilitySolutionSpace< Val, U > space, int numberOfChildren, U zero, U infeasibleUtil, boolean maximize, boolean collectStats)
 A constructor (Only used in testing the datastructure).
 InnerNodeTree (String ownVariable, Val[] ownVariableDomain, List< UtilitySolutionSpace< Val, U > > spaces, int numberOfChildren, U zero, U infeasibleUtil, boolean maximize, boolean collectStats)
 A constructor.
int add (Good< Val, U > g, int sender, HashMap< String, Val[]> domains)
 This method adds a received GOOD to the tree.
Good< Val, U > getAmax ()
 This method obtains the aMax.
void getBestAssignmentForOwnVariable (HashMap< String, Val > assignments)
 Given the assignment of variables in its separator, this method returns the best assignment possible.
Val getRandomValue ()
HashMap< String, Val > getChildValues (HashMap< String, Val > parentContext, int child)
 Given a map that maps variables to values, this method returns the values belonging to the variables in a child's separator.
int getVariableIndex (String variable)
int getSpeculativeUTILcounter ()
int getUTILcounter ()
boolean knowsVariable (String variable)
boolean notEnoughInfo ()
 If there is only one variable in this tree, that means that there is not enough information to send a good.
int getNbrVariables ()
boolean ignoreGood (Good< Val, U > g, int sender)
 If this good reports a value for an already confirmed assignment, the information in the good can be considered outdated and should be ignored.
void ownVariableValue (HashMap< String, Val > currentContext)
 Returns the value of the trees own variable for the current next best assignment.
boolean checkLeaf (LeafNode< U > leaf, IntArrayWrapper currentPath, boolean checkUB, U utility, int sender)
 Method to check that the utility and UB are consistent with the available information.
Public Member Functions inherited from frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.InnerNodeTree< Val, U, LeafNode< U > >
boolean add (Good< Val, U > g, int sender, HashMap< String, Val[]> domains)
 Adds a good to the tree.

Protected Member Functions

LeafNode< U > createLeaf (IntArrayWrapper currentPath, frodo2.algorithms.odpop.Good< Val, U > g, int child, final boolean withUB)
 Method to create a new leaf node.
LeafNode< U > createLeaf (IntArrayWrapper currentPath, final boolean withUB)
 Method to create a new leaf node.
boolean findUnused (int depth, int[] localPath, int[] unusedPath, InnerNode< U, LeafNode< U > > currentNode)
 Looks for parts of the tree where the local solution as defined by localPath can still be used to create new leafs.
getOwnVariableOptions (int[] optimalPath, Val[] assignments)
 Given the assignment of variables in its separator, this method returns the utility for all domain elements of the own variable.
void init (int numberOfChildren, U zero)
 Initialize all the variables of the tree.
void nextVariableAssignment (int[] max, int[] position)
 Given a point in the domain space of value combinations between 0 and max, the next point is calculated and position is set to this new point.
void updateLocalProblem ()
Protected Member Functions inherited from frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.InnerNodeTree< Val, U, LeafNode< U > >
 InnerNodeTree (L leafNodeInstance, String ownVariable, Val[] ownVariableDomain, UtilitySolutionSpace< Val, U > space, U zero, int numberOfChildren, U infeasibleUtil, boolean maximize, boolean collectStats)
 A dummy constructor to be used by extending classes.
frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > createInnerNode (int numberOfChildren)
void updateLocalProblem ()
recalculateUB (int depth, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > currentNode, U UBtoBeat, boolean recalculateUtil, boolean recalculateUB)
 This method recalculates the upper bound for a particular node.

Protected Attributes

U[] localOptions
 For each option the optimal utility your own local problem provides.

Private Member Functions

boolean checkGood (Val[] values)
 Method used to check whether the assignment to be reported by the good point to an existing assignment.

Private Attributes

ArrayList< HashMap< IntArrayWrapper, Boolean > > goodsConfirmed
 For each child a map that stores the utilities received from children.
Val[] optimalLocalSolution
 The optimal solution of the local problem.
int speculativeUTILcounter
 Counts the number of speculative UTIL messages.
int UTILcounter = 0
 Counts the total number of UTIl messages received.

Static Private Attributes

static final long serialVersionUID = 4206985864919963001L
 Used for serialization.

Additional Inherited Members

Static Protected Attributes inherited from frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.InnerNodeTree< Val, U, LeafNode< U > >
static final long serialVersionUID
 Used for serialization.

Detailed Description

This class is designed to store GOODs received by a node from its children, and is used in the ASODPOP algorithm.

A GOOD contains an assignment to a set of variables, a utility and a variable denoting whether it is a confirmed or speculative good. A GOOD is identified by its assignment, and in this class the GOODs are ordered using a tree based on these assignments.

The basic functionality of this class is to either add a received GOOD to the tree, or to obtain the assignment that has the highest utility.

Author
Brammert
Parameters
<Val>type used for variable values
<U>type used for utility values
Todo
write Unit test for this class

Constructor & Destructor Documentation

◆ InnerNodeTree() [1/2]

frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.InnerNodeTree ( String ownVariable,
Val[] ownVariableDomain,
UtilitySolutionSpace< Val, U > space,
int numberOfChildren,
U zero,
U infeasibleUtil,
boolean maximize,
boolean collectStats )

A constructor (Only used in testing the datastructure).

Warning
we assume that the agent's own variable is put in the end of variables_order
Parameters
ownVariableThe variable ID
ownVariableDomainThe domain of ownVariable
spaceA list of utility values for the different value combinations
numberOfChildrenThe number of children
zeroThe zero utility
infeasibleUtilThe infeasible utility
maximizewhen true we are maximizing, when false we are minimizing
collectStatstrue when statistics should be collected, and false otherwise

References init(), and updateLocalProblem().

Here is the call graph for this function:

◆ InnerNodeTree() [2/2]

frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.InnerNodeTree ( String ownVariable,
Val[] ownVariableDomain,
List< UtilitySolutionSpace< Val, U > > spaces,
int numberOfChildren,
U zero,
U infeasibleUtil,
boolean maximize,
boolean collectStats )

A constructor.

Warning
we assume that the agents own variable is put in the end of variables_order
Parameters
ownVariableThe variable ID
ownVariableDomainThe domain of ownVariable
spacesThe hypercubes representing the local problem
numberOfChildrenThe number of children
zeroThe zero utility
infeasibleUtilThe infeasible utility
maximizewhen true we are maximizing, when false we are minimizing
collectStatstrue when statistics should be collected, and false otherwise

References init(), and updateLocalProblem().

Here is the call graph for this function:

Member Function Documentation

◆ add()

◆ checkGood()

boolean frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.checkGood ( Val[] values)
private

Method used to check whether the assignment to be reported by the good point to an existing assignment.

Author
Brammert Ottens, 1 nov 2009
Parameters
valuesthe values constituting the assigment
Returns
true when the assignment exists and false otherwise

References checkGood(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.Node< U extends Addable< U > >.isAlive().

Referenced by checkGood(), and updateLocalProblem().

Here is the call graph for this function:

◆ checkLeaf()

boolean frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.checkLeaf ( LeafNode< U > leaf,
IntArrayWrapper currentPath,
boolean checkUB,
U utility,
int sender )

Method to check that the utility and UB are consistent with the available information.

The utility should match exactly, but because UBs are only recomputed when necessary, and then should only decrease by such a recomputation, the stored UB should be at least as high as the real UB

Parameters
leafthe leaf to be checked
currentPaththe path to this leaf
checkUBtrue when the UB must be checked
utilitythe utility reported by the sender
senderthe sender of the good
Returns
always returns true

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.getUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.getUtil(), and goodsConfirmed.

Here is the call graph for this function:

◆ createLeaf() [1/2]

LeafNode< U > frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.createLeaf ( IntArrayWrapper currentPath,
final boolean withUB )
protected

◆ createLeaf() [2/2]

LeafNode< U > frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.createLeaf ( IntArrayWrapper currentPath,
frodo2.algorithms.odpop.Good< Val, U > g,
int child,
final boolean withUB )
protected

◆ findUnused()

boolean frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.findUnused ( int depth,
int[] localPath,
int[] unusedPath,
InnerNode< U, LeafNode< U > > currentNode )
protected

Looks for parts of the tree where the local solution as defined by localPath can still be used to create new leafs.

Author
Brammert Ottens, 5 okt 2009
Parameters
depththe current depth in the tree
localPaththe path representing the local solution
unusedPatha path where the local solution has not yet been used
currentNodethe current node being visited
Returns
true when there are unused parts of the tree, and false otherwise

References findUnused().

Referenced by findUnused().

Here is the call graph for this function:

◆ getAmax()

Good< Val, U > frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getAmax ( )

This method obtains the aMax.

If aMax is a confirmed assignment, i.e. no other assignment will ever have a higher utility, then the path belonging to aMax must be removed.

Returns
Good

References getAmax().

Referenced by getAmax().

Here is the call graph for this function:

◆ getBestAssignmentForOwnVariable()

void frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getBestAssignmentForOwnVariable ( HashMap< String, Val > assignments)

Given the assignment of variables in its separator, this method returns the best assignment possible.

Parameters
assignmentsthe, possible partial, assignment to the variables in the variables separator

References getOwnVariableOptions().

Here is the call graph for this function:

◆ getChildValues()

HashMap< String, Val > frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getChildValues ( HashMap< String, Val > parentContext,
int child )

Given a map that maps variables to values, this method returns the values belonging to the variables in a child's separator.

Author
Brammert Ottens, 19 aug 2009
Parameters
parentContextthe value map
childthe child for who we want to know the separator values
Returns
an array containing the values of the child's separator variables

◆ getNbrVariables()

int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getNbrVariables ( )
Returns
the number of variables stored in this goods tree

◆ getOwnVariableOptions()

U frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getOwnVariableOptions ( int[] optimalPath,
Val[] assignments )
protected

Given the assignment of variables in its separator, this method returns the utility for all domain elements of the own variable.

Parameters
optimalPaththe path to the optimal solution
assignmentscollection of assignments of variables in the separator
Returns
an array of utilities

References getOwnVariableOptions().

Referenced by getBestAssignmentForOwnVariable(), and getOwnVariableOptions().

Here is the call graph for this function:

◆ getRandomValue()

Val frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getRandomValue ( )
Author
Brammert Ottens, 26 mei 2010
Returns
a random value in the domain of the owning variable

◆ getSpeculativeUTILcounter()

int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getSpeculativeUTILcounter ( )
Returns
total number of speculative UTIl messages received

◆ getUTILcounter()

int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getUTILcounter ( )
Returns
total number of UTIl messages received

◆ getVariableIndex()

int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getVariableIndex ( String variable)
Parameters
variablevariable ID
Returns
the depth of the variable in the array

◆ ignoreGood()

boolean frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.ignoreGood ( Good< Val, U > g,
int sender )

If this good reports a value for an already confirmed assignment, the information in the good can be considered outdated and should be ignored.

Author
Brammert Ottens, 4 sep 2009
Parameters
gthe good to be checked
senderthe sender of the good
Returns
true when the assignment in the good already has a confirmed utility

References frodo2.algorithms.odpop.Good< Val extends Addable< Val >, U extends Addable< U > >.getValues(), frodo2.algorithms.odpop.Good< Val extends Addable< Val >, U extends Addable< U > >.getVariables(), goodsConfirmed, and frodo2.algorithms.asodpop.Good< Val extends Addable< Val >, U extends Addable< U > >.isConfirmed().

Here is the call graph for this function:

◆ init()

void frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.init ( int numberOfChildren,
U zero )
protected

Initialize all the variables of the tree.

Parameters
numberOfChildrenThe number of children
zeroThe zero utility

References goodsConfirmed, init(), localOptions, and optimalLocalSolution.

Referenced by init(), InnerNodeTree(), and InnerNodeTree().

Here is the call graph for this function:

◆ knowsVariable()

boolean frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.knowsVariable ( String variable)
Parameters
variableThe variable for which we want to know whether this tree is aware of it
Returns
true if this tree is familier with this variable

◆ nextVariableAssignment()

void frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.nextVariableAssignment ( int[] max,
int[] position )
protected

Given a point in the domain space of value combinations between 0 and max, the next point is calculated and position is set to this new point.

Author
Brammert Ottens, 19 jul 2009
Parameters
maxfor each entry the maximal value
positionthe position in the domain space

Referenced by add().

◆ notEnoughInfo()

boolean frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.notEnoughInfo ( )

If there is only one variable in this tree, that means that there is not enough information to send a good.

Returns
boolean

◆ ownVariableValue()

void frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.ownVariableValue ( HashMap< String, Val > currentContext)

Returns the value of the trees own variable for the current next best assignment.

Author
Brammert Ottens, 10 nov 2009
Parameters
currentContextThe current assignment of all variables in ownVariable's separator

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U extends Addable< U >, L extends LeafNode< U > >.getChild(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U extends Addable< U >, L extends LeafNode< U > >.getMaxChild(), and ownVariableValue().

Referenced by ownVariableValue().

Here is the call graph for this function:

◆ updateLocalProblem()

void frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.updateLocalProblem ( )
protected

Member Data Documentation

◆ goodsConfirmed

ArrayList<HashMap<IntArrayWrapper, Boolean> > frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.goodsConfirmed
private

For each child a map that stores the utilities received from children.

Referenced by add(), checkLeaf(), createLeaf(), createLeaf(), ignoreGood(), and init().

◆ localOptions

U [] frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.localOptions
protected

For each option the optimal utility your own local problem provides.

Referenced by init().

◆ optimalLocalSolution

Val [] frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.optimalLocalSolution
private

The optimal solution of the local problem.

Referenced by init(), and updateLocalProblem().

◆ serialVersionUID

final long frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.serialVersionUID = 4206985864919963001L
staticprivate

Used for serialization.

◆ speculativeUTILcounter

int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.speculativeUTILcounter
private

Counts the number of speculative UTIL messages.

◆ UTILcounter

int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.UTILcounter = 0
private

Counts the total number of UTIl messages received.


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