
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Distributed Pareto Local Search for MultiObjective DCOPs
Maxime CLEMENT Tenda OKIMOTO Katsumi INOUE
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E100D
No.12
pp.28972905 Publication Date: 2017/12/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2016AGP0006
Type of Manuscript: Special Section PAPER (Special Section on Frontiers in Agentbased Technology) Category: Information Network Keyword: multiobjective, distributed constraint optimization problem, pareto local search,
Full Text: PDF(408.1KB)>>
Summary:
Many real world optimization problems involving sets of agents can be modeled as Distributed Constraint Optimization Problems (DCOPs). A DCOP is defined as a set of variables taking values from finite domains, and a set of constraints that yield costs based on the variables' values. Agents are in charge of the variables and must communicate to find a solution minimizing the sum of costs over all constraints. Many applications of DCOPs include multiple criteria. For example, mobile sensor networks must optimize the quality of the measurements and the quality of communication between the agents. This introduces tradeoffs between solutions that are compared using the concept of Pareto dominance. MultiObjective Distributed Constraint Optimization Problems (MODCOPs) are used to model such problems where the goal is to find the set of Pareto optimal solutions. This set being exponential in the number of variables, it is important to consider fast approximation algorithms for MODCOPs. The bounded multiobjective maxsum (BMOMS) algorithm is the first and only existing approximation algorithm for MODCOPs and is suited for solving a lessconstrained problem. In this paper, we propose a novel approximation MODCOP algorithm called Distributed Pareto Local Search (DPLS) that uses a local search approach to find an approximation of the set of Pareto optimal solutions. DPLS provides a distributed version of an existing centralized algorithm by complying with the communication limitations and the privacy concerns of multiagent systems. Experiments on a multiobjective extension of the graphcoloring problem show that DPLS finds significantly better solutions than BMOMS for problems with medium to high constraint density while requiring a similar runtime.

