pydcop.algorithms.mgm2

MGM2 : a 2-coordinated DCOP algorithm

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

Algorithm’s parameters:

threshold: float
the threshold under which the agent is an offerer. This must be between 0 and 1. Defaults to 0.5.
favor: str
the type of move that is favored by the algorithm : ‘unilateral’, ‘no’ or ‘coordinated’. Defaults to ‘unilateral’.
stop_cycle: int
number of cycles before stopping. If None, the computation does not stop autonomously.

class Mgm2Computation(computation_def: ComputationDef | None = None)

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

Warning: The attribute _neighbors is the list of the variable neighbors as Variable objects, while the property neighbors gives access to the list of the names of neighbors’ variables.

Parameters:: computation_def (ComputationDef) – The computation definition this computation has been built from.

on_start(): Start the computation node with randomly choosing a value for its variable and entering value mode.

on_stop()

Called when stopping the computation

This method is meant to be overwritten in subclasses.

class Mgm2GainMessage(value)

Class to send to neighbors what best gain can be achieved by the agent if it moves alone

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 Mgm2GoMessage(go: bool)

Class to send my commited partner if we can change our values or not

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 Mgm2OfferMessage(offers: Dict[Tuple[Any, Any], float] | None = None, is_offering=False)

Class to send an offer message to a neighbor. The value of the message is a dictionary which keys are couples representing coordinate moves (sender_val, receiver_val), and which values are the gain realized by the offerer. E.g. {(1,0): 5, (0,1): 2}

Moreover, to handle asynchronicity, we add the following fact. Each agent send an offer message to all its neighbors. The agent distinguish a real offer thanks to the ‘offer’ attribute. A real (fake) offer has ‘offer’ set to ‘(not) offering’. This artifice allows every agents to know if they have received all the offers they should before processing next step.

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 Mgm2ResponseMessage(accept: bool, value=None, gain=None)

Class to send a response message to an offer made by a neighbor

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 Mgm2ValueMessage(value)

Class to send a message informing neighbors of the agent 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

build_computation: alias of Mgm2Computation

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

Return the communication load between two variables.

Notes

The biggest messages in MGM2 is the ‘offer’ message, which contains a map of coordinated moves and associated gains.

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 MGM2 computation.

Notes

With MGM2, a computation must remember the current value and gain for each of its neighbors.

Parameters:: computation (VariableComputationNode) – a computation in the hyper-graph computation graph
Returns:: the memory footprint of the computation.
Return type:: float