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

THE COMMUNICATION COMPLEXITY FOR decentralized EVALUATION OF FUNCTIONS

INFORMATION PROCESSING LETTERS 1990年第4期35卷 177-182页

作者： YUAN, SM Adv. Technol. Cent. Electron. Res. Serv. Org. Ind. Technol. Res. Inst. Taiwan

decentralized algorithms can be characterized by successive rounds of message interchanges. In each round, all nodes exchange information and carry out computations. The computations at each node are based on the information available at that node after the communication phase. Thus, the complexity of the communication requirement is a major determining factor of the performance of a decentralized algorithm. The total number of messages passed among all processing nodes, called message complexity, and the total number of bits used for all messages exchanged, called bit complexity, are measures for describing the communication complexity. The lower bound of message complexity for decentralized evaluation of functions is established. For evaluating fully reducible functions, the message complexity is as good as the bit complexity. However, for evaluating irreducible or partially reducible functions, the message complexity no longer is a good performance indicator because it does not consider the effect of variant message sizes. The bit complexity becomes a better choice for evaluating such functions.

关键词： decentralized algorithms message complexity bit complexity

来源：评论

学校读者我要写书评

暂无评论

decentralized spectrum and radio resource management enabled by an on-demand Cognitive Pilot Channel

引用

ANNALS OF TELECOMMUNICATIONS 2008年第5-6期63卷 281-294页

作者： Sallent, O. Agusti, R. Perez-Romero, J. Giupponi, L. Univ Politecn Cataluna Dept Signal Theory & Commun ES-08034 Barcelona Spain

This paper presents a framework to achieve an efficient dynamic and decentralized spectrum and radio resource usage in heterogeneous wireless network scenarios. The envisaged technical solution follows a layered approach, where joint radio resource management (JRRM) and advanced spectrum management mechanisms are identified at both the intra- and inter-operator levels. The importance of cognitive network functionalities is highlighted. An on-demand Cognitive Pilot Channel (CPC) is proposed as radio enabler solution for decentralized operation with decision making processes executed at the mobile terminal side. The suitability of the proposed solution is shown by comparison with a broadcast CPC approach. Finally, the paper presents and evaluates decentralized JRRM algorithms both at the intra- and inter-operator levels using the proposed framework.

关键词： advanced spectrum management joint radio resource management decentralized algorithms Cognitive Pilot Channel cognitive networks

来源：评论

学校读者我要写书评

暂无评论

Prioritized Planning algorithms for Trajectory Coordination of Multiple Mobile Robots

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2015年第3期12卷 835-849页

作者： Cap, Michal Novak, Peter Kleiner, Alexander Selecky, Martin Czech Tech Univ Dept Comp Sci Prague 12135 Czech Republic Delft Univ Technol Dept Software & Comp Technol NL-2628 CC Delft Netherlands iRobot Pasadena CA 91125 USA

In autonomous multirobot systems one of the concerns is how to prevent collisions between the individual robots. One approach to this problem involves finding coordinated trajectories from start to destination for all the robots and then letting the robots follow the preplanned coordinated trajectories. A widely used practical method for finding such coordinated trajectories is "classical" prioritized planning, where robots plan sequentially one after another. This method has been shown to be effective in practice, but it is incomplete (i.e., there are solvable problem instances that the algorithm fails to solve) and it has not yet been formally analyzed under what circumstances is the method guaranteed to succeed. Further, prioritized planning is a centralized algorithm, which makes the method unsuitable for decentralized multirobot systems. The contributions of this paper are: a) an adapted version of classical prioritized planning called revised prioritized planning with a formal characterization of a class of instances that are provably solvable by this algorithm and b) an asynchronous decentralized variant of both classical and revised prioritized planning together with a formal analysis showing that the algorithm terminates and inherits completeness properties from its centralized counterpart. The experimental evaluation performed in simulation on real-world indoor maps shows that: a) the revised version of prioritized planning reliably solves a wide class of instances on which both classical prioritized planning and popular reactive technique ORCA fail and b) the asynchronous decentralized implementation of classical and revised prioritized planning finds solution in large multirobot teams up to 2x-faster than the previously proposed synchronized decentralized approach. Note to Practitioners-Consider a large warehouse in which the goods are stored and retrieved by autonomous mobile robots. One way to deal with possible collisions between the robots is to igno

关键词： Collision avoidance decentralized algorithms multirobot systems trajectory planning

来源：评论

学校读者我要写书评

暂无评论

Integrated Online Learning and Adaptive Control in Queueing Systems with Uncertain Payoffs

引用

OPERATIONS RESEARCH 2022年第2期70卷 1166-1181页

作者： Hsu, Wei-Kang Xu, Jiaming Lin, Xiaojun Bell, Mark R. Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA Duke Univ Fuqua Sch Business Durham NC 27708 USA

We study task assignment in online service platforms, where unlabeled clients arrive according to a stochastic process and each client brings a random number of tasks. As tasks are assigned to servers, they produce client/server-dependent random payoffs. The goal of the system operator is to maximize the expected payoff per unit time subject to the servers' capacity constraints. However, both the statistics of the dynamic client population and the client-specific payoff vectors are unknown to the operator. Thus, the operator must design task-assignment policies that integrate adaptive control (of the queueing system) with online learning (of the clients' payoff vectors). A key challenge in such integration is how to account for the nontrivial closed-loop interactions between the queueing process and the learning process, which may significantly degrade system performance. We propose a new utility-guided online learning and task assignment algorithm that seamlessly integrates learning with control to address such difficulty. Our analysis shows that, compared with an oracle that knows all client dynamics and payoff vectors beforehand, the gap of the expected payoff per unit time of our proposed algorithm can be analytically bounded by three terms, which separately capture the impact of the client-dynamic uncertainty, client-server payoff uncertainty, and the loss incurred by backlogged clients in the system. Further, our bound holds for any finite time horizon. Through simulations, we show that our proposed algorithm significantly outperforms a myopic-matching policy and a standard queue-length-based policy that does not explicitly address the closed-loop interactions between queueing and learning.

关键词： online learning online service platforms convex optimization decentralized algorithms

来源：评论

学校读者我要写书评

暂无评论

An Enhanced SD-GS-AL Algorithm for Coordinating the Optimal Power and Traffic Flows With EVs

引用

IEEE TRANSACTIONS ON SMART GRID 2024年第4期15卷 3904-3918页

作者： Sharma, Santosh Li, Qifeng Wei, Wei Univ Cent Florida Dept Elect Engn Orlando FL 32826 USA Tsinghua Univ Dept Elect Engn State Key Lab Power Syst Beijing 100084 Peoples R China

The electric power distribution network (PDN) and the transportation network (TN) are generally operated/coordinated by different entities. However, they are coupled through electric vehicle charging stations (EVCSs). This paper proposes to coordinate the operation of the two systems via a fully decentralized framework where the PDN and TN operators solve their own operation problems independently, with only limited information exchange. Nevertheless, the operation problems of both systems are generally mixed-integer programs (MIP), for which mature algorithms like the alternating direction method of multipliers (ADMM) may not guarantee convergence. This paper applies a novel distributed optimization algorithm called the SD-GS-AL method, which is a combination of the simplicial decomposition, gauss-seidel, and augmented Lagrangian, which can guarantee convergence and optimality for MIPs. However, the original SD-GS-AL may be computationally inefficient for solving a complex engineering problem like the PDN-TN coordinated optimization investigated in this paper. To improve the computational efficiency, an enhanced SD-GS-AL method is proposed by redesigning the inner loop of the algorithm, which can automatically and intelligently determine the iteration number of the inner loop. Simulations on the test cases show the efficiency and efficacy of the proposed framework and algorithm.

关键词： decentralized algorithms mixed-integer programs optimal power-traffic flow

来源：评论

学校读者我要写书评

暂无评论

decentralized RESOURCE ALLOCATION IN DYNAMIC NETWORKS OF AGENTS

引用

SIAM JOURNAL ON OPTIMIZATION 2008年第2期19卷 911-940页

作者： Lakshmanan, Hariharan De Farias, Daniela Pucci MIT Dept Civil & Environm Engn Cambridge MA 02139 USA MIT Dept Mech Engn Cambridge MA 02139 USA

We consider the problem of n agents that share m common resources. The objective is to derive an optimal allocation that maximizes a global objective expressed as a separable concave objective function. We propose a decentralized, asynchronous gradient-descent method that is suitable for implementation in the case where the communication between agents is described in terms of a dynamic network. This communication model accommodates situations such as mobile agents and communication failures. The method is shown to converge provided that the objective function has Lipschitz-continuous gradients. We further consider a randomized version of the same algorithm for the case where the objective function is nondifferentiable but has bounded subgradients. We show that both algorithms converge to near-optimal solutions and derive convergence rates in terms of the magnitude of the gradient of the objective function. We show how to accommodate nonnegativity constraints on the resources using the results derived. Experimental results with the problems of varying dimensions suggest that the algorithms are competitive with centralized approaches and scale well with problem size.

关键词： decentralized algorithms resource allocation nondifferentiable optimization

来源：评论

学校读者我要写书评

暂无评论

Selfish decentralized Computation Offloading for Mobile Cloud Computing in Dense Wireless Networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2019年第1期18卷 207-220页

作者： Josilo, Sladana Dan, Gyorgy KTH Royal Inst Technol Sch Elect Engn & Comp Sci Stockholm Sweden

Offloading computation to a mobile cloud is a promising solution to augment the computation capabilities of mobile devices. In this paper, we consider selfish mobile devices in a dense wireless network, in which individual mobile devices can offload computations through multiple access points or through the base station to a mobile cloud so as to minimize their computation costs. We provide a game theoretical analysis of the problem, prove the existence of pure strategy Nash equilibria, and provide an efficient decentralized algorithm for computing an equilibrium. For the case when the cloud computing resources scale with the number of mobile devices, we show that all improvement paths are finite. Furthermore, we provide an upper bound on the price of anarchy of the game, which serves as an upper bound on the approximation ratio of the proposed decentralized algorithms. We use simulations to evaluate the time complexity of computing Nash equilibria and to provide insights into the price of anarchy of the game under realistic scenarios. Our results show that the equilibrium cost may be close to optimal, and the convergence time is almost linear in the number of mobile devices.

关键词： Computation offloading mobile edge computing Nash equilibria decentralized algorithms

来源：评论

学校读者我要写书评

暂无评论

Learning-Based UAV Trajectory Optimization With Collision Avoidance and Connectivity Constraints

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2022年第6期21卷 4350-4363页

作者： Wang, Xueyuan Gursoy, M. Cenk Syracuse Univ Dept Elect Engn & Comp Sci Syracuse NY 13244 USA

Unmanned aerial vehicles (UAVs) are expected to be an integral part of wireless networks, and determining collision-free trajectories for multiple UAVs while satisfying requirements of connectivity with ground base stations (GBSs) is a challenging task. In this paper, we consider non-cooperative multi-UAV scenarios, in which multiple UAVs need to fly from initial locations to destinations, while satisfying collision avoidance, wireless connectivity, and kinematic constraints. We aim to find trajectories for the UAVs with the goal to minimize their mission completion time. We first formulate the multi-UAV trajectory optimization problem as a sequential decision making problem. We, then, propose a decentralized deep reinforcement learning approach to solve the problem. More specifically, a value network is developed to obtain values given the agent's joint state (including the agent's information, the nearby agents' observable information, and the locations of the nearby GBSs). A signal-to-interference-plus-noise ratio (SINR)-prediction neural network is also designed, using accumulated SINR measurements obtained when interacting with the cellular network, to map the GBSs' locations into the SINR levels in order to predict the UAV's SINR. Numerical results show that with the value network and SINR-prediction network, real-time navigation for multi-UAVs can be efficiently performed in various environments with high success rate.

关键词： Reinforcement learning Collision avoidance Wireless communication Autonomous aerial vehicles Trajectory optimization Cellular networks Antennas Collision avoidance decentralized algorithms deep reinforcement learning multi-UAV trajectory design wireless connectivity

来源：评论

学校读者我要写书评

暂无评论

A Graph-Assisted Framework for Multiple Graph Learning

引用

IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS 2024年 10卷 162-178页

作者： Zhang, Xiang Wang, Qiao Southeast Univ Sch Informat Sci & Engn Nanjing 210096 Peoples R China

In this paper, we endeavor to jointly learn multiple distinct but related graphs by exploiting the underlying topological relationships between them. The difficulty lies in how to design a regularizer that accurately describes the intricate topological relationships, especially without prior knowledge. This problem becomes more challenging for the scenarios where data for different graphs are stored separately and prohibited from being transmitted to an unreliable central server due to privacy concerns. To address these issues, we propose a novel regularizer termed pattern graph to flexibly describe our priors on topological patterns. Theoretically, we provide the estimation error upper bound of the proposed graph estimator, which characterizes the impact of some factors on estimation errors. Furthermore, an approach that can automatically discover relationships among graphs is proposed to handle awkward situations without priors. On the algorithmic aspect, we develop a decentralized algorithm that updates each graph locally without sending the private data to a central server. Finally, extensive experiments on both synthetic and real data are carried out to validate the proposed method, and the results demonstrate that our framework outperforms the state-of-the-art methods.

关键词： Task analysis Laplace equations Covariance matrices Servers Data privacy Topology Signal processing algorithms Graph learning decentralized algorithms graph Laplacian topological patterns multiple graph learning

来源：评论

学校读者我要写书评

暂无评论

A New Approach to Laplacian Solvers and Flow Problems

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2019年第1期20卷 1311-1347页

作者： Rebeschini, Patrick Tatikonda, Sekhar Univ Oxford Dept Stat Oxford OX1 3LB England Yale Univ Dept Stat & Data Sci New Haven CT 06511 USA

This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. Voltage and flow problems involve the minimization of quadratic functions and are fundamental primitives that arise in several domains. algorithms that have been proposed are typically centralized and involve multiple graph-theoretic constructions or sampling mechanisms that make them difficult to implement and analyze. On the other hand, message passing routines are distributed, simple, and easy to implement. In this paper we establish a framework to analyze Min-Sum to solve voltage and flow problems. We characterize the error committed by the algorithm on general weighted graphs in terms of hitting times of random walks defined on the computation trees that support the operations of the algorithms with time. For d-regular graphs with equal weights, we show that the convergence of the algorithms is controlled by the total variation distance between the distributions of non-backtracking random walks defined on the original graph that start from neighboring nodes. The framework that we introduce extends the analysis of MinSum to settings where the contraction arguments previously considered in the literature (based on the assumption of walk summability or scaled diagonal dominance) can not be used, possibly in the presence of constraints.

关键词： Min-Sum message passing decentralized algorithms Laplacian solver network flows

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：