Good morning,
I'm a Computer Engineer and I'm using Frodo for one of my project.
I've read the User Manual and also digged into the source code, but I'm unable to get an answer: is it possible to run Frodo in the following way?
I have 3 agents for instance: agent A, agent B and agent C.
Each daemon is assigned to a specific agent and it knows only the domains/varibales/constraint of that specific agent. Of course each deamon holds a subpart of the same problem, so there is a common shared goal. The controller only connects the daemons and starts the resolution of the problem, but it should not know all the agents' variables, domains, contraints, ecc.
Is it feasible?
Thank you in advance
Andrea
Hi Andrea,
Welcome to the FRODO2 user community!
The short answer to your question is: no, at the moment (i.e. in FRODO version 2.14), there is no way to deploy algorithms in a truely distributed setting, in which the problem instance to be solved would not be known to any central controller, but rather in which each agent would initially know its subproblem (rather than being told its subproblem by the controller, which would extract it from the overal problem).
The longer answer is: it might not take a lot of work to add support for this, but I would first be interested in better understanding what you are trying to achieve. Are you trying to deploy DCOP algorithms in real life? Why is it that, in your case, the controller (assuming that there indeed exists one) does not know the whole problem?
Would the following behavior be acceptable and suit your purpose?
1. You start a centralized controller;
2. You start one daemon per agent in your problem;
3. You tell each daemon how to contact the controller (using the "controller" command);
4. Rather than pass a centralized configuration file to the controller (using the "open" command), you pass one configuration file to each daemon, which lists one (or more, consecutive) subproblem file(s) for the corresponding agent;
5. You tell all agents to start solving the problem(s) by passing the "start" command to the controller.
Would such a usage procedure make sense?
Should the statistics about the problem (and in particular its solution) then be recorded and displayed by each agent rather that reported to the controller, which currently takes care of recording and displaying them?
Best,
Thomas
Last edit: Thomas B. Léauté 2016-12-17
Thank you for your prompt answer!
The problem involves some white-goods made my different manufacturers. Each appliance is an agent and it has some proprieties associated, such as its load profile, the internal states, ecc.
The manufacturers are not willing to share these proprieties freely and here comes the problem: the controller should not know these proprieties and each appliance should know only its own proprieties.
That’s fine. In my mind the controller can be any appliance (e.g. it could be chosen by election), but that’s not a big issue.
Yes, because each agent already knows its own configuration
Yes!
Yes, more or less. Let me explain better. Each agent has some shared variables which can be sent to every other agents and some private variables/constraints/domains, so, at the end of the process, everybody should know the final assignment only of the shared variables.
Do you think we can reach a comprimise and implement some of the feature?
Best,
Andrea
Hi Andrea,
Very interesting! So you indeed intend to deploy FRODO in real life... As far as I know, it would be a first. Until now, FRODO has only been used for scientific experiments, to compare the performance of various algorithms, in a setting where the experimenter knows the whole problem. This raises a few questions.
You mention that your problem domain contains shared variables. You should keep in mind that the vast majority of DCOP algorithms do not support shared variables; they assume that each variable is owned and controlled by a specific agent. To work around this limitation, for each shared variable, you need to introduce one copy of the variable owned by each interested agent, and introduce equality constraints between these variable copies to enforce that they take the same value. In the meeting scheduling domain, this is known as the "Private Events As Variables" formulation — "PEAV."
Furthermore, you mention that privacy is important in this problem domain. This means you need to be extra careful about your problem formulation. Most DCOP algorithms (with the exceptions of Max-Sum and MPC-Dis[W]CSP4) assume that each constraint is known to all agents owning a variable in its scope, so if you want a constraint to be private to one agent, it needs to involve only variables owned by that agent.
Similarly, if you want a variable (and its domain) to be private to one agent, it needs to be owned by that agent, and it needs to only share constraints with other variables owned by the same agent, because most DCOP algorithms assume that an agent knows all the variables involved in constraints expressed over its variables.
Once you have formulated the problem in such a way that each agent initially knows all it needs to know (and not more) to express its local sub-problem and run the DCOP algorithm, you have to keep in mind that executing the DCOP algorithm can leak private information about other agents' variables and constraints. Are you considering the use of privacy-preserving DCOP algorithms like P-DPOP, P3/2-DPOP, P2-DPOP, or MPC-Dis[W]CSP4 that address this?
Finally, at the moment the information exchanged between the FRODO agents is sent in clear text over the network, so someone evesdropping on the network would be able to discover private information about the agents' respective subproblems. Is this an issue?
Regardless of these concerns, I should be able to implement the functionality I proposed in my previous post, following which each agent's local subproblem is loaded directly at each daemon, rather than extracted by the controller from an overall problem. This could take 1-2 weeks, though.
Best,
Thomas
Hi Thomas
I’m currently involved in an academic project, its name is SMITh and its main goal is to create an ecosystem where all appliances are interconnected and can interact and without leveraging a central logic controller (where every appliance can autonomously choose how to behave, according to user desires).
I would like to apply Frodo to get a fast and reliable constrained optimization. Why am I talking about “optimization”?
Because an achievement of the system is to use as much as possible sustainable power sources (e.g solar panel), reduce costs and energy consumption (according also to possible new energy market where the energy cost is computed hourly and it’s not fixed).
Yes, I do. But I chose the wrong term because with “shared variables” I mean variables which are known by every agent.
To be more precise I make a very small example:
Let me consider a system with just 2 agents, agent A and agent B.
Agent A has a “private variable” called
x. The existence ofx, its values and everything else related toxmust remain unknown to agent B.Agent A has also a “shared variable” called
j. The value ofjcan be communicated outside the agent A, and also all the other proprieties related toj(domain, constraints involving it, ecc.) can be shared with the outside.This is what I mean with “shared” and ”private variable”.
That’s a very good point! In my very first implementation I have some constraints involving both private and shared variables.
For instance, one is the power consumption: the overall power must be lower than a fixed number every time step, but each agent should only know its own power consumption (and maybe the overall sum, but not in the detail the consumption on each other agent).
Is this feasible in some way or I should consider a relaxation of this “privacy issue”?
This is not a problem at this stage. Communication can be sent in clear text without any problem.
The timing of the implementation is not a problem! I could help you if needed (maybe expanding the Python module to support also running custom DCOP problem and not only the experiments but I don’t know the feasibility and how much it’s expandable, let me know if it could be useful).
Hi Andrea,
Does that mean that you would actually like a setting in which there is no controller at all? Or is it still OK to have a controller that tells the agents how to connect to each other (i.e. offers a "white pages" service) and tells them to start solving the problem, as long as the controller doesn't need to know the overall problem?
Most DCOP algorithms assume that a variable x is known to all agents controlling a neighboring variable (i.e. any other variable y that shares a constraint with x). I understand now that by "shared variable" you don't mean a variable that is not controlled by any specific agent — each "shared variable" would have a dedicated owner agent. However, if you want a variable to be known by all agents, then it needs to be constrained with at least one variable owned by each agent.
By the way, this is starting to raise some concerns about how coupled your problem is. If there exist "shared variables" that each agent has a constraint over, then it looks like the agents' respective subproblems are highly coupled. If this is the case, then you should not expect miracles from existing DCOP algorithms: they tend to only work well for DCOP problems in which the agents' respective subproblems are only loosely coupled.
How many agents are we talking about? What is the size of the domains of the "shared variables?"
If a constraint only involves variables owned by the same agent, then only that agent needs to know the constraint. However, if it involves variables owned by multiple agents, then most DCOP algorithm will require all of these agents to know the constraint. If you want to avoid this, you need to use the "PEAV" trick mentioned earlier.
I am planning to enrich FRODO with a way to take an overall problem, and have FRODO output each agent's subproblem. You will then be able to check whether your overall problem formulation has the desired properties in terms of which agent needs to know which variable and which constraint for the DCOP algorithms to be able to solve it.
It looks like you have a constraint that involves all agents (the upper bound on the overall power). As mentioned earlier, this makes the agents' respective subproblems tightly coupled, and might result in poor performance and/or solution quality with most DCOP algorithms.
Furthermore, the kind of privacy that you are describing is impossible to achieve with most existing DCOP algorithms, because there needs to be one agent that imposes the constraint on the overall power, and this agent needs to know each agent's power consumption in order to check that their overall sum is not higher than the limit. In order to hide from each agent the power consumptions of the other agents, you would need a DCOP algorithm that protects full decision privacy (have a look at my PhD thesis, Sections 3.1 and 3.6.4). In FRODO, there are "only" 3 DCOP algorithms that fully protect decision privacy: P3/2-DPOP, P2-DPOP, and MPC-DisWCSP4. None of them is able to scale to large problems (with a few exceptions, depending on the problem topology).
To get arond this, you could consider splitting the overall sum of all power consumptions into sums of sub-sums. If there are 3 agents in your problem, instead of imposing:
you could decompose the constraint as follows:
This way, the agent imposing the first constraint only needs to know the consumptions of Agents 1 & 2, and the agent imposing the second constraint only needs to know the consumption of Agent 3, and the total consumptions of Agents 1 & 2. This approach might also make the problem easier for existing DCOP algorithms. The problem is that it requires the agents to agree beforehand on a hierarchical way of decomposing the overall sum constraint.
Notice that there has been some previous work on DCOP with resource constraints. You might want to have a look at the paper below. Unfortunately, the algorithm described in that paper (which is a variant of ADOPT) has not yet been implemented in FRODO.
Toshihiro Matsui, Hiroshi Matsuo, Marius-Calin Silaghi, Katsutoshi Hirayama, and Makoto Yokoo. Resource constrained distributed constraint optimization with virtual variables. In Proceedings of the Twenty-Third Conference on Artificial Intelligence (AAAI’08), pages 120–125, Chicago, Illinois, USA, July 13—17 2008. AAAI Press.
In addition, I have done some work myself on a variant of DPOP that would efficiently handle sum constraints. This work has not yet been published (neither the theory in a paper, nor the code in FRODO).
If you intend to use FRODO's Python module to carry out experiments (which I think is a good idea), then there are at least two things you need to do (and I can't do them for you, since you know your problem domain, and I don't):
Best,
Thomas
Last edit: Thomas B. Léauté 2016-12-20
Hi Andrea,
FRODO version 2.15, which was just released, now includes:
1. a way to run FRODO without an omniscient controller;
2. a way to tell FRODO to take an overall problem description, and split it into each agent's corresponding subproblem (in your case, for debugging purposes).
Let me know if this helps and if you have any further questions.
Best wishes for 2017,
Thomas