Top > JACIII > A Two-Phase Complete Algorithm for Multi-Objective Distributed ...

single-jc.php

JACIII Vol.18 No.4 pp. 573-580
doi: 10.20965/jaciii.2014.p0573
(2014)

Paper:

Views over last 60 days: 855

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

Received:
July 24, 2013
Accepted:
January 31, 2014
Published:
July 20, 2014
Creative Commons License
Keywords:
multi-agent system, distributed constraint optimization, multi-criteria
Abstract
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.
Cite this article as:
A. Medi, T. Okimoto, and K. Inoue, “A Two-Phase Complete Algorithm for Multi-Objective Distributed Constraint Optimization,” J. Adv. Comput. Intell. Intell. Inform., Vol.18 No.4, pp. 573-580, 2014.
Data files:
References
  1. [1] 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.
  2. [2] A. Petcu and B. Faltings, “A Scalable Method for Multiagent Constraint,” Optimization, pp. 266-271, 2005.
  3. [3] 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.
  4. [4] V. Lesser, C. Ortiz, and M. Tambe (Eds.), “Distributed Sensor Networks: A Multiagent Perspective,” Vol.9, 2003.
  5. [5] 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.
  6. [6] 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.
  7. [7] 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.
  8. [8] 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.
  9. [9] 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.
  10. [10] 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.
  11. [11] 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.
  12. [12] K. Hirayama and M. Yokoo, “The distributed breakout algorithms,” Artificial Intelligence, Vol.161, No.1-2, pp. 89-115, 2005.
  13. [13] 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.
  14. [14] 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.
  15. [15] K. Hirayama and M. Yokoo, “Distributed partial constraint satisfaction problem,” Principles and Practice of Constraint Programming, pp. 222-236, 1997.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 22, 2024