AOF-Based Algorithm for Dynamic Multi-Objective Distributed Constraint Optimization

Many real world problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Distributed Constraint Optimization Problem (MO-DCOP) is the extension of a mono-objective Distributed Constraint Optimization Problem (DCOP). A DCOP is a fundamental problem that can formalize various applications related to multi-agent cooperation. This problem consists of a set of agents, each of which needs to decide the value assignment of its variables so that the sum of the resulting rewards is maximized. An MO-DCOP is a DCOP which involves multiple criteria. Most researches have focused on developing algorithms for solving static problems. However, many real world problems are dynamic. In this paper, we focus on a change of criteria/objectives and model a Dynamic MO-DCOP (DMO-DCOP) which is defined by a sequence of static MO-DCOPs. Furthermore, we develop a novel algorithm for DMO-DCOPs. The characteristics of this algorithm are as follows: (i) it is a reused algorithm which finds Pareto optimal solutions for all MO-DCOPs in a sequence using the information of previous solutions, (ii) it utilizes the Aggregate Objective Function (AOF) technique which is the widely used classical method to find Pareto optimal solutions, and (iii) the complexity of this algorithm is determined by the induced width of problem instances.