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

distributed constraint optimization for teams of mobile sensing agents

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2015年第3期29卷 495-536页

作者： Zivan, Roie Yedidsion, Harel Okamoto, Steven Glinton, Robin Sycara, Katia Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel Carnegie Mellon Univ Inst Robot Pittsburgh PA 15213 USA

Coordinating a mobile sensor team (MST) to cover targets is a challenging problem in many multiagent applications. Such applications are inherently dynamic due to changes in the environment, technology failures, and incomplete knowledge of the agents. Agents must adaptively respond by changing their locations to continually optimize the coverage of targets. We propose distributed constraint optimization problems (DCOP)_MST, a new model for representing MST problems that is based on DCOP. In DCOP_MST, agents maintain variables for their physical positions, while each target is represented by a constraint that reflects the quality of coverage of that target. In contrast to conventional, static DCOPs, DCOP_MST not only permits dynamism but exploits it by restricting variable domains to nearby locations;consequently, variable domains and constraints change as the agents move through the environment. DCOP_MST confers three major advantages. It directly represents the multiple forms of dynamism inherent in MSTs. It also provides a compact representation that can be solved efficiently with local search algorithms, with information and communication locality based on physical locality as typically occurs in MST applications. Finally, DCOP_MST facilitates organization of the team into multiple sub-teams that can specialize in different roles and coordinate their activity through dynamic events. We demonstrate how a search-and-detection team responsible for finding new targets and a surveillance sub-team tasked with coverage of known targets can effectively work together to improve performance while using the DCOP_MST framework to coordinate. We propose different algorithms to meet the specific needs of each sub-team and several methods for cooperation between sub-teams. For the search-and-detection team, we develop an algorithm based on the DSA that forces intensive exploration for new targets. For the surveillance sub-team, we adapt several incomplete DCOP algorithms, inclu

关键词： Multi-agent systems Dynamic distributed problems distributed constraint optimization

来源：评论

学校读者我要写书评

暂无评论

distributed constraint optimization Problems: Review and perspectives

引用

EXPERT SYSTEMS WITH APPLICATIONS 2014年第11期41卷 5139-5157页

作者： Leite, Allan R. Enembreck, Fabricio Barthes, Jean-Paul A. Pontificia Univ Catolica Parana PUCPR Curitiba Parana Brazil Pontifical Catholic Univ Parana PUC PR Postgrad Program Informat PPGIA Curitiba Parana Brazil Univ Technol Compiegne UTC Compiegne France

Intelligent agents is a research area of the Artificial Intelligence intensely studied since the 1980s. Multi-agent systems represent a powerful paradigm of analyzing, projecting, and developing complex systems. One of the main difficulties in modeling a multi-agent system is defining the coordination model, due to the autonomous behavior of the agents. distributed constraint optimization Problems (DCOP) have emerged as one of most important formalisms for coordination and distributed problem solving in multi-agent systems and are capable of modeling a large class of real world problems naturally. This work aims to provide an overview and critical review of DCOP, addressing the most popular methods and techniques, the evolution and comparison of algorithms, and future perspectives on this promising research area. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Multi-agent systems Autonomous agents distributed constraint optimization Problems

来源：评论

学校读者我要写书评

暂无评论

Applying Max-sum to asymmetric distributed constraint optimization problems

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2020年第1期34卷 1-29页

作者： Zivan, Roie Parash, Tomer Cohen-Lavi, Liel Naveh, Yarden Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

We study the adjustment and use of the Max-sum algorithm for solving Asymmetric distributed constraint optimization Problems (ADCOPs). First, we formalize asymmetric factor-graphs and apply the different versions of Max-sum to them. Apparently, in contrast to local search algorithms, most Max-sum versions perform similarly when solving symmetric and asymmetric problems and some even perform better on asymmetric problems. Second, we prove that the convergence properties of Max-sum_ADVP (an algorithm that was previously found to outperform standard Max-sum and Bounded Max-sum) and the quality of the solutions it produces, are dependent on the order between nodes involved in each constraint, i.e., the inner constraint order (ICO). A standard ICO allows to reproduce the properties achieved for symmetric problems. Third, we demonstrate that a non-standard ICO can be used to balance exploration and exploitation. Our results indicate that Max-sum_ADVP with non-standard ICO and Damped Max-sum, when solving asymmetric problems, both outperform other versions of Max-sum, as well as local search algorithms specifically designed for solving ADCOPs.

关键词： distributed constraint optimization Incomplete inference distributed algorithms Max-sum

来源：评论

学校读者我要写书评

暂无评论

Cluster Tree Elimination for distributed constraint optimization with Quality Guarantees

引用

FUNDAMENTA INFORMATICAE 2010年第3-4期102卷 263-286页

作者： Brito, Ismel Meseguer, Pedro CSIC IIIA Spanish Natl Res Council Artificial Intelligence Res Inst Bellaterra 08193 Spain

Some distributed constraint optimization algorithms use a linear number of messages in the number of agents, but of exponential size. This is often the main limitation for their practical applicability. Here we present some distributed algorithms for these problems when they are arranged in a tree of agents. The exact algorithm, DCTE, computes the optimal solution but requires messages of size exp(s), where s is a structural parameter. Its approximate version, DMCTE(r), requires smaller messages of size exp(r), r < s, at the cost of computing approximate solutions. It provides a cost interval that bounds the error of the approximation. Using the technique of cost function filtering, we obtain DMCTEf(r). Combining cost function filtering with bound reasoning, we propose DIMCTEf, an algorithm based on repeated executions of DMCTEf (r) with increasing r. DIMCTEf uses messages of previous iterations to decrease the size of messages in the current iteration, which allows to alleviate their high size. We provide evidences of the benefits of our approach on two benchmarks.

关键词： distributed constraint optimization distributed cluster-tree elimination function filtering

来源：评论

学校读者我要写书评

暂无评论

An improved DPOP algorithm based on breadth first search pseudo-tree for distributed constraint optimization

引用

APPLIED INTELLIGENCE 2017年第3期47卷 607-623页

作者： Chen, Ziyu He, Zhen He, Chen Chongqing Univ Coll Comp Sci Chongqing Peoples R China

Depth First Search (DFS) pseudo-tree is popularly used as the communication structure in complete algorithms for solving distributed constraint optimization Problems (DCOPs) from multiagent systems. The advantage of a DFS pseudo-tree lies in its parallelism derived from pseudo-tree branches because the nodes in different branches are relatively independent and can compute concurrently. However, the constructed DFS pseudo-trees in experiments often come to be chain-like and greatly impair the performances of solving algorithms. Therefore, we propose a new DPOP algorithm using a Breadth First Search (BFS) pseudo-tree as the communication structure, named BFSDPOP. Compared with a DFS pseudo-tree, a BFS pseudo-tree is more excellent on the parallelism as it has much more branches. Another notable advantage is that the height of a BFS pseudo-tree is much lower than that of a DFS pseudo-tree, which gives rise to the shorter communication paths and less communication time. The method of Cluster Removing is also presented to allocate cross-edge constraints to reduce the size of the largest message in BFSDPOP. In the experiment, BFSDPOP with a BFS pseudo-tree and original DPOP with a DFS pseudo-tree are compared on three types of problems - graph coloring problems, meeting scheduling problems and random DCOPs. The results show that BFSDPOP outperforms original DPOP in most cases, which proves the excellent attributes of BFS pseudo-tree over DFS pseudo-tree.

关键词： Multiagent system distributed constraint optimization Breadth first search pseudo-tree DPOP

来源：评论

学校读者我要写书评

暂无评论

Explorative anytime local search for distributed constraint optimization

引用

ARTIFICIAL INTELLIGENCE 2014年第1期212卷 1-26页

作者： Zivan, Roie Okamoto, Steven Peled, Hilla Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

distributed constraint optimization Problems (DCOPs) are an elegant model for representing and solving many realistic combinatorial problems that are distributed by nature. DCOPs are NP-hard and therefore many recent studies consider incomplete algorithms for solving them. distributed local search algorithms, in which agents in the system hold value assignments to their variables and iteratively make decisions on whether to replace them, can be used for solving DCOPs. However, because of the differences between the global evaluation of a system's state and the private evaluation of states by agents, agents are unaware of the global best state that is explored by the algorithm. Previous attempts to use local search algorithms for solving DCOPs reported the state held by the system at the termination of the algorithm, which was not necessarily the (global) best state explored. A general framework that enhances distributed local search algorithms for DCOPs with the anytime property is proposed. The proposed framework makes use of a BFS-tree in order to accumulate the costs of the system's state during the algorithm's iterative performance and to propagate the detection of a new best state when it is found. The proposed framework does not require additional network load. Agents are required to hold a small (linear) additional space (beside the requirements of the algorithm in use). We further propose a set of increased exploration heuristics that exploit the proposed anytime framework. These exploration methods implement different approaches towards exploration. Our empirical study considers various scenarios including random, realistic, and structured problems. It reveals the advantage of the use of the proposed heuristics in the anytime framework over state-of-the-art local search algorithms. (C) 2014 Elsevier B.V. All rights reserved.

关键词： distributed constraint optimization Incomplete search Exploration heuristics

来源：评论

学校读者我要写书评

暂无评论

Back-feed power restoration using distributed constraint optimization in smart distribution grids clustered into microgrids

引用

APPLIED ENERGY 2017年 206卷 1102-1117页

作者： El-Sharafy, M. Zaki Farag, Hany E. Z. York Univ Dept Elect Engn & Comp Sci 4700 Keele St Toronto ON M3J 1P3 Canada

In this paper, an optimization problem is formulated for the automatic back-feed service restoration in smart distribution grids. The formulated problem relies on the structure of smart distribution grids, clustered into multi-microgrids, capable of operating in both grid-connected and islanded modes of operation. To that end, three types of power transfer between the neighboring microgrids, during the restoration processes are introduced: load transfer, distributed generation (DG) transfer, and combined load DG transfer. The formulated optimization problem takes into account the ability of forming new, not predefined islanded microgrids, in the post-restoration configuration, to maximize service restoration. To obviate the need for a central unit, the optimization problem is reformulated, in this work, as a distributed constraint optimization problem, in which the variables and constraints are distributed among automated agents. To reduce the problem complexity, the restoration problem is decomposed into two sequential and interdependent distributed sub-problems: supply adequacy, and optimal reconfiguration. The proposed algorithm adopts the Optimal Asynchronous Partial Overlay (OPTAPO) technique, which is based on the distributed constraint agent search to solve distributed sub-problems in a multi-agent environment. Several case studies have been carried out to evaluate the effectiveness and robustness of the proposed algorithm.

关键词： distributed constraint optimization distributed generation Microgrids Restoration Smart distribution grids

来源：评论

学校读者我要写书评

暂无评论

A Two-Phase Complete Algorithm for Multi-Objective distributed constraint optimization

引用

JOURNAL OF ADVANCED COMPUTATIONAL INTELLIGENCE AND INTELLIGENT INFORMATICS 2014年第4期18卷 573-580页

作者： Medi, Alexandre Okimoto, Tenda Inoue, Katsumi Univ Nantes Direct Relat Int BP 13522 F-44035 Nantes 1 France Kobe Univ Fac Maritime Sci Kobe Hyogo 6580022 Japan Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

A distributed constraint optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Many application problems in multi-agent systems can be formalized as DCOPs. However, many real world optimization problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective distributed constraint optimization Problem (MO-DCOP) is an extension of a mono-objective DCOP. Compared to DCOPs, there exists few works on MO-DCOPs. In this paper, we develop a novel complete algorithm for solving an MO-DCOP. This algorithm utilizes a widely used method called Pareto Local Search (PLS) to generate an approximation of the Pareto front. Then, the obtained information is used to guide the search thresholds in a Branch and Bound algorithm. In the evaluations, we evaluate the runtime of our algorithm and show empirically that using a Pareto front approximation obtained by a PLS algorithm allows to significantly speed-up the search in a Branch and Bound algorithm.

关键词： multi-agent system distributed constraint optimization multi-criteria

来源：评论

学校读者我要写书评

暂无评论

distributed constraint optimization with Structured Resource constraints 09

Distributed Constraint Optimization with Structured Resource...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Akshat Kumar Boi Faltings Adrian Petcu Department of Computer Science University of Massachusetts Artificial Intelligence Laboratory Swiss Federal Institute of Technology SAP Research

ISBN: (纸本)9781615673346

distributed constraint optimization (DCOP) provides a framework for coordinated decision making by a team of agents. Often, during the decision making, capacity constraints on agents' resource consumption must be taken into account. To address such scenarios, an extension of DCOP- Resource Constrained DCOP- has been proposed. However, certain type of resources have an additional structure associated with them and exploiting it can result in more efficient algorithms than possible with a general framework. An example of these are distribution networks, where the flow of a commodity from sources to sinks is limited by the flow capacity of edges. We present a new model of structured resource constraints that exploits the acyclicity and the flow conservation property of distribution networks. We show how this model can be used in efficient algorithms for finding the optimal flow configuration in distribution networks, an essential problem in managing power distribution networks. Experiments demonstrate the efficiency and scalability of our approach on publicly available benchmarks and compare favorably against a specialized solver for this task. Our results extend significantly the effectiveness of distributed constraint optimization for practical multi-agent settings.

关键词： Algorithms Theory distributed constraint optimization Power restoration

来源：评论

学校读者我要写书评

暂无评论

Combining Agent Based Modeling with distributed constraint optimization for Service Delivery optimization 18

Combining Agent Based Modeling with Distributed Constraint O...

引用

18th IEEE International Enterprise distributed Object Computing Conference (EDOC)

作者： Mohagheghian, Mohammadreza Sindhgatta, Renuka Ghose, Aditya Univ Wollongong Sch Comp Sci & Software Engn Decis Syst Lab Wollongong NSW 2522 Australia IBM Res India New Delhi India

ISBN: (纸本)9781479954674

Service delivery optimization is a challenge for most service organizations. Most organizations tend to allocate tasks to service workers using simple (and often ad-hoc) policies without leveraging explicit optimization techniques for resource allocation. This is, in part, due to the difficulty of modeling the resource allocation problem in the context of the complex social setting in which service delivery occurs as an optimization problem. This is also, in part, due to several practical impediments to deploying traditional optimization technology in an effective fashion in service delivery settings. This paper offers a novel solution which combines agent-based modeling (ABM) and distributed constraint optimization (DCOP). ABM is used to model the social context of service delivery, while the use of DCOP techniques enables us to bring the dynamic knowledge (and insights) residing in service workers to bear on the optimal resource allocation problem without imposing the unrealistic requirement that all service workers continually communicate their local knowledge to a traditional (centralized) optimization solver. The combination of ABM and DCOP enables us to analyze and assess the efficiency gains that might be possible by optimizing resource allocation in a particular service delivery setting. Our empirical evaluation, based on data patterned on those in a large service delivery organization, provides encouraging results.

关键词： Service Delivery Problem Agent Based Modeling distributed constraint optimization DCOP

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：