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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Minimizing Negative Side Effects in Cooperative Multi-Agent Systems using distributed Coordination 24

Minimizing Negative Side Effects in Cooperative Multi-Agent ...

引用

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

作者： Moumita Choudhury Sandhya Saisubramanian Hao Zhang Shlomo Zilberstein University of Massachusetts Amherst Amherst MA USA Oregon State University Corvallis OR USA

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.

关键词： ai safety cooperative multi-agent systems distributed constraint optimization problems negative side effects

来源：评论

学校读者我要写书评

暂无评论

Ask and You Shall be Served: Representing & Solving Multi-agentoptimization problems with Service Requesters and Providers 23

Ask and You Shall be Served: Representing & Solving Multi-ag...

引用

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

作者： Maya Lavie Tehila Caspi Omer Lev Roie Zivan Ben Gurion University of the Negev Be'er Sheva Israel

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

关键词： multi-agent optimization distributed problem solving multi-agent system distributed constraint optimization problems

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：