Distributed Constraint Optimization Problems and Applications: A Survey
Open accessThe DOI matches its Crossref record; 105 of the 105 references it cites were found in a registry or an index.
Abstract
The field of multi-agent system (MAS) is an active area of research within artificial intelligence, with an increasingly important impact in industrial and other real-world applications. In a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as a prominent agent model to govern the agents' autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have been proposed to enable support of MAS in complex, real-time, and uncertain environments. This survey provides an overview of the DCOP model, offering a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949 · cited 1×
“t repeats until a termination condition is met. D-Gibbs [47]. The Distributed Gibbs (D-Gibbs) algorithm is an incomplete, synchronous, sampling-based algorithm that extends the Gibbs sampling process [48] by tailoring it to solve DCOPs in a decentralized manner. The Gibbs sampling process is a centralized Markov chain…”
MethodWireless sensor networks: a survey
Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002) · Computer Networks · doi:10.1016/s1389-1286(01)00302-4 · Cited by 17,418 · cited 1×
“, battlefield surveillance), and target tracking [138].”
The Internet of Things: A survey
Atzori, L., Iera, A., & Morabito, G. (2010) · Computer Networks · doi:10.1016/j.comnet.2010.05.010 · Cited by 15,613 · cited 1×
“unsuitable delays. This context may be exacerbated with the advent of concepts such as the Internet of the Things, which expects to see million of connected devices, possibly sharing several mediums [12,34,119]. Thus, orthogonal to the direction pursed by anytime and any-space algorithms, we envision the development o…”
BackgroundTime, clocks, and the ordering of events in a distributed system
Lamport, L. (1978) · Communications of the ACM · doi:10.1145/359545.359563 · Cited by 8,488
Power Generation, Operation, and Control
Wood, A. J., & Wollenberg, B. F. (1984) · Cited by 8,303
Factor graphs and the sum-product algorithm
Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910572 · Cited by 6,486 · cited 1×
“Another way to represent DCOPs is through a factor graph [15].”
BackgroundFinite-time Analysis of the Multiarmed Bandit Problem
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002) · Machine Learning · doi:10.1023/a:1013689704352 · Cited by 6,033 · cited 3×
“To do so, it employs a belief propagation algorithm, known as generalized distributive law (GDL) [5], in order to maximize the UCB in a decentralized fashion.”
BackgroundAn Introduction to MultiAgent Systems
Wooldridge, M. (2002) · Cited by 5,394
Nonlinear Multiobjective Optimization
Miettinen, K. (1998) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4615-5563-6 · Cited by 4,710 · cited 8×
“Multi-objective optimization (MOO) [116,107] aims at solving problems involving more than one objective function to be optimized simultaneously.”
BackgroundMethodInfluentialSurvey of multi-objective optimization methods for engineering
Marler, R. T., & Arora, J. S. (2004) · Structural and Multidisciplinary Optimization · doi:10.1007/s00158-003-0368-6 · Cited by 4,710
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
Solomon, M. M. (1987) · Operations Research · doi:10.1287/opre.35.2.254 · Cited by 4,298 · cited 3×
“Scheduling problems are an important class of problems, and they have been long studied in the area of Constraint Programming and Operations Research [52,165,118,66].”
Background(1992) · Lecture Notes in Computer Science · doi:10.1007/bfb0022433 · Cited by 3,955
Partitioning procedures for solving mixed-variables programming problems
Benders, J. F. (1962) · Numerische Mathematik · doi:10.1007/bf01386316 · Cited by 3,855
Internet of things: Vision, applications and research challenges
Miorandi, D., Sicari, S., De Pellegrini, F., & Chlamtac, I. (2012) · Ad Hoc Networks · doi:10.1016/j.adhoc.2012.02.016 · Cited by 3,578 · cited 1×
“This context may be exacerbated with the advent of concepts such as the Internet of the Things, which expects to see million of connected devices, possibly sharing several mediums [12,34,119].”
BackgroundNonlinear Multiobjective Optimization
Mardle, S., & Miettinen, K. M. (2000) · The Journal of the Operational Research Society · doi:10.2307/254267 · Cited by 3,049
Developing Multi‐Agent Systems with JADE
Bellifemine, F., Caire, G., & Greenwood, D. (2007) · Wiley eBooks · doi:10.1002/9780470058411 · Cited by 2,509
Decision Analysis: Introductory Lectures on Choices Under Uncertainty.
Klevorick, A. K., & Raiffa, H. (1969) · The Journal of Finance · doi:10.2307/2325714 · Cited by 1,928
(1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61769-8 · Cited by 1,865
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
The Complexity of Decentralized Control of Markov Decision Processes
Bernstein, D. S., Givan, R., Immerman, N., & Zilberstein, S. (2002) · Mathematics of Operations Research · doi:10.1287/moor.27.4.819.297 · Cited by 1,192
Introduction to Multi-Agent Systems
Hadzic, M., Wongthongtham, P., Dillon, T., & Chang, E. (2009) · Studies in Computational Intelligence · doi:10.1007/978-3-642-01904-3_2 · Cited by 1,180
Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images*
Geman, S., & Geman, D. (1993) · Journal of Applied Statistics · doi:10.1080/02664769300000058 · Cited by 983
Decision Analysis: Introductory Lectures on Choices Under Uncertainty.
Raiffa, H. (1969) · The Statistician · doi:10.2307/2987280 · Cited by 940
Principles of Constraint Programming
Apt, K. (2003) · Cambridge University Press eBooks · doi:10.1017/cbo9780511615320 · Cited by 888 · cited 1×
“, which form the foundation of Distributed Constraint Optimization. Figure 3 illustrates the relations among these models. 2.1 Constraint Satisfaction Problems Constraint Satisfaction Problems (CSPs) [9,161] are decision problems that involve the assignment of values to variables, under a set of specified constraints o…”
BackgroundInfluentialMinimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems
Minton, S., Johnston, M. D., Philips, A. B., & Laird, P. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90007-k · Cited by 843 · cited 3×
“Scheduling problems are an important class of problems, and they have been long studied in the area of Constraint Programming and Operations Research [52,165,118,66].”
BackgroundPartitioning procedures for solving mixed-variables programming problems
Benders, J. F. (2005) · Computational Management Science · doi:10.1007/s10287-004-0020-y · Cited by 837 · cited 1×
“The algorithm extends the Iterative Constraint Generation (ICG) method [87, 88] to the decentralized case, by decomposing the overall problem into a master problem and a subproblem that are iteratively solved until convergence.”
MethodDetermining computational complexity from characteristic ‘phase transitions’
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., & Troyansky, L. (1999) · Nature · doi:10.1038/22055 · Cited by 790
MiniZinc: Towards a Standard CP Modelling Language
Nethercote, N., Stuckey, P. J., Becket, R., Brand, S., Duck, G. J., & Tack, G. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74970-7_38 · Cited by 764 · cited 1×
“the AI communities to model and test the applicability of new problems, extending the applicability of DCOPs to new areas. For instance, within the CP community, the adoption of the MiniZinc language [128] to model CSPs and COPs has gained wide traction, and it is becoming a modeling choice even outside the CP communi…”
BackgroundStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
GEMAN, S., & GEMAN, D. (1987) · Readings in Computer Vision · doi:10.1016/b978-0-08-051581-6.50057-x · Cited by 750
The generalized distributive law
Aji, S. M., & McEliece, R. J. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825794 · Cited by 735 · cited 7×
“To do so, it employs a belief propagation algorithm, known as generalized distributive law (GDL) [5], in order to maximize the UCB in a decentralized fashion.”
MethodInfluentialMackworth, A. K., & Freuder, E. C. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90041-4 · Cited by 692
(1992) · Cited by 691
Using anytime algorithms in intelligent systems
Shlomo Zilberstein, B. (1996) · doi:10.1609/aimag.v17i3.1232 · Cited by 680 · cited 1×
“in environment 61 FIORETTO, PONTELLI, & YEOH seems particularly suitable. Within the current incomplete methods proposed, a considerable effort has been employed in developing anytime algorithms (Zilberstein, 1996). Anytime algorithms can return a valid solution even if the DCOP agents are interrupted at any time…”
MethodStructural Descriptions and Inexact Matching
Shapiro, L. G., & Haralick, R. M. (1981) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1981.4767144 · Cited by 544
Graphical Models for Game Theory
Kearns, M. J., Littman, M. L., & Singh, S. P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.2281 · Cited by 544
Multi-armed Bandit Algorithms and Empirical Evaluation
Vermorel, J., & Mohri, M. (2005) · Lecture Notes in Computer Science · doi:10.1007/11564096_42 · Cited by 513
Golomb, S. W., & Baumert, L. D. (1965) · Journal of the ACM · doi:10.1145/321296.321300 · Cited by 498
A scalable method for multiagent constraint optimization
Petcu, A., & Faltings, B. V. (2005) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 491
Negotiation and cooperation in multi-agent environments
Kraus, S. (1997) · Artificial Intelligence · doi:10.1016/s0004-3702(97)00025-8 · Cited by 451 · cited 1×
“Some of the most compelling applications of game theory to MAS have been in the area of auctions and negotiations [5, 6, 7].”
BackgroundAverage reward reinforcement learning: Foundations, algorithms, and empirical results
Mahadevan, S. (1996) · Machine Learning · doi:10.1007/bf00114727 · Cited by 385 · cited 1×
“earning algorithms are synchronous reinforcement-learning-based algorithms that extend the centralized Q-learning (Abounadi, Bertsekas, & Borkar, 2001) and centralized R-learning (Schwartz, 1993; Mahadevan, 1996) algorithms. Each agent maintains Q-values and R-values for each ˙ t 1;d t i pair, where ˙ t 1 is the s…”
BackgroundLynch, N. (1996) · Cited by 354
Algorithms for Distributed Constraint Satisfaction: A Review
Yokoo, M., & Hirayama, K. (2000) · Autonomous Agents and Multi-Agent Systems · doi:10.1023/a:1010078712316 · Cited by 350
Michel, L., & Van Hentenryck, P. (2017) · Handbook of Heuristics · doi:10.1007/978-3-319-07153-4_7-1 · Cited by 348
Agent-based control for decentralised demand side management in the smart grid
Ramchurn, S. D., Vytelingum, P., Rogers, A., & Jennings, N. (2011) · International Joint Conference on Autonomous Agents and Multiagent Systems · doi:10.65109/pihb7069 · Cited by 341 · cited 1×
“Other examples include supply chain management problems [53], where different consumers have different levels of urgency, and smart grid applications [54], where consumption costs are dictated by a varying pricing scheme, but the price depends on the agents’ power loads, which are not evenly distributed among users—as…”
BackgroundHandbook of Constraint Programming (Foundations of Artificial Intelligence)
Rossi, F., van Beek, P., & Walsh, T. (2006) · Elsevier eBooks · Cited by 330
Challenges and opportunities of internet of things
Chen, Y.-K. (2012) · 17th Asia and South Pacific Design Automation Conference · doi:10.1109/aspdac.2012.6164978 · Cited by 320 · cited 1×
“be exacerbated with the advent of concepts such as the Internet of the Things, which expects to see million of connected devices, possibly sharing several mediums (Atzori, Iera, & Morabito, 2010; Chen, 2012; Miorandi, Sicari, De Pellegrini, & Chlamtac, 2012). Thus, orthogonal to the direction pursed by anytime…”
BackgroundKravari, K., & Bassiliades, N. (2015) · Journal of Artificial Societies and Social Simulation · doi:10.18564/jasss.2661 · Cited by 308
A Reinforcement Learning Method for Maximizing Undiscounted Rewards
Schwartz, A. (1993) · Machine Learning Proceedings 1993 · doi:10.1016/b978-1-55860-307-3.50045-9 · Cited by 308 · cited 1×
“The Distributed Q-learning and R-learning algorithms are synchronous reinforcement-learning-based algorithms that extend the centralized Q-learning [104] and centralized Rlearning [105, 106] algorithms.”
MethodTaking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling
Maheswaran, R. T., Tambe, M., Bowring, E., Pearce, J. P., & Varakantham, P. R. (2004) · doi:10.1109/aamas.2004.257 · Cited by 251 · cited 1×
“In [104], the authors discuss three possible DCOP formulations for this problem: time slots as variables (TSAV), events as variables (EAV), and private events as variables (PEAV).”
BackgroundPareto Local Optimum Sets in the Biobjective Traveling Salesman Problem: An Experimental Study
Paquete, L., Chiarandini, M., & Stützle, T. (2004) · Lecture notes in economics and mathematical systems · doi:10.1007/978-3-642-17144-4_7 · Cited by 245
Evolution of the GPGP/TÆMS domain-independent coordination framework
Lesser, V. (2002) · Adaptive Agents and Multi-Agents Systems · doi:10.1145/544741.544742 · Cited by 233
Michel, L., & Hentenryck, P. V. (2018) · Handbook of Heuristics · doi:10.1007/978-3-319-07124-4_7 · Cited by 230 · cited 3×
“Scheduling problems are an important class of problems, and they have been long studied in the area of Constraint Programming and Operations Research [52,165,118,66].”
BackgroundDistributed Constraint Satisfaction: Foundations of Cooperation in Multi-agent Systems
Yokoo, M. (2000) · Medical Entomology and Zoology · Cited by 207
Game Theory and Decision Theory in Multi-Agent Systems
Parsons, S., & Wooldridge, M. (2002) · Autonomous Agents and Multi-Agent Systems · doi:10.1023/a:1015575522401 · Cited by 206 · cited 1×
“Some of the most compelling applications of game theory to MAS have been in the area of auctions and negotiations [5, 6, 7].”
BackgroundLearning Algorithms for Markov Decision Processes with Average Cost
Abounadi, J., Bertsekas, D., & Borkar, V. S. (2001) · SIAM Journal on Control and Optimization · doi:10.1137/s0363012999361974 · Cited by 204 · cited 3×
“Distributed Q-learning and R-learning [131].”
MethodKey Challenges in Cloud Computing: Enabling the Future Internet of Services
Moreno-Vozmediano, R., Montero, R. S., & Llorente, I. M. (2013) · IEEE Internet Computing · doi:10.1109/mic.2012.69 · Cited by 202 · cited 1×
“Efficient solutions with optimal use of resources is crucial in this paradigm and has a wide industrial impact [148].”
BackgroundSelf-Stabilization in Spite of Distributed Control
Dijkstra, E. W. (1982) · Selected Writings on Computing: A personal Perspective · doi:10.1007/978-1-4612-5695-3_7 · Cited by 190
Evolution of the GPGP/TÆMS Domain-Independent Coordination Framework
Lesser, V., Decker, K., Wagner, T., Carver, N., Garvey, A., Horling, B., Neiman, D. E., Podorozhny, R. M., Prasad, M. N., Raja, A., et al. (2004) · Autonomous Agents and Multi-Agent Systems · doi:10.1023/b:agnt.0000019690.28073.04 · Cited by 187
Decentralized control of partially observable Markov decision processes
Amato, C., Chowdhary, G. V., Geramifard, A., Üre, N. K., & Kochenderfer, M. J. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760239 · Cited by 180
Decentralized Coordination in RoboCup Rescue
Ramchurn, S. D., Farinelli, A., Macarthur, K., & Jennings, N. R. (2010) · The Computer Journal · doi:10.1093/comjnl/bxq022 · Cited by 158 · cited 3×
“A DCOP formalization for the CFST is described in [99], where ambulances and fire brigades are modeled as DCOP agents.”
BackgroundMethodBounded approximate decentralised coordination via the max-sum algorithm
Rogers, A., Farinelli, A., Stranders, R., & Jennings, N. R. (2010) · Artificial Intelligence · doi:10.1016/j.artint.2010.11.001 · Cited by 144 · cited 1×
“…the solutions found by removing a subset of edges from a cyclic DCOP graph to make it acyclic, and by running Max-Sum to solve the acyclic problem [159], Improved Bounded Max-Sum improves on the error bounds [160], and Max-Sum AD guarantees convergence in acyclic graphs through a two-phase value…”
MethodConstraint Solving in Uncertain and Dynamic Environments: A Survey
Verfaillie, G., & Jussien, N. (2005) · Constraints · doi:10.1007/s10601-005-2239-9 · Cited by 140
Coordinating multi-agent reinforcement learning with limited communication
Zhang, C., & Lesser, V. (2013) · Adaptive Agents and Multi-Agents Systems · doi:10.5555/2484920.2485093 · Cited by 115
Robust Broadcast-Communication Control of Electric Vehicle Charging
Turitsyn, K. S., Sinitsyn, N. A., Backhaus, S., & Chertkov, M. (2010) · IEEE International Conference on Smart Grid Communications (SmartGridComm) · doi:10.1109/smartgrid.2010.5622044 · Cited by 91 · cited 1×
“The number of next-day trips is often estimated using a probabilistic model [80].”
MethodYeoh, W., & Yokoo, M. (2012) · AI Magazine · doi:10.1609/aimag.v33i3.2429 · Cited by 89 · cited 2×
“With respect to our categorization, in the classical DCOP model [9, 10, 11], the agents are completely cooperative”
BackgroundMethodSelf-citationExplorative anytime local search for distributed constraint optimization
Zivan, R., Okamoto, S., & Peled, H. (2014) · Artificial Intelligence · doi:10.1016/j.artint.2014.03.002 · Cited by 85
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems
Macarthur, K., Stranders, R., Ramchurn, S. D., & Jennings, N. R. (2011) · AAAI Publications (The Association for the Advancement of Artificial Intelligence (AAAI)) · doi:10.1609/aaai.v25i1.7866 · Cited by 74 · cited 1×
“Branch-and-Bound Fast Max-Sum (BnB-FMS) extends FMS providing online domain pruning using a branch-and-bound technique [101].”
MethodBnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
Yeoh, W., Felner, A., & Koenig, S. (2008) · Adaptive Agents and Multi-Agents Systems · doi:10.5555/1402298.1402307 · Cited by 74
Self-citationAsymmetric Distributed Constraint Optimization Problems
Grinshpoun, T., Grubshtein, A., Zivan, R., Netzer, A., & Meisels, A. (2013) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3945 · Cited by 72 · cited 2×
“showed that most of the existing incomplete classical DCOP algorithms cannot be used to effectively solve Asymmetric DCOPs, even when the problems are reformulated through the PEAV model [50].”
MethodOptimal decentralised dispatch of embedded generation in the smart grid
Miller, S. L., Ramchurn, S. D., & Rogers, A. (2012) · ePrints Soton (University of Southampton) · doi:10.5555/2343576.2343616 · Cited by 67
A Multiagent System Approach to Scheduling Devices in Smart Homes
Fioretto, F., Yeoh, W., & Pontelli, E. (2017) · Adaptive Agents and Multi-Agents Systems · doi:10.5555/3091125.3091265 · Cited by 61
Self-citationDynamic Multi-Agent Task Allocation with Spatial and Temporal Constraints
Nelke, S. A., Okamoto, S., & Zivan, R. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8889 · Cited by 60
Distributed learning and multi-objectivity in traffic light control
Brys, T., Pham, T., & Taylor, M. E. (2014) · Connection Science · doi:10.1080/09540091.2014.885282 · Cited by 59 · cited 1×
“In [153,28], the authors propose a P-DCOP-based approach with partial agent knowledge to solve the traffic light synchronization problem in the context where agents have partial information about their reward functions.”
BackgroundJain, M., Taylor, M. E., Tambe, M., & Yokoo, M. (2009) · Cited by 58
DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimization Problems
Ottens, B., Christos Dimitrakakis, A., & Faltings, B. V. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v26i1.8129 · Cited by 53
Cognitive Radio Resource Management Using Multi-Agent Systems
Xie, J. L., Howitt, I. L., & Raja, A. (2007) · IEEE Consumer Communications and Networking Conference · doi:10.1109/ccnc.2007.226 · Cited by 51 · cited 1×
“In [121, 122], the authors study dynamic solutions to the problem of allocating and utilizing the wireless network’s available spectrum.”
BackgroundDecentralised coordination of continuously valued control parameters using the max-sum algorithm
Stranders, R., Farinelli, A., Rogers, A., & Jennings, N. R. (2009) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/zmkp4320 · Cited by 49
Giuliani, M., Castelletti, A. F., Francesco Amigoni, A., & Cai, X. (2014) · Journal of Water Resources Planning and Management · doi:10.1061/(asce)wr.1943-5452.0000463 · Cited by 49 · cited 2×
“ve Channel Assignment T D S [124,125] T D D [184,120] RECOMMENDATION SYSTEMS Group Recommendation T D S [98] SCHEDULING Distributed Meeting Scheduling T D S [104,19] Water Allocation Scheduling T D S [53,8] Patient Scheduling T D S [64] T D D [24,23,78,77] SENSOR NETWORK Target Tracking T D/S D [197,108,136,70] Roboti…”
BackgroundDistributed Constraint Optimization for Large Teams of Mobile Sensing Agents
Zivan, R., Glinton, R., & Sycara, K. P. (2009) · IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT) · doi:10.1109/wi-iat.2009.176 · Cited by 48 · cited 6×
“The Mobile Sensor Team (MST) problem is similar to the target tracking problem with the difference that agents are capable of moving autonomously within the environment and that time is modeled explicitly as a discrete sequence of time steps.”
BackgroundMethodInfluentialRobust Policy Computation in Reward-Uncertain MDPs Using Nondominated Policies
Regan, K., & Boutilier, C. (2010) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v24i1.7740 · Cited by 48 · cited 1×
“nd robust solutions to the uncertain problem distributions; it does so by finding the solution that minimizes the maximum regret. The algorithm extends the Iterative Constraint Generation (ICG) method [16,158] to the decentralized case, by decomposing the overall problem into a master problem and a subproblem that are…”
MethodOptimal Solution Stability in Dynamic, Distributed Constraint Optimization
Petcu, A., & Faltings, B. V. (2007) · IEEE/WIC/ACM International Conference on Intelligent Agent Technology · doi:10.1109/iat.2007.11 · Cited by 45
Distributed Gibbs: a memory-bounded sampling-based DCOP algorithm
Nguyen, D. T., Yeoh, W., & Lau, H. C. (2013) · doi:10.5555/2484920.2484950 · Cited by 43
Self-citationNetwork Management: Current Trends and Future Perspectives
Gupta, A. K. (2006) · Journal of Network and Systems Management · doi:10.1007/s10922-006-9044-7 · Cited by 41 · cited 1×
“This problem is the problem of coordinating network generators with respect to network cost, while satisfying the load and network constraints [160].”
BackgroundMax/min-sum distributed constraint optimization through value propagation on an alternating DAG
Zivan, R., & Peled, H. (2012) · doi:10.5555/2343576.2343614 · Cited by 40
Bounded decentralised coordination over multiple objectives
Fave, F. M. D., Stranders, R., Rogers, A., & Jennings, N. R. (2011) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/cbmf7777 · Cited by 39 · cited 1×
“[39].”
Efficient Inter-Team Task Allocation in RoboCup Rescue
Pujol-González, M., Cerquides, J., Farinelli, A., Meseguer, P., & Rodríguez-Aguilar, J. A. (2015) · doi:10.5555/2772879.2772933 · Cited by 32
Decentralized multi-agent reinforcement learning in average-reward dynamic DCOPs
Nguyen, D. T., Yeoh, W., Lau, H. C., Zilberstein, S., & Zhang, C. (2014) · Singapore Management University Institutional Knowledge (InK) (Singapore Management University) · doi:10.5555/2615731.2617463 · Cited by 29
Self-citationWhen should there be a "Me" in "Team"?: distributed multi-agent optimization under uncertainty
Taylor, M. E., Jain, M., Jin, Y., Yokoo, M., & Tambe, M. (2010) · Adaptive Agents and Multi-Agents Systems · doi:10.5555/1838206.1838222 · Cited by 27
Real-Time Solving of Quantified CSPs Based on Monte-Carlo Game Tree Search
Baba, S., Joe, Y., Iwasaki, A., & Yokoo, M. (2012) · Cited by 24
DCOPs and bandits: exploration and exploitation in decentralised coordination
Stranders, R., Tran-Thanh, L., Fave, F. M. D., Rogers, A., & Jennings, N. R. (2012) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/chlg9257 · Cited by 24 · cited 1×
“H EIST [169].”
Caching schemes for DCOP search algorithms
Yeoh, W., Varakantham, P. R., & Koenig, S. (2009) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/pxwd4353 · Cited by 22
Self-citationTrading off solution quality for faster computation in DCOP search algorithms
Yeoh, W., Sun, X., & Koenig, S. (2009) · International Joint Conference on Artificial Intelligence · Cited by 21
Self-citationA Cooperative Multiagent Based Spectrum Sharing
Mir, U., Merghem, L., & Gaïti, D. (2010) · International Conference on Internet and Web Applications and Services · doi:10.1109/aict.2010.31 · Cited by 20 · cited 1×
“In [184,120], the authors study dynamic solutions to the problem of allocating and utilizing the wireless network’s available spectrum.”
BackgroundModeling the Management of Water Resources Systems Using Multi-Objective DCOPs
Francesco Amigoni, A., Castelletti, A. F., & Giuliani, M. (2015) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/btmn6085 · Cited by 18 · cited 1×
“A solution to such problem, which makes use of a multi-objective DCOP formalization, is presented in [134].”
MethodDesigning a Marketplace for the Trading and Distribution of Energy in the Smart Grid
Cerquides, J., Picard, G., & Rodríguez-Aguilar, J. A. (2015) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/sbia4550 · Cited by 17 · cited 2×
“ent T D S [74,97] Server Allocation T D D [36] SMART GRID Economic Dispatch T D/S D [117,58,10,72] Power Supply Restoration T D S [59] Microgrid Islanding T D S [84,4] Prosumer Energy Trading T D/S S [31] SUPPLY CHAIN MANAGEMENT Supply Chain Formation T D S [48,142,143,181,144] T D D [35] TRAFFIC CONTROL Traffic Light…”
BackgroundTaylor, M. E., Jain, M., TANDON, P., Yokoo, M., & Tambe, M. (2011) · Advances in Complex Systems · doi:10.1142/s0219525911003104 · Cited by 16 · cited 2×
“Following the region-optimal approaches presented in the context of classical DCOPs, the authors propose a version of the algorithm, called BE-Rebid-2 [173], that allows pairs of agents to explore in a coordinated fashion.”
BackgroundMethodProactive Dynamic Distributed Constraint Optimization
Hoang, K. D., Fioretto, F., Hou, P., Yokoo, M., Yeoh, W., & Zivan, R. (2016) · Adaptive Agents and Multi-Agents Systems · doi:10.5555/2936924.2937013 · Cited by 16
Self-citationRegret-Based Multi-Agent Coordination with Uncertain Task Rewards
Wu, F., & Jennings, N. R. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8879 · Cited by 15
Optimizing Preferences within Groups: A Case Study on Travel Recommendation
Lorenzi, F., dos Santos, F., Ferreira, P. R., & Bazzan, A. L. C. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88190-2_16 · Cited by 13
Message-Passing Algorithms for Quadratic Programming Formulations of MAP EstimationPreprint
Kumar, A., & Zilberstein, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.3739 · Cited by 13 · cited 1×
“oblems and Applications: A Survey 41 reasoning strategies in DCOP with partially cooperative agents. Another direction is to relate DCOP with machine learning techniques. For instance, as outlined in [86,51], one can use inference-based algorithms such as expectation-maximization and convex optimization machinery to d…”
MethodInfinite-Horizon Proactive Dynamic DCOPs
Hoang, K. D., Hou, P., Fioretto, F., Yeoh, W., Zivan, R., & Yokoo, M. (2017) · Adaptive Agents and Multi-Agents Systems · doi:10.5555/3091125.3091160 · Cited by 12
Self-citationOptimum operation of a customer-driven microgrid: A comprehensive approach
Jain, P., Ranade, S. J., Gupta, S., & Pontelli, E. (2012) · IEEE International Conference on Power Electronics, Drives and Energy Systems · doi:10.1109/pedes.2012.6484437 · Cited by 10 · cited 2×
“Researchers have cast this problem as a DCOP [156, 161, 162, 158], where the authors consider a network of nodes (agents), each of which relays power to other nodes, but can also contain a combination of generators and loads.”
BackgroundMethodSelf-citationThe multi variable multi constrained distributed constraint optimization framework
Portway, C., & Durfee, E. H. (2010) · doi:10.5555/1838206.1838394 · Cited by 5
Speeding Up Distributed Constraint Optimization Search Algorithms
Koenig, S., & Yeoh, W. (2014) · Cited by 5
Self-citationLeximin Multiple Objective Optimization for Preferences of Agents
Matsui, T., Silaghi, M. C., Hirayama, K., Yokoo, M., & Matsuo, H. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-13191-7_34 · Cited by 4
Cited by
Blockchain for AI: review and open research challenges
Salah, K., Rehman, M. H. U., Nizamuddin, N., & Al-Fuqaha, A. (2019) · IEEE Access · doi:10.1109/access.2018.2890507 · Cited by 1,001
“Finding a set of best solutions from all possible solutions is one of the main features of AI-enabled applications and systems [51].”
Background
Metadata
- Authors
- Fioretto, F., Pontelli, E., & Yeoh, W.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2018-03-29
- Volume
- 61
- Pages
- 623-698
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W2287429606
- Cited by
- 201
- References
- 105
- FWCI
- 11.67
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.