pyDCOP: DCOP solver in python¶
Overview¶
pyDCOP is a library and command line application for Distributed Constraints Optimization Problems (aka DCOP).
A Distributed Constraints Optimization Problems is traditionally represented as a tuple \(\langle \mathcal{A}, \mathcal{X}, \mathcal{D}, \mathcal{C}, \mu \rangle\) , where:
\(\mathcal{A} = \{a_1,\ldots,a_{|A|}\}\) is a set of agents;
\(\mathcal{X} = \{x_1,\ldots, x_n\}\) are variables owned by the agents;
\(\mathcal{D} = \{\mathcal{D}_{x_1},\ldots,\mathcal{D}_{x_n}\}\) is a set of finite domains, such that variable \(x_i\) takes values in \(\mathcal{D}_{x_i} = \{v_1,\ldots, v_k\}\);
\(\mathcal{C} = \{c_1,\ldots,c_m\}\) is a set of soft constraints, where each \(c_i\) defines a cost \(\in \mathbb{R} \cup \{\infty\}\) for each combination of assignments to a subset of variables (a constraint is initially known only to the agents involved);
\(\mu: \mathcal{X} \rightarrow \mathcal{A}\) is a function mapping variables to their associated agent.
A solution to the DCOP is an assignment to all variables that minimizes the overall sum of costs.
pyDCOP has already been used for several scientific papers.
Features¶
pyDCOP provides implementations of many classic DCOP algorithms (DSA, MGM, MaxSum, DPOP, etc.).
pyDCOP allows you to implement our own DCOP algorithm easily, by providing all the required infrastructure: agents, messaging system, metrics collection, etc.
Agents can run on the same computer or on different machines, making real distributed experiments easy.
Multi-platform : pyDCOP can run on windows, Mac and Linux.
pyDCOP is especially suited for IoT use-case and can run agents on single-board computers like the Raspberry Pi.
In addition to classical DCOP algorithm, pyDCOP also provide novel approaches for using DCOP in IoT systems: several strategies are available to distribute DCOP computations on agents and achieve resiliency.
Documentation¶
Contributing¶
We welcome contributions, especially the implementation of DCOP algorithms (novel or well-known). Join us on GitHub.
Licence¶
pyDCOP is license under the BSD-3-clause license.