检索结果-内蒙古大学图书馆

The improved local cost simulation algorithms based on coalition structure generation for solving distributed constraint optimization problems

引用

JOURNAL OF SUPERCOMPUTING 2025年第1期81卷 1-21页

作者： Shi, Meifeng Jia, Guoyan Yokoo, Makoto Chongqing Univ Technol Dept Comp Sci & Engn 69 Hongguang Chongqing 400054 Peoples R China Kyushu Univ Fac Informat Sci & Elect Engn 744 Motooka Fukuoka 8190395 Japan

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.

关键词： distributed constraint optimization problems Coalition structure generation Symmetrically multiple neighbor ignoring Local search

来源：评论

学校读者我要写书评

暂无评论

Concurrent forward bounding for distributed constraint optimization problems

引用

ARTIFICIAL INTELLIGENCE 2012年 193卷 186-216页

作者： Netzer, Arnon Grubshtein, Alon Meisels, Amnon Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

A distributed search algorithm for solving distributed constraints optimization problems (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.

关键词： distributed constraint optimization problems Algorithms ConcFB

来源：评论

学校读者我要写书评

暂无评论

Dynamic Continuous distributed constraint optimization problems 24th

Dynamic Continuous Distributed Constraint Optimization Probl...

引用

24th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA)

作者： Hoang, Khoi D. Yeoh, William Washington Univ St Louis MO 63110 USA

ISBN: (纸本)9783031212024;9783031212031

The distributed constraint optimization 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.

关键词： Multiagent systems distributed constraint optimization problems Continuous DCOPs Dynamic DCOPs

来源：评论

学校读者我要写书评

暂无评论

Incomplete distributed constraint optimization problems: Model, Algorithms, and Heuristics 1

引用

3rd International Conference on distributed Artificial Intelligence, DAI 2021

作者： Tabakhi, Atena M. Yeoh, William Zivan, Roie Washington University in St. Louis St. Louis United States Ben Gurion University of the Negev Beer Sheva Israel

ISBN: (数字)9783030946623

ISBN: (纸本)9783030946616

The distributed constraint optimization 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 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. In this paper, 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 SyncBB, a complete DCOP algorithm, and ALS-MGM, an incomplete DCOP algorithm, to solve I-DCOPs. We also propose parameterized heuristics that those algorithms can utilize to trade off solution quality for faster runtime and fewer elicitation. They also provide theoretical quality guarantees when used by SyncBB when elicitations are free. Our model and heuristics thus extend the state-of-the-art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences. © 2022, Springer Nature Switzerland AG.

关键词： distributed constraint optimization problems distributed problem solving Multi-agent problems Preference elicitation

来源：评论

学校读者我要写书评

暂无评论

An Adaptive Ant Colony Algorithm Based on Local Information Entropy to Solve distributed constraint optimization problems

引用

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE 2023年第9期37卷 2359013-2359013页

作者： Shi, Meifeng Xiao, Shichuan Feng, Xin Chongqing Univ Technol Coll Comp Sci & Engn Chongqing 400054 Peoples R China

As a meta-heuristic algorithm, the ant colony algorithm has been successfully used to solve various combinatorial optimization problems. 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.

关键词： Ant colony algorithm distributed constraint optimization problems local information entropy pheromone DCOPs algorithms

来源：评论

学校读者我要写书评

暂无评论

Evaluating Incomplete DCOP Algorithms On Large-Scale problems

Evaluating Incomplete DCOP Algorithms On Large-Scale Problem...

引用

International Joint Conference on Neural Networks (IJCNN)

作者： Leite, Allan Enembreck, Fabricio Pontifical Catholic Univ Parana PUCPR Postgrad Program Appl Informat PPGia Curitiba Parana Brazil

ISBN: (纸本)9781728119854

The distributed constraint optimization 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.

关键词： multi-agent systems distributed constraint optimization problems large-scale problems

来源：评论

学校读者我要写书评

暂无评论

Decomposing Utility Functions in Bounded Max-Sum for distributed constraint optimization

Decomposing Utility Functions in Bounded Max-Sum for Distrib...

引用

4th Global Congress on Intelligent Systems (GCIS)

作者： Rollon, Emma Larrosa, Javier Univ Politecn Cataluna Dept Llenguatges & Sistemes Informat Barcelona Spain

ISBN: (纸本)9781479928859

Bounded Max-Sum is a message-passing algorithm for solving distributed constraint optimization problems (DCOP) able to compute solutions with a guaranteed approximation ratio. In this paper we show that the introduction of an intermediate step that decomposes functions may significantly improve its accuracy. This is especially relevant in critical applications (e.g. automatic surveillance, disaster response scenarios) where the accuracy of solutions is of vital importance.

关键词： distributed constraint optimization problems approximate algorithms decomposition

来源：评论

学校读者我要写书评

暂无评论

Reducing the Number of Samples in distributed Cooperative Solution Method for Resource Supply Networks

Reducing the Number of Samples in Distributed Cooperative So...

引用

IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (WI-IAT)

作者： Matsui, Toshihiro Kaneko, Masayuki Takama, Yuho Matsuo, Hiroshi Nagoya Inst Technol Showa Ku Nagoya Aichi 4668555 Japan

ISBN: (纸本)9781479941438

distributed constraint optimization problems (DCOPs) are applied to resource allocation problems in resource supply networks. In previous studies, distributed cooperative solution methods based on feeder trees have been utilized. However, in most cases with resource supply networks, the size of variable's domains in the problems is very large, since the variables originally take continuous values. This is critical even if the networks are trees because it increases the number of combinations. Therefore, sampling of solutions is necessary to restrict the size of the problems. In this study, we propose methods to reduce the number of samples for resource allocation problems of resource supply networks. To maintain the feasibility with the samples, boundaries for the resource amount and cost values were introduced. With the proposed methods, the size of problems is reduced while the methods keep relatively better feasibility and quality of the solutions.

关键词： multi-agent systems optimisation power engineering computing resource allocation sampling methods smart power grids trees (mathematics) DCOPs distributed constraint optimization problems distributed cooperative solution method feeder trees power supply networks resource allocation problems resource supply networks smart grid systems solution sampling constraint optimization Cost function Equations Interpolation Multi-agent systems Resource management Multi-agent systems Resource utilization management of resources Smart grids Constrained optimization Power engineering computing Cost functions sampling methods Interpolation supply network Solutions

来源：评论

学校读者我要写书评

暂无评论

Communication-Sensitive Pseudo-Tree Heuristics for DCOP Algorithms

引用

INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS 2018年第7期27卷

作者： Tabakhi, Atena M. Yeoh, William Tourani, Reza Natividad, Francisco Misra, Satyajayant Washington Univ Dept Comp Sci & Engn St Louis MO 63130 USA St Louis Univ Dept Comp Sci St Louis MO 63103 USA New Mexico State Univ Dept Comp Sci Las Cruces NM 88003 USA

distributed constraint optimization 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.

关键词： distributed constraint optimization problems smart grid customer-driven microgrid network simulators communication times multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

Counterexamples and amendments to the termination and optimality of ADOPT-based algorithms

引用

ARTIFICIAL INTELLIGENCE 2024年 329卷

作者： Noshiro, Koji Hasebe, Koji Univ Tsukuba Degree Programs Syst & Informat Engn Tsukuba Japan Univ Tsukuba Dept Comp Sci Tsukuba Japan

A distributed constraint optimization problem (DCOP) is a framework to model multi -agent coordination problems. Asynchronous distributed optimization (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.

关键词： distributed constraint optimization problems Asynchronous distributed optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：