Distributed collaborative complete coverage path planning based on hybrid strategy

Collaborative coverage path planning(CCPP) refers to obtaining the shortest paths passing over all places except obstacles in a certain area or space. A multi-unmanned aerial vehicle(UAV) collaborative CCPP algorithm is proposed for the urban rescue search or military search in outdoor environment.Due to flexible control of small UAVs, it can be considered that all UAVs fly at the same altitude, that is, they perform search tasks on a two-dimensional plane. Based on the agents’ motion characteristics and environmental information, a mathematical model of CCPP problem is established. The minimum time for UAVs to complete the CCPP is the objective function, and complete coverage constraint, no-fly constraint, collision avoidance constraint, and communication constraint are considered. Four motion strategies and two communication strategies are designed. Then a distributed CCPP algorithm is designed based on hybrid strategies. Simulation results compared with patternbased genetic algorithm(PBGA) and random search method show that the proposed method has stronger real-time performance and better scalability and can complete the complete CCPP task more efficiently and stably.

A Fully Distributed Approach to Optimal Energy Scheduling of Users and Generators Considering a Novel Combined Neurodynamic Algorithm in Smart Grid

A fully distributed microgrid system model is presented in this paper.In the user side,two types of load and plug-in electric vehicles are considered to schedule energy for more benefits.The charging and discharging states of the electric vehicles are represented by the zero-one variables with more flexibility.To solve the nonconvex optimization problem of the users,a novel neurodynamic algorithm which combines the neural network algorithm with the differential evolution algorithm is designed and its convergence speed is faster.A distributed algorithm with a new approach to deal with the inequality constraints is used to solve the convex optimization problem of the generators which can protect their privacy.Simulation results and comparative experiments show that the model and algorithms are effective.

2-D distributed pose estimation of multi-agent systems using bearing measurements

This article studies distributed pose(orientation and position)estimation of leader–follower multi-agent systems over𝜅-layer graphs in 2-D plane.Only the leaders have access to their orientations and positions,while the followers can measure the relative bearings or(angular and linear)velocities in their unknown local coordinate frames.For the orientation estimation,the local relative bearings are used to obtain the relative orientations among the agents,based on which a distributed orientation estimation algorithm is proposed for each follower to estimate its orientation.For the position estimation,the local relative bearings are used to obtain the position constraints among the agents,and a distributed position estimation algorithm is proposed for each follower to estimate its position by solving its position constraints.Both the orientation and position estimation errors converge to zero asymptotically.A simulation example is given to verify the theoretical results.

Distributed computations for large-scale networked systems using belief propagation

This paper introduces several related distributed algorithms,generalised from the celebrated belief propagation algorithm for statistical learning.These algorithms are suitable for a class of computational problems in largescale networked systems,ranging from average consensus,sensor fusion,distributed estimation,distributed optimisation,distributed control,and distributed learning.By expressing the underlying computational problem as a sparse linear system,each algorithm operates at each node of the network graph and computes iteratively the desired solution.The behaviours of these algorithms are discussed in terms of the network graph topology and parameters of the corresponding computational problem.A number of examples are presented to illustrate their applications.Also introduced is a message-passing algorithm for distributed convex optimisation.

Distributed Filtering Algorithm Based on Tunable Weights Under Untrustworthy Dynamics

Aiming at effective fusion of a system state estimate of sensor network under attack in an untrustworthy environment, distributed filtering algorithm based on tunable weights is proposed. Considering node location and node influence over the network topology, a distributed filtering algorithm is developed to evaluate the certainty degree firstly. Using the weight reallocation approach, the weights of the attacked nodes are assigned to other intact nodes to update the certainty degree, and then the weight composed by the certainty degree is used to optimize the consensus protocol to update the node estimates. The proposed algorithm not only improves accuracy of the distributed filtering,but also enhances consistency of the node estimates. Simulation results demonstrate the effectiveness of the proposed algorithm.

Fast Distributed Demand Response Algorithm in Smart Grid

This paper proposes a fast distributed demand response(DR)algorithm for future smart grid based on primaldual interior method and Gaussian belief propagation(Ga BP)solver.At the beginning of each time slot,each end-user/energysupplier exchanges limited rounds of messages that are not private with its neighbors,and computes the amount of energy consumption/generation locally.The proposed demand response algorithm converges rapidly to a consumption/generation decision that yields the optimal social welfare when the demands of endusers are low.When the demands are high,each end-user/energysupplier estimates its energy consumption/generation quickly such that a sub-optimal social welfare is achieved and the power system is ensured to operate within its capacity constraints.The impact of distributed computation errors on the proposed algorithm is analyzed theoretically.The simulation results show a good performance of the proposed algorithm.

An Approach of Distributed Joint Optimization for Cluster-based Wireless Sensor Networks

Wireless sensor networks(WSNs) are energyconstrained,so energy saving is one of the most important issues in typical applications.The clustered WSN topology is considered in this paper.To achieve the balance of energy consumption and utility of network resources,we explicitly model and factor the effect of power and rate.A novel joint optimization model is proposed with the protection for cluster head.By the mean of a choice of two appropriate sub-utility functions,the distributed iterative algorithm is obtained.The convergence of the proposed iterative algorithm is proved analytically.We consider general dual decomposition method to realize variable separation and distributed computation,which is practical in large-scale sensor networks.Numerical results show that the proposed joint optimal algorithm converges to the optimal power allocation and rate transmission,and validate the performance in terms of prolonging of network lifetime and improvement of throughput.

A Fully Distributed Hybrid Control Framework For Non-Differentiable Multi-Agent Optimization

This paper develops a fully distributed hybrid control framework for distributed constrained optimization problems.The individual cost functions are non-differentiable and convex.Based on hybrid dynamical systems,we present a distributed state-dependent hybrid design to improve the transient performance of distributed primal-dual first-order optimization methods.The proposed framework consists of a distributed constrained continuous-time mapping in the form of a differential inclusion and a distributed discrete-time mapping triggered by the satisfaction of local jump set.With the semistability theory of hybrid dynamical systems,the paper proves that the hybrid control algorithm converges to one optimal solution instead of oscillating among different solutions.Numerical simulations illustrate better transient performance of the proposed hybrid algorithm compared with the results of the existing continuous-time algorithms.

Distributed Alternating Direction Method of Multipliers for Multi-Objective Optimization

In this paper, a distributed algorithm is proposed to solve a kind of multi-objective optimization problem based on the alternating direction method of multipliers. Compared with the centralized algorithms, this algorithm does not need a central node. Therefore, it has the characteristics of low communication burden and high privacy. In addition, numerical experiments are provided to validate the effectiveness of the proposed algorithm.

An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem

The multi-compartment electric vehicle routing problem(EVRP)with soft time window and multiple charging types(MCEVRP-STW&MCT)is studied,in which electric multi-compartment vehicles that are environmentally friendly but need to be recharged in course of transport process,are employed.A mathematical model for this optimization problem is established with the objective of minimizing the function composed of vehicle cost,distribution cost,time window penalty cost and charging service cost.To solve the problem,an estimation of the distribution algorithm based on Lévy flight(EDA-LF)is proposed to perform a local search at each iteration to prevent the algorithm from falling into local optimum.Experimental results demonstrate that the EDA-LF algorithm can find better solutions and has stronger robustness than the basic EDA algorithm.In addition,when comparing with existing algorithms,the result shows that the EDA-LF can often get better solutions in a relatively short time when solving medium and large-scale instances.Further experiments show that using electric multi-compartment vehicles to deliver incompatible products can produce better results than using traditional fuel vehicles.

Improved Estimation of Distribution Algorithm for Solving Unrelated Parallel Machine Scheduling Problem

Scheduling problem is a well-known combinatorial optimization problem.An effective improved estimation of distribution algorithm(IEDA) was proposed for minimizing the makespan of the unrelated parallel machine scheduling problem(UPMSP).Mathematical description was given for the UPMSP.The IEDA which was combined with variable neighborhood search(IEDA_VNS) was proposed to solve the UPMSP in order to improve local search ability.A new encoding method was designed for representing the feasible solutions of the UPMSP.More knowledge of the UPMSP were taken consideration in IEDA_ VNS for probability matrix which was based the processing time matrix.The simulation results show that the proposed IEDA_VNS can solve the problem effectively.

Algorithm Design and Approximation Analysis on Distributed Robust Game

This paper designs a distributed algorithm to seek generalized Nash equilibria of a robust game with uncertain coupled constraints.Due to the uncertainty of parameters in set constraints,the authors aim to find a generalized Nash equilibrium in the worst case.However,it is challenging to obtain the exact equilibria directly because the parameters are from general convex sets,which may not have analytic expressions or are endowed with high-dimensional nonlinearities.To solve this problem,the authors first approximate parameter sets with inscribed polyhedrons,and transform the approximate problem in the worst case into an extended certain game with resource allocation constraints by robust optimization.Then the authors propose a distributed algorithm for this certain game and prove that an equilibrium obtained from the algorithm induces anε-generalized Nash equilibrium of the original game,followed by convergence analysis.Moreover,resorting to the metric spaces and the analysis on nonlinear perturbed systems,the authors estimate the approximation accuracy related toεand point out the factors influencing the accuracy ofε.

Fast and scalable routing protocols for data center networks

Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.

Joint computation offloading and resource allocation in vehicular edge computing networks

Vehicular Edge Computing(VEC)is a promising technique to accommodate the computation-intensive and delaysensitive tasks through offloading the tasks to the RoadSide-Unit(RSU)equipped with edge computing servers or neighboring vehicles.Nevertheless,the limited computation resources of edge computing servers and the mobility of vehicles make the offloading policy design very challenging.In this context,through considering the potential transmission gains brought by the mobility of vehicles,we propose an efficient computation offloading and resource allocation scheme in VEC networks with two kinds of offloading modes,i.e.,Vehicle to Vehicle(V2V)and Vehicle to RSU(V2R).We define a new cost function for vehicular users by incorporating the vehicles’offloading delay,energy consumption,and expenses with a differentiated pricing strategy,as well as the transmission gain.An optimization problem is formulated to minimize the average cost of all the task vehicles under the latency and computation capacity constraints.A distributed iterative algorithm is proposed by decoupling the problem into two subproblems for the offloading mode selection and the resource allocation.Matching theorybased and Lagrangian-based algorithms are proposed to solve the two subproblems,respectively.Simulation results show the proposed algorithm achieves low complexity and significantly improves the system performance compared with three benchmark schemes.

Microcontroller Design Based on Dynamic Heterogeneous Redundancy Architecture

Redundancy control can effectively enhance the stability and robustness of a system.Based on the conventional redundancy control switchover and majority arbitration strategy,this paper introduces the concept of heterogeneity and dynamics,constructs a dynamic heterogeneous redundancy-based microcontroller architecture DHR-MCU,and designs a fixed-leader distributed consensus algorithm that satisfies the program running state control of this architecture.The theoretical analysis and actual measurement of the prototype system prove that this architecture has good anti-attack and self-recovery capabilities under normal functions and performances and meets the general robust features in terms of safety and security.

Distributed exact Grover’s algorithm

Distributed quantum computation has gained extensive attention.In this paper,we consider a search problem that includes only one target item in the unordered database.After that,we propose a distributed exact Grover’s algorithm(DEGA),which decomposes the original search problem into■n/2■parts.Specifically,(i)our algorithm is as exact as the modified version of Grover’s algorithm by Long,which means the theoretical probability of finding the objective state is 100%;(ii)the actual depth of our circuit is 8(n mod 2)+9,which is less than the circuit depths of the original and modified Grover’s algorithms,1+8■π/4√2^(n)■and 9+8■π/4√2^(n)-1/2■,respectively.It only depends on the parity of n,and it is not deepened as n increases;(iii)we provide particular situations of the DEGA on MindQuantum(a quantum software)to demonstrate the practicality and validity of our method.Since our circuit is shallower,it will be more resistant to the depolarization channel noise.

Continuous-time Distributed Heavy-ball Algorithm for Distributed Convex Optimization over Undirected and Directed Graphs

This paper proposes second-order distributed algorithms over multi-agent networks to solve the convex optimization problem by utilizing the gradient tracking strategy, with convergence acceleration being achieved. Both the undirected and unbalanced directed graphs are considered, extending existing algorithms that primarily focus on undirected or balanced directed graphs. Our algorithms also have the advantage of abandoning the diminishing step-size strategy so that slow convergence can be avoided. Furthermore, the exact convergence to the optimal solution can be realized even under the constant step size adopted in this paper. Finally, two numerical examples are presented to show the convergence performance of our algorithms.

A High Precision Biorthogonal 9/7 Wavelet Filter Implemented in the FPGA

An efficient high precision biorthogonal 9/7 wavelet filter structure for image processing applications was proposed. This structure aimed at high precision applications. A precision improved distributed algorithms (DA) had been proposed. Comparing with traditional DA implementations, the new DA had higher precision while preserves smaller area. The proposed structure was verified in Spartan-6 field programmable gate array (FPGA) and achieved 200 MHz operation frequency. The peak signal to noise ratio (PSNR) of reconstructed image (Lena) achieves 74 dB which is very high comparing with other implementations.

Distributed dynamic stochastic approximation algorithm over time-varying networks

In this paper,a distributed stochastic approximation algorithm is proposed to track the dynamic root of a sum of time-varying regression functions over a network.Each agent updates its estimate by using the local observation,the dynamic information of the global root,and information received from its neighbors.Compared with similar works in optimization area,we allow the observation to be noise-corrupted,and the noise condition is much weaker.Furthermore,instead of the upper bound of the estimate error,we present the asymptotic convergence result of the algorithm.The consensus and convergence of the estimates are established.Finally,the algorithm is applied to a distributed target tracking problem and the numerical example is presented to demonstrate the performance of the algorithm.

Distributed Truss Computation in Dynamic Graphs

Large-scale graphs usually exhibit global sparsity with local cohesiveness,and mining the representative cohesive subgraphs is a fundamental problem in graph analysis.The k-truss is one of the most commonly studied cohesive subgraphs,in which each edge is formed in at least k 2 triangles.A critical issue in mining a k-truss lies in the computation of the trussness of each edge,which is the maximum value of k that an edge can be in a k-truss.Existing works mostly focus on truss computation in static graphs by sequential models.However,the graphs are constantly changing dynamically in the real world.We study distributed truss computation in dynamic graphs in this paper.In particular,we compute the trussness of edges based on the local nature of the k-truss in a synchronized node-centric distributed model.Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm.Moreover,the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation.Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.