1 Instructions
Final Project Spring 2022
1.1 ExpectationsandGrading……………………………… 2 1.2 Deadlines ……………………………………… 2
2 Background 3
Copyright By PowCoder代写 加微信 powcoder
2.1 Distributedaveraging ……………………………….. 3
2.2 Networks ……………………………………… 3
2.3 Model……………………………………….. 4
2.3.1 Discretetime………………………………… 4
2.3.2 Continuoustime ………………………………. 5
2.4 Disagreement……………………………………. 5
3 Part A: Interaction Networks 6
3.1 Staticnetworks…………………………………… 6
3.2 Randomnetworks …………………………………. 6
4 Part B: Averaging Algorithms 7
4.1 Averagingoverstaticnetworks …………………………… 7 4.1.1 Discreteandcontinuoustimemodels…………………….. 7 4.1.2 Equilibria………………………………….. 7 4.1.3 Eigenvaluesandstability ………………………….. 7 4.1.4 Simulations…………………………………. 7
4.2 Averagingoverswitchingnetworks …………………………. 8
1 Instructions
This document contains the information you will need to complete the final project for CMDA 3605. Read the instructions so you know specific deadlines and expectations for the project. This is an individual project; no collaboration with classmates is permitted.
This document is subject to minor changes. Any changes will be clearly communicated with Canvas announcements, and you will be responsible for using the most recent version of the document. At the time of releasing this document, you will not yet know all the concepts needed to complete the project. There will be concepts that go beyond lecture material. Necessary background to understand these concepts is found in the background section. You are responsible for reading this section and asking any questions to understand these components.
Section 1 contains details on the project and guidelines on grading. Section 2 gives background that will be helpful in completing the project. Section 3 is an initial exploration of the network models. Section 4 requires in depth analysis and simulation of various forms of the models.
1.1 Expectations and Grading
You will submit each part of your project in Canvas by the date and time listed below. For each submission, there will be two components:
1. A single pdf consisting of a coherent report including responses to all problems. The pdf file should be named
LastName FirstName PartX.pdf where X is replaced with the project part: A or B.
2. A single zip file with all your Matlab code. The zip file should be named
LastName FirstName PartX.zip
where X is replaced with the project part: A or B. All plots in the project pdf should easily
reproducible from submitted code, including commenting in the code on how to produce them.
You must do the following, or risk losing at least 20% of the project grade:
• Submit a typed pdf. You are required to type your term project and may use your favorite editing software (e.g. Word, Google docs, latex).
• Submit with your name on the first page.
• Submit a coherent report, not simply a list of solutions to proposed problems. Projects must offer
a coherent discussion (i.e. describe results not just state them).
• Submit on time. Submissions should be in Canvas by the time and date listed.
• Submit complete figures. All figures must have legends, appropriately labeled axes and detailed captions.
Note: you may use other resources (for example, textbooks, websites, journal articles) excluding conver- sation with other students, but you must cite the appropriate source.
If you are unclear what any of the above criteria mean, come talk with me.
1.2 Deadlines
• Part A: Interaction Networks is due Friday, April 15, 2022 by 11:59 pm.
• Part B: Averaging Algorithms is due Wednesday, May 4, 2022 by 11:59 pm.
2 Background
Consensus, or agreement, is a well-studied phenomenon in systems made up of multiple individuals. For example, flocking birds must agree on a common heading direction to achieve collective motion for migration. In engineered systems, sensor networks must consolidate their measurements to build a consistent data set. In this project, we will study systems that attempt to reach consensus, which can be thought of as abstract models for any of these varied applications in the physical world.
2.1 Distributed averaging
We can write mathematical models that generate consensus, and which capture the qualitative behavior of the systems described above. The type of consensus algorithms we’ll study for this project is distributed averaging algorithms. In distributed averaging algorithms, individual systems (think: functions with scalar-valued states that can change over time) average their states with other individual systems to try to reach an agreement. The parameters that determine the outcome of the algorithm are:
• The initial states of all the individual systems
• The “neighbors” that individuals choose to average their states with, which is a process we call
interacting
• How each individual weights its “neighbors” in the averaging process
This project will explore the impact that the network of interactions linking individual
systems has on the group’s ability to reach consensus.
2.2 Networks
Networks are mathematical objects that represent relationships between sets of individuals in a conve- nient format. Individuals can be written as nodes which are connected to each other via edges. We can draw networks (also sometimes called graphs) where the nodes are points and the edges are lines connecting the nodes.
For convenience, let’s consider a set of nodes V = {1,2,3} which support a network shown in the figure below:
The nodes are shown as gray circles with their node index as white numbers and the edges are black lines connecting the nodes. The edges between the nodes can be encoded in a matrix called the adjacency matrix A, whose ijth element aij equals 1 if there is an edge between nodes i and j in the network and equals 0 otherwise. For this project, we will only consider networks where an edge from node i to j implies that an edge is also from j to i (these are so-called undirected networks). So the adjacency matrix for the network above is
0 1 0 A=1 0 1
Notice that the adjacency matrix has zeros on the diagonal since the network does not have edges from a node to itself.
The network structure is typically represented algebraically in a matrix called the graph Laplacian, which can be computed from the adjacency matrix. First, we need to define the degree matrix, which is a diagonal matrix whose iith element is the number of edges which intersect node i (also called the degree of node i). Then the graph Laplacian L is defined as the difference of the degree matrix and the adjacency matrix:
which, for the sample network above, equals
100 010 1 −1 0 L=0 2 0−1 0 1=−1 2 −1
001 010 0−11
This matrix has an elegant structure, with the node degrees residing on the diagonal where the adjacency matrix must equal zero. Moreover, since the degree of the node equals the number of edges that start or end at that node, the graph Laplacian has zero row sum, that is,
where 1N is the N × 1 vector of all ones and 0N is the N × 1 vector of all zeros. Notice that this equation is exactly the eigenvalue equation showing that L has an eigenvalue of 0 corresponding to an eigenvector of 1N . This matrix will be used to compactly define the averaging protocols below.
Consider N individual systems whose scalar states are combined in the N × 1 real vector x. We will allow this vector to evolve in time using averaging algorithms which consider time either as discrete or continuous.
2.3.1 Discrete time
When time is discrete, the averaging algorithm can be written as a system of difference equations with time step k = 0,1,2,…:
x1(k+1)=x1(k)+εN a1j(xj(k)−x1(k)) j=1
x2(k + 1) = x2(k) + ε Nj=1 a2j (xj (k) − x2(k)) …
xN (k + 1) = xN (k) + ε Nj=1 aN j (xj (k) − xN (k))
Here, xi(k) is the ith element of the state vector x at time step k, which is the state of the ith individual at time step k. The term aij is the ijth element of the interaction network’s adjacency matrix, which means that it equals 1 if individuals i and j are neighbors and 0 otherwise.
The system of equations above define the updated state of each individual at time step k + 1 as its state at time step k plus the difference between the node and its neighbors at time step k. This can be written in a more compact matrix form using the matrix representation for the interaction network:
x(k+1)=x(k)−εLx(k)=(IN −εL)x(k)
where L is the graph Laplacian of the interaction network, IN is the N dimensional identity matrix, and ε > 0 can be thought of as an averaging weight.
Notice that, if ε = 0, the individual systems do not change their states in response to their neighbors and no consensus can be expected in general. As ε increases, the individuals take their neighbors’ states into account for the averaging process and consensus may occur. However, if ε is too large, the averaging algorithm will diverge and consensus will not be reached.
2.3.2 Continuous time
When real time is continuous, the averaging algorithm can be written as a system of differential equations
with time variable t > 0:
x ̇1=N a1j(xj−x1) j=1
x ̇2 =Nj=1a2j(xj −x2) …
x ̇N =Nj=1aNj(xj −xN)
Here, xi is the ith element of the state vector x (i.e. the state of the ith individual) at time t. The dot notation is the derivative with respect to t. Analogously to the discrete time system, we can write this as a matrix equation:
x ̇ = − L x
2.4 Disagreement
Now that we have a way to potentially create consensus, we need a quantity to measure agreement between the individual systems. For the networks we will use for this project, the consensus state will be the average of the the initial conditions of the individual systems x0, an N × 1 vector. In other words,
1 N x ̄=N x0j
where x ̄, the consensus state, is a real number.
Since the system is designed to reach consensus, we define the disagreement vector ξ as the difference
between the current state and this consensus state:
ξ = x − x ̄ 1 N
Notice that this vector changes in time just as x does. We will use the norm of this disagreement vector ∥ξ∥ as a scalar that changes in time to quantify the progression of the system as a whole toward consensus.
3 Part A: Interaction Networks
Before we tackle the problem of consensus, we will become familiar with the types of interaction networks that distributed systems may use.
3.1 Static networks
The Matlab data file adjacency matrices.mat accompanying this project assignment contains three matrices A1, A2, and A3, which are adjacency matrices for three interaction networks.
Problem 3.1. Draw the networks given by each of the three adjacency matrices, remembering to label the nodes. Describe similarities and differences between the networks. You may use a digital drawing software, a computational software like Matlab, or scan a hand-drawn sketch for the network diagrams.
Problem 3.2. Compute the graph Laplacian for each of the three networks and find their eigenvalues (you may use a computational software for this). Describe the eigenvalues, particularly the meaning of the eigenvalue equal to 0 and its corresponding eigenvector(s).
3.2 Random networks
In the network analysis above and in the definition of the model in Section 2, we implicitly said the interaction network did not change in time, that is, it had no explicit dependence on the time variable in either model. Networks with this property are called static networks. However, real networks that connect systems trying to reach consensus often change in time due to, for example, inconsistent com- munication networks. We will now generate interaction networks that change in time, which are called switching networks, to be used in the averaging protocol in the next part of the project.
Here we will use switching networks that are generated through a random variable, which we will call random networks. The model for these networks comes from the Erd ̈os-R ́enyi random network model. These random networks have N nodes and the edges are built using the following random process: in a realization of the random network, the edge between any pair of nodes is present in the network with a uniform probability p that is the same for all the edges. The existence of the edges are all independent, identically distributed random variables. If it is helpful in your own research, random variables defined like this are said to have Bernoulli distributions.
Problem 3.3. Write a script to generate a random network with N = 4 and p = 0.1 and another random network with N = 4 and p = 0.9. You may find that using the uniform random number generator function rand in Matlab is helpful. Draw an example of the networks with each of these parameters and describe them.
4 Part B: Averaging Algorithms 4.1 Averaging over static networks
We will first explore consensus through averaging algorithms where the interaction networks are static in time, which is consistent with the equations we wrote the equations in Section 2.
4.1.1 Discrete and continuous time models
As we saw in Section 2, the discrete time averaging algorithm for the interaction networks we built in Section 3 is the system of linear difference equations
x(k + 1) = (I4 − εL)x(k) when time is discrete and is the system of linear differential equations
when time is continuous.
4.1.2 Equilibria
x ̇ = − L x
Equilibria for averaging algorithms, as for all dynamical systems, are states from which the system does not deviate if it begins there. The models should be designed so that the consensus state is an equilibrium, meaning that coordination between individuals persists once it’s achieved.
Problem 4.1. Explain why the vector α14 is an equilibrium for the discrete and continuous models above when any of the three adjacency matrices are considered, for a scalar α. Are there any other equilibria for any of the three networks: A1, A2, and A3? If so, why?
4.1.3 Eigenvalues and stability
For the continuous-time model, convergence to consensus can depend on the interaction network and initial conditions. However, the discrete-time model also has the averaging weight ε which controls the stability of the equilibrium at α14.
Problem 4.2. First, write a general relationship between the eigenvalues of the graph Laplacian and those of I4 − εL, and then write an inequality showing the values of ε (depending on the eigenvalues of L) that will allow the system to reach consensus. For each of the three networks, compute bounds for ε that ensure the system reaches consensus.
4.1.4 Simulations
Now that we have an expectation of what networks and what values of ε may enable the networked individuals to reach consensus, we can demonstrate the behavior of the system through numerical sim- ulations.
Problem 4.3. Use Matlab to simulate the averaging algorithms to demonstrate the effect of the inter- action network on consensus.
1. Randomly generate or manually define initial conditions that you will use for your simulations. This should be a 4×1 vector of real numbers. Save this vector in a file named initial conditions.mat.
2. Write a Matlab script to simulate the discrete time model for 20 time steps for each of the inter- action networks A1 and A2. For each network, select two values of ε: one that allows consensus and one that is too large to allow consensus. Plot the 4 elements of the vector x with time on the horizontal axis for each simulation. Clearly label all plots and discuss your observations.
Use this Matlab script to simulate the discrete time algorithm with A3 with two values of ε of your choosing. Discuss the behavior of the system. How does consensus depend on the interaction network and ε? Can you relate this back to the network properties encoded in the graph Laplacian?
Use the method script developed in Module 13 to simulate the continuous time model for 20 units of time with a time step of 0.5. Simulate the system for each of the parameter sets (ε and interaction network) you selected above and compare the results between the continuous and discrete time models.
Averaging over switching networks
Now, we will allow the interaction network to change in time using the random networks we constructed in Section 3.
Problem 4.4. Use Matlab to simulate the discrete time averaging algorithm to demonstrate the effect of switching interaction networks.
1. Write a Matlab script to perform the discrete time algorithm where the interaction network is an independent realization of a random network that switches at each time step.
2. Simulate the algorithm with a switching network using parameter values of N = 4, ε = 0.4 and p = {0.1, 0.9} for 20 time steps. (You will notice that individual simulations will vary due to the stochastic nature of the switching network.)
3. Compute the disagreement ∥ξ∥ for the two simulations above (the one with p = 0.1 versus the one with p = 0.9) and for a static network that uses A2 and ε = 0.4 for 20 time steps. Plot the disagreement for each simulation with time on the horizontal axis. Describe your observations. What is the effect of interaction networks that switch in time?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com