pydcop.algorithms.mgm

MGM : Maximum Gain Message

Algorithm Parameters

MGM supports two parameters:

  • break_mode: lexic or random, defaulting to lexic

  • stop_cycle: integer

Example

TODO

BREAK_MODES = ['lexic', 'random']

MGM supports two parameters:

  • break_mode

  • stop_cycle

class MgmComputation(computation_definition: ComputationDef)

MgmComputation implements MGM algorithm as described in ‘Distributed Algorithms for DCOP: A Graphical-Game-Base Approach’ (R. Maheswaran, J. Pearce, M. Tambe, 2004).

Parameters:

computation_definition (ComputationDef) –

property neighbors: Set[str]

The neighbors of this computation.

Notes

This is just a convenience shorthand to the neighbors of the node in the computation node :

my_dcop_computation.computation_def.node.neighbors

Returns:

a list containing the names of the neighbor computations.

Return type:

list of string

on_start()

Start the algorithm and select an initial value for the variable when the agent is started.

class MgmGainMessage(value, random_nb=0)

A class designed to send Gain messages to inform neighbors about the maximum (local) gain the variable can achieve if it changes its value

property size

Returns the size of the message.

You should overwrite this methods in subclasses, will be used when computing the communication load of an algorithm and by some distribution methods that optimize the distribution of computation for communication load.

Returns:

size

Return type:

int

class MgmValueMessage(value)

A class to send Value messages to neighbors to inform them of the variable value

property size

Returns the size of the message.

You should overwrite this methods in subclasses, will be used when computing the communication load of an algorithm and by some distribution methods that optimize the distribution of computation for communication load.

Returns:

size

Return type:

int

communication_load(src: VariableComputationNode, target: str) → float

Return the communication load between two variables.

Notes

The main messages in MGM are the ‘value’ and ‘gain’ messages, which both contains a simple value.

Parameters:

  • src (VariableComputationNode) – The ComputationNode for the source variable.

  • target (str) – the name of the other variable src is sending messages to

Returns:

The size of messages sent from the src variable to the target variable.

Return type:

float

computation_memory(computation: VariableComputationNode) → float

Return the memory footprint of a MGM computation.

Notes

With MGM, a computation must only remember the current value for each of it’s neighbors.

Parameters:

  • computation (VariableComputationNode) – a computation in the hyper-graph computation graph

  • links (iterable of links) – links for this computation node. links maps to constraints in the computation graph and can be hyper-edges (when the arity of the constraint is > 2)

Returns:

the memory footprint of the computation.

Return type:

float