|
FRODO Version 2.19.1
An open-source framework for Distributed Constraint Optimization (DCOP)
|
This class is designed to store GOODs received by a node from its children, and is used in the ASODPOP algorithm. More...

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. | |
| U | 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 () |
| U | 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. | |
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.
| <Val> | type used for variable values |
| <U> | type used for utility values |
| 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).
| ownVariable | The variable ID |
| ownVariableDomain | The domain of ownVariable |
| space | A list of utility values for the different value combinations |
| numberOfChildren | The number of children |
| zero | The zero utility |
| infeasibleUtil | The infeasible utility |
| maximize | when true we are maximizing, when false we are minimizing |
| collectStats | true when statistics should be collected, and false otherwise |
References init(), and updateLocalProblem().

| 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.
| ownVariable | The variable ID |
| ownVariableDomain | The domain of ownVariable |
| spaces | The hypercubes representing the local problem |
| numberOfChildren | The number of children |
| zero | The zero utility |
| infeasibleUtil | The infeasible utility |
| maximize | when true we are maximizing, when false we are minimizing |
| collectStats | true when statistics should be collected, and false otherwise |
References init(), and updateLocalProblem().

| int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.add | ( | Good< Val, U > | g, |
| int | sender, | ||
| HashMap< String, Val[]> | domains ) |
This method adds a received GOOD to the tree.
| g | The good to be added |
| sender | The sender of the good |
| domains | The domains of the reported variables |
true when a new variable has been discovered References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.InnerNodeTree< Val, U, LeafNode< U > >.createInnerNode(), frodo2.algorithms.odpop.Good< Val extends Addable< Val >, U extends Addable< U > >.getUtility(), 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, frodo2.algorithms.asodpop.Good< Val extends Addable< Val >, U extends Addable< U > >.isConfirmed(), and nextVariableAssignment().

|
private |
Method used to check whether the assignment to be reported by the good point to an existing assignment.
| values | the values constituting the assigment |
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().

| 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
| leaf | the leaf to be checked |
| currentPath | the path to this leaf |
| checkUB | true when the UB must be checked |
| utility | the utility reported by the sender |
| sender | the sender of the good |
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.

|
protected |
Method to create a new leaf node.
| currentPath | The path to the leaf |
| withUB | true when the upper bound must be set |
References frodo2.solutionSpaces.AddableDelayed< T extends Addable< T > >.addDelayed(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.counter, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.fromBooleanArrayToInt(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.getUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.getUtil(), goodsConfirmed, frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.LeafNode< U extends Addable< U > >.newInstance(), frodo2.solutionSpaces.AddableDelayed< T extends Addable< T > >.resolve(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.setUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.setUbSum(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.setUpToDate(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.setUtil(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.updateUB.

|
protected |
Method to create a new leaf node.
| currentPath | The path to the leaf |
| g | the received good |
| child | the child that reported it |
| withUB | true when the upper bound must be set |
References frodo2.solutionSpaces.AddableDelayed< T extends Addable< T > >.addDelayed(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.counter, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.fromBooleanArrayToInt(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.getUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.getUtil(), goodsConfirmed, frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.LeafNode< U extends Addable< U > >.newInstance(), frodo2.solutionSpaces.AddableDelayed< T extends Addable< T > >.resolve(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.setUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.setUbSum(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.setUpToDate(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.setUtil(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.LeafNode< U extends Addable< U > >.updateUB.

|
protected |
Looks for parts of the tree where the local solution as defined by localPath can still be used to create new leafs.
| depth | the current depth in the tree |
| localPath | the path representing the local solution |
| unusedPath | a path where the local solution has not yet been used |
| currentNode | the current node being visited |
true when there are unused parts of the tree, and false otherwise References findUnused().
Referenced by findUnused().

| Good< Val, U > frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getAmax | ( | ) |
| 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.
| assignments | the, possible partial, assignment to the variables in the variables separator |
References getOwnVariableOptions().

| 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.
| parentContext | the value map |
| child | the child for who we want to know the separator values |
| int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getNbrVariables | ( | ) |
|
protected |
Given the assignment of variables in its separator, this method returns the utility for all domain elements of the own variable.
| optimalPath | the path to the optimal solution |
| assignments | collection of assignments of variables in the separator |
References getOwnVariableOptions().
Referenced by getBestAssignmentForOwnVariable(), and getOwnVariableOptions().

| Val frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getRandomValue | ( | ) |
| int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getSpeculativeUTILcounter | ( | ) |
| int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getUTILcounter | ( | ) |
| int frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.getVariableIndex | ( | String | variable | ) |
| variable | variable ID |
| 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.
| g | the good to be checked |
| sender | the sender of the good |
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().

|
protected |
Initialize all the variables of the tree.
| numberOfChildren | The number of children |
| zero | The zero utility |
References goodsConfirmed, init(), localOptions, and optimalLocalSolution.
Referenced by init(), InnerNodeTree(), and InnerNodeTree().

| boolean frodo2.algorithms.asodpop.goodsTree.innerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U > >.knowsVariable | ( | String | variable | ) |
| variable | The variable for which we want to know whether this tree is aware of it |
true if this tree is familier with this variable
|
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.
| max | for each entry the maximal value |
| position | the position in the domain space |
Referenced by add().
| 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.
| 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.
| currentContext | The 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().

|
protected |
References checkGood(), and optimalLocalSolution.
Referenced by InnerNodeTree(), and InnerNodeTree().

|
private |
For each child a map that stores the utilities received from children.
Referenced by add(), checkLeaf(), createLeaf(), createLeaf(), ignoreGood(), and init().
|
protected |
For each option the optimal utility your own local problem provides.
Referenced by init().
|
private |
The optimal solution of the local problem.
Referenced by init(), and updateLocalProblem().
|
staticprivate |
Used for serialization.
|
private |
Counts the number of speculative UTIL messages.
|
private |
Counts the total number of UTIl messages received.