This article addresses the problem of seeking a common fixed point for a finite collection of nonexpansive operators over time-varying multi-agent networks in real Hilbert spaces. Each operator is assumed to be only p...
详细信息
This article addresses the problem of seeking a common fixed point for a finite collection of nonexpansive operators over time-varying multi-agent networks in real Hilbert spaces. Each operator is assumed to be only privately and approximately known to each individual agent, and all agents need to cooperate to solve this problem by local communications over time-varying networks. To handle this problem, inspired by the centralized inexact Krasnoselski.i-Mann iteration, we propose a distributed algorithm, called distributed inexact averaged operator algorithm (DIO). It is shown that the DIO can converge weakly to a common fixed point of the family of nonexpansive operators. Moreover, under the assumption that all operators and their own fixed point sets are (boundedly) linearly regular, it is proved that the distributed averaged operator algorithm converges with a rate O(gamma l(og16(4k))) for some constant gamma is an element of (0, 1), where k is the iteration number. To reduce computational complexity, a scenario, where only a random part of coordinates of each operator is computed at each iteration, is further considered. In this case, a corresponding algorithm, named distributed block-coordinate inexact averaged operator algorithm, is developed. The algorithm is proved to be weakly convergent to a common fixed point of the group of considered operators almost surely, and, with the extra assumption of (bounded) linear regularity, the distributed block-coordinate averaged operator algorithm is convergent in the mean square sense with a rate O(gamma(log4(4k))) for some constant eta is an element of (0, 1). Furthermore, it is shown that the same convergence rates can still be guaranteed under a more relaxed (bounded) power regularity condition. A couple of examples are finally presented to illustrate the effectiveness of the proposed algorithms.
This article proposes three distributed algorithms for solving linear algebraic equations to seek a least-squares (LS) solution via multiagent networks. We consider that each agent has only access to a small and incom...
详细信息
This article proposes three distributed algorithms for solving linear algebraic equations to seek a least-squares (LS) solution via multiagent networks. We consider that each agent has only access to a small and incomplete block of linear equations rather than the complete row or column in the existing results. First, we focus on the case of a homogeneous partition of linear equations. A distributed algorithm is proposed via a single-layered grid network, in which each agent only needs to control three scalar states. Second, we consider the case of heterogeneous partitions of linear equations. Two distributed algorithms with a doubled-layered network are developed, which allow each agent's states to have different dimensions and can be applied to heterogeneous agents with different storage and computation capabilities. Rigorous proofs show that the proposed distributed algorithms collaboratively obtain an LS solution with exponential convergence and also own a solvability verification property, i.e., a criterion to verify whether the obtained solution is an exact solution. Finally, some simulation examples are provided to demonstrate the effectiveness of the proposed algorithms.
A k-core C-k of a tree T is subtree with exactly k leaves for k less than or equal to n(l), where n(l) the number of leaves in T, and minimizes the sum of the distances of all nodes from C-k. In this paper first we pr...
详细信息
A k-core C-k of a tree T is subtree with exactly k leaves for k less than or equal to n(l), where n(l) the number of leaves in T, and minimizes the sum of the distances of all nodes from C-k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices. (C) 2003 Elsevier B.V. All rights reserved.
In this paper, we propose a cooperative distributed framework to optimize a variety of rate and energy-efficiency (EE) utility functions, such as the minimum-weighted rate or the global EE, for the K-user interference...
详细信息
In this paper, we propose a cooperative distributed framework to optimize a variety of rate and energy-efficiency (EE) utility functions, such as the minimum-weighted rate or the global EE, for the K-user interference channel. We focus on the single-input multiple-output (SIMO) case, where each user, based solely on local channel state information (CSI) and limited exchange information from other users, optimizes its transmit power and receive beamformer, although the framework can also be extended to the multiple-output multiple-input (MIMO) case. The distributed framework combines an alternating optimization approach with majorization-minimization (MM) techniques, thus ensuring convergence to a stationary point of the centralized cost function. Closed-form power update rules are obtained for some utility functions, thus obtaining very fast convergence algorithms. The receivers treat interference as noise (TIN) and apply the beamformers that maximize the signal-to-interference-plus-noise (SINR). The proposed cooperative distributed algorithms are robust against channel variations and network topology changes and, as our simulation results suggest, they perform close to the centralized solution that requires global CSI. As a benchmark, we also study a non-cooperative distributed framework based on the so-called "signal-to-leakage-plus-noise ratio" (SNLR) that further reduces the overhead of the cooperative version.
This paper presents analysis and design results for distributed consensus algorithms in multi-agent networks. We consider continuous consensus functions of the initial state of the network agents. Under mild smoothnes...
详细信息
This paper presents analysis and design results for distributed consensus algorithms in multi-agent networks. We consider continuous consensus functions of the initial state of the network agents. Under mild smoothness assumptions, we obtain necessary and sufficient conditions characterizing any algorithm that asymptotically achieves consensus. This characterization is the building block to obtain various design results for networks with weighted, directed interconnection topologies. We first identify a class of smooth functions for which one can synthesize in a systematic way distributed algorithms that achieve consensus. We apply this result to the family of weighted power mean functions, and characterize the exponential convergence properties of the resulting algorithms. We establish the validity of these results for scenarios with switching interconnection topologies. Finally, we conclude with two discontinuous distributed algorithms that achieve, respectively, max and min consensus in finite time. (C) 2007 Elsevier Ltd. All rights reserved.
We present distributed algorithms for multirobot task assignment where the tasks have to be completed within given deadlines. Each robot has a limited battery life and thus there is an upper limit on the amount of tim...
详细信息
We present distributed algorithms for multirobot task assignment where the tasks have to be completed within given deadlines. Each robot has a limited battery life and thus there is an upper limit on the amount of time that it has to perform tasks. Performing each task requires certain amount of time (called the task duration) and each robot can have different payoffs for the tasks. Our problem is to assign the tasks to the robots such that the total payoff is maximized while respecting the task deadline constraints and the robot's battery life constraints. Our problem is NP-hard since a special case of our problem is the classical generalized assignment problem (which is NP-hard). There are no known algorithms (distributed or centralized) for this problem with provably good guarantees of performance. We present a distributed algorithm for solving this problem and prove that our algorithm has an approximation ratio of 2. For the special case of constant task duration we present a distributed algorithm that is provably almost optimal. Our distributed algorithms are polynomial in the number of robots and the number of tasks. We also present simulation results to depict the performance of our algorithms. Note to Practitioners-In this paper, we present provably good multirobot task assignment algorithms, while considering practical constraints like task deadlines and limited battery life of robots. Such constraints are relevant in many applications including parts movement by robots in manufacturing, delivery of goods by unmanned vehicles, and search and rescue operations. Our solution is applicable to a group of heterogeneous robots with different suitability (i.e., payoffs) for different tasks. Our distributed approach is independent of the underlying robot communication network topology, and thus can be applied to a wide range of robot network deployments. Finally, our approach is easy to implement, has low communication requirements, and it is scalable, since its ru
We study distributed composite optimization over networks: agents minimize a sum of smooth (strongly) convex functions-the agents' sum-utility-plus a nonsmooth (extended-valued) convex one. We propose a general un...
详细信息
We study distributed composite optimization over networks: agents minimize a sum of smooth (strongly) convex functions-the agents' sum-utility-plus a nonsmooth (extended-valued) convex one. We propose a general unified algorithmic framework for such a class of problems and provide a convergence analysis leveraging the theory of operator splitting. Distinguishing features of our scheme are: (i) When each of the agent's functions is strongly convex, the algorithm converges at a linear rate, whose dependence on the agents' functions and network topology is decoupled;(ii) When the objective function is convex (but not strongly convex), similar decoupling as in (i) is established for the coefficient of the proved sublinear rate. This also reveals the role of function heterogeneity on the convergence rate. (iii) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity;and (iv) A by-product of our analysis is a tuning recommendation for several existing (non-accelerated) distributed algorithms yielding provably faster (worst-case) convergence rate for the class of problems under consideration.
Novel network infrastructures require the distribution of computing and network resource control to meet stringent requirements in terms of latency, reliability and bitrate. 5G systems bring a key novelty in systems d...
详细信息
Novel network infrastructures require the distribution of computing and network resource control to meet stringent requirements in terms of latency, reliability and bitrate. 5G systems bring a key novelty in systems design that it the 'network slice'as a new resource provisioning entity. A network slice is meant to serve end-to-end services as a composition of different network and system resources as radio, link, storage and computing resources. Conventionally, each resource is managed by a distinct decision-maker, platform, provider, orchestrator or controller. Naturally, centralized slice orchestration approaches are proposed in the literature, where a multi-domain orchestrator allocates the resources, for instance using a multi-resource allocation rule. Nonetheless, while simplifying the algorithmic approach, centralization can come at the expense of scalability and performance. In this article, we propose new ways to distribute the slice multi-resource resource allocation problem, using cascade and parallel resource allocations that are functionally compatible with novel software platforms. We also show how to adapt the proposed algorithms to make them able to guarantee service level agreements on the minimum resource needed, and to take into account deadline priority policy scheduling. We provide an exhaustive analysis of the advantages and disadvantages of the different approaches, including a numerical analysis for a realistic setting.
Let N = (V, A, C, L) be a network with node set V, arc set A, positive arc capacity function C, and nonnegative arc lead time function L. The quickest path problem is to find paths in N to transmit a given amount of d...
详细信息
Let N = (V, A, C, L) be a network with node set V, arc set A, positive arc capacity function C, and nonnegative arc lead time function L. The quickest path problem is to find paths in N to transmit a given amount of data such that the transmission time is minimized. In this paper, distributed algorithms are developed for the quickest path problem in an asynchronous communication network. For the one-source quickest path problem, we present three algorithms that require O(rn2) messages and O(rn2) time, O(rmn) messages and O(rn) time, and O(rm(1+epsilon)log w) messages and O(rn(1+epsilon)log w) time for any epsilon, 0 < epsilon < 1, respectively, where m = \A\, n = \V\, r is the number of distinct capacity values of N, and w is the maximal arc weight of N. For the all-pairs quickest path problem, we present an algorithm that requires O(mn) messages and O(m) time.
This letter develops two distributed algorithms to solve multi-robot task assignment problems (MTAP). We first describe MTAP as an integer linear programming (ILP) problem and then reformulate it as a relaxed convex o...
详细信息
This letter develops two distributed algorithms to solve multi-robot task assignment problems (MTAP). We first describe MTAP as an integer linear programming (ILP) problem and then reformulate it as a relaxed convex optimization problem. Based on the saddle-point dynamics, we propose two distributed optimization algorithms using optimistic gradient decent ascent (OGDA) and extra-gradient (EG) methods, which achieve exact convergence to an optimal solution of the relaxed problem. In most cases, such an solution reflects the optimality of the original ILP problems. For some special ILP problems, we provide a perturbation-based distributed method to avoid the inconsistency phenomenon, such that an optimal solution to any ILP problem is obtained. Compared with some decentralized algorithms requiring a central robot that communicates with the other robots, our developed algorithms are fully distributed, in which each robot only communicates with the nearest neighbors for an arbitrary connected graph. We evaluate the developed algorithms in terms of computation, communication, and data storage complexities, and compare them with some typical algorithms. It is shown that the developed algorithms have low computational and communication complexities. We also verify the effectiveness of our algorithms via numerical examples.
暂无评论