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

distributed Newton Method Over Graphs: Can Sharing of Second-Order Information Eliminate the Condition Number Dependence?

引用

IEEE SIGNAL PROCESSING LETTERS 2021年 28卷 1180-1184页

作者： Berglund, Erik Magnusson, Sindri Johansson, Mikael KTH Royal Inst Technol Sch EECS Div Decis & Control Syst S-11428 Stockholm Sweden Stockholm Univ Dept Comp & Syst Sci S-11419 Stockholm Sweden

One of the main advantages of second-order methods in a centralized setting is that they are insensitive to the condition number of the objective function's Hessian. For applications such as regression analysis, this means that less pre-processing of the data is required for the algorithm to work well, as the ill-conditioning caused by highly correlated variables will not be as problematic. Similar condition number independence has not yet been established for distributed methods. In this paper, we analyze the performance of a simple distributed second-order algorithm on quadratic problems and show that its convergence depends only logarithmically on the condition number. Our empirical results indicate that the use of second-order information can yield large efficiency improvements over first-order methods, both in terms of iterations and communications, when the condition number is of the same order of magnitude as the problem dimension.

关键词： Signal processing algorithms Complexity theory Optimization Peer-to-peer computing Convergence Gradient methods Linear regression distributed algorithms optimization

来源：评论

学校读者我要写书评

暂无评论

Policy Gradient Play with Networked Agents in Markov Potential Games 5

Policy Gradient Play with Networked Agents in Markov Potenti...

引用

5th Annual Conference on Learning for Dynamics and Control

作者： Aydin, Sarper Eksin, Ceyhun Texas A&M Univ College Stn TX 77843 USA

We introduce a distributed policy gradient play algorithm with networked agents playing Markov potential games. Agents have rewards at each stage of the game, that depend on the joint actions of agents given a common dynamic state. Agents implement parameterized and differentiable policies to take actions against each other. Markov potential games assume the existence of potential value functions. In a differentiable Markov potential game, partial gradients of a potential function are equal to the local gradients with respect to the individual parameters. In this work, agents receive information on other agents' parameters via a communication network in addition to rewards. Agents then use stochastic gradients with respect to local estimates of joint policy parameters to update their policy parameters. We show that agents' joint policy converges to a first-order stationary point of Markov potential value function with any type of function approximation, state and action spaces. Numerical experiments confirm the convergence result in the lake game, a Markov potential game.

关键词： Game theory reinforcement learning distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

FAULT-TOLERANT CONSENSUS WITH NOMA IN MOBILE NETWORKS

引用

IEEE WIRELESS COMMUNICATIONS 2022年第3期29卷 80-86页

作者： Zou, Yifei Xu, Minghui Yu, Jiguo Zhao, Feng Cheng, Xiuzhen Shandong Univ Sch Comp Sci & Technol Qingdao Peoples R China Shandong Univ Comp Sci Qingdao Peoples R China Qilu Univ Technol Shandong Acad Sci Jinan Peoples R China Yulin Norma Univ Guangxi Coll & Univ Key Lab Complex Syst Optimiza Yulin Peoples R China

As a traditional research topic, consensus is one of the foundational building blocks in distributed systems and networks, by which all agents can reach an agreement in the judgments, opinions, and actions for some events. In this article, we study the fault-tolerant consensus problem in mobile networks, considering that the faults and mobility of agents are common and nearly ineluctable in mobile networks. Specifically, a distributed algorithm is proposed to achieve the fault-tolerant consensus in mobile networks with Byzantine faults. When designing our algorithm, the NOMA technique in 5G is adopted to facilitate the transmissions between agents, which makes our algorithm efficient in runtime. Both the theoretical analysis and extensive simulation are included in this article to evaluate the performance of our algorithm. By designing an algorithm such as the one in this article, we not only want to show an efficient solution for the fault-tolerant consensus problem, but also hope to shed light on how to design resilient algorithms in mobile networks.

关键词： Fault tolerance NOMA Analytical models Runtime 5G mobile communication Fault tolerant systems distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic Resilient Containment Control in Multirobot Systems

引用

IEEE TRANSACTIONS ON ROBOTICS 2022年第1期38卷 57-70页

作者： Santilli, Matteo Franceschelli, Mauro Gasparri, Andrea Roma Tre Univ Dept Engn I-00146 Rome Italy Univ Cagliari Dept Elect & Elect Engn I-09123 Cagliari Italy

In this article, we study the dynamic resilient containment control problem for continuous-time multirobot systems (MRSs), i.e., the problem of designing a local interaction protocol that drives a set of robots, namely the followers, toward a region delimited by the positions of another set of robots, namely the leaders, under the presence of adversarial robots in the network. In our setting, all robots are anonymous, i.e., they do not recognize the identity or class of other robots. We consider as adversarial all those robots that intentionally or accidentally try to disrupt the objective of the MRS, e.g., robots that are being hijacked by a cyber-physical attack or have experienced a fault. Under specific topological conditions defined by the notion of (r,s)-robustness, our control strategy is proven to be successful in driving the followers toward the target region, namely a hypercube, in finite time. It is also proven that the followers cannot escape the moving containment area despite the persistent influence of anonymous adversarial robots. Numerical results with a team of 44 robots are provided to corroborate the theoretical findings.

关键词： Robots Protocols Robot sensing systems Sensors Robustness Service robots Decentralized control Containment control distributed algorithms large-scale networks multirobot systems (MRSs) resilient protocols

来源：评论

学校读者我要写书评

暂无评论

A Second Order Primal-Dual Method for Nonsmooth Convex Composite Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第8期67卷 4061-4076页

作者： Dhingra, Neil K. Khong, Sei Zhen Jovanovic, Mihailo R. Orbit Logic Inc Boulder CO 80302 USA Univ Southern Calif Ming Hsieh Dept Elect & Comp Engn Los Angeles CA 90089 USA

We develop a second order primal-dual method for optimization problems in which the objective function is given by the sum of a strongly convex twice differentiable term and a possibly nondifferentiable convex regularizer. After introducing an auxiliary variable, we utilize the proximal operator of the nonsmooth regularizer to transform the associated augmented Lagrangian into a function that is once, but not twice, continuously differentiable. The saddle point of this function corresponds to the solution of the original optimization problem. We employ a generalization of the Hessian to define secondorder updates on this function and prove global exponential stability of the corresponding differential inclusion. Furthermore, we develop a globally convergent customized algorithm that utilizes the primal-dual augmented Lagrangian as a merit function. We show that the search direction can be computed efficiently and prove quadratic/superlinear asymptotic convergence. We use the l(1) -regularized model predictive control problem and the problem of designing a distributed controller for a spatially invariant system to demonstrate the merits and the effectiveness of our method.

关键词： Control design control system synthesis design optimization distributed algorithms gradient methods newton Method optimization optimization methods

来源：评论

学校读者我要写书评

暂无评论

distributed Broadcasting in Dynamic Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2021年第5期29卷 2142-2155页

作者： Yu, Dongxiao Zou, Yifei Yu, Jiguo Wu, Yu Lv, Weifeng Cheng, Xiuzhen Dressler, Falko Lau, Francis C. M. Shandong Univ Sch Comp Sci & Technol Inst Intelligent Comp Qingdao 266510 Peoples R China Qilu Univ Technol Sch Comp Sci & Technol Shandong Acad Sci Jinan 250014 Peoples R China Natl Supercomp Ctr Jinan Shandong Comp Sci Ctr Jinan 250014 Peoples R China Natl Super Comp Ctr Jinan Shandong Comp Sci Ctr Dongguan 523808 Peoples R China Beihang Univ Sch Comp Sci & Engn Beijing 100191 Peoples R China TU Berlin Sch Elect Engn & Comp Sci D-10587 Berlin Germany Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

In this paper, we investigate distributed broadcasting in dynamic networks, where the topology changes continually over time. We propose a network model that captures the dynamicity caused by both churn and mobility of nodes. In contrast to existing work on dynamic networks, our model defines the dynamicity in terms of localized topological changes in the vicinity of each node, rather than a global view of the whole network. Obviously, a local dynamic model suits distributed algorithms better than a global one. The proposed dynamic model uses the more realistic SINR model to depict wireless interference, instead of oversimplified graph-based models adopted in most existing work. We consider the fundamental communication primitive of global broadcast, which is to disseminate a message from a source node to the whole network. Specifically, we present a randomized distributed algorithm that can accomplish dynamic broadcasting in an asymptotically optimal running time of O(D-T) with a high probability guarantee, under the assumption of reasonably constant dynamicity rate, where D-T is the dynamic diameter, a parameter proposed to depict the complexity of dynamic broadcasting. We believe our local dynamic model can greatly facilitate distributed algorithm studies in mobile and dynamic wireless networks.

关键词： Heuristic algorithms Interference Signal to noise ratio distributed algorithms Broadcasting Network topology Computational modeling Dynamic network SINR model distributed algorithm global broadcast

来源：评论

学校读者我要写书评

暂无评论

Force-Based Algorithm for Motion Planning of Large Agent

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第1期52卷 654-665页

作者： Semnani, Samaneh Hosseini de Ruiter, Anton H. J. Liu, Hugh H. T. Isfahan Univ Technol Dept Elect & Comp Engn Esfahan *** Iran Ryerson Univ Aerosp Engn Dept Toronto ON M5B 2K3 Canada Univ Toronto Fac Appl Sci & Engn Toronto ON M3H 5T6 Canada

This article presents a distributed, efficient, scalable, and real-time motion planning algorithm for a large group of agents moving in 2-D or 3-D spaces. This algorithm enables autonomous agents to generate individual trajectories independently with only the relative position information of neighboring agents. Each agent applies a force-based control that contains two main terms: 1) collision avoidance and 2) navigational feedback. The first term keeps two agents separate with a certain distance, while the second term attracts each agent toward its goal location. Compared with existing collision-avoidance algorithms, the proposed force-based motion planning (FMP) algorithm can find collision-free motions with lower transition time, free from velocity state information of neighboring agents. It leads to less computational overhead. The performance of proposed FMP is examined over several dense and complex 2-D and 3-D benchmark simulation scenarios, with results outperforming existing methods.

关键词： Planning Heuristic algorithms Trajectory Real-time systems Navigation Computational complexity Force Collision avoidance distributed algorithms evolutionary computation flocking algorithm motion planning multiagent systems trajectory optimization

来源：评论

学校读者我要写书评

暂无评论

Engineering Massively Parallel MST algorithms 37

Engineering Massively Parallel MST Algorithms

引用

37th IEEE International Parallel and distributed Processing Symposium (IPDPS)

作者： Sanders, Peter Schimek, Matthias Karlsruhe Inst Technol Inst Theoret Informat Karlsruhe Germany

ISBN: (纸本)9798350337662

We develop and extensively evaluate highly scalable distributed-memory algorithms for computing minimum spanning trees (MSTs). At the heart of our solutions is a scalable variant of Bor degrees uvka's algorithm. For partitioned graphs with many local edges we improve this with an effective form of contracting local parts of the graph during a preprocessing step. We also adapt the filtering concept of the best practical sequential algorithm to develop a massively parallel Filter-Bor degrees uvka algorithm that is very useful for graphs with poor locality and high average degree. Our experiments indicate that our algorithms scale well up to at least 65 536 cores and are up to 800 times faster than previous distributed MST algorithms.

关键词： graph algorithms distributed algorithms minimum spanning tree MPI

来源：评论

学校读者我要写书评

暂无评论

distributed Size-constrained Clustering Algorithm for Modular Robot-based Programmable Matter

引用

ACM TRANSACTIONS ON AUTONOMOUS AND ADAPTIVE SYSTEMS 2023年第1期18卷 1-1页

作者： Bassil, Jad Makhoul, Abdallah Piranda, Benoit Bourgeois, Julien Univ Bourgogne Franche Comte CNRS FEMTO ST Inst 1 Cours Leprince Ringuet F-25200 Montbeliard France

Modular robots are defined as autonomous kinematic machines with variable morphology. They are composed of several thousands or even millions of modules that are able to coordinate to behave intelligently. Clustering the modules in modular robots has many benefits, including scalability, energy-efficiency, reducing communication delay, and improving the self-reconfiguration process that focuses on finding a sequence of reconfiguration actions to convert robots from an initial shape to a goal one. The main idea of clustering is to divide the modules in an initial shape into a number of groups based on the final goal shape to enhance the self-reconfiguration process by allowing clusters to reconfigure in parallel. In this work, we prove that the size-constrained clustering problem is NP-complete, and we propose a new tree-based size-constrained clustering algorithm called "SC-Clust." To show the efficiency of our approach, we implement and demonstrate our algorithm in simulation on networks of up to 30,000 modules and on the Blinky Blocks hardware with up to 144 modules.

关键词： Programmable matter modular robots clustering algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Placement of UAVs for Minimum Outage Probability

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2022年第9期71卷 9558-9570页

作者： Shabanighazikelayeh, Maryam Koyuncu, Erdem Univ Illinois Dept Elect & Comp Engn Chicago IL 60607 USA

We consider multiple unmanned aerial vehicles (UAVs) serving a density of ground terminals (GTs) as base stations. The objective is to minimize the outage probability of GT-to-UAV transmissions. Optimal placement of UAVs under different UAV altitude constraints and GT densities is studied. A practical variant of the Rician fading model, which has been developed by Azari et al. (2018) specifically for UAV systems, is used to model the communication channels. First, the structure of optimal deployments is determined when the common altitude constraint is large. For a wide class of GT densities, it is shown that all UAVs should be placed to the same location in an optimal deployment. A design implication is that one can use a single multi-antenna UAV as opposed to multiple single-antenna UAVs without loss of optimality. Next, using a random deployment argument, a general upper bound on the optimal outage probability is found for any density of GTs and any number of UAVs. Further, for any arbitrary user density, centralized and distributed numerical algorithms are designed using particle swarm optimization and modified gradient descent algorithms, respectively. Simulations show that our distributed algorithm provides almost optimal results even with considerably reduced communication and sensing ranges at the UAVs.

关键词： Probability Power system reliability Autonomous aerial vehicles Rician channels Numerical models distributed algorithms Base stations distributed algorithms optimal placement outage probability UAV-aided communications

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：