pydcop.algorithms.amaxsum

AMaxSum: Asynchronous belief-propagation DCOP algorithm

Max-Sum [FRPJ08] is an incomplete inference-based DCOP algorithm.

This is a asynchronous implementation of Max-Sum, where factors and variable send messages every time they receive a message. For a synchronous version, see MaxSum.

Algorithm Parameters

These are the same as for MaxSum

  • damping: float, default = 0.5

    Amount of damping [0-1].

  • damping_nodes: “vars”, “factors”, “both” or “none”, default = “both”

    Nodes that apply damping to messages.

  • stability: float, default = 0.1 (STABILITY_COEFFICIENT)

    Stability detection coefficient

  • noise: float, default = 0.01

    Noise level for variables

  • start_messages: “leafs”, “leafs_vars”, “all”, default = “leafs”

    Nodes that initiate messages.

Example

pydcop solve -algo amaxsum  \
 -d adhoc graph_coloring_csp.yaml

FIXME: add results

See also

Max-Sum: a synchronous implementation of Max-Sum.

class MaxSumFactorComputation(comp_def=None)

FactorAlgo encapsulate the algorithm running at factor’s node.

footprint() → float

The footprint of the computation.

A DCOP computation has a footprint, which represents the amount of memory this computation requires to run. This depends on the algorithm used and thus must be overwritten in subclasses. This footprint is used when distributing computation on agents, to ensure that agents only host computation they can run.

Returns:

the footprint

Return type:

float

on_pause(paused: bool)

Called when pausing or resuming the computation.

This method is meant to be overwritten in subclasses.

Parameters:

paused (boolean) – the new pause status. This method is only called is the status has changed

on_start()

Called when starting the computation.

This method is meant to be overwritten in subclasses.

class MaxSumVariableComputation(comp_def: ComputationDef | None = None)

Maxsum Computation for variable.

Parameters:

comp_def (ComputationDef) –

on_pause(paused: bool)

Called when pausing or resuming the computation.

This method is meant to be overwritten in subclasses.

Parameters:

paused (boolean) – the new pause status. This method is only called is the status has changed

on_start() → None

Startup handler for MaxSum variable computations.

At startup, a variable select an initial value and send its cost to the factors it depends on.