The distributed constraint optimization Problem (DCOP) formulation is a powerful tool for modeling multi-agent coordination problems. Researchers have recently extended this model to Proactive Dynamic DCOPs (PD-DCOPs)...
详细信息
ISBN:
(纸本)9781510855076
The distributed constraint optimization Problem (DCOP) formulation is a powerful tool for modeling multi-agent coordination problems. Researchers have recently extended this model to Proactive Dynamic DCOPs (PD-DCOPs) to capture the inherent dynamism present in many coordination problems. The PD-DCOP formulation is a finite-horizon model that assumes a finite horizon is known a priori. It ignores changes to the problem after the horizon and is thus not guaranteed to find optimal solutions for infinite-horizon problems, which often occur in the real world. Therefore, we (i) propose the Infinite-Horizon PD-DCOP (IPD-DCOP) model, which extends PD-DCOPs to handle infinite horizons; (ii) exploit the convergence properties of Markov chains to determine the optimal solution to the problem after it has converged; (iii) propose three distributed greedy algorithms to solve IPD-DCOPs; (iv) provide theoretical quality guarantees on the new model; and (v) empirically evaluate both proactive and reactive algorithms to determine the tradeoffs between the two classes. The final contribution is important as, thus far, researchers have exclusively evaluated the two classes of algorithms in isolation. As a result, it is difficult to identify the characteristics of problems that they excel in. Our results are the first in this important direction.
DPOP is an algorithm for distributed constraint optimization which has, as main drawback, the exponential size of some of its messages. Recently, some algorithms for distributed cluster tree elimination have been prop...
详细信息
ISBN:
(纸本)9780982657119
DPOP is an algorithm for distributed constraint optimization which has, as main drawback, the exponential size of some of its messages. Recently, some algorithms for distributed cluster tree elimination have been proposed. They also suffer from exponential size messages. However, using the strategy of cost function filtering, in practice these algorithms obtain important reductions in maximum message size and total communication cost. In this paper, we explain the relation between DPOP and these algorithms, and show how cost function filtering can be combined with DPOP. We present experimental evidence of the benefits of this new approach.
Asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative, is a model for representing multi-agent optimization problems in which agents, are willing to cooperate in or...
详细信息
ISBN:
(纸本)9781450383073
Asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative, is a model for representing multi-agent optimization problems in which agents, are willing to cooperate in order to achieve a global goal, as long as some minimal threshold on their personal utility is *** contribute by: 1) extending the ADCOP model to represent resource allocation problems in which indivisible resources are periodically allocated, e.g., meeting rooms, operating rooms, etc. 2) adjusting partially cooperative local search algorithms to solve problems represented by the extended model. 3) presenting an implementation of a realistic problem that is represented by the proposed model, and empirical evidence of the compatibility of partially cooperative algorithms for this scenario.
Several multiagent tasks can be formulated and solved as DCOPs. BnB-ADOPT~+-AC is one of the most efficient algorithms for optimal DCOP solving. It is based on BnBADOPT, removing redundant messages and maintaining sof...
详细信息
ISBN:
(纸本)9781627481564
Several multiagent tasks can be formulated and solved as DCOPs. BnB-ADOPT~+-AC is one of the most efficient algorithms for optimal DCOP solving. It is based on BnBADOPT, removing redundant messages and maintaining soft arc consistency during search. In this paper, we present several improvements for this algorithm, namely (i) a better implementation, (ii) processing exactly simultaneous deletions, and (iii) searching on arc consistent cost functions. We present empirical results showing the benefits of these improvements on several benchmarks.
Coordination of agent activites in non-deterministic, distributed environments is computationally difficult. distributed constraint optimization (DCOP) provides a rich framework for modeling such multi-agent coordinat...
详细信息
ISBN:
(纸本)9780982657119
Coordination of agent activites in non-deterministic, distributed environments is computationally difficult. distributed constraint optimization (DCOP) provides a rich framework for modeling such multi-agent coordination problems, but existing representations, problem domains, and techniques for DCOP focus on small (<100 variables), deterministic solutions. We present a novel approach to DCOP for large-scale applications that contain uncertain *** types of real-time domains require distributed, scalable algorithms to meet difficult bounds on computation and communication time. To achieve this goal, we develop a new distributed neighbor exchange algorithm for DCOPs that scales to problems involving hundreds of variables and constraints and offers faster convergence to high quality solutions than existing DCOP algorithms. In addition, our complete solution includes new techniques for dynamic distributed constraint optimization and uncertainty in constraint processing. We validate our approach using test scenarios from the DARPA Coordinators program and show that our solution is very competitive with existing approaches.
distributed constraint optimization (DCOP) is useful for solving agent-coordination problems. Any-space DCOP search algorithms require only a small amount of memory but can be sped up by caching information. However, ...
详细信息
ISBN:
(纸本)9780981738161
distributed constraint optimization (DCOP) is useful for solving agent-coordination problems. Any-space DCOP search algorithms require only a small amount of memory but can be sped up by caching information. However, their current caching schemes do not exploit the cached information when deciding which information to preempt from the cache when a new piece of information needs to be cached. Our contributions are three-fold: (1) We frame the problem as an optimization problem. (2) We introduce three new caching schemes (MaxPriority, MaxEffort and MaxUtility) that exploit the cached information in a DCOP-specific way. (3) We evaluate how the resulting speed up depends on the search strategy of the DCOP search algorithm. Our experimental results show that, on all tested DCOP problem classes, our MaxEffort and MaxUtility schemes speed up ADOPT (which uses best-first search) more than the other tested caching schemes, while our MaxPriority scheme speeds up BnB-ADOPT (which uses depth-first branch-and-bound search) at least as much as the other tested caching schemes.
Coordinated multi-agent reinforcement learning (MARL) provides a promising approach to scaling learning in large cooperative multi-agent systems. distributed constraint optimization (DCOP) techniques have been used to...
详细信息
ISBN:
(纸本)9781450319935
Coordinated multi-agent reinforcement learning (MARL) provides a promising approach to scaling learning in large cooperative multi-agent systems. distributed constraint optimization (DCOP) techniques have been used to coordinate action selection among agents during both the learning phase and the policy execution phase (if learning is off-line) to ensure good overall system performance. However, running DCOP algorithms for each action selection through the whole system results in significant communication among agents, which is not practical for most applications with limited communication bandwidth. In this paper, we develop a learning approach that generalizes previous coordinated MARL approaches that use DCOP algorithms and enables MARL to be conducted over a spectrum from independent learning (without communication) to fully coordinated learning depending on agents' communication bandwidth. Our approach defines an interaction measure that allows agents to dynamically identify their beneficial coordination set (i.e., whom to coordinate with) in different situations and to trade off its performance and communication cost. By limiting their coordination set, agents dynamically decompose the coordination network in a distributed way, resulting in dramatically reduced communication for DCOP algorithms without significantly affecting overall learning performance. Essentially, our learning approach conducts co-adaptation of agents' policy learning and coordination set identification, which outperforms approaches that sequence them.
Current DCOP algorithms suffer from a major limiting assumption—each agent can handle only a single variable of the problem—which limits their scalability. This paper proposes a novel Multi-Variable Agent (MVA) DCOP...
详细信息
ISBN:
(纸本)9781450337717
Current DCOP algorithms suffer from a major limiting assumption—each agent can handle only a single variable of the problem—which limits their scalability. This paper proposes a novel Multi-Variable Agent (MVA) DCOP decomposition, which: (i) Exploits co-locality of an agent's variables, allowing us to adopt efficient centralized techniques; (ii) Enables the use of hierarchical parallel models, such us those based on GPGPUs; and (iii) Empirically reduces the amount of communication required in several classes of DCOP algorithms. Experimental results show that our MVA decomposition outperforms non-decomposed DCOP algorithms, in terms of network load and scalability.
A key assumption in distributed constraint optimization Problem (DCOP) model is that all constraints are fully specified or known a priori, which may not hold in applications where constraints encode preferences of hu...
详细信息
ISBN:
(纸本)9781450375184
A key assumption in distributed constraint optimization Problem (DCOP) model is that all constraints are fully specified or known a priori, which may not hold in applications where constraints encode preferences of human users. We extend the model to Incomplete DCOPs (I-DCOPs), where some constraints can be partially specified. User preferences for these partially-specified constraints can be elicited during the execution of I-DCOP algorithms, but they incur some elicitation costs. Additionally, we extend the Synchronous Branch-and-Bound (SyncBB) algorithm to solve I-DCOPs. Our model extends the state of the art in distributedconstraint reasoning to better model and solve distributed agent-based applications with user preferences.
For agents to be trusted with sensitive data, they must have mechanisms to protect their users' privacy. This paper explores the privacy properties of k-optimal algorithms: those algorithms that produce locally op...
详细信息
ISBN:
(纸本)9781615673346
For agents to be trusted with sensitive data, they must have mechanisms to protect their users' privacy. This paper explores the privacy properties of k-optimal algorithms: those algorithms that produce locally optimal solutions that cannot be improved by changing the assignments of k or fewer agents. While these algorithms are subject to large amounts of privacy loss, they can be modified to reduce this privacy loss by an order of magnitude. The greatest improvements are achieved by replacing the centralized local search with a distributed algorithm, such as DPOP.
暂无评论