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

Molecular pattern formation on grids in the M OBLOT model

THEORETICAL COMPUTER SCIENCE 2024年 996卷

作者： Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo Univ Aquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy Univ Perugia Dept Math & Comp Sci Via Vanvitelli 1 I-06123 Perugia Italy

In the theoretical studies on distributed algorithms for swarm robotics, the complexity and capabilities of the robots are usually reduced to their minimum. Recently, the M OBLOT model has been introduced in order to deal with robots considered silent, anonymous, and oblivious but capable to aggregate into more complex structures, called molecules. . We study the case where robots move along a graph based on a square lattice and we formally define the Molecular Pattern Formation (MPF) problem, where a specific configuration of robots assembled into molecules must be reached. As a preliminary general result, we provide a necessary condition for its solvability. Then, we actually show that dealing with molecules can resolve in some cases the symmetry breaking issue on grids where otherwise robots cannot. Finally, we introduce an interesting case study, representative of the MPF problem, in which the molecules can be formed by the set of the seven tetrominoes (aka Tetris blocks). We provide a complete characterization of this specific problem, providing a distributed algorithm able to form a molecular pattern whenever the necessary condition for the solvability of MPF is verified.

关键词： distributed algorithms Mobile robots Pattern formation Oblivious robots Grid graph

来源：评论

学校读者我要写书评

暂无评论

Sublinear algorithms in T-Interval Dynamic Networks

引用

ALGORITHMICA 2024年第9期86卷 2959-2996页

作者： Jahja, Irvan Yu, Haifeng Natl Univ Singapore Singapore Singapore

We consider standard T-interval dynamic networks, under the synchronous timing model and the broadcast CONGEST model. In a T-interval dynamic network, the set of nodes is always fixed and there are no node failures. The edges in the network are always undirected, but the set of edges in the topology may change arbitrarily from round to round, as determined by some adversary and subject to the following constraint: For every T consecutive rounds, the topologies in those rounds must contain a common connected spanning subgraph. Let H-r to be the maximum (in terms of number of edges) such subgraph for round r through r + T - 1. We define the backbone diameter d of a T-interval dynamic network to be the maximum diameter of all such H-r's, for r >= 1. We use n to denote the number of nodes in the network. Within such a context, we consider a range of fundamental distributed computing problems including COUNT/MAX/MEDIAN/SUM/LEADERELECT/CONSENSUS/CONFIRMEDFLOOD. Existing algorithms for these problems all have time complexity of Omega(n) rounds, even for T = infinity and even when d is as small as O(1). This paper presents a novel approach/framework, based on the idea of massively parallel aggregation. Following this approach, we develop a novel deterministic COUNT algorithm with O(d(3)log(2) n) complexity, for T-interval dynamic networks with T >= c center dot d(2) log(2) n. Here c is a (sufficiently large) constant independent of d, n, and T. To our knowledge, our algorithm is the very first such algorithm whose complexity does not contain a Theta(n) term. This paper further develops novel algorithms for solving MAX/MEDIAN/SUM/LEADERELECT/CONSENSUS/CONFIRMEDFLOOD, while incurring O(d(3) polylog (n)) complexity. Again, for all these problems, our algorithms are the first ones whose time complexity does not contain a Theta(n) term.

关键词： distributed algorithms T-interval dynamic networks Sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Newton Optimization With Maximized Convergence Rate

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第10期67卷 5555-5562页

作者： Marelli, Damian Edgardo Xu, Yong Fu, Minyue Huang, Zenghong Guangdong Univ Technol Sch Automat Prov Key Lab Intelligent Decis & Cooperat Control Guangzhou 510006 Peoples R China Natl Sci & Tech Res Council French Argentine Int Ctr Informat & Syst Sci RA-2000 Rosario Argentina Univ Newcastle Sch Elect Engn & Comp Callaghan NSW 2308 Australia

The distributed optimization problem is set up in a collection of nodes interconnected via a communication network. The goal is to find the minimizer of a global objective function formed by the sum of local functions known at individual nodes. A number of methods, having different advantages, are available for addressing this problem. The goal of this article is to achieve the maximum possible convergence rate. As the first step toward this end, we propose a new method, which we show converges faster than other available options. As the second step toward our goal, we complement the proposed method with a fully distributed method for estimating the optimal step size that maximizes the convergence rate. We provide theoretical guarantees for the convergence of the resulting method in a neighborhood of the solution. We present numerical experiments showing that, when using the same step size, our method converges significantly faster than its rivals. Experiments also show that the distributed step-size estimation method achieves an asymptotic convergence rate very close to the theoretical maximum.

关键词： Convergence Linear programming Optimization methods distributed algorithms Minimization Estimation Communication networks distributed algorithms local convergence Newton method step size

来源：评论

学校读者我要写书评

暂无评论

Online distributed Optimization With Nonconvex Objective Functions: Sublinearity of First-Order Optimality Condition-Based Regret

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第6期67卷 3029-3035页

作者： Lu, Kaihong Wang, Long Jiangsu Univ Sch Elect & Informat Engn Zhenjiang 212013 Jiangsu Peoples R China Peking Univ Coll Engn Ctr Syst & Control Beijing 100871 Peoples R China

In this article, the problem of online distributed optimization with a set constraint is solved by employing a network of agents. Each agent only has access to a local objective function and set constraint, and can only communicate with its neighbors via a digraph, which is not necessarily balanced. Moreover, agents do not have prior knowledge of their future objective functions. Different from existing works on online distributed optimization, we consider the scenario, where objective functions at each time step are nonconvex. To handle this challenge, we propose an online distributed algorithm based on the consensus algorithm and the mirror descent algorithm. Of particular interest is that regrets involving first-order optimality condition are used to measure the performance of the proposed algorithm. Under mild assumptions on the communication graph and objective functions, we prove that regrets grow sublinearly. Finally, a simulation example is worked out to demonstrate the effectiveness of our theoretical results.

关键词： Optimization Linear programming distributed algorithms Convex functions Mirrors Standards Mathematical model distributed nonconvex optimization multiagent systems (MASs) online optimization

来源：评论

学校读者我要写书评

暂无评论

distributed Optimization Design of Iterative Refinement Technique for Algebraic Riccati Equations

引用

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2022年第5期52卷 2833-2847页

作者： Zeng, Xianlin Chen, Jie Hong, Yiguang Beijing Inst Technol Sch Automat Key Lab Intelligent Control & Decis Complex Syst Beijing 100081 Peoples R China Tongji Univ Dept Control Sci & Engn Shanghai 200092 Peoples R China Tongji Univ Shanghai Res Inst Intelligent Autonomous Syst Shanghai 200092 Peoples R China Beijing Inst Technol Minist Educ Beijing Adv Innovat Ctr Intelligent Beijing 100081 Peoples R China

This article focuses on the problem of a distributed computation of continuous-time algebraic Riccati equations (CARE), where information of matrices is split and known by multiple agents. This article proposes a distributed optimization design of the iterative refinement technique (IRM), a well-established centralized method for CARE. By assuming that each agent only knows partial information of CARE, we reformulate IRM for CARE as three classes of distributed optimization subproblems with different formulations and constraints. Then, we propose distributed algorithms for obtained distributed optimization subproblems and prove convergence properties of proposed algorithms. Numerical results show the efficacy of the proposed distributed IRM.

关键词： Optimization Riccati equations distributed algorithms Cost function Convergence Optimal control Linear matrix inequalities Continuous-time algebraic Riccati equation (CARE) distributed algorithm distributed optimization iterative refinement method

来源：评论

学校读者我要写书评

暂无评论

Finite-Time distributed Flow Balancing

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第12期67卷 6926-6933页

作者： Hadjicostis, Christoforos N. Dominguez-Garcia, Alejandro D. Rikos, Apostolos, I Univ Cyprus Dept Elect & Comp Engn CY-1678 Nicosia Cyprus Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA KTH Royal Inst Technol Div Decis & Control Syst S-11428 Stockholm Sweden

We consider a flow network that is described by a digraph, each edge of which can admit a flow within a certain interval, with nonnegative end points that correspond to lower and upper flow limits. We propose and analyze a distributed iterative algorithm for solving, in finite time, the so-called feasible circulation problem, which consists of computing flows that are admissible (i.e., within the given intervals at each edge) and balanced (i.e., the total in-flow equals the total out-flow at each node). The algorithm assumes a communication topology that allows bidirectional message exchanges between pairs of nodes that are physically connected (i.e., nodes that share a directed edge in the physical topology) and is shown to converge to a feasible and balanced solution as long as the necessary and sufficient circulation conditions are satisfied with strict inequality. In case, the initial flows and flow limits are commensurable (i.e., they are integer multiples of a given constant), then the proposed algorithm reduces to a previously proposed finite-time balancing algorithm, for which we provide an explicit bound on the number of steps required for termination.

关键词： Balancing distributed algorithms distributed balancing feasible circulation finite-time flow networks

来源：评论

学校读者我要写书评

暂无评论

A Game-Theoretic Approach to Solving the Roman Domination Problem

引用

IEEE-CAA JOURNAL OF AUTOMATICA SINICA 2025年第5期12卷 1024-1040页

作者： Chen, Xiuyang Tang, Changbing Zhang, Zhao Chen, Guanrong Xinjiang Univ Coll Math & Syst Sci Urumqi 830000 Peoples R China Zhejiang Normal Univ Coll Phys & Elect Informat Engn Jinhua 321004 Peoples R China Zhejiang Normal Univ Coll Math Sci Jinhua 321004 Peoples R China City Univ Hong Kong Dept Elect Engn Hong Kong 999077 Peoples R China

The Roman domination problem is an important combinatorial optimization problem that is derived from an old story of defending the Roman Empire and now regains new significance in cyber space security, considering backups in the face of a dynamic network security requirement. In this paper, firstly, we propose a Roman domination game (RDG) and prove that every Nash equilibrium (NE) of the game corresponds to a strong minimal Roman dominating function (S-RDF), as well as a Pareto-optimal solution. Secondly, we show that RDG is an exact potential game, which guarantees the existence of an NE. Thirdly, we design a game-based synchronous algorithm (GSA), which can be implemented distributively and converge to an NE in O(n) rounds, where $n$ is the number of vertices. In GSA, all players make decisions depending on local information. Furthermore, we enhance GSA to be enhanced GSA (EGSA), which converges to a better NE in O(n(2)) rounds. Finally, we present numerical simulations to demonstrate that EGSA can obtain a better approximate solution in promising computation time compared with state-of-the-art algorithms.

关键词： Games Resource description framework Nash equilibrium Approximation algorithms distributed algorithms Optimization Multi-agent systems Heuristic algorithms Gallium arsenide Faces distributed algorithm game theory multi-agent system potential game Roman dominating function

来源：评论

学校读者我要写书评

暂无评论

DOT and DOP: Linearly Convergent algorithms for Finding Fixed Points of Multiagent Operators

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第6期69卷 3689-3704页

作者： Li, Xiuxian Meng, Min Xie, Lihua Tongji Univ Coll Elect & Informat Engn Dept Control Sci & Engn Shanghai 200092 Peoples R China Tongji Univ Shanghai Res Inst Intelligent Autonomous Syst Shanghai 200092 Peoples R China Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

This article investigates the distributed fixed-point finding problem for a global operator over a directed and unbalanced multiagent network, where the global operator is quasi-nonexpansive and only partially accessible to each individual agent. Two cases are addressed, i.e., the global operator is sum separable and block separable. For this first case, the global operator is the sum of local operators, which are assumed to be Lipschitz, and each local operator is privately known to each individual agent. To deal with this scenario, a distributed (or decentralized) algorithm, called distributed quasi-averaged operator tracking algorithm (DOT), is proposed and analyzed, and it is shown that the algorithm can converge to a fixed point of the global operator at a linear rate under a linear regularity condition, which is strictly weaker than the strong convexity assumption on cost functions in existing convex optimization literature. For the second scenario, the global operator is composed of a group of local block mappings which are Lipschitz and can be accessed only by each individual agent. In this setup, a distributed algorithm, called distributed quasi-averaged operator playing algorithm (DOP), is developed and shown to be linearly convergent to a fixed point of the global operator under the linear regularity condition. The above studied problems provide a unified framework for many interesting problems. As examples, the proposed DOT and DOP are exploited to cope with distributed optimization and multiplayer games under partial-decision information. Finally, numerical examples are presented to corroborate the theoretical results.

关键词： distributed algorithms Hilbert space Optimization Convergence US Department of Transportation Games Game theory distributed optimization fixed point game linear convergence linear regularity multiagent networks real Hilbert spaces

来源：评论

学校读者我要写书评

暂无评论

distributed Resilient Nash Equilibrium Seeking Under Network Attacks and Disturbances

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第6期9卷 4287-4296页

作者： Shao, Guangru Wang, Xue-Fang Ye, Maojiao Wang, Rui Yantai Univ Sch Math & Informat Sci Yantai 264005 Peoples R China Dalian Univ Technol Key Lab Intelligent Control & Optimizat Ind Equip Minist Educ Dalian 116024 Peoples R China Nanjing Univ Sci & Technol Sch Automat Nanjing 210094 Peoples R China Dalian Univ Technol Key Lab Adv Technol Aerosp Vehicles Dalian 116024 Liaoning Peoples R China Dalian Univ Technol Sch Aeronaut & Astronaut Dalian 116024 Liaoning Peoples R China

This paper investigates the Nash equilibrium (NE) seeking problem of the game in which the dynamics of all players are affected by external disturbances and the communication network among players may be influenced by persistent attacks. To solve this problem, a distributed robust switched algorithm is proposed. This distributed switched strategy consists of two modules: One is the internal-model based dynamics that can be used to compensate the effects caused by external disturbances;the other is gradient-based optimization module which can utilize the local information to estimate the players' decisions and dynamically seek the optimal solution. By utilizing average dwell-time and time-ratio constraints to characterize the network attacks, the proposed switched strategy is modeled into a hybrid dynamical system. Moreover, employing the hybrid systems approach, we prove that the decisions of all players can exponentially converge to the NE of the considered game. Finally, an example is provided to illustrate the theoretical results.

关键词： Heuristic algorithms Games Vehicle dynamics Topology Eigenvalues and eigenfunctions distributed algorithms Cost function Nash equilibrium Disturbance rejection distributed robust switched algorithm hybrid systems Nash equilibrium (NE) seeking network attacks

来源：评论

学校读者我要写书评

暂无评论

Communication-Efficient distributed Cooperative Learning With Compressed Beliefs

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2022年第3期9卷 1215-1226页

作者： Toghani, Mohammad Taha Uribe, Cesar A. Rice Univ Dept Elect & Comp Engn Houston TX 77005 USA

In this article, we study the problem of distributed cooperative learning, where a group of agents seeks to agree on a set of hypotheses that best describes a sequence of private observations. In the scenario where the set of hypotheses is large, we propose a belief up-date rule where agents share compressed (either sparse or quantized) beliefs with an arbitrary positive compression rate. Our algorithm leverages a unified communication rule that enables agents to access wide-ranging compression operators as black-box modules. We prove the almost sure asymptotic convergence of beliefs on the set of optimal hypotheses. Additionally, we show a nonasymptotic, explicit, and linear concentration rate in probability of the beliefs on the optimal hypothesis set. We provide numerical experiments to illustrate the communication benefits of our method. The simulation results show that the number of transmitted bits can be reduced to 5%-10% of the noncompressed method in the studied scenarios.

关键词： Algorithm design and analysis Bayesian update compressed communication distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：