Abstract
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 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. Solving an MO-DCOP is to find the Pareto front which is a set of cost vectors obtained by Pareto optimal solutions. In MO-DCOPs, even if a constraint graph has the simplest tree structure, the size of the Pareto front (the number of Pareto optimal solutions) is often exponential in the number of agents. Since finding all Pareto optimal solutions becomes easily intractable, it is important to consider fast but approximate algorithms. Various sophisticated algorithms have been developed for solving a DCOP and an MO-COP. However, there exists few works on an MO-DCOP. The Bounded Multi-Objective Max-Sum (B-MOMS) algorithm is the first and only existing approximate MO-DCOP algorithm. In this paper, we develop a novel approximate MO-DCOP algorithm called Distributed Iterated Pareto Local Search (DIPLS) and empirically show that DIPLS outperforms the state-of-the-art B-MOMS algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Fave, F.D., Stranders, R., Rogers, A., Jennings, N.: Bounded decentralised coordination over multiple objectives. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems, pp. 371–378 (2011)
Fitzpatrick, S., Meertens, L.: An experimental assessment of a stochastic, anytime, decentralized, soft colourer for sparse graphs. In: Steinhöfel, K. (ed.) SAGA 2001. LNCS, vol. 2264, pp. 49–64. Springer, Heidelberg (2001)
Hirayama, K., Yokoo, M.: The distributed breakout algorithms. Artificial Intelligence 161(1-2), 89–115 (2005)
Junges, R., Bazzan, A.: Evaluating the performance of DCOP algorithms in a real world, dynamic problem. In: Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, pp. 599–606 (2008)
Lesser, V., Ortiz, C., Tambe, M. (eds.): Distributed Sensor Networks: A Multiagent Perspective (Edited book), May 2003. Kluwer Academic Publishers (2003)
Maheswaran, R., Tambe, M., Bowring, E., Pearce, J., Varakantham, P.: Taking dcop to the real world: efficient complete solutions for distributed multi-event scheduling. In: Proceedings of the 3rd International Conference on Autonomous Agents and Multiagent Systems, pp. 310–317 (2004)
Marinescu, R.: Exploiting problem decomposition in multi-objective constraint optimization. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 592–607. Springer, Heidelberg (2009)
Marinescu, R.: Best-first vs. depth-first and/or search for multi-objective constraint optimization. In: Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence, pp. 439–446 (2010)
Matsui, T., Silaghi, M., Hirayama, K., Yokoo, M., Matsuo, H.: Distributed search method with bounded cost vectors on multiple objective dCOPs. In: Rahwan, I., Wobcke, W., Sen, S., Sugawara, T. (eds.) PRIMA 2012. LNCS, vol. 7455, pp. 137–152. Springer, Heidelberg (2012)
Modi, P., Shen, W., Tambe, M., Yokoo, M.: ADOPT: asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence 161(1-2), 149–180 (2005)
Okimoto, T., Ribeiro, T., Clement, M., Inoue, K.: Modeling and algorithm for dynamic multi-objective weighted constraint satisfaction problem. In: Proceedings of the 6th International Conference on Agents and Artificial Intelligence, pp. 420–427 (2014)
Okimoto, T., Schwind, N., Clement, M., Inoue, K.: Lp-norm based algorithm for multi-objective distributed constraint optimization. In: Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, pp. 1427–1428 (2014)
Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 86–92 (2000)
Paquete, L., Chiarandini, M., Stutzle, T.: Pareto local optimum sets in the bi-objective traveling salesman problem: An experimental study. In: Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, pp. 177–200. Springer (2004)
Perny, P., Spanjaard, O.: Near admissible algorithms for multiobjective search. In: Proceedings of the 18th European Conference on Artificial Intelligence, pp. 490–494 (2008)
Petcu, A., Faltings, B.: A scalable method for multiagent constraint optimization. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 266–271 (2005)
Rogers, A., Farinelli, A., Stranders, R., Jennings, N.: Bounded approximate decentralised coordination via the max-sum algorithm. Artificial Intelligence 175(2), 730–759 (2011)
Rollon, E., Larrosa, J.: Bucket elimination for multiobjective optimization problems. Journal of Heuristics 12(4-5), 307–328 (2006)
Rollon, E., Larrosa, J.: Multi-objective russian doll search. In: Proceedings of the 22nd AAAI Conference on Artificial Intelligence, pp. 249–254 (2007)
Sivakumar, A., Tan, C.: UAV swarm coordination using cooperative control for establishing a wireless communications backbone. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, pp. 1157–1164 (2010)
Thibaut, L., Jacques, T.: Two-phase pareto local search for the biobjective traveling salesman problem. Journal of Heuristics 16(3), 475–510 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Wack, M., Okimoto, T., Clement, M., Inoue, K. (2014). Local Search Based Approximate Algorithm for Multi-Objective DCOPs. In: Dam, H.K., Pitt, J., Xu, Y., Governatori, G., Ito, T. (eds) PRIMA 2014: Principles and Practice of Multi-Agent Systems. PRIMA 2014. Lecture Notes in Computer Science(), vol 8861. Springer, Cham. https://doi.org/10.1007/978-3-319-13191-7_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-13191-7_32
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13190-0
Online ISBN: 978-3-319-13191-7
eBook Packages: Computer ScienceComputer Science (R0)