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

distributed Optimization for Robot Networks: From Real-Time Convex Optimization to Game-Theoretic Self-Organization

PROCEEDINGS OF THE IEEE 2020年第11期108卷 1953-1967页

作者： Jaleel, Hassan Shamma, Jeff S. Lahore Univ Management Sci LUMS Intelligent Machines & Sociotech Syst iMaSS Lab Dept Elect Engn Syed Babar Ali Sch Sci & Engn Lahore 54792 Pakistan King Abdullah Univ Sci & Technol KAUST Robot Intelligent Syst & Control RISC Lab Comp Elect & Math Sci & Engn CEMSE Div Thuwal 239556900 Saudi Arabia

Recent advances in sensing, communication, and computing technologies have enabled the use of multirobot systems for practical applications such as surveillance, area mapping, and search and rescue. For such systems, a major challenge is to design decision rules that are real-time-implementable, require local information only, and guarantee some desired global performance. distributed optimization provides a framework for designing such local decision-making rules for multirobot systems. In this article, we present a collection of selected results for distributed optimization for robot networks. We will focus on two special classes of problems: 1) real-time path planning for multirobot systems and 2) self-organization in multirobot systems using game-theoretic approaches. For multirobot path planning, we will present some recent approaches that are based on approximately solving distributed optimization problems over continuous and discrete domains of actions. The main idea underlying these approaches is that a variety of path planning problems can be formulated as convex optimization and submodular minimization problems over continuous and discrete action spaces, respectively. To generate local update rules that are efficiently implementable in real time, these approaches rely on approximate solutions to the global problems that can still guarantee some level of desired global performance. For game-theoretic self-organization, we will present a sampling of results for area coverage and real-time target assignment. In these results, the problems are formulated as games, and online updating rules are designed to enable teams of robots to achieve the collective objective in a distributed manner.

关键词： Optimization Robot kinematics Convex functions Task analysis Real-time systems Multi-robot systems Convex functions distributed algorithms multi-robot systems optimization

来源：评论

学校读者我要写书评

暂无评论

distributed Smooth Convex Optimization With Coupled Constraints

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第1期65卷 347-353页

作者： Liang, Shu Wang, Le Yi Yin, George Univ Sci & Technol Beijing Key Lab Knowledge Automat Ind Proc Minist Educ Sch Automat & Elect Engn Beijing 100083 Peoples R China Univ Sci & Technol Beijing Inst Artificial Intelligence Beijing 100083 Peoples R China Wayne State Univ Dept Elect & Comp Engn Detroit MI 48202 USA Wayne State Univ Dept Math Detroit MI 48202 USA

This note develops a distributed algorithm to solve a convex optimization problem with coupled constraints. Both coupled equality and inequality constraints are considered, where functions in the equality constraints are affine and functions in the inequality constraints are convex. Different from primal-dual subgradient methods with decreasing stepsizes for nonsmooth optimizations, our algorithm focuses on smooth problems and uses a fixed stepsize to find the exact optimal solution. Convergence analysis is derived with rigorous proofs. Our result is also illustrated by simulations.

关键词： Convex functions distributed algorithms Optimization Heuristic algorithms Convergence Linear programming Indexes Convergence analysis coupled constraints distributed optimization fixed stepsize smooth convex optimization

来源：评论

学校读者我要写书评

暂无评论

distributed algorithm for AP association with random arrivals and departures of users

引用

IET COMMUNICATIONS 2020年第5期14卷 846-856页

作者： Chen, Zhenwei Zhang, Wenjie Zheng, Yifeng Yang, Liwei Yeo, Chai Kiat Minnan Mormal Univ Sch Comp Sci Key Lab Data Sci & Intelligence Applicat Zhangzhou Peoples R China China Univ Petr Coll Geophys & Informat Engn Beijing Peoples R China China Agr Univ Coll Informat & Elect Engn Beijing Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore Singapore

Here, the authors study the novel problem of optimising access point (AP) association by maximising the network throughput, subject to the degree bound of AP. The formulated problem is a combinatorial optimisation. They resort to the Markov Chain approximation technique to design a distributed algorithm. They first approximate their optimal objective via Log-Sum-Exp function. Thereafter, they construct a special class of Markov Chain with steady-state distribution specify to their problem to yield a distributed solution. Furthermore, they extend the static problem setting to a dynamic environment where the users can randomly leave or join the system. Their proposed algorithm has provable performance, achieving an approximation gap of (1/eta)log vertical bar F vertical bar. It is simple and can be implemented in a distributed manner. Their extensive simulation results show that the proposed algorithm can converge very fast, and achieve a close-to-optimal performance with a guaranteed loss bound.

关键词： Markov processes combinatorial mathematics distributed algorithms approximation theory optimisation wireless LAN distributed algorithm AP association random arrivals user departures access point association combinatorial optimisation Markov Chain approximation technique Log-Sum-Exp function steady-state distribution static problem WLAN wireless local area networks

来源：评论

学校读者我要写书评

暂无评论

Randomized Local Network Computing: Derandomization Beyond Locally Checkable Labelings

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2021年第4期8卷 1–25页

作者： Feuilloley, Laurent Fraigniaud, Pierre Univ Chile DII Santiago Chile Univ Paris IRIF F-75205 Paris France CNRS F-75205 Paris France

We carry on investigating the line of research questioning the power of randomization for the design of distributed algorithms. In their seminal paper, Naor and Stockmeyer [STOC 1993] established that, in the context of network computing in which all nodes execute the same algorithm in parallel, any construction task that can be solved locally by a randomized Monte-Carlo algorithm can also be solved locally by a deterministic algorithm. This result, however, holds only for distributed tasks such that the correctness of their solutions can be locally checked by a deterministic algorithm. In this article, we extend the result of Naor and Stockmeyer to a wider class of tasks. Specifically, we prove that the same derandomization result holds for every task such that the correctness of their solutions can be locally checked using a 2-sided error randomized Monte-Carlo algorithm.

关键词： distributed algorithms locality derandomization

来源：评论

学校读者我要写书评

暂无评论

Asynchronous Delayed Optimization With Time-Varying Minibatches

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY

引用

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2021年第2期2卷 784-801页

作者： Al-Lawati, Haider Adikari, Tharindu B. Draper, Stark C. Univ Toronto Elect & Comp Engn Dept Toronto ON M5S 2E4 Canada

Large-scale learning and optimization problems are often solved in parallel. In a master-worker distributed setup, worker nodes are most often assigned fixed-sized minibatches of data points to process. However, workers may take different amounts of time to complete their per-batch calculations. To deal with such variability in processing times, an alternative approach has recently been proposed wherein each worker is assigned a fixed duration to complete the calculations associated with each batch. This fixed-time approach results in time-varying minibatch sizes and has been shown to outperform the fixed minibatch approach in synchronous optimization. In this paper we make a number of contributions in the analysis and experimental verification of such systems. First, we formally present a system model of an asynchronous optimization scheme with variable-sized minibatches and derive the expected minibatch size. Second, we show that for our fixed-time asynchronous approach, the expected gradient staleness does not depend on the number of workers contrary to existing schemes. Third, we prove that for convex smooth objective functions the asynchronous variable minibatch method achieves the optimal regret and optimality gap bounds. Finally, we run experiments comparing the performances of the asynchronous fixed-time and fixed-minibatch methods. We present results for CIFAR-10 and ImageNet.

关键词： Asynchronous optimization distributed algorithms delayed gradients methods convergence

来源：评论

学校读者我要写书评

暂无评论

distributed algorithm for a finite time horizon resource allocation over a directed network

引用

IET CONTROL THEORY AND APPLICATIONS 2020年第9期14卷 1170-1182页

作者： Li, Wei Lin, Zhiyun Cai, Kai Yan, Gangfeng Zhejiang Univ Coll Elect Engn Hangzhou 310007 Zhejiang Peoples R China Hangzhou Dianzi Univ Sch Automat Hangzhou 310007 Zhejiang Peoples R China Osaka City Univ Urban Res Plaza Osaka 5588585 Japan

This work investigates a finite time horizon resource allocation problem under a strongly connected multi-agent network. In this network, each agent at each time is associated with a resource variable and a quadratic cost function. The objective is to minimise the total cost of all agents over the finite time horizon in a distributed manner, while enforcing a total amount of resources per time unit and per agent. The major challenge of this problem lies in the coupled equality constraints across the agents and time periods, which should be satisfied simultaneously in the end. In addition, the local information structure imposed by the digraph within the time horizon should be taken into account when solving the problem. This study develops a consensus-based multipliers decomposition method to solve the problem. The authors show that the convergence and optimality can be ensured provided that the digraph within the time horizon is strongly connected. Numerical simulations are presented to verify the effectiveness of the proposed algorithm.

关键词： resource allocation directed graphs distributed algorithms stochastic processes distributed algorithm directed network multiagent network resource variable quadratic cost function finite-time horizon resource allocation problem numerical simulations consensus-based multiplier decomposition method

来源：评论

学校读者我要写书评

暂无评论

Secured distributed routing technique using extended DART and table elimination (ET-DART) technique in wireless sensor networks environment

引用

JOURNAL OF SUPERCOMPUTING 2020年第2期76卷 915-931页

作者： Chinnasamy, N. V. Senthilkumar, A. Sri Vijay Vidyalaya Coll Arts & Sci PG & Res Dept Comp Sci Dharmapuri Tamil Nadu India Arignar Anna Arts Coll Dept Comp Sci Namakkal Tamil Nadu India

distributed wireless sensor networks (WSNs) particularly deployed in urban applications like traffic surveillance are the main source of big data, and they produce a massive quantity of data. Multipath routing favors reliable data delivery in the case of sensitive data. However, the disadvantage is that many routes might increase the number of control packets. In this paper, we present an extended dynamic address routing technique (DART) with table elimination (ET) technique named ET-DART to reduce the complexity by handling a high degree of connectedness. The new idea of "connectedness" is used to distribute data from one node as it collected from another node. This method is used for defending capture attacks, and it modifies the security in every node without modifying the packet received ratios. A set of simulations takes place to verify the superiority of the presented ET-DART in terms of different performance metrics. Under the presence of 400 nodes, the presented ET-DART method successfully decrypts 154 packets with a maximum throughput of 82.15%. The experimental outcome verified the enhanced results of the presented method over the compared ones under several aspects.

关键词： distributed algorithms Parallel computing Urban big data WSN Multihop routing Energy Routing table Table elimination

来源：评论

学校读者我要写书评

暂无评论

distributed Penalty Dual Decomposition Algorithm for Optimal Power Flow in Radial Networks

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2020年第3期35卷 2176-2189页

作者： Zhao, Ming-Min Shi, Qingjiang Cai, Yunlong Zhao, Min-Jian Li, Yongjie Zhejiang Univ Coll Informat Sci & Elect Engn Hangzhou 310027 Peoples R China Tongji Univ Sch Software Engn Shanghai 200092 Peoples R China Shenzhen Res Inst Big Data Shenzhen Peoples R China Ningbo Univ Coll Elect Engn & Comp Sci Ningbo 315211 Peoples R China

Optimal power flow (OPF) is a fundamental problem in power system operating and planning. The need for distributed solutions is rapidly growing in distribution systems with radial networks, discrete equipments and many distributed generation units. Typically the model is difficult to solve due to the highly non-convexity and even non-continuity of the arising OPF problem. In this paper, we address these challenges by developing a penalty dual decomposition (PDD) based algorithm to obtain distributed solutions. The proposed PDD based algorithm mainly consists of two loops: in the outer loop we update the dual variables and the penalty parameter according to the constraint violation, while in the inner loop we divide the primal variables into several blocks and employ the block successive upper-bound minimization (BSUM) method to iteratively optimize each block variables with fixed penalty parameter and dual variables. Each subproblem in the proposed PDD based algorithm can be solved either in closed-form or by the bisection method and every limit point generated by the proposed algorithm is guaranteed to be a stationary point of the OPF problem. Simulation results, and comparison with centralized PDD and concave-convex procedure (CCCP) based algorithms are presented to validate the effectiveness of the proposed algorithm.

关键词： Optimization distributed algorithms Power system stability Minimization Capacitors Programming Convergence Optimal power flow distributed optimization augmented Lagrangian penalty dual decomposition non-linear systems

来源：评论

学校读者我要写书评

暂无评论

Achieving Linear Convergence in distributed Asynchronous Multiagent Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第12期65卷 5264-5279页

作者： Tian, Ye Sun, Ying Scutari, Gesualdo Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA

This article studies multiagent (convex and nonconvex) optimization over static digraphs. We propose a general distributed asynchronous algorithmic framework whereby 1) agents can update their local variables as well as communicate with their neighbors at any time, without any form of coordination;and 2) they can perform their local computations using (possibly) delayed, out-of-sync information from the other agents. Delays need not be known to the agent or obey any specific profile, and can also be time-varying (but bounded). The algorithm builds on a tracking mechanism that is robust against asynchrony (in the above sense), whose goal is to estimate locally the average of agents' gradients. When applied to strongly convex functions, we prove that it converges at an R-linear (geometric) rate as long as the step-size is sufficiently small. A sublinear convergence rate is proved, when nonconvex problems and/or diminishing, uncoordinated step-sizes are considered. To the best of our knowledge, this is the first distributed algorithm with provable geometric convergence rate in such a general asynchronous setting. Preliminary numerical results demonstrate the efficacy of the proposed algorithm and validate our theoretical findings.

关键词： Delays Convergence Optimization Convex functions distributed algorithms Robustness Indexes Asynchrony delay directed graphs distributed optimization linear convergence nonconvex optimization

来源：评论

学校读者我要写书评

暂无评论

Online distributed Optimization With Strongly Pseudoconvex-Sum Cost Functions

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第1期65卷 426-433页

作者： Lu, Kaihong Jing, Gangshan Wang, Long Xidian Univ Sch Mechanoelect Engn Ctr Complex Syst Xian 710071 Peoples R China Peking Univ Coll Engn Ctr Syst & Control Beijing 100871 Peoples R China

In this paper, the problem of online distributed optimization is investigated, where the sum of locally dynamic cost functions is considered to be strongly pseudoconvex. To address this problem, we propose an online distributed algorithm based on an auxiliary optimization strategy. The algorithm involves each agent minimizing its own cost function subject to a common convex set while exchanging local information with others under a time-varying directed communication graph sequence. The dynamic regret is employed to measure performance of the algorithm. Under mild conditions on the graph, it is shown that if the increasing rate of minimizer sequence's deviation is within a certain range, then the bound of each dynamic regret function grows sublinearly. Simulations are presented to demonstrate the effectiveness of our theoretical results.

关键词： Cost function Heuristic algorithms distributed algorithms Benchmark testing Topology Complexity theory Consensus dynamic regret multiagent systems online distributed optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：