Published on Fri Apr 22 2016

Utilitarian Distributed Constraint Optimization Problems

Julien Savaux, Julien Vion, Sylvain Piechowiak, René Mandiau, Toshihiro Matsui, Katsutoshi Hirayama, Makoto Yokoo, Shakre Elmane, Marius Silaghi

Privacy has been a major motivation for distributed problem optimization. The Distributed Constraint Optimization Problem (DCOP) is a fundamental model used to approach various families of distributed problems. Privacy loss does not occur when a solution is accepted.

0
0
0
Abstract

Privacy has been a major motivation for distributed problem optimization. However, even though several methods have been proposed to evaluate it, none of them is widely used. The Distributed Constraint Optimization Problem (DCOP) is a fundamental model used to approach various families of distributed problems. As privacy loss does not occur when a solution is accepted, but when it is proposed, privacy requirements cannot be interpreted as a criteria of the objective function of the DCOP. Here we approach the problem by letting both the optimized costs found in DCOPs and the privacy requirements guide the agents' exploration of the search space. We introduce Utilitarian Distributed Constraint Optimization Problem (UDCOP) where the costs and the privacy requirements are used as parameters to a heuristic modifying the search process. Common stochastic algorithms for decentralized constraint optimization problems are evaluated here according to how well they preserve privacy. Further, we propose some extensions where these solvers modify their search process to take into account their privacy requirements, succeeding in significantly reducing their privacy loss without significant degradation of the solution quality.

Mon Mar 20 2017
Artificial Intelligence
Distributed Constraint Problems for Utilitarian Agents with Privacy Concerns, Recast as POMDPs
Privacy has traditionally been a major motivation for distributed problem solving. Here we approach the problem by assuming that computation is performed among utilitarian agents. We show that these extended solvers succeed in significantly reducing privacy loss without significant degradation of the solution quality.
0
0
0
Tue Feb 04 2014
Artificial Intelligence
Asymmetric Distributed Constraint Optimization Problems
Distributed Constraint Optimization (DCOP) is a powerful framework for representing and solving distributed combinatorial problems. Many multi-agent problems include constraints that produce different gains (or costs) for the participating agents. Asymmetric gains of constrained agents cannot beaturally represented by the standard DCOP model.
0
0
0
Wed May 07 2014
Artificial Intelligence
Logic and Constraint Logic Programming for Distributed Constraint Optimization
Distributed Constraint Optimization Problems (DCOPs) have gained momentum. This paper investigates an infrastructure for solving DCOPs that is built on logic programming technologies. The preliminary experiments show that logic programming provides benefits over a state-of-the-art DCOP system.
0
0
0
Sat Feb 20 2016
Artificial Intelligence
Distributed Constraint Optimization Problems and Applications: A Survey
Multi-Agent System (MAS) is an active area of research within Artificial Intelligence. Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent architectures to govern the agents' autonomous behavior.
0
0
0
Sat Sep 14 2019
Artificial Intelligence
Speeding Up Distributed Pseudo-tree Optimization Procedure with Cross Edge Consistency to Solve DCOPs
Distributed Pseudo-tree Optimization Procedure (DPOP) is a well-known message-passing algorithm. It has been used to provide optimal solutions of distributed Constraint Optimization Problems.
0
0
0
Wed Feb 22 2017
Artificial Intelligence
Solving DCOPs with Distributed Large Neighborhood Search
Solving Distributed Constraint Optimization Problems (DCOPs) optimally is NP-hard. In large-scale applications, incomplete DCOP algorithms are necessary. We propose a Distributed Large Neighborhood Search (D-LNS) framework to solve DCOPs.
0
0
0