distributed constraint optimization problems (DCOPs) are a fundamental framework for modeling multi-agent systems (MAS) where agents coordinate their decision-making to optimize a global objective. However, existing i...
详细信息
distributed constraint optimization problems (DCOPs) are a fundamental framework for modeling multi-agent systems (MAS) where agents coordinate their decision-making to optimize a global objective. However, existing incomplete local search algorithms for solving DCOPs face a huge challenge of falling into the local optimum since the information and controls are distributed among multiple autonomous agents. Considering this, two improved local cost simulation algorithms based on coalition structure generation (CSG) named LCS-CSG-F and LCS-CSG-C that execute CSG in fixed and consecutive rounds, respectively, are proposed in this paper to expand the search for solution space. CSG involves partitioning a set of agents into disjoint exhaustive coalitions according to the neighbor relationship between agents, where agents of the original DCOPs are partitioned into coalitions to relax constraints between agents. To verify the effectiveness of the CSG strategy, two competing schemes that execute neighbor ignoring in fixed rounds, named asymmetric single neighbor ignoring (ASI-F) and asymmetric multiple neighbor ignoring (AMI-F), are designed since the CSG strategy symmetrically ignores multiple neighbors in different coalitions simultaneously. From statistical perspective, the Friedman test reveals significant differences between the LCS-CSG algorithm and other algorithms. Extensive experimental results indicate that the proposed CSG-based algorithms significantly outperform the state-of-the-art DCOPs incomplete algorithms in various benchmarks.
The distributedconstraintoptimization Problem (DCOP) formulation is a powerful tool to model multi-agent coordination problems that are distributed by nature. While DCOPs assume that variables are discrete and the e...
详细信息
ISBN:
(纸本)9783031212024;9783031212031
The distributedconstraintoptimization Problem (DCOP) formulation is a powerful tool to model multi-agent coordination problems that are distributed by nature. While DCOPs assume that variables are discrete and the environment does not change over time, agents often interact in a more dynamic and complex environment. To address these limiting assumptions, researchers have proposed Dynamic DCOPs (D-DCOPs) to model how DCOPs dynamically change over time and Continuous DCOPs (C-DCOPs) to model DCOPs with continuous variables and constraints in functional form. However, these models address each limiting assumption of DCOPs in isolation, and it remains a challenge to model problems that both have continuous variables and are in dynamic environment. Therefore, in this paper, we propose Dynamic Continuous DCOPs (DC-DCOPs), a novel formulation that models both dynamic nature of the environment and continuous nature of the variables, which are inherent in many multi-agent problems. In addition, we introduce several greedy algorithms to solve DC-DCOPs and discuss their theoretical properties. Finally, we empirically evaluate the algorithms in random networks and in distributed sensor network application.
The distributedconstraintoptimization Problem (DCOP) formulation is a powerful tool to model cooperative multi-agent problems, especially when they are sparsely constrained with one another. A key assumption in this...
详细信息
As a meta-heuristic algorithm, the ant colony algorithm has been successfully used to solve various combinatorial optimizationproblems. However, the existing algorithm that takes the power of ants to solve distribute...
详细信息
As a meta-heuristic algorithm, the ant colony algorithm has been successfully used to solve various combinatorial optimizationproblems. However, the existing algorithm that takes the power of ants to solve distributed constraint optimization problems (ACO_DCOP) is easy to fall into local optima. To deal with this issue, this paper presents an adaptive ant colony algorithm based on local information entropy to solve distributed constraint optimization problems, named LIEAD. In LIEAD, the local information entropy is introduced to help agents adaptively select the pheromone update strategy and value selection strategy, which improves the convergence speed and the quality of the solution. Moreover, a restart mechanism is designed to break the accumulation state of pheromone, which increases the population diversity and helps the algorithm jump out of the local optima. The extensive experimental results indicate that LIEAD can significantly outperform ACO_DCOP and is competitive with the state-of-the-art DCOPs algorithms.
A distributed search algorithm for solving distributedconstraints optimizationproblems (DCOPs) is presented. The new algorithm scans the search space by using multiple search processes (SPs) that run on all agents c...
详细信息
A distributed search algorithm for solving distributedconstraints optimizationproblems (DCOPs) is presented. The new algorithm scans the search space by using multiple search processes (SPs) that run on all agents concurrently. SPs search in non-intersecting parts of the global search space and perform Branch & Bound search. Each search process (SP) uses the mechanism of forward bounding (FB) to prune efficiently its part of the global search space. The Concurrent Forward-Bounding (ConcFB) algorithm enables all SPs to share their upper bound across all parts of the global search space. The number of concurrent SPs is controlled dynamically by the ConcFB algorithm, by performing dynamic splitting. Within each SP a dynamic variable ordering is employed in order to help control the balance of computational load among all agents and across different SPs. The ConcFB algorithm is evaluated experimentally and compared to all state of the art DCOP algorithms. The number of Non-Concurrent Logical Operations, Non-Concurrent Steps, the total number of messages sent and CPU time are used as performance metrics. The evaluation procedure considers different DCOP problem types with a varying number of agents and different constraint graphs. As problems become larger and denser. ConcFB is shown to outperform all other evaluated algorithms by 2-3 orders of magnitude in all performance measures. Further evaluations comparing different variants of ConcFB provide important insights into the working of the algorithm and reveals the contribution of its different components. (C) 2012 Elsevier B.V. All rights reserved.
A distributedconstraintoptimization problem (DCOP) is a framework to model multi -agent coordination problems. Asynchronous distributedoptimization (ADOPT) is a well-known complete DCOP algorithm, and many of its v...
详细信息
A distributedconstraintoptimization problem (DCOP) is a framework to model multi -agent coordination problems. Asynchronous distributedoptimization (ADOPT) is a well-known complete DCOP algorithm, and many of its variants have been proposed over the last decade. It is considered proven that ADOPT -based algorithms have the key properties of termination and optimality, which guarantee that the algorithms terminate in a finite time and obtain an optimal solution, respectively. In this paper, we present counterexamples to the termination and optimality of ADOPT -based algorithms. They are classified into three types, at least one of which exists in each of ADOPT and eight of its variants that we analyzed. In other words, the algorithms may potentially not terminate or terminate with a suboptimal solution. Furthermore, we show that the bounded -error approximation of ADOPT, which enables the algorithm to terminate faster with the quality of the solution guaranteed within a predefined error bound, also suffers from flaws. Additionally, we propose an amended version of ADOPT that avoids the flaws in existing algorithms and prove that it has the properties of termination and optimality.
Autonomous agents in real-world environments may encounter undesirable outcomes or negative side effects (NSEs) when working collaboratively alongside other agents. We frame the challenge of minimizing NSEs in a multi...
详细信息
ISBN:
(纸本)9798400704864
Autonomous agents in real-world environments may encounter undesirable outcomes or negative side effects (NSEs) when working collaboratively alongside other agents. We frame the challenge of minimizing NSEs in a multi-agent setting as a lexicographic decentralized Markov decision process in which we assume independence of rewards and transitions with respect to the primary assigned tasks, but allowing negative side effects to create a form of dependence among the agents. We present a lexicographic Q-learning approach to mitigate the NSEs using human feedback models while maintaining near-optimality with respect to the assigned tasks-up to some given slack. Our empirical evaluation across two domains demonstrates that our collaborative approach effectively mitigates NSEs, outperforming non-collaborative methods.
In scenarios with numerous emergencies that arise and require the assistance of various rescue units (e.g., medical, fire, & police forces), the rescue units would ideally be allocated quickly and distributedly wh...
详细信息
ISBN:
(纸本)9781450394321
In scenarios with numerous emergencies that arise and require the assistance of various rescue units (e.g., medical, fire, & police forces), the rescue units would ideally be allocated quickly and distributedly while aiming to minimize casualties. This is one of many examples of distributed settings with service providers (the rescue units) and service requesters (the emergencies) which we termservice oriented settings. Allocating the service providers in a distributed manner while aiming for a global optimum is hard to model, let alone achieve, using the existing distributedconstraintoptimization Problem (DCOP) framework. Hence, the need for a novel approach and corresponding algorithms. We present the Service Oriented Multi-Agent optimization Problem (SOMAOP), a new framework that overcomes the shortcomings of DCOP in service oriented settings. We evaluate the framework using various algorithms based on auctions and matching algorithms (e.g., Gale Shapely). We empirically show that algorithms based on repeated auctions converge to a high quality solution very fast, while repeated matching problems converge slower, but produce higher quality solutions. We demonstrate the advantages of our approach over standard incomplete DCOP algorithms and a greedy centralized algorithm.
The distributedconstraintoptimization problem (UCOP) has emerged as one of the most promising coordination techniques in multi-agent systems (MAS). However, because DCOP is known to be NP-hard, the existing DCOP tec...
详细信息
ISBN:
(纸本)9781728119854
The distributedconstraintoptimization problem (UCOP) has emerged as one of the most promising coordination techniques in multi-agent systems (MAS). However, because DCOP is known to be NP-hard, the existing DCOP techniques are often unsuitable for large-scale applications, which require scalable algorithms to deal with severely limited computing and communication. Moreover, the selection of DCOP algorithm is a challenging and critical task for obtaining a desirable performance on certain MAS domains. In this paper, we present a performance analysis of incomplete DCOP algorithms on large-scale DCOPs. We experimentally evaluate the state-of-the-art incomplete algorithms on two types of problems involving hundreds of variables with different network topologies and densities. Such performance analysis can help to mitigate the challenges of selection of algorithm for a number of realistic large-scale, complex MAS applications.
distributedconstraintoptimization Problem (DCOP) is a powerful paradigm to model multi-agent systems through enabling multiple agents to coordinate with each other to solve a problem. These agents are often assumed ...
详细信息
distributedconstraintoptimization Problem (DCOP) is a powerful paradigm to model multi-agent systems through enabling multiple agents to coordinate with each other to solve a problem. These agents are often assumed to be cooperative, that is, they communicate with other agents in order to optimize a global objective. However, the communication times between all pairs of agents are assumed to be identical in the evaluation of most DCOP algorithms. This assumption is impractical in almost all real-world applications. In this paper, we study the impact of empirically evaluating a DCOP algorithm under the assumption that communication times between pairs of agents can vary. In addition, we evaluate a DCOP algorithm using ns-2, a discrete-event simulator that is widely used in the computer networking community, to simulate the communication times, as opposed to the standard DCOP simulators that are used to evaluate DCOP algorithms in the AI community. Furthermore, we propose heuristics that exploit the non-uniform communication times to speed up DCOP algorithms that operate on pseudo-trees. Our empirical results demonstrate that the proposed heuristics improve the runtime of those algorithms up to 20%. These heuristics are evaluated on different benchmarks such as scale-free graphs, random graphs, and an instance of the smart grid, Customer-Driven Microgrid (CDMG) application.
暂无评论