DCOP algorithm Implementation
Note: This document build upon the tutorial Implementing a DCOP algorithm, you should follow it before reading this.
By providing all the infrastructure, pyDCOP makes it easier to implement a new DCOP algorithm ; you only have one python module to implement, with only one mandatory class.
To implement an algorithm you must:
create a python module
define one or several
Message
implement your logic in one or several
DcopComputation
class
Optionally, you may also
declare the algorithm’s parameters
implement some other methods used for some distribution methods
Module
An algorithm must be defined in its own module in pydcop.algorithms
.
For example, dsa
is implemented in the module pydcop.algorithms.dsa
.
The name of the module is the name you will use
when running your algorithm with the pydcop
command line interface (-a
or --algo
parameter).
For example, for a new algorithm named my_algorithm
,
you simply create a file my_algorithm.py
in pydcop/algorithms
.
You will then be able to use this algorithm
to solve a DCOP with the following command:
pydcop solve --algo my_algorithm [...]
The module of your algorithm must also have an attribute
named GRAPH_TYPE
which contains the name of the computation graph type used.
Available computation graph types are 'factor_graph'
, 'pseudo_tree'
and
'constraints_hypergraph'
, other could be defined in the future.
For example, in dsa.py
:
GRAPH_TYPE = 'constraints_hypergraph'
Messages
DCOP algorithms are message passing algorithms: they work by sending
messages to each other. You must define the message(s) used by your algorithm.
The easiest approach is to use the
message_type()
class factory method to define your message(s).
For example, the following will define a message type MyMessage
, with two
fields foo
and bar
:
MyMessage = message_type('MyMessage', ['foo', 'bar'])
You can then use MyMessage
like any class:
>>> msg = MyMessage(foo=42, bar=21)
>>> msg.foo
42
>>> msg.type
'MyMessage'
You can also subclass pydcop.infrastructure.computations.Message
,
which is more verbose but can be convenient if you want to use python’s type
annotations:
class MyMessage(Message):
def __init__(self, foot: int, bar; float):
super().__init__('my_message', None)
self._foo = foo
self._bar = bar
@property
def foo(self) -> int:
return self._foo
@property
def bar(self) -> float:
return self._bar
In any case, your messages must use the
pydcop.utils.simple_repr.SimpleRepr
mixin
(Message
already extends it)
for your message to be serializable.
When subclassing Message
or
using message_type()
this is done automatically.
This is necessary when running the agents in
different processes, as messages will be sent over the network.
Computation
An algorithms consists in one or several DcopComputation
class.
Most algorithms have one single type of computation, which is
responsible for selecting the value for a single variable.
In this case you must subclass VariableComputation
,
which provides some convenient methods for value selection.
For more complex algorithm, you can define several computations (with pyDCOP, your algorithm can have as many kind of computation as you want), look at MaxSum’s implementation for an example (MaxSum has two kind of computations, for Factor and Variable).
Receiving messages
At runtime, an instance of a computation is deployed on an agent, which notifies it when receiving a message. The computation then processes the message and, if necessary, emits new messages for other computations.
For each message type, you must declare a handler method using the
register()
decorator:
@register("my_message_type")
def _on_my_message(self, sender_name, msg, t):
# handle message of type 'my_message'
# sender_name is the name of the computation that sent the message
# t is the time the message was received by the agent.
Sending messages
When sending messages, a computation never needs
to care about the agent hosting the target computations :
all message routing and delivery is taken care of by
the agent and communication infrastructure.
Messages are sent by calling self.post_msg
:
self.post_msg(target_computation_name, message_object)
You can also send a message to all neighbors by using
self.post_to_all_neighbors
.
Selecting a value
In your computation, when selecting a value for a variable, you must
call self.value_selection
with the value and the associated local cost.
This is allows pyDcop to monitor value selection on each agent and
extract the final assignment:
self.value_selection(self._v.initial_value, local_cost)
The local_cost
is the cost as seen from this variable.
Cycles
Each your algorithm has a concept of cycle
(i.e. it works in sycnhronized steps), you should call
self.new_cycle()
when you start a new cycle.
Terminating the algorithm
TODO
Argument Parameters
If the algorithm supports parameters, you must give a definition of these
parameters in your module, by defining a variable named algo_params
that contains a list of AlgoParameterDef
.
See for example in mgm implementation:
algo_params = [
AlgoParameterDef('break_mode', 'str', ['lexic', 'random'], 'lexic'),
AlgoParameterDef('stop_cycle', 'int', None, None),
]
These definitions will be automatically used
(with pydcop.algorithms.prepare_algo_params()
) to check parameters
for validity and add default values.
An AlgoritmDef
instance populated with the parsed parameters will be passed to
your __init__
method, you can then use it to pass these parameters
to the computation instance.
Builder method
TODO
Distribution and deployment
Your module must also provide a a few predefined utility methods, used to build and deploy your algorithm, and may define some optional methods, used for deployment and distribution.
Most distribution methods require the following two methods. These methods are generally required for a correct distribution of the computations on agents, but if you only want to use oneagent distribution (or simply during development) you can simply return 0:
def computation_memory(computation: ComputationNode, links):
"""
This method must return the memory footprint for the given computation
from the graph.
"""
def communication_load(link: Link):
"""
This method must return the communication load for this link in the
computation graph.
"""
When deploying the computation, concrete MessagePassingComputation
objects
must be instantiated on their assigned agent. For this, an algorithm
module must also provide a factory method to build computation object:
def build_computation(node: ComputationNode, links: Iterable[Link], algo: AlgorithmDef)-> MessagePassingComputation:
"""
Build a computation instance for a given algorithm (and parameters)
"""
Computations’s footprint
TODO
Communication load
TODO