Abstract
In this paper, we extend the Support Based Distributed Optimization (SBDO) algorithm to support problems which do not have a total pre-order over the set of solutions. This is the case in common real life problems that have multiple objective functions. In particular, decision support problems. These disparate objectives are not well supported by existing Distributed Constraint Optimization Problem (DCOP) techniques, which assume a single cost or utility function. As a result, existing Distributed COP techniques (with some recent exceptions) require that all agents subscribe to a common objective function and are therefore unsuitable for settings where agents have distinct, competing objectives. This makes existing constraint optimization technologies unsuitable for many decision support roles, where the decision maker wishes to observe the different trade-offs before making a decision.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fave, F.M.D., Stranders, R., Rogers, A., Jennings, N.R.: Bounded Decentralised Coordination over Multiple Objectives. In: AAMAS, pp. 371–378 (2011)
Alba, E., Troya, J.M.: A survey of parallel distributed genetic algorithms. Complexity 4(4), 31–52 (1999)
Billiau, G., Chang, C.F., Ghose, A.: SBDO: A new robust approach to dynamic distributed constraint optimisation. In: Desai, N., Liu, A., Winikoff, M. (eds.) PRIMA 2010. LNCS, vol. 7057, pp. 11–26. Springer, Heidelberg (2012)
Bowring, E., Tambe, M., Yokoo, M.: Multiply-constrained distributed constraint optimization. In: Nakashima, H., Wellman, M.P., Weiss, G., Stone, P. (eds.) AAMAS, pp. 1413–1420. ACM (2006)
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)
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint satisfaction and optimization. J. ACM 44(2), 201–236 (1997)
Schiex, T., Verfaillie, G.: Nogood Recording for Static and Dynamic Constraint Satisfaction Problem. International Journal of Artifical Intelligence Tools 3(2), 187–207 (1994)
Harvey, P., Chang, C.F., Ghose, A.: Support-based distributed search: a new approach for multiagent constraint processing. In: AAMAS 2006, pp. 377–383. ACM (2006)
Chandy, K.M., Lamport, L.: Distributed Snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems 3(1), 63–75 (1985)
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
Billiau, G., Chang, C.F., Ghose, A. (2014). Multi-objective Distributed Constraint Optimization Using Semi-rings. 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_33
Download citation
DOI: https://doi.org/10.1007/978-3-319-13191-7_33
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13190-0
Online ISBN: 978-3-319-13191-7
eBook Packages: Computer ScienceComputer Science (R0)