A Two-Phase Complete Algorithm for Multi-Objective Distributed Constraint Optimization
Alexandre Medi*, Tenda Okimoto**, and Katsumi Inoue***
*University of Nantes, Direction des Relations Internationales, BP 13522, F-44 035, Nantes cedex 1, France
**Faculty of Maritime Sciences, Kobe University, 5-1-1 Higashinadaku, Fukaeminamimachi, Kobe 658-0022, Japan
***National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyodaku, Tokyo 101-8430, Japan
A Distributed Constraint Optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Many application problems in multi-agent systems can be formalized as DCOPs. However, many real world optimization problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Distributed Constraint Optimization Problem (MO-DCOP) is an extension of a mono-objective DCOP. Compared to DCOPs, there exists few works on MO-DCOPs. In this paper, we develop a novel complete algorithm for solving an MO-DCOP. This algorithm utilizes a widely used method called Pareto Local Search (PLS) to generate an approximation of the Pareto front. Then, the obtained information is used to guide the search thresholds in a Branch and Bound algorithm. In the evaluations, we evaluate the runtime of our algorithm and show empirically that using a Pareto front approximation obtained by a PLS algorithm allows to significantly speed-up the search in a Branch and Bound algorithm.
-  P. Modi, W.-M. Shen, M. Tambe, and M. Yokoo, “ADOPT: asynchronous distributed constraint optimization with quality guarantees,” Artificial Intelligence, Vol.161, No.1-2, pp. 149-180, 2005.
-  A. Petcu and B. Faltings, “A Scalable Method for Multiagent Constraint,” Optimization, pp. 266-271, 2005.
-  R. T. Maheswaran, M. Tambe, E. Bowring, J. P. Pearce, and P. Varakantham, “Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling,” Proc. of the 3rd Int. Conf. on Autonomous Agents and Multiagent Systems, pp. 310-317, 2004.
-  V. Lesser, C. Ortiz, and M. Tambe (Eds.), “Distributed Sensor Networks: A Multiagent Perspective,” Vol.9, 2003.
-  R. Junges and A. L. C. Bazzan, “Evaluating the performance of DCOP algorithms in a real world, dynamic problem,” Proc. of the 7th Int. Conf. on Autonomous Agents and Multiagent Systems, pp. 599-606, 2008.
-  F. M. D. Fave, R. Stranders, A. Rogers, and N. R. Jennings, “Bounded Decentralised Coordination over Multiple Objectives,” Proc. of the 10th Int. Conf. on Autonomous Agents and Multiagent Systems, pp. 371-378, 2011.
-  T. Matsui, M. Silaghi, K. Hirayama, M. Yokoo, and H. Matsuo, “Distributed Search Method with Bounded Cost Vectors on Multiple Objective DCOPs,” Proc. of the 15th Int. Conf. on Principles and Practice of Multi-Agent Systems, pp. 137-152, 2012.
-  A. Sivakumar and C. K.-Y. Tan, “UAV swarm coordination using cooperative control for establishing a wireless communications backbone,” Proc. of the 9th Int. Conf. on Autonomous Agents and Multiagent Systems, pp. 1157-1164, 2010.
-  A. Rogers, A. Farinelli, R. Stranders, and N. Jennings, “Bounded approximate decentralised coordination via the max-sum algorithm,” Artificial Intelligence, Vol.175, No.2, pp. 730-759, 2011.
-  L. Paquete, M. Chiarandini, and T. Stutzle, “Pareto local optimum sets in the biobjective traveling salesman problem: An experimental study,” In Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, pp. 177-200, 2004.
-  T. Schiex, H. Fargier, and G. Verfaillie, “Valued constraint satisfaction problems: Hard and easy problems,” Proc. of the 14th Int. Joint Conf. on Artificial Intelligence, pp. 631-639, 1995.
-  K. Hirayama and M. Yokoo, “The distributed breakout algorithms,” Artificial Intelligence, Vol.161, No.1-2, pp. 89-115, 2005.
-  S. Fitzpatrick and L. G. L. T. Meertens, “An Experimental Assessment of a Stochastic, Anytime, Decentralized, Soft Colourer for Sparse Graphs,” Pro. of the 1st Symp. on Stochastic Algorithms: Foundations and Applications, pp. 49-64, 2001.
-  T. Lust and J. Teghem, “Two-phase Pareto local search for the biobjective traveling salesman problem,” J. of Heuristics, Vol.16, No.3, pp. 475-510, 2010.
-  K. Hirayama and M. Yokoo, “Distributed partial constraint satisfaction problem,” Principles and Practice of Constraint Programming, pp. 222-236, 1997.