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

Learning Generalized Nash Equilibria in a Class of Convex Games

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第4期64卷 1426-1439页

作者： Tatarenko, Tatiana Kamgarpour, Maryam Tech Univ Darmstadt Control Methods & Robot Lab D-64283 Darmstadt Germany Swiss Fed Inst Technol Automat Control Lab CH-8092 Zurich Switzerland

We consider multiagent decision making where each agent optimizes its convex cost function subject to individual and coupling constraints. The constraint sets are compact convex subsets of a Euclidean space. To learn Nash equilibria, we propose a novel distributed payoff-based algorithm, where each agent uses information only about its cost value and the constraint value with its associated dual multiplier. We prove convergence of this algorithm to a Nash equilibrium, under the assumption that the game admits a strictly convex potential function. In the absence of coupling constraints, we prove convergence to Nash equilibria under significantly weaker assumptions, not requiring a potential function. Namely, strict monotonicity of the game mapping is sufficient for convergence. We also derive the convergence rate of the algorithm for strongly monotone game maps.

关键词： distributed algorithms learning in games muitiagent decision making payoff-based learning

来源：评论

学校读者我要写书评

暂无评论

Impact Vertices-Aware Diffusion Walk Algorithm for Efficient Subgraph Pattern Matching in Massive Graphs

引用

IEEE ACCESS 2019年 7卷 44555-44561页

作者： Ai, Lihua Ramaswamy, Lakshmish Luo, Siwei Beijing Jiaotong Univ Beijing Key Lab Traff Data Anal & Min Beijing 100044 Peoples R China Univ Georgia Dept Comp Sci Athens GA 30602 USA

Subgraph pattern matching is a basic building block for many applications. Where to commence the pattern matching task and how to proceed are fundamental issues in massive graphs. In this paper, we propose the most impact vertices in view of a query graph and diffusion walk on data graph. We present a novel impact vertices-aware diffusion walk algorithm, a distributed algorithm named DiffWalk, for subgraph pattern matching. Our algorithm employs the most impact vertices from a query graph to locate the initial search position and then proceeds to traverse a large-scale data graph by diffusion walk. We give theoretical analyses based on probability inference and spectral graph, which prove that graph pattern matching beginning at the most impact vertices could prevent comparison overhead by low-probability events first, also prove that diffusion walk could traverse graph efficiently. We have performed a range of experiments that demonstrate our algorithm efficiency both in running time and communication size.

关键词： distributed algorithms graph theory optimal matching subgraph matching

来源：评论

学校读者我要写书评

暂无评论

distributed Localization for Multi-Robot Systems in Presence of Unlocalizable Robots

Distributed Localization for Multi-Robot Systems in Presence...

引用

IEEE Conference on Decision and Control

作者： Zhiyun Lin Zhimin Han Ming Cao Artificial Intelligence Institute School of Automation Hangzhou Dianzi University Hangzhou China Faculty of Science and Engineering University of Groningen The Netherlands

ISBN: (数字)9781728174471

ISBN: (纸本)9781728174488

This paper considers the distributed localization problem for multi-robot systems in the plane with bearing measurements. A necessary and sufficient condition for individual robot to check triangular localizability is provided in terms of a geometric condition. Then a distributed orthogonal algorithm is presented for verifying whether a robot is triangularly localizable. In addition, this paper develops a distributed conjugate residual algorithm, which can solve the localization problem in a more efficient manner. Numerical simulations demonstrate the effectiveness of the approach.

关键词： Robot kinematics Robot sensing systems Noise measurement Multi-robot systems Position measurement distributed algorithms Coordinate measuring machines

来源：评论

学校读者我要写书评

暂无评论

Dynamic Average Diffusion With Randomized Coordinate Updates

引用

IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS 2019年第4期5卷 753-767页

作者： Ying, Bicheng Yuan, Kun Sayed, Ali H. Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA Ecole Polytech Fed Lausanne Sch Engn CH-1015 Lausanne Switzerland

This work derives and analyzes an online learning strategy for tracking the average of time-varying distributed signals by relying on randomized coordinate-descent updates. During each iteration, each agent selects or observes a random entry of the observation vector, and different agents may select different entries of their observations before engaging in a consultation step. Careful coordination of the interactions among agents is necessary to avoid bias and ensure convergence. We provide a convergence analysis for the proposed methods, and illustrate the results by means of simulations.

关键词： Heuristic algorithms Indexes Convergence Optimization Information processing distributed algorithms Network topology Dynamic average diffusion consensus push-sum algorithm coordinate descent exact diffusion

来源：评论

学校读者我要写书评

暂无评论

distributed Edge Coloring and a Special Case of the Constructive Lovasz Local Lemma

引用

ACM TRANSACTIONS ON algorithms 2020年第1期16卷 8-8页

作者： Chang, Yi-Jun He, Qizheng Li, Wenzheng Pettie, Seth Uitto, Jara Univ Michigan Dept EECS 2260 Hayward St Ann Arbor MI 48109 USA Tsinghua Univ Inst Interdisciplinary Informat Sci IIIS FIT Bldg 1-208 Beijing 100084 Peoples R China Swiss Fed Inst Technol Univ Str 6 CH-8092 Zurich Switzerland Univ Freiburg Georges Kohler AlleeGebaude 106 D-79110 Freiburg Germany

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Delta. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. Lower Bounds: First, we simplify the round elimination technique of Brandt et al. [16] and prove that (2 Delta -2)-edge coloring requires Omega (log(Delta) log n) time with high probability and Omega (log(Delta) n) time deterministically, even on trees. Second, we show that a natural approach to computing (Delta + 1)-edge colorings (Vizing's theorem), namely, extending an arbitrary partial coloring by iteratively recoloring subgraphs, requires Omega (Delta log n) time. Upper Bounds on General Graphs: We give a randomized edge coloring algorithm that can use palette sizes as small as Delta + (O) over tilde(root Delta), which is a natural barrier for randomized approaches. The running time of our (1 + is an element of)Delta-edge coloring algorithm is usually dominated by O(log is an element of(-)(1)) calls to a distributed Lovasz local lemma (LLL) algorithm. For example, using the Chung-Pettie-Su LLL algorithm, we compute a (1 + is an element of)Delta-edge coloring in O(log n) time when is an element of >= (log(3) Delta)/root Delta, or O(log(Delta) n) + (log log n)(3+o(1)) time when is an element of = Omega(1). When Delta is sublogarithmic in n the performance is improved with the Ghaffari-Harris-Kuhn LLL algorithm. Upper Bounds on Trees: We show that the Omega (log(Delta) log n) lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lovasz local lemma algorithm for tree-structured dependency graphs, which arise naturally from O(1)-round probabilistic algorithms run on trees. Specifically, our (1 + is an element of)Delta-edge coloring algorithm for trees takes O(log(1/is an element of)). max {log log n/log log log n, log(log Delta) log n} time when is an element of

关键词： distributed algorithms edge coloring LOCAL model Lovasz local lemma

来源：评论

学校读者我要写书评

暂无评论

distributed Maximization of Submodular and Approximately Submodular Functions

Distributed Maximization of Submodular and Approximately Sub...

引用

IEEE Conference on Decision and Control

作者： Lintao Ye Shreyas Sundaram School of Electrical and Computer Engineering Purdue University

ISBN: (数字)9781728174471

ISBN: (纸本)9781728174488

We study the problem of maximizing a submodular function, subject to a cardinality constraint, with a set of agents communicating over a connected graph. We propose a distributed greedy algorithm that allows all the agents to converge to a near-optimal solution to the global maximization problem using only local information and communication with neighbors in the graph. The near-optimal solution approaches the (1-1/e) approximation of the optimal solution to the global maximization problem with an additive factor that depends on the number of communication steps in the algorithm. We then analyze convergence guarantees of the proposed algorithm. This analysis reveals a tradeoff between the number of communication steps and the performance of the algorithm. Finally, we extend our analysis to nonsubmodular settings, using the notion of approximate submodularity.

关键词： Greedy algorithms Approximation algorithms Linear programming Resource management Optimization Additives distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Collision-Free distributed Multi-Target Tracking Using Teams of Mobile Robots with Localization Uncertainty

Collision-Free Distributed Multi-Target Tracking Using Teams...

引用

2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

作者： Jun Chen Philip Dames Temple University Philadelphia PA USA

ISBN: (数字)9781728162126

ISBN: (纸本)9781728162133

Accurately tracking dynamic targets relies on robots accounting for uncertainties in their own states to share information and maintain safety. The problem becomes even more challenging when there is an unknown and time-varying number of targets in the environment. In this paper we address this problem by introducing four new distributed algorithms that allow large teams of robots to: i) run the prediction and ii) update steps of a distributed recursive Bayesian multi- target tracker, iii) determine the set of local neighbors that must exchange data, and iv) exchange data in a consistent manner. All of these algorithms account for a bounded level of localization uncertainty in the robots by leveraging our recent introduction of the convex uncertainty Voronoi (CUV) diagram, which extends the traditional Voronoi diagram to account for localization uncertainty. The CUV diagram introduces a tessellation over the environment, which we use in this work both to distribute the multi-target tracker and to make control decisions about where to search next. We examine the efficacy of our method via a series of simulations and compare them to our previous work which assumed perfect localization.

关键词： Location awareness Uncertainty Target tracking distributed databases Collision avoidance distributed algorithms Robots

来源：评论

学校读者我要写书评

暂无评论

Vertex Coloring with Communication Constraints in Synchronous Broadcast Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed SYSTEMS 2019年第7期30卷 1672-1686页

作者： Lakhlef, Hicham Raynal, Michel Taiani, Francois Univ Technol Compiegne CNRS UMR 6174 Maitre Conference F-60200 Compiegne France Univ Rennes CNRS INRIA IRISA F-35000 Rennes France Polytech Univ Hong Kong Hung Hom Hong Kong Peoples R China

This paper considers distributed vertex-coloring in broadcast/receive networks suffering from conflicts and collisions. (A collision occurs when, during the same round, messages are sent to the same process by too many neighbors;a conflict occurs when a process and one of its neighbors broadcast during the same round.) More specifically, the paper focuses on multi-channel networks, in which a process may either broadcast a message to its neighbors or receive a message from at most gamma of them. The paper first provides a new upper bound on the corresponding graph coloring problem (known as frugal coloring) in general graphs, proposes an exact bound for the problem in trees, and presents a deterministic, parallel, color-optimal, collision-and conflict-free distributed coloring algorithm for trees, and proves its correctness.

关键词： distributed algorithms message-passing broadcast/receive communication synchronous systems multi-coloring vertex coloring TDMA slot allocation

来源：评论

学校读者我要写书评

暂无评论

Distributing Frank-Wolfe via map-reduce

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2019年第2期60卷 665-690页

作者： Moharrer, Armin Ioannidis, Stratis Northeastern Univ Elect & Comp Engn Dept Medford MA 02155 USA

Large-scale optimization problems abound in data mining and machine learning applications, and the computational challenges they pose are often addressed through parallelization. We identify structural properties under which a convex optimization problem can be massively parallelized via map-reduce operations using the Frank-Wolfe (FW) algorithm. The class of problems that can be tackled this way is quite broad and includes experimental design, AdaBoost, and projection to a convex hull. Implementing FW via map-reduce eases parallelization and deployment via commercial distributed computing frameworks. We demonstrate this by implementing FW over Spark, an engine for parallel data processing, and establish that parallelization through map-reduce yields significant performance improvements: We solve problems with 20 million variables using 350 cores in 79 min;the same operation takes 48 h when executed serially.

关键词： Frank-Wolfe distributed algorithms Convex optimization and spark

来源：评论

学校读者我要写书评

暂无评论

The firing squad problem revisited

引用

THEORETICAL COMPUTER SCIENCE 2019年 793卷 100-112页

作者： Charron-Bost, Bernadette Moran, Shlomo Ecole Polytech F-91128 Palaiseau France Technion Dept Comp Sci IL-32000 Haifa Israel

In the classical firing squad problem, an unknown number of nodes represented by identical finite states machines is arranged on a line and in each time unit each node may change its state according to its neighbors' states. Initially all nodes are passive, except one specific node located at an end of the line, which issues a fire command. This command needs to be propagated to all other nodes, so that eventually all nodes simultaneously enter some designated "firing" state. A natural extension of the firing squad problem, introduced in this paper, allows each node to postpone its participation in the squad for an arbitrary time, possibly forever, and firing is allowed only after all nodes decided to participate. This variant is highly relevant in the context of decentralized distributed computing, where processes have to coordinate for initiating various tasks simultaneously. The main goal of this paper is to study the above variant of the firing squad problem under the assumptions that the nodes are infinite state machines, and that the internode communication links can be changed arbitrarily in each time unit, i.e., are defined by a dynamic graph. In this setting, we study the following fundamental question: what connectivity requirements enable a solution to the firing squad problem? Our main result is an exact characterization of the dynamic graphs for which the firing squad problem can be solved. When restricted to static directed graphs, this characterization implies that the problem can be solved if and only if the graph is strongly connected. We also discuss how information on the number of nodes or on the diameter of the network, and the use of randomization, can improve the solutions to the problem. (C) 2019 Elsevier B.V. All rights reserved.

关键词： distributed algorithms Firing squad Dynamic graphs Asynchronous start Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：