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

Privacy loss in distributed constraint reasoning: A quantitative framework for analysis and its applications

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2006年第1期13卷 27-60页

作者： Maheswaran, RT Pearce, JP Bowring, E Varakantham, P Tambe, M Univ So Calif Dept Comp Sci Los Angeles CA 90089 USA Univ So Calif Inst Sci Informat Los Angeles CA 90089 USA

It is critical that agents deployed in real-world settings, such as businesses, offices, universities and research laboratories, protect their individual users' privacy when interacting with other entities. Indeed, privacy is recognized as a key motivating factor in the design of several multiagent algorithms, such as in distributed constraint reasoning (including both algorithms for distributed constraint optimization (DCOP) and distributed constraint satisfaction (DisCSPs)), and researchers have begun to propose metrics for analysis of privacy loss in such multiagent algorithms. Unfortunately, a general quantitative framework to compare these existing metrics for privacy loss or to identify dimensions along which to construct new metrics is currently lacking. This paper presents three key contributions to address this shortcoming. First, the paper presents VPS (Valuations of Possible States), a general quantitative framework to express, analyze and compare existing metrics of privacy loss. Based on a state-space model, VPS is shown to capture various existing measures of privacy created for specific domains of DisCSPs. The utility of VPS is further illustrated through analysis of privacy loss in DCOP algorithms, when such algorithms are used by personal assistant agents to schedule meetings among users. In addition, VPS helps identify dimensions along which to classify and construct new privacy metrics and it also supports their quantitative comparison. Second, the article presents key inference rules that may be used in analysis of privacy loss in DCOP algorithms under different assumptions. Third, detailed experiments based on the VPS-driven analysis lead to the following key results: (i) decentralization by itself does not provide superior protection of privacy in DisCSP/DCOP algorithms when compared with centralization;instead, privacy protection also requires the presence of uncertainty about agents' knowledge of the constraint graph. (ii) one needs to carefu

关键词： distributed constraint reasoning privacy distributed constraint optimization

来源：评论

学校读者我要写书评

暂无评论

DCOPolis: A framework for simulating and deploying distributed constraint reasoning algorithms

DCOPolis: A framework for simulating and deploying distribut...

引用

7th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2008

作者： Sultanik, Evan A. Lass, Robert N. Regli, William C. Department of Computer Science Drexel University Philadelphia PA United States

来源：评论

学校读者我要写书评

暂无评论

Multiagent Systems and distributed constraint reasoning for Regulatory Mechanism Design in Water Management

引用

JOURNAL OF WATER RESOURCES PLANNING AND MANAGEMENT 2015年第4期141卷 04014068-04014068页

作者： Giuliani, Matteo Castelletti, Andrea Amigoni, Francesco Cai, Ximing Politecn Milan Dept Elect Informat & Bioengn I-20133 Milan Italy Univ Illinois Dept Civil & Environm Engn Urbana IL 61801 USA

Many water resources systems include multiple, independent, and distributed decision makers representing different and conflicting interests. In much of the water resources literature, the operation of these systems is studied assuming a fully cooperative attitude by the parties involved and maximizing the global efficiency at the system-level. However, assuming the presence of a social planner might be questionable when multiple institutions are involved, particularly in transboundary systems. At the other extreme, totally uncoordinated strategies among institutionally independent decision makers, acting according to the principle of individual-rationality, are more often experienced in these contexts, yielding a decrease in the system-level performance. In this paper, a novel approach is proposed based on multiagent systems to support the design of regulatory mechanisms, which drive the originally fully independent decision makers towards a more coordinated and system-wide efficient situation. The agent-based model is coupled with tools and algorithms based on distributed constraint reasoning to represent the interactions between the decision makers. The approach is demonstrated on a hypothetical water allocation problem, involving several active human agents and passive ecological agents. Different regulatory mechanisms are explored in three different scenarios of water availability to quantitatively support the discussion about the efficiency-acceptability trade-off. Numerical results show that the proposed approach has a great potential to support the design of distributed solutions balancing system-level efficiency and individual-level acceptability. (C) 2014 American Society of Civil Engineers.

关键词： Multiagent systems distributed constraint reasoning Mechanism design Water management

来源：评论

学校读者我要写书评

暂无评论

DCOPolis: a framework for simulating and deploying distributed constraint reasoning algorithms 08

DCOPolis: a framework for simulating and deploying distribut...

引用

Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: demo papers

作者： Evan A. Sultanik Robert N. Lass William C. Regli Drexel University Philadelphia PA

The proliferation of mobile computers---such as laptops, personal digital assistants, and smart phones---has propelled distributed computing into mainstream society. Over the past decade these technologies have spurred interest in both decentralized multiagent systems and wireless mobile ad-hoc networks. Such networks, however, present many challenges to information sharing and coordination. Interference, obstacles, and other environmental effects conspire with power-and processing-limited hardware to impose a number of challenging networking characteristics. Messages are routinely lost or delayed, connections may be only sporadically available, and network transfer capacity is nowhere near that available on modern wired networks. It is therefore imperative to emphasize local decision making and autonomy over a centralized analogue, insofar as it is possible. The majority of such decentralized decision making can be seen as a fundamental problem of propagating and then solving systems of constraints, otherwise known as distributed constraint reasoning (DCR).

关键词： simulation middleware distributed constraint reasoning

来源：评论

学校读者我要写书评

暂无评论

Nogood-based asynchronous forward checking algorithms

引用

constraintS 2013年第3期18卷 404-433页

作者： Wahbi, Mohamed Ezzahir, Redouane Bessiere, Christian Bouyakhf, El Houssine Ecole Mines Nantes Nantes France Univ Ibn Zohr ENSA Agadir Agadir Morocco Univ Montpellier F-34059 Montpellier France Univ Mohammed V Agdal LIMIARF Rabat Morocco

We propose two new algorithms for solving distributed constraint Satisfaction Problems (DisCSPs). The first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). Besides its use of nogoods as justification of value removals, AFC-ng allows simultaneous backtracks going from different agents to different destinations. The second algorithm, Asynchronous Forward Checking Tree (AFC-tree), is based on the AFC-ng algorithm and is performed on a pseudo-tree ordering of the constraint graph. AFC-tree runs simultaneous search processes in disjoint problem subtrees and exploits the parallelism inherent in the problem. We prove that AFC-ng and AFC-tree only need polynomial space. We compare the performance of these algorithms with other DisCSP algorithms on random DisCSPs and instances from real benchmarks: sensor networks and distributed meeting scheduling. Our experiments show that AFC-ng improves on AFC and that AFC-tree outperforms all compared algorithms, particularly on sparse problems.

关键词： distributed constraint reasoning Search algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed envy minimization for resource allocation

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2016年第2期30卷 364-402页

作者： Netzer, Arnon Meisels, Amnon Zivan, Roie Ben Gurion Univ Negev IL-84105 Beer Sheva Israel

Minimizing envy in distributed discrete resource or task allocation, is an unusual distributed optimization challenge, since the quality of the allocation for each of the agents is dependent, not only on its own allocation, but on the allocation of others as well. Thus, in order to perform distributed search for allocations with minimal envy there is a need to design innovative algorithms that can cope with the challenging constraint structure of an envy minimization problem. distributed methods for minimizing envy among agents in indivisible resource allocation problems are presented. First, distributed Envy Minimization Problems (DEMP) are formulated as distributed constraint reasoning problems. When the DEMPs are large, and cannot be solved by a complete search an incomplete local search algorithm is presented. Each transfer of a good from one agent to another involves the change of state of more than one agent. Thus, a minimizing envy local search algorithm must build upon actions (transfers) that include multiple agents. Since DEMPs are particularly susceptible to local minima during local search, the paper proposes an algorithm that alternates between two different hill climbing search phases. The first phase uses one-transfer steps while the other exploits envy cycle elimination steps. An algorithm that minimizes envy while preserving efficiency, is proposed. The proposed algorithm finds a Pareto optimal allocation with low envy. In the context of resource allocation problems, a Pareto optimal solution is particularly desirable since it presents a stable solution. The proposed algorithm first finds a divisible Pareto optimal envy-free allocation using a Fisher market equilibrium. This allocation is transferred into an indivisible allocation of goods while maintaining the Pareto optimal characteristic of the allocation and a low envy level among agents.

关键词： Envy minimization Indivisible resource allocation distributed constraint reasoning Fisher market equilibrium

来源：评论

学校读者我要写书评

暂无评论

Reordering all agents in asynchronous backtracking for distributed constraint satisfaction problems

引用

ARTIFICIAL INTELLIGENCE 2020年 278卷 103169-000页

作者： Mechqrane, Younes Wahbi, Mohamed Bessiere, Christian Brown, Kenneth N. Mohammed V Univ Rabat Morocco Univ Coll Cork Insight Ctr Data Analyt Cork Ireland Univ Montpellier CNRS Montpellier France

distributed constraint satisfaction problems (DisCSPs) can express decision problems where physically distributed agents control different decision variables, but must coordinate with each other to agree on a global solution. Asynchronous Backtracking (ABT) is a pivotal search procedure for DisCSPs. ABT requires a static total ordering on the agents. However, reordering agents during search is an essential component for efficiently solving a DisCSP. All polynomial space algorithms proposed so far to improve ABT by reordering agents during search only allow a limited amount of reordering. In this paper, we propose AgileABT, a general framework for reordering agents asynchronously that is able to change the ordering of all agents. This is done via the original notion of termination value, a label attached to the orders exchanged by agents during search. We prove that AgileABT is sound and complete. We show that, thanks to termination values, our framework allows us to implement the main variable ordering heuristics from centralized CSPs, which until now could not be applied to the distributed setting. We prove that AgileABT terminates and has a polynomial space complexity in all these cases. Our empirical study shows the significance of our framework compared to state-of-the-art asynchronous dynamic ordering algorithms for solving distributed CSP. (C) 2019 Elsevier B.V. All rights reserved.

关键词： distributed constraint reasoning Asynchronous backtracking Dynamic variable ordering

来源：评论

学校读者我要写书评

暂无评论

Communication-constrained DCOPs: message approximation in GDL with function filtering 11

Communication-constrained DCOPs: message approximation in GD...

引用

The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 1

作者： Marc Pujol-Gonzalez Jesus Cerquides Pedro Meseguer J. A. Rodriguez-Aguilar Artificial Intelligence Research Institute (IIIA) Spanish Scientific Research Council (CSIC) Campus de la UAB Bellaterra Spain

ISBN: (纸本)9780982657157

In this paper we focus on solving DCOPs in communication constrained scenarios. The GDL algorithm optimally solves DCOP problems, but requires the exchange of exponentially large messages which makes it impractical in such settings. Function filtering is a technique that alleviates this high communication requirement while maintaining optimality. Function filtering involves calculating approximations of the exact cost functions exchanged by GDL. In this work, we explore different ways to compute such approximations, providing a novel method that empirically achieves significant communication savings.

关键词： DCOP filtering GDL distributed constraint reasoning

来源：评论

学校读者我要写书评

暂无评论

Sensitivity analysis for distributed optimization with resource constraints 09

Sensitivity analysis for distributed optimization with resou...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Emma Bowring Zhengyu Yin Rob Zinkov Milind Tambe University of the Pacific University of Southern California

ISBN: (纸本)9781615673346

Previous work in multiagent coordination has addressed the challenge of planning in domains where agents must optimize a global goal, while satisfying local resource constraints. However, the imposition of resource constraints naturally raises the question of whether the agents could significantly improve their team performance if a few more resources were made available. Sensitivity analysis aims to answer that question. This paper focuses on sensitivity analysis in the context of the distributed coordination framework, Multiply-Constrained DCOP (MC-DCOP). There are three main challenges in performing sensitivity analysis: (i) to perform it in a distributed fashion, (ii) to avoid re-solving an NP-hard MC-DCOP optimization from scratch, and (iii) to avoid considering unproductive uses for extra resources. To meet these challenges, this paper presents three types of locally optimal algorithms: link analysis, local reoptimization and local constraint propagation. These algorithms are distributed and avoid redundant computation by ascertaining just the effects of local perturbations on the original problem. Deploying our algorithms on a large number of MC-DCOP problems revealed several results. While our cheapest algorithm successfully identified quality improvements for a few problems, our more complex techniques were necessary to identify the best uses for additional resources. Furthermore, we identified two heuristics that can help identify a priori which agents might benefit most from additional resources: density rank, which works well when nodes received identical resources and remaining resource rank, which works well when nodes received resources based on the number of neighbors they had.

关键词： Design distributed constraint reasoning DCOP Multiagent systems

来源：评论

学校读者我要写书评

暂无评论

Coordination of first responders under communication and resource constraints 08

Coordination of first responders under communication and res...

引用

Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 3

作者： Robert N. Lass Joseph B. Kopena Evan A. Sultanik Duc N. Nguyen Christopher P. Dugan Pragnesh J. Modi William C. Regli Drexel University Philadelphia PA

ISBN: (纸本)9780981738123

This paper discusses the application of distributed constraint optimization to coordination in disaster management situations under sub-optimal network conditions. It presents an example system for the problem of shelter assignment and outlines some of the challenges and future research directions that must be addressed before real-world deployment of distributed constraint optimization becomes a reality.

关键词： distributed constraint reasoning MANETs evacuation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：