--- abstract: 'This work concentrates on different aspects of the *consensus problem*, when applying it to a swarm of flocking agents. We examine the possible influence an external agent, referred to as <span>*influencing agent*</span> has on the flock. We prove that even a single influencing agent with a *Face Desired Orientation behaviour* that is injected into the flock is sufficient for guaranteeing desired consensus of the flock of agents which follow a Vicsek-inspired Model. We further show that in some cases this can be guaranteed also in dynamic environments.' author: - | Saar Cohen$^{1}$, Noa Agmon$^{2}$\ Department of Computer Science\ Bar Ilan University, Israel\ gabriellajones@example.org$^{1}$, gabriellajones@example.org$^{2}$\ bibliography: - 'sample.bib' title: - 'Abstract, keywords and references template' - Converging to a Desired Orientation in a Flock of Agents --- <span> ***Keywords—*** Coordination, Consensus Algorithms, Flocking, Swarm Robotics, Multi-Agent Systems, Cooperative Control, Graph Laplacians, Networked Control Systems, Graph Theory, Lyapunov Function, Switched Systems, Computational Geometry </span> <span>2</span> Introduction {#sec:intro} ============ Reaching a consensus within a group of simple robots that have limited sensing, use no explicit communication and have limited computational capabilities is one of the core problems in swarm robotics. The goal is to find a protocol for the robots such that eventually they will all agree on a certain value. In this work we consider the problem of converging a flock of agents to a single orientation, that is, reaching a consensus on the orientation. As opposed to previous work @ren2005consensus [@olfati2004consensus; @olfati2007consensus], we examine the problem of forcing the flock to reach a <span>*desired*</span> orientation by inserting one or *more* agents, referred to as <span>*influencing agents*</span>, into the flock. We assume that the agents are initially placed in one connected component, facing random directions. We prove that influencing agents with a *Face Desired Orientation behaviour* are sufficient for guaranteeing consensus, while employing them into a swarm of flocking agents that follow the Vicsek Model @vicsek1995novel. Genter and Stone @genter2016ad [@genter2016adding] introduced this kind of baseline behaviour, according to which influencing agents face a predetermined desired orientation at all times. This behaviour was actually inspired by Jadbabaie et al. @jadbabaie2003coordination, who considered a modified version of Vicsek's model which utilizes a *single* leader with a fixed orientation and several followers. Hence, the *Face Desired Orientation behaviour* is the one described in their work, except that we propose several significant extensions regarding this behaviour: 1. We consider *both* the fixed topology case and the switching topology case, instead of considering just a single one of them. 2. Opposed to their work, we consider *multiple* Vicsek-inspired Models, instead of just a *single* one. 3. Furthermore, Jadbabaie et al. @jadbabaie2003coordination utilized an *undirected* graph model with a *single* leader, but we consider a *directed* one with *multiple* influencing agents. 4. Whereas Genter and Stone @genter2016ad [@genter2016adding] solely give *experimental results* regarding this behaviour, we also propose *theoretical proofs* of useful properties while such behaviour is incorporated. For a *fixed topology*, we also prove that continuous-time update rules converge exponentially *faster* than discrete-time ones, thus yielding the benefits of the continuous-time case. For a *switching topology with a continuous-time update rule*, we propose a much more concrete convergence rate than the one proposed by Olfati-Saber and Murray @olfati2004consensus. We also propose a computational geometric algorithm, referred to as the *Intersection Points Placement Method*, which guarantees in polynomial time that a *single* influencing agent can be inserted into the flock in a manner that it will necessarily influence an entire single connected component. This algorithm utilizes the locus of all point in $\mathbb{R}^2$, which lie on the linear line connecting the intersection points of neighborhoods which correspond to a random pair flocking agents. We have situated our research in the MASON simulator @luke2005mason, demonstrating the impact of the number of influencing agents on the convergence rate in different scenarios. Finally, we discuss and demonstrate the concept of "lost" flocking agents @genter2017fly in a switching topology. Related Work ============ In this section, we provide a review of the state-of-the-art in different domains that are related to our work. The articles mentioned below concentrate on reaching a consensus among swarms, while utilizing various tools for the sake of achieving it. Ad-Hoc Teamwork --------------- Due to the rise in the use of autonomous agents, both in software and robotic settings, they will increasingly need to band together for cooperative activities with previously unfamiliar teammates. As described by Stone et al. @stone2013teaching, multiple agents with different knowledge and capabilities find themselves in a situation such that their goals and utilities are perfectly aligned (for instance, everyone's sole interest is to help find survivors), yet they have had no prior opportunity to coordinate. Genter and Stone @genter2013ad consider the problem of leading a team of flocking agents in an ad-hoc teamwork setting. An ad-hoc teamwork setting is one in which a teammate - which they call an *influencing agent* - must determine how to best achieve a team goal given a set of possibly suboptimal teammates. The main question addressed in this paper is: *how should influencing agents behave so as to orient the rest of the flock towards a target heading as quickly as possible?* The main contribution of this paper is the 1-step lookahead algorithm for orienting a flock to travel in a particular direction and its variations. Genter et al. @genter2015determining further examine where these influencing agents should be placed in the flock. Specifically, their research question is: *where should influencing agents be located within a flock to maximize their influence on the flock?* They introduce a graph-based method for deciding where to place the influencing agents and their approach to control the influencing agents. They suggest two cases for controlling: the **Drop** case (in which the k influencing agents are at their desired positions at $t = 0$) and the **Dispatch** case (in which the influencing agents are initially positioned outside of the flock). Researches investigate those ad-hoc settings from different angles @genter2013ad [@stone2013teaching]. For instance, @stone2013teaching focuses on settings in which we are designing a new agent that has full information about its environment, that must coordinate with an older, less aware, more reactive agent whose behaviour is known, while using game-theoretic tools. These researches usually deploy the main idea of letting each robot execute a simple algorithm and plan its motion adaptively based on the observed movement of other agents, so that the agents as a group will achieve the given goal. Fu et al. @fu2018influencing observe on this problem from a different perspective. They focus on lower-density settings where interactions are rarer and flock formation is more difficult. They study how such influencing agent priorities must change in these settings to be successful and propose new influencing agent strategies to adapt to the challenges posed by these settings. Low-density settings are important to study because they capture dynamics in situations where flocking may not occur naturally, but where we might want to instigate flocking behaviour; imagine a herd of buffalo that is currently grazing, or a spooked flock of birds where individual agents fail to coordinate. Considerable research into ad-hoc teamwork has established a number of theoretical and empirical methods for handling unknown teammates, but these analyses largely focus on simple scenarios that may not be representative of the real problems that agents may encounter in influencing teams. Barret and Stone @barrett2015cooperating come to address this gap. The main contribution is the introduction of an algorithm (PLASTIC–Policy) for selecting effective actions for cooperating with a variety of teammates in complex domains. This algorithm learns policies of how to cooperate with previous teammates and then reuses this knowledge to cooperate with new teammates. Learning these policies is treated as a *reinforcement learning problem*, where the inputs are features derived from the world state and the actions are soccer moves such as passing or dribbling. Then, PLASTIC–Policy observes the current teammates' behaviours to select which of these policies will lead to the best performance for the team. Consensus in Groups of Autonomous Agents ---------------------------------------- In the traditional consensus problem of distributed computing @fischer1983consensus, the goal is for all processors in a network to agree on a certain value. The problem becomes challenging as the network becomes more complex, and the consensus protocol should handle sparse networks, asynchronous timing and possible faults in the system @fischer1985impossibility [@olfati2004consensus; @olfati2007consensus]. Regarding the consensus problem in swarm robotics, the dynamic nature of the network is brought to its extreme: the network topology changes throughout the execution, and a robot controls not only the decision of how to change its own value, but also its movement. The robot's choice of action in the physical world has an impact on what its neighbors observe, and thus also its own state in the future @fax2004information [@olfati2004consensus; @olfati2007consensus]. Modeling those topologies is usually done using graph theory and matrix theory. According to Ren and Beard @ren2005consensus, those topologies are depicted using directed graphs and the minimum requirements to reach consensus are explored in the case of strongly connected graphs. More specifically, it is shown that the agents reach a consensus asymptotically if and only if the associated interaction graph has a spanning tree. Olfati-Saber and Murray @olfati2004consensus examine directed networks with fixed or switching topologies. They present two consensus protocols which solve agreement problems in a network of either continuous-time (CT) integrator or discrete-time (DT) model. One protocol depicts either a fixed or a switching topology with zero communication time-delay, while the other depicts a fixed topology with communication time-delay corresponding to every edge. They also present the model using a linear system, induced by the *Laplacian* matrix or the *Perron* matrix @olfati2004consensus, both induced by the interaction graph of the topology. Their paper also examines the spectral properties of both matrices, while proving conditions under which the flock reaches a consensus. On the contrary, some researches examine the coordination of flocking agents using the Vicsek Model @vicsek1995novel. According to this model, each agent's heading is updated using a simple local rule based on the average of its own heading plus the headings of its neighbors. Jadbabaie et al. @jadbabaie2003coordination, both leaderless and leader following coordinations are examined. For each case, this article gives us conditions under which the flock reaches a consensus upon its orientation. In the case of leaderless coordination, it is shown that given an infinite sequence of contiguous, nonempty, bounded, time-intervals, with the property that across each such interval the agents are linked together, the flock will reach a consensus. In the case of leader following coordination, a similar condition is proven. Some researches use the Laplacian matrix's spectral properties for exploring the consensus problem. The second eigenvalue of the Laplacian is widely used in Olfati-Saber and Murray @olfati2004consensus. This eigenvalue is known as the *algebraic connectivity* of the graph associated with the Laplacian matrix, and aside from depicting the connectivity of the graph, this article gives us the speed in which the flock reaches a consensus. Moreover, Olfati-Saber and Murray @olfati2004consensus also use the spectral properties of the Laplacian to provide conditions for solving the average-consensus problem. It considers the case of topologies with either zero communication time-delay or with communication time-delay and shows conditions under which consensus is achieved. Olfati-Saber et al. @olfati2007consensus also examine the spectral properties of the Laplacian in order to investigate the average-consensus problem (in which the consensus value equals to the average of the the initial value of the state of each agents). It gives conditions under which a consensus is asymptotically reached for all initial states, using these spectral properties. It considers both the continuous-time (CT) case and the discrete-time (DT) case. In the DT case, the *Perron* matrix is examined, while examining its connection to the Laplacian matrix. Hong et al. @hong2007lyapunov consider neighbor-based rules which are adopted to realize local control strategies for these continuous-time autonomous agents described by double integrators. Although the inter-agent connection structures vary over time and related graphs may not be connected, a sufficient condition to make all the agents converge to a common value is given for the problem by a proposed Lyapunov-based approach and related space decomposition technique. The Lyapunov-based approach also provides a way of showing the speed in which a dynamics vanishes @olfati2007consensus [@olfati2004consensus]. A disagreement dynamics is shown, which measures how far the agents are from a consensus. This article uses the Lyapunov-based approach to show the speed in which the agents reach a consensus asymptotically. The Flocking Model {#sec:flocking-model} ================== The flock comprises of $k$ flocking agents, trying to converge to the same orientation $\theta^*$, and $m$ influencing agents. On the one hand, the flocking agents $A^F : = \{a_0,...,a_{k-1}\}$ are agents which we cannot directly control and we would like to consider the implications of various definitions for their global orientation separately. On the other hand, we can control the behaviour of the influencing agents $A^D := \{a_k,...,a_{n-1}\}$, where $n = m + k$. We assume that the influencing agents are capable of communication, they have full knowledge of the world and a high computability. In contrast to the flocking agents, each influencing agent's position is updated according to their assumed behaviour. That is, it is not necessarily updated after its orientation is updated in accordance to a specific update rule. At each time step $t$, the number of influencing agents inside $a_i$'s neighborhood is denoted by $m_i (t)$ and the number of flocking agents inside the neighborhood is denoted by $k_i (t)$, where $n_i (t) = m_i (t) + k_i (t) \leq n$. *Lemma 2* from @genter2013ad will be used throughout the entire research. This lemma is phrased as follows: \[Same Orientaion\] When $m_i(t)$ influencing agents work together to influence $k_i(t)$ flocking agents to align the team to some orientation, it suffices to consider only algorithms that choose at each time step just one orientation for all the agents to adopt. Flocking agents update their orientation based on the orientations of the other agents in their neighborhood, defined by the *visibility radius*. Let $N_i (t)$ be the set of $n_i (t) \leq n$ agents (including agent $a_i$) at time $t$ which are located within a *visibility radius* $R$ of agent $a_i$. This means that each agent's *visibility cone* equals to $2\pi$. We shall make the following definitions: \[def:flocking-neighbors-graph\] (*Flocking Neighbors Graph*) The relationships between neighbors which exist in time step $t$ and influence the form of the update equations can be described by a simple, **directed** graph (digraph) $\mathcal{G}(t) = (\mathcal{V},\mathcal{E}(t))$, where: - $\mathcal{V} = \{0,...,k-1\}$ - The vertex set represents the flocking agents. - $\mathcal{E}(t) = \{(i,j) \in \mathcal{V} \times \mathcal{V} | a_i \neq a_j \in N_i(t)\}$ This graph will be named the *Flocking Neighbors Graph*. We denote its number of connected components at time $0$ by $\eta$. \[def:strongly-connected-digraphs\] (*Strongly Connected Digraphs*) A digraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is *strongly connected* if there is a directed path connecting any two arbitrary nodes $s,t \in \mathcal{V}$ of the graph. \[def:balanced-digraphs\] (*Balanced Graphs* @olfati2004consensus) A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ (which is either directed or undirected) with an adjacency matrix $A$ is *balanced* if $\sum_{j \neq i} A[i,j] = \sum_{j \neq i} A[j,i]$ for all $i \in \mathcal{V}$. \[def:fixed-topology\] (*Fixed Topology*) If there exists some digraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ for which $\mathcal{G}(t) = \mathcal{G}$ for any time step $t$, we say that this is a *fixed topology*. \[def:switching-topolgy\] (*Switching Topology*) A *switching topology* can be modeled using a dynamic graph $\mathcal{G}(t) = \mathcal{G}_{\sigma(t)}$ parameterized with a switching signal $\sigma(t):\mathbb{N} \rightarrow \mathcal{Q}_k$, where $\mathcal{Q}_k$ denotes a suitably defined set, indexing the class of all simple graphs defined on $k$ vertices. We denote the *adjacency matrix* and the *degree matrix* of the flocking neighbors graph at time step $t$ by $A(t),D(t)$ (respectively). We also denote by $L(t) = D(t) - A(t)$ the *graph Laplacian* of the flocking neighbors graph at time step $t$, whose elements are defined as follows: $$L(t)[i,j] = \begin{cases} -1, \quad a_j \in N_i(t) \\ |N_i(t)|, \quad j=i \end{cases}$$ We denote by $P(t) = I - \varepsilon L(t)$ the *Perron matrix* of the flocking neighbors graph at time step $t$, where $I$ is the identity matrix and $\varepsilon > 0$ is the step-size. We denote the global orientation of a flocking agent $a_i$, $0 \leq i \leq k-1$, at time step $t+1$, by $\theta_i (t+1)$. Each agent $a_i$ moves with velocity $v_i$. At each time step $t$, each agent $a_i$ has a position $p_i(t) = (x_i (t),y_i (t))$ in the environment and an orientation $\theta_i (t)$. According to @genter2015determining, each agent's position $p_i (t)$ at time $t$ is updated after its orientation is updated, such that: $$\begin{cases} x_i(t) = x_i(t-1) + v_i cos(\theta_i(t)) \\ y_i(t) = y_i(t-1) - v_i sin(\theta_i(t)) \end{cases}$$ The influencing agents join the flock in order to influence its members to behave in a particular way. We consider the **Drop** case @genter2015determining for the initial placements $\{p_k (0),...,p_{n-1} (0)\}$ of the influencing agents, in which the influencing agents are at their desired location at time $t=0$. Alternatively, we could define a neighboring graph which also takes the influencing agents into consideration. This graph's definition is as follows: \[def:influencing-neighbors-graph\] (*influencing Neighbors Graph*) The relationships between neighbors (both flocking and influencing) which exist in time step $t$ and influence the form of the update equations can be described by a simple, directed graph (digraph) $\tilde{\mathcal{G}}(t) = (\tilde{\mathcal{V}},\tilde{\mathcal{E}}(t))$, where: - $\tilde{\mathcal{V}} = \{0,...,n-1\}$ - The vertex set representing both the flocking agents and the influencing agents. - $\tilde{\mathcal{E}}(t) = \{(i,j) \in \mathcal{V} \times \mathcal{V} | a_i \neq a_j \in N_i(t)\}$ This graph will be named the *influencing Neighbors Graph*. Clearly, for all $t \geq 0$, we denote the adjacency matrix, the degree matrix, the Laplacian matrix and the Perron matrix of $\tilde{\mathcal{G}}(t)$ by $\tilde{A}(t),\tilde{D}(t),\tilde{L}(t), \tilde{P}(t)$ (respectively). Definitions \[def:fixed-topology\] and \[def:switching-topolgy\] also hold for an influencing neighbors graph. Throughout the entire research, we will be considering the connected components of either the flocking neighbors graph or the influencing neighbors graph and the subgraph which they induce upon them. For this sake, we make the following definition: \[def:induced-subgraph\] (*Induced Subgraph*) Let $\mathcal{G} = (\mathcal{V},\mathcal{E})$ be some simple graph. For some subset $\mathcal{U} \subseteq \mathcal{V}$ of vertices, $\mathcal{G}(\mathcal{U}) = (\mathcal{U},\mathcal{E}(\mathcal{U}))$ with $\mathcal{E}(\mathcal{U}) = \{(v,u) \in \mathcal{U} \times \mathcal{U} | (v,u) \in \mathcal{E}\}$ is called the *subgraph* of $\mathcal{G}$ *induced* by $\mathcal{U}$. It should be noted that the update rule for each agent's position is performed in accordance to the update rule defining the global orientation of each agent. For each *flocking* agent, it is either the discrete-time update rule presented in Subsection \[sec:dt-update-rule\] or the continuous-time update rule presented in Subsection \[sec:ct-update-rule\]). These update rules are based on the Vicsek Model @vicsek1995novel. Agent $a_j$'s position in the environment at time step $t$ is located at angle $\beta_{ij}(t) \leq \pi$ with respect to $a_i$'s position. ### Discrete-Time Update Rule {#sec:dt-update-rule} The global orientation of a flocking agent $a_i$, $0 \leq i \leq k-1$, at time step $t+1$, $\theta_i (t+1)$, can be defined in two ways in the discrete-time (DT) case. According to Olfati-Saber et al. @olfati2007consensus, if we denote $\theta(t) = [\theta_i(t)]$ ($0 \leq i \leq k-1$), it can be defined as follows: $$\label{eq:orientation-perron} \theta (t+1) = P(t)\theta (t)$$ According to @genter2015determining, it can be set to be the average orientation of all agents in $N_i (t)$ (including itself) at time step $t$. This definition is actually a special case of the previous one, in the manner that it is a variation of the case $\varepsilon = 1$: $$\label{eq:orientation-calcdiff} \theta_i (t+1) = \theta_i (t) + \frac{1}{n_i (t)} \sum_{a_j \in N_i (t)}calcDiff(\theta_j (t),\theta_i (t))$$ \[alg:calc-diff\] Instead of taking the mathematical average orientation of all agents, we use Equation 1 because of the special cases handled by Algorithm 1 (from @genter2015determining). As a convention, we assume $\theta_i (t)$ is within $[0,2\pi)$. ### Continuous-Time Update Rule {#sec:ct-update-rule} The global orientation of an agent $a_i$, $0 \leq i \leq n-1$, at time step $t$ can be defined in two ways in the continuous-time (CT) case. According to @olfati2004consensus, it can be defined using the following linear system: $$\label{eq:global-orient-linear} \dot{\theta_i}(t) = \sum_{a_j \in N_i(t)} \tilde{A}(t)[i,j] (\theta_j(t) - \theta_i(t))$$ The following lemma gives us an equivalent definition in matrix terms: \[lemma:global-orient-linear-matrix\] We denote the adjacency matrix, the degree matrix and the Laplcian matrix of the influencing neighbors graph at time step $t$ by $\tilde{A}(t),\tilde{D}(t),\tilde{L}(t)$ (respectively). Denoting $\tilde{\theta}(t) = [\theta_i(t)]$ ($0 \leq i \leq n-1$), the following heading system is equivalent to Equation \[eq:global-orient-linear\]: $$\dot{\tilde{\theta}}(t) = - \tilde{L}(t) \tilde{\theta}(t)$$ The elements of the degree matrix are defined as follows: $$\tilde{D}(t)[i,j] = \begin{cases} \sum_{a_j \in N_i(t)}\tilde{A}[t][i,j], \quad i = j\\ 0, \quad j \neq i \end{cases}$$ Since $\tilde{L}(t) = \tilde{D}(t) - \tilde{A}(t)$ by definition, then its elements are defined as follows: $$\tilde{D}(t)[i,j] = \begin{cases} \sum_{a_j \in N_i(t)}\tilde{A}[t][i,j] - \tilde{A}(t)[i,i], \quad i = j\\ - \tilde{A}(t)[i,j], \quad j \neq i \end{cases}$$ Therefore: $$(- \tilde{L}(t) \tilde{\theta}(t))[i] = \bigg[\tilde{A}(t)[i,i] - \sum_{a_j \in N_i(t)}\tilde{A}[t][i,j]\bigg]\theta_i(t) +$$ $$+ \sum_{a_i \neq a_j \in N_i(t)}\tilde{A}(t)[i,j]\theta_j(t) =$$ $$=\sum_{a_j \in N_i(t)} \tilde{A}(t)[i,j] (\theta_j(t) - \theta_i(t)) = \dot{\theta_i}(t)$$ Fax and Murray @fax2004information introduced the following version of a Laplacian-based system in a flock with 0–1 weights: $$\label{eq:global-orient-zero-one} \dot{\theta_i}(t) = \frac{1}{|N_i(t)|}\sum_{a_j \in N_i(t)} (\theta_j(t) - \theta_i(t))$$ The following lemma gives us an equivalent definition in matrix terms: \[lemma:global-orient-zero-one-matrix\] We denote the adjacency matrix, the degree matrix and the Laplcian matrix of the influencing neighbors graph at time step $t$ by $\tilde{A}(t),\tilde{D}(t),\tilde{L}(t)$ (respectively). Denoting $\tilde{\theta}(t) = [\theta_i(t)]$ ($0 \leq i \leq n-1$), the following heading system is equivalent to Equation \[eq:global-orient-zero-one\]: $$\dot{\tilde{\theta}}(t) = (\tilde{D}(t) ^ {-1} \tilde{A}(t) - I) \tilde{\theta}(t)$$ This is a special case of an influencing neighbors graph $\mathcal{G}^*(t)$, for which $I$ is the degree matrix and $\tilde{D}(t) ^ {-1} \tilde{A}(t)$ is the adjacency matrix. Thus, based on Lemma \[lemma:global-orient-linear-matrix\], we have that: $$\dot{\tilde{\theta}}(t) = - (I - \tilde{D}(t) ^ {-1} \tilde{A}(t)) \tilde{\theta}(t) = (\tilde{D}(t) ^ {-1} \tilde{A}(t) - I) \tilde{\theta}(t)$$ Influencing Connected Components {#sec:influencing-connected-components} ================================ In this section, we deal with reaching a consensus among agents, which correspond to a single connected component in either the flocking neighbors graph or the influencing neighbors graph. Each kind of topology (either fixed or switching) affects the influence an influencing agent has upon some connected component. Furthermore, in each case, we shall take into consideration both the discrete-time update rules defined in Subsection \[sec:dt-update-rule\] (Equations \[eq:orientation-perron\] and \[eq:orientation-calcdiff\]) and the continuous-time update rules defined in Subsection \[sec:ct-update-rule\] (Equations \[eq:global-orient-linear\] and \[eq:global-orient-zero-one\]). Both kinds of update rules affect the speed at which the flocking agents converge to their desired orientation. First, we show a simplification of the update rule defined by Equation \[eq:orientation-calcdiff\] called the **normalized Perron matrix** and show some properties regarding it (Subsection \[sec:normalized-Perron-matrix\]). Then, we consider the influence of the influencing agents, both in the fixed topology case (Subsection \[sec:fixed-topology\]) and in the switching topology case (Subsection \[sec:switching-topology\]). More accurately, in each case, we give theoretical proofs regarding that influencing agents with a *Face Desired Orientation behaviour* are sufficient for guaranteeing consensus, while employing them into a flocking model that is based on the Vicsek Model @vicsek1995novel. Normalized Perron Matrix {#sec:normalized-Perron-matrix} ------------------------ When considering Equation \[eq:orientation-calcdiff\], we would like to also consider taking the mathematical average orientation of all agents, which is a simplification of the update rule defined by Equation \[eq:orientation-calcdiff\]. The following lemma gives us a property of Algorithm \[alg:calc-diff\]. This lemma claims that the difference between the orientations of two agents is always within $[-\pi,\pi]$ since the difference of $\pi + \varepsilon$ is equivalent to a difference of $\varepsilon - \pi$ in the opposite direction \[lemma:difference-restricted\] For each pair of agents $a_i,a_j$, the following holds for all time step $t \geq 0$: $calcDiff(\theta_i(t),\theta_j(t)) \in [-\pi,\pi]$. Let $t \geq 0$ be some time step. Let $a_i,a_j$ be two flocking agents. The proof is divided into three parts: 1. According to lines 1-2 of Algorithm \[alg:calc-diff\]: $$calcDiff(\theta_i(t),\theta_j(t)) = \theta_i(t) - \theta_j (t)$$ Therefore, the proof for this case is derived instantly. 2. According to lines 4-5 of Algorithm \[alg:calc-diff\]: $$calcDiff(\theta_i(t),\theta_j(t)) = 2\pi + (\theta_i(t) - \theta_j (t)) < 2\pi - \pi = \pi$$ where the inequality follows from our assumption in this case. We assume by contradiction that $calcDiff(\theta_i(t),\theta_j(t)) < -\pi$. Therefore: $$2\pi + (\theta_i(t) - \theta_j (t)) < -\pi \Rightarrow \theta_i(t) - \theta_j (t) < -3\pi$$ Since $\theta_i(t),\theta_j(t) \in [0,2\pi)$, then: $\theta_i(t) - \theta_j (t) > 0 - 2\pi = -2\pi$. From the previous two inequalities we infer that $-2\pi < -3\pi$ - . 3. According to line 7 of Algorithm \[alg:calc-diff\]: $$calcDiff(\theta_i(t),\theta_j(t)) = (\theta_i(t) - \theta_j (t)) - 2\pi > \pi - 2\pi = -\pi$$ where the inequality follows from our assumption in this case. We assume by contradiction that $calcDiff(\theta_i(t),\theta_j(t)) > \pi$. Therefore: $$(\theta_i(t) - \theta_j (t)) - 2\pi > \pi \Rightarrow \theta_i(t) - \theta_j (t) > 3\pi$$ Since $\theta_i(t),\theta_j(t) \in [0,2\pi)$, then: $\theta_i(t) - \theta_j (t) < 2\pi - 0 = 2\pi$. From the previous two inequalities we infer that $2\pi > 3\pi$ - . Moreover, since $\theta_i(t)$ is assumed to be within $[0,2\pi)$ for each agent $a_i$, the mathematical average orientation of all agents is restricted to be within $[0,2\pi)$ as well. Thus, we infer that for any agent $a_i$ and for any time step $t \geq 0$: $$\frac{1}{n_i(t)} \sum_{a_j \in N_i (t)}\theta_j(t) \in [0,2\pi)$$ In light of the above, we will make the following assumption for the simplification of the update rule defined by Equation \[eq:orientation-calcdiff\]: \[assump:update-rule-simplification\] For each pair of agents $a_i,a_j$, the difference between their orientations is always within $[-\pi,\pi]$, i.e. $\theta_j(t) - \theta_i(t) \in [-\pi,\pi]$ for any time step $t \geq 0$. For justifying this assumption, note that Algorithm \[alg:calc-diff\] handles the special cases for the differences between the orientation of some agent $a_i$ and each of its neighbors, while restricting these differences such that they are always within $[-\pi,\pi]$ (According to Lemma \[lemma:difference-restricted\]). Therefore, the assumption in question can be made for simplifying the update rule of each agent, while still restricting the mathematical average orientation of all agents to be within $[0, 2\pi)$ as previously mentioned. Given this assumption, the resulting simplified update rule for each flocking agent $a_i$ is as follows: $$\label{eq:simplified-calcdiff} \theta_i(t+1) = \frac{1}{n_i(t)} \sum_{a_j \in N_i (t)} \theta_j(t)$$ The following lemma gives us this simplification in matrix terms: \[lemma:simple-calcdiff-matrix\] Let the *adjacency matrix* and the *degree matrix* of the flocking neighbors graph at time step $t$ be $A(t),D(t)$ (respectively). Denoting $\theta(t) = [\theta_i(t)]$ ($0 \leq i \leq k-1$), the following heading system is equivalent to Equation \[eq:simplified-calcdiff\]: $$\theta(t+1) = (I+D(t))^{-1}(I+A(t)) \theta(t)$$ For each flocking agent $a_i$, its neighborhood is the set of $n_i(t) \leq k$ agents including agent $a_i$ at time step $t$. In contrast, the degree of the vertex $i$ in the flocking neighbors graph in time step $t$ equals to the number agents in agent $a_i$'s neighborhood **except for itself**, i.e., the degree of the vertex $i$ equals to $D(t)[i,i]=n_i(t) - 1$. Thus, it also holds that $A(t)[i,i]=0$ for each flocking agent $a_i$. Therefore, for a pair of flocking agents $a_i,a_j$, the $(i,j)$-th cell of the matrix $(I+D(t))^{-1}(I+A(t))$ equals to $\frac{1}{n_i(t)}A(t)[i,j]$ and its $(i,i)$-th cell equals to $\frac{1}{n_i(t)}$. Therefore, for each flocking agent $a_i$ the following holds: $$((I+D(t))^{-1}(I+A(t)) \theta(t))[i]=$$ $$= \sum_{i \neq j=0} ^{k-1}\frac{1}{n_i(t)}A(t)[i,j]\theta_j(t) + \frac{1}{n_i(t)}\theta_i(t) =$$ $$= \frac{1}{n_i(t)} \sum_{a_j \in N_i (t)} \theta_j(t) = \theta_i(t+1)$$ where the second equality stems from the definition of the adjacency matrix $A(t)$ and the last one stems from Equation \[eq:simplified-calcdiff\]. As a matter of fact, $P(t) := (I+D(t))^{-1}(I+A(t))$ is the **normalized** Perron matrix obtained from the following **normalized** Laplacian matrix with $\varepsilon=1$: $$\label{eq:normalized-laplacian} \bar{L}(t) := I - (I+D(t))^{-1}(I+A(t))$$ Lemma \[lemma:simple-calcdiff-matrix\] that follows presents some structural properties regarding the normalized Perron matrix. To prove them, we will be using Gershgorin disk theorem @gershgorin1931uber, which is stated as follows: \[theorem:Gershgorin\] (**Gershgorin Disk Theorem, 1931**) Let $M$ be a complex $n \times n$ matrix. For $1 \leq i \leq n$, let $R_{i}=\sum _{{j\neq {i}}}\left|M[i,j]\right|$ be the sum of the absolute values of the non-diagonal entries in the $i$-th row. Let $B(M[i,i],R_{i})\subseteq \mathbb {C}$ be a closed disc centered at $M[i,i]$ with radius $R_{i}$. Such a disc is called a **Gershgorin disc**. Then, Every eigenvalue of $M$ lies within at least one of the Gershgorin discs $B(M[i,i],R_{i})$. Before proving these properties, we prove that both the following propety of the flocking neighbors graph and the influencing neighbors graph: \[lemma:neighbors-graphs-balanced\] At each time step $t$, the flocking neighbors graph and the influencing neighbors graph are balanced digraphs (according to Definition \[def:balanced-digraphs\]). Since the proof for both graphs is identical, we will be proving the lemma only for the flocking neighbors. Let the *adjacency matrix* of the flocking neighbors graph at time step $t$ be $A(t)$. Let $i \in \mathcal{V}$. For each $i \neq j \in \mathcal{V}$, we divide the proof into two cases: 1. This also means that $a_i \in N_j(t)$. According to the definition of the flocking neighbors graph, we have that $A(t)[i,j] = A(t)[j,i] = 1$. 2. This also means that $a_i \notin N_j(t)$. According to the definition of the flocking neighbors graph, we have that $A(t)[i,j] = A(t)[j,i] = 0$. Thus: $\sum_{j \neq i} A(t)[i,j] = \sum_{j \neq i} A(t)[j,i]$, which means that the flocking neighbors graph is a balanced digraph. Let the *adjacency matrix* of the flocking neighbors graph at time step $t$ be $A(t)$. If the flocking neighbors graph was assumed to be **undirected**, it could be directly inferred that $A(t)[i,j] = A(t)[j,i]$. In other words, each undirected graph is necessarily a balanced graph. We shall also consider the following definitions: \[def:stochastic\] (*Row Stochastic Matrix* @horn1985johnson) A matrix $M$ is called **row stochastic** if it is a **nonnegative** matrix (a matrix whose entries are all nonnegative) and its row sums all equal 1 (i.e., $M1 = 1$). \[def:column-stochastic\] (*Column Stochastic Matrix* @horn1985johnson) A matrix $M$ is called **column stochastic** if it is a **nonnegative** matrix (a matrix whose entries are all nonnegative) and its column sums all equal 1 (i.e., $1M = 1$). \[def:doubly-stochastic\] (*Doubly Stochastic Matrix*) A matrix $M$ is called **doubly stochastic** if it is a **nonnegative** matrix (a matrix whose entries are all nonnegative), which is both row stochastic and column stochastic. \[def:irreducible\] (*Irreducible Matrix*) An adjacency matrix $A(t)$ is **irreducible** if and only if $\mathcal{G}(t)$ is strongly connected. \[def:period\] (*Period*) Let $M$ be a nonnegative matrix. Fix an index $i$ and define the **period of index $i$** to be the greatest common divisor of all natural numbers $j$ such that $(M ^ j)[i,i] > 0$. When $M$ is irreducible, the period of every index is the same and is called the **period of $M$**. If the period is 1, A is **aperiodic**. \[def:aperiodic\] (*Aperiodic Matrix*) Let $M$ be an irreducible nonnegative matrix. If its period is 1, $M$ is **aperiodic**. \[def:primitive\] (*Primitive Matrix*) A matrix $M$ is **primitive** if it is an irreducible aperiodic nonnegative matrix. \[lemma:normalized-perron-properties\] The normalized Perron matrix $P(t) = (I+D(t))^{-1}(I+A(t))$ has the following structural properties: 1. $P(t)$ is a **row stochastic nonnegative** matrix with a trivial eigenvalue of $1$. 2. $P(t)$ is a **column stochastic nonnegative** matrix. Combined with the first property, this makes $P(t)$ a **doubly stochastic** matrix. 3. If $\mathcal{G}(t)$ is a strongly connected graph, then $P(t)$ is a **primitive** matrix. 4. All eigenvalues of $P(t)$ are in a unit disk. The proof for each property is as follows: 1. Clearly, $P(t)$ is a nonnegative matrix. According to the definitions of $D(t)$ and $A(t)$: $$D(t)[i,j] = \begin{cases} n_i(t)-1, \quad i=j\\ 0, \quad i \neq j \end{cases}$$ $$A(t)[i,j] = \begin{cases} 1, \quad \{i,j\} \in \mathcal{E}(t)\\ 0, \quad otherwise \end{cases}$$ Therefore, it holds that: $$((I + A(t))1)[i,j] = (I + D(t))[i,j] = \begin{cases} n_i(t), \quad i=j\\ 0, \quad i \neq j \end{cases}$$ which leads to $P(t)1 = 1$, i.e., $P(t)$ is **row stochastic**. 2. Since $G(t)$ is a balanced digraph (\[lemma:neighbors-graphs-balanced\]), the proof is similar to the proof of the previous property. 3. Given the stated above, we have that: $$P(t)[i,j] = \frac{1}{n_i(t)} (I+A(t))[i,j] = \begin{cases} \frac{1}{n_i(t)}, \quad i=j\\ \frac{1}{n_i(t)} A(t)[i,j], \quad i \neq j \end{cases}$$ That is, $P(t)$ is primitive if and only if $I + A(t)$ is primitive. Since $G(t)$ is a strongly connected digraph, according to Definition \[def:irreducible\], the matrix $I + A(t)$ is **irreducible**. Since $(I + A(t))[i,i] = 1 > 0$, then the period of $I + A(t)$ is 1, which means it is **aperiodic**. According to the first property, this matrix is also **nonnegative**, which means that $I + A(t)$ is a **primitive** matrix, as desired. 4. Based on the Gershgorin disk theorem @gershgorin1931uber, all the eigenvalues of $P(t)$ are located in the union of the following disks: $$\mathcal{B}_i(t) = \{z \in \mathbb{C}:\left| z - P(t)[i,i] \right| \leq \sum _{{j\neq {i}}}\left|P(t)[i,j]\right|\}$$ According to the proof of the previous property: $$\sum _{{j\neq {i}}}\left|P(t)[i,j]\right| = \sum _{{j\neq {i}}}\left|\frac{1}{n_i(t)} A(t)[i,j]\right| = \frac{n_i(t) - 1}{n_i(t)} = 1 - \frac{1}{n_i(t)}$$ Therefore: $$\mathcal{B}_i(t) = \Bigg\{z \in \mathbb{C}:\left| z - \frac{1}{n_i(t)} \right| \leq 1 - \frac{1}{n_i(t)}\Bigg\}$$ Setting $j := \operatorname*{arg\,max}_i n_i(t)$, clearly $\mathcal{B}_i(t) \subseteq \mathcal{B}_j(t)$. Since $1 - \frac{1}{n_i(t)} < 1$ for all $i$, then all the disks $\mathcal{B}_i(t)$ are proper subsets of the following unit disk: $$\Bigg\{z \in \mathbb{C}:\left| z - \frac{1}{n_j(t)} \right| \leq 1\Bigg\}$$ Note that Lemma \[lemma:simple-calcdiff-matrix\] also holds for the **influencing** neighbors graph (Definition \[def:influencing-neighbors-graph\]). Denoting $\tilde{\theta}(t) = [\theta_i(t)]$ ($0 \leq i \leq n-1$), we have that: $$\label{eq:influencing-heading-system} \tilde{\theta}(t+1) = (I+\tilde{D}(t))^{-1}(I+\tilde{A}(t)) \tilde{\theta}(t) =: \tilde{P}(t) \tilde{\theta}(t)$$ Notice that this heading system induces a heading system for each connected component of the **influencing** neighbors graph at time step $0$. This heading system can be viewed while only considering the orientations of the agents which correspond to this specific connected component. We shall phrase this formally in the following lemma: \[lemma:connected-component-normalized-laplacian\] Let $C$ be some connected component of $\tilde{\mathcal{G}}(0)$. We denote by $\tilde{\theta} ^ C (t)$ the orientations vector which corresponds to the agents in $C$. Then, $C$ induces a topology $\tilde{\mathcal{G}}(0)(C)$ (according to Definition \[def:induced-subgraph\]), with a normalized Perron matrix $\tilde{P} ^ C(t)$ for which $\tilde{\theta} ^ C (t+1) = \tilde{P} ^ C(t) \tilde{\theta} ^ C (t)$ according to Equation \[eq:influencing-heading-system\]. We denote by $n(C)$ the number of agents which correspond to $C$. Assuming that $a_{i_1}, \dots ,a_{i_{n(C)}}$ are those agents, we denote by $\tilde{\theta} ^ C (t) := [\theta_{i_1} (t+1), \dots, \theta_{i_{n(C)}} (t+1)]$ the orientations vector associated with the connected component $C$ at time step $t$. We denote by $\tilde{P} ^ C(t) \in \mathbb{R} ^ {n(C) \times n(C)}$ the Perron matrix which results after omitting all the rows and columns in $\tilde{P}(t)$ except for those that correspond to the indexes $i_1, \dots ,i_{n(C)}$. Clearly, we have that $\tilde{\theta} ^ C (t+1) = \tilde{P} ^ C(t) \tilde{\theta} ^ C (t)$ according to Equation \[eq:influencing-heading-system\]. The convergence analysis of this discrete-time algorithm in Subsection \[sec:fixed-topology\] relies on Perron-Frobenius Theorem @horn1985johnson, which is stated as follows: \[theorem:perron-frobenius\] (**Perron-Frobenius Theorem, 1907/1912**) Let $M$ be a primitive nonnegative matrix. Then, $M$ has left and right eigenvectors $w$ and $v$ (respectively), satisfying $Mv = v, w^T M = w^T$, and $v^T w = 1$. In particular: $\lim_{t \rightarrow \infty} M^t = v w^T$. Fixed Topology {#sec:fixed-topology} -------------- In this section, we deal with the behaviour an influencing agent as well as its influence has upon a connected component in a **fixed topology**, after it is inserted into the neighborhood of a flocking agent which corresponds to some vertex in this connected component. According to Definition \[def:fixed-topology\], it holds that there exists some balanced digraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ such that $\mathcal{G}(t) = \mathcal{G}$ for any time step $t$. We denote this graph's adjacency matrix, degree matrix, Perron matrix and Laplacian matrix by $A,D,P,L$ (respectively). Similarly, considering the influencing neighbors graph, it holds that there exists some balanced digraph $\mathcal{\tilde{G}}=(\mathcal{\tilde{V}},\mathcal{\tilde{E}})$ such that $\mathcal{\tilde{G}}(t) = \mathcal{\tilde{G}}$ for any time step $t$. We denote this graph's adjacency matrix, degree matrix, Perron matrix and Laplacian matrix by $\tilde{A},\tilde{D},\tilde{P},\tilde{L}$ (respectively). First, we shall describe the influence an influencing agent has upon some connected component, after it is inserted into the neighborhood of a flocking agent which corresponds to some vertex in this connected component. We will be considering each definition for the global orientation of both the flocking agents and the influencing agents. ### Discrete-Time Case {#sec:dt-fixed} **We will first consider Equation \[eq:orientation-perron\]**. The following theorem gives us the orientation the influencing agents should adopt in order to make the flocking agents in some connected component converge to their desired orientation. \[theorem:orientation-perron-influence-same-orient\] Consider a **fixed topology** network $\mathcal{\tilde{G}}$ of agents, where the flocking agents update their global orientation according to Equation \[eq:orientation-perron\], with a Perron matrix $\tilde{P}= I - \varepsilon \tilde{P}$ and maximum degree $\Delta = \max_i(\sum_{j \neq i} \tilde{A}[i,j])$. Let $C$ be some connected component of $\mathcal{\tilde{G}}$. Let $\alpha_i$ be the orientation the flocking agents associated with this connected component should converge to. Let $\tilde{\theta}^C(0)$ be fixed. Assuming that $0 < \varepsilon < \frac{1}{\Delta}$ and $m(C)$ influencing agents are inserted into this connected component, **all** the influencing agents should **constantly** adopt the orientation $\alpha_i$ in order for the flocking agents to converge to $\alpha_i$. Considering Lemma \[lemma:connected-component-normalized-laplacian\], note that: $$\tilde{\theta}^C(t+1) = \tilde{P}^C \tilde{\theta}^C(t) = (\tilde{P}^C)^t \tilde{\theta}^C(0)$$ Thus, a consensus is reached in discrete-time, if the limit $\lim_{t \rightarrow \infty} (\tilde{P}^C)^t$ exists. According to Perron-Frobenius Theorem, this limit exists for primitive matrices. Therefore, we denote $\alpha := \lim_{t \rightarrow \infty} \tilde{\theta}^C_j(t)$, for a flocking agent $a_j \in A^F$, which corresponds to the vertex $j$ in the connected component $C$. Considering Subsection \[sec:flocking-model\]-model, we note that $k_j(0) \geq 1$ since $C$ is a connected component. Moreover, since the topology is fixed, $k_j(t)=k_j(0)$ and $m_j(t)=m_j(0)$ for any time step $t$. In particular, $N_j(0)=N_j(t)$ for any time step $t$. Necessarily, there exists a flocking agent for which some influencing agent lies within its neighborhood. Without loss of generality, we assume that $a_j$ is such a flocking agent, i.e., $m_j(t) \geq 1$. The following holds according to the definition of the Perron matrix $\tilde{P}^C$: $$\tilde{\theta}^C_j(t+1) = \tilde{\theta}^C_j(t) +$$ $$+ \varepsilon \sum_{\ell_1 \in N_j(0) \cap A^F} (\tilde{\theta}^C_{\ell_1}(t) - \tilde{\theta}^C_j(t)) + \varepsilon \sum_{\ell_2 \in N_j(0) \cap A^D} (\tilde{\theta}^C_{\ell_2}(t) - \tilde{\theta}^C_j(t))$$ Since all the influencing agents are **constantly** adopting the orientation $\alpha_i$, we have that: $$\tilde{\theta}^C_j(t+1) =$$ $$= \tilde{\theta}^C_j(t) + \varepsilon \sum_{\ell_1 \in N_j(0) \cap A^F} (\tilde{\theta}^C_{\ell_1}(t) - \tilde{\theta}^C_j(t)) + \varepsilon \sum_{\ell_2 \in N_j(0) \cap A^D} (\alpha_i - \tilde{\theta}^C_j(t)) =$$ $$= \tilde{\theta}^C_j(t) + \varepsilon \sum_{\ell_1 \in N_j(0) \cap A^F} (\tilde{\theta}^C_{\ell_1}(t) - \tilde{\theta}^C_j(t)) + \varepsilon m_j(0) (\alpha_i - \tilde{\theta}^C_j(t))$$ Taking the limit $t \rightarrow \infty$ in both sides results in the following: $$\alpha = \alpha + \varepsilon \sum_{\ell_1 \in N_j(0) \cap A^F} (\alpha - \alpha) + \varepsilon m_j(0) (\alpha_i - \alpha) \Rightarrow \boxed{\alpha = \alpha_i}$$ The speed of reaching a consensus is the key in design of the network topology as well as analysis of the influence the influencing agents have upon the flocking agents in a given connected component. To demonstrate this in the discrete-time case, we note that the following quantity is invariant (while recalling that the Perron matrix $\tilde{P}$ is row stochastic - $1^T \tilde{P}=\tilde{P}$): $$AVG_1(t+1) := \frac{1}{n}1^T \tilde{\theta}(t+1) = \frac{1}{n} (1^T \tilde{P}) \theta(t) = \frac{1}{n} 1^T \tilde{\theta}(t) = AVG_1(t)$$ This invariance allows to define the *disagreement vector* @olfati2004consensus: $$\label{eq:dis-vec} \delta(t) = \tilde{\theta}(t) - AVG_1(t) 1$$ Similarly to Lemma \[lemma:connected-component-normalized-laplacian\], Equation \[eq:dis-vec\] induces a disagreement vector for each connected component of the flocking neighbors graph. We shall phrase this formally in the following lemma: \[lemma:induced-dis-vec-linear\] Let $C$ be some connected component of $\mathcal{\tilde{G}}$. We denote by $\tilde{\theta} ^ C (t),\delta^C(t)$ the orientations vector and disagreement vector (respectively), which correspond to the flocking agents in $C$. We also denote $Avg^C(t) := \frac{1}{|C|}1^T \tilde{\theta}^C(t)$. Then, the connected component $C$ induces the disagreement vector $\delta^C(t) = \tilde{\theta}^C(t) - Avg^C(t) 1$. Furthermore, the discrete-time dynamics of the disagreement vector is given as follows: $$\label{eq:dis-vec-dt} \delta(t+1) = \tilde{P} \delta(t)$$ We make the following definitions: \[def:eigenvalues\] (*Eigenvalues of a Matrix*) Let $\mathcal{M}$ be a matrix with real eigenvalues. We denote by $\lambda_1(\mathcal{M}) \leq \lambda_2(\mathcal{M}) \leq \ldots \leq \lambda_e(\mathcal{M})$ the eigenvalues of the matrix $\mathcal{M}$, ordered sequentially in an ascending order. \[def:sym-part\] (*Symmetric Part of a Matrix*) Let $\mathcal{M}$ be a matrix. We denote its *symmetric part* by $\mathcal{M}^{Sym} = \frac{\mathcal{M}+\mathcal{M}^T}{2}$. Thus, based on @godsil2013algebraic and *Theorem 3* from @olfati2004consensus, the following lemma gives us a property of second eigenvalue: \[lemma:eigenvalues-sym\] Let $\mathcal{G}$ be an balanced digraph with Laplacian $L$ with a symmetric part $L^{Sym} = \frac{L+L^T}{2}$ and with Perron $P=I - \varepsilon L$ with a symmetric part $P^{Sym} = \frac{P+P^T}{2}$. Then, for all disagreement vectors $\delta$: 1. $\lambda_2 = \min_{1^T\delta=0}\frac{\delta^T L \delta}{\delta^T \delta}$ with $\lambda_2 =\lambda_2(L^{Sym})$, i.e.: $$\delta^T L \delta \geq \lambda_2 ||\delta||^2$$ 2. $\mu_2 = \min_{1^T\delta=0}\frac{\delta^T P \delta}{\delta^T \delta}$ with $\mu_2 =1- \varepsilon \lambda_2$, i.e.: $$\delta^T P \delta \geq \mu_2 ||\delta||^2$$ Now, we shall define the notion of exponential convergence: \[def:exp-conv\] (*Exponential Convergence*) We say that $f(t)$ *converges exponentially* toward $f^\infty$ with a rate $r < 0$ if $||f(t) - f^\infty|| \leq O( e^{rt})$. Using Lemma \[lemma:eigenvalues-sym\], *Corollary 2* in @olfati2004consensus characterizes the performance of consensus. It is stated as follows: \[lemma:dt-conv-rate\] Consider a **fixed topology** network $\mathcal{G}$ which is a strongly connected balanced digraph. Then, the following statements hold: 1. The continuous-time disagreement vector $\delta$, as the solution for Equation \[eq:dis-vec-ct\], converges exponentially with a rate which equals to $\log(\mu_2)$, where $\mu_2 =\lambda_2(P^{Sym})$ with $P^{Sym} = \frac{P+P^T}{2}$, i.e.: $$||\delta(t+1)|| \leq \mu_2||\delta(t)||$$ 2. $\Phi(\delta) = \delta(t)^T\delta(t)$ is a smooth, positive-definite and proper function, which acts as a valid Lyapunov function for the disagreement dynamics. Considering the first statement of this lemma, we infer that for any time step $t$ (by induction): $$\label{eq:dis-vec-dt-vanish} ||\delta(t)|| \leq \mu_2 ^ t||\delta(0)||$$ Following *Lemma 3* from @olfati2007consensus, $P$ is a primitive matrix and $0 < \mu_2 < 1$. Thus, the vanishing of the disagreement vector is guaranteed. Moreover, considering the definition of exponential convergence in Definition \[def:exp-conv\], note that: $$\mu_2 ^ t = e ^{t \log(\mu_2)}$$ Thus, the convergence rate equals to $\log(\mu_2)$, as stated in the first statement of the lemma. This result is consistent with the Definition \[def:exp-conv\] since $\log(\mu_2) < 0$ due to $0 < \mu_2 < 1$. Since $\theta(t) = \delta(t) + Avg(t) 1$, this also means that average-consensus is globally asymptotically reached with a speed faster or equal to $\mu_2 =\lambda_2(P^{Sym})$ with $P^{Sym} = \frac{P+P^T}{2}$. Moreover, this lemma also holds for any connected component of the influencing neighbors graph $\mathcal{\tilde{G}}$ (while considering Lemma \[lemma:induced-dis-vec-linear\]). **We shall now consider Equation \[eq:orientation-calcdiff\]**. The following lemma gives us the number of time steps it take for the flocking agents in some connected component to converge to their desired orientation. \[lemma:orientation-calcdiff-influence\] Consider a **fixed topology** network $\mathcal{G}$ of flocking agents given by Equation \[eq:orientation-calcdiff\]. Let $C$ be some connected component of $\mathcal{G}$. Let $\alpha_i$ be the orientation the flocking agents associated with this connected component should converge to. Assuming $m(C)$ influencing agents are inserted into this connected component, they can influence the $|C|$ flocking agents to align to $\alpha_i$ within $Z = 1 + \Big\lceil \frac{\frac{\pi}{2}}{\frac{m(C)\pi}{|C|+m(C)}-\epsilon} \Big\rceil$ time steps. According to *Lemma 4* in @genter2013ad, this can be done if $2\pi > (Z-2)\frac{m(C)\pi}{|C|+m(C)}-\epsilon$ and $\theta_i(t) - \alpha_i \leq (Z-1)\frac{m(C)\pi}{|C|+m(C)}-\epsilon + \beta_{ij}(t) + \theta_i(t) - \theta_i(t+1) + \pi$. Clearly, the first inequality always holds. For the second one, noting that $\beta_{ij}(t) \leq \pi$ by definition and that $\theta_i(t)$ is on both of its sides, it is equivalent to the inequality $\theta_i(t+1) - \alpha_i \leq (Z-1)\frac{m(C)\pi}{|C|+m(C)}-\epsilon + 2\pi$. Since $\theta_i(t+1) - \alpha_i \leq 2\pi$, this also holds. For characterizing the behaviour each influencing agent should adopt, we consider the simplification of the update rule defined by Equation \[eq:orientation-calcdiff\]. Since we consider a fixed topology, according to Definition \[def:fixed-topology\], it holds that there exists some balanced digraph $\tilde{\mathcal{G}}=(\tilde{\mathcal{V}},\tilde{\mathcal{E}})$ such that $\tilde{\mathcal{G}}(t) = \tilde{\mathcal{G}}$ for any time step $t$. We denote this graph's adjacency matrix and degree matrix by $\tilde{A},\tilde{D}$ (respectively). Thus, by Equation \[eq:simplified-calcdiff\]: $$\label{eq:fixed-simplified-calcdiff} \tilde{\theta}(t+1) = (I+\tilde{D})^{-1}(I+\tilde{A}) \tilde{\theta}(t) := \tilde{P} \tilde{\theta}(t)$$ We would like to characterize the group decision value of a connected component in the influencing neighbors graph at time step $0$. The following lemma give us this desired characterization: The following theorem gives us the orientation the influencing agents should adopt in order to make the flocking agents in some connected component converge to their desired orientation. \[theorem:orientation-normalized-perron-influence\] Consider a **fixed topology** network $\tilde{\mathcal{G}}$ of agents given by Equation \[eq:fixed-simplified-calcdiff\], with a Perron matrix $\tilde{P} = (I+\tilde{D})^{-1}(I+\tilde{A})$. Let $C$ be some connected component of $\tilde{\mathcal{G}}$. We denote by $|C|$ the number of agents which correspond to $C$ and assume that $a_{i_1}, \dots ,a_{i_{|C|}}$ are those agents. Let $\alpha_i$ be the orientation the agents associated with this connected component should converge to. Let $\theta(0)$ be fixed. Assuming that $m(C)$ influencing agents are inserted into this connected component, in order for the flocking agents to converge to $\alpha_i$, **all** the influencing agents should **constantly** adopt the orientation $\alpha_i$ in order for the flocking agents to converge to $\alpha_i$. Considering Lemma \[lemma:connected-component-normalized-laplacian\], note that: $$\tilde{\theta}^C(t+1) = \tilde{P}^C \tilde{\theta}^C(t) = (\tilde{P}^C)^t \tilde{\theta}^C(0)$$ Thus, a consensus is reached in discrete-time, if the limit $\lim_{t \rightarrow \infty} (\tilde{P}^C)^t$ exists. By Lemma \[lemma:normalized-perron-properties\], $\tilde{P} ^ C$ is row stochastic, that is: $\tilde{P} ^ C 1 = 1$. By Perron-Frobenius Theorem, $\tilde{P} ^ C$ has a left eigenvector $w \in \mathbb{R} ^ {|C|}$ for which: 1. $w^T \tilde{P} ^ C = w^T$ 2. $1^T w = 1 \Rightarrow \sum_{j = 1} ^ {|C|} w_j = 1$ 3. $\lim_{t \rightarrow \infty} (\tilde{P} ^ C) ^t = 1 w^T$ Therefore, we denote $\alpha := \lim_{t \rightarrow \infty} \tilde{\theta}^C_j(t)$, for a flocking agent $a_j \in A^F$, which corresponds to the vertex $j$ in the connected component $C$. Considering Subsection \[sec:flocking-model\]-model, we note that $k_j(0) \geq 1$ since $C$ is a connected component. Moreover, since the topology is fixed, $k_j(t)=k_j(0)$ and $m_j(t)=m_j(0)$ for any time step $t$. In particular, $N_j(0)=N_j(t)$ for any time step $t$. Necessarily, there exists a flocking agent for which some influencing agent lies within its neighborhood. Without loss of generality, we assume that $a_j$ is such a flocking agent, i.e., $m_j(t) \geq 1$. The following holds according to Equation \[eq:simplified-calcdiff\] and Lemma \[lemma:simple-calcdiff-matrix\]: $$\tilde{\theta}^C_j(t+1) = \frac{1}{n_j(0)} \sum_{\ell_1 \in N_j(0) \cap A^F} \tilde{\theta}^C_{\ell_1}(t) + \frac{1}{n_j(0)} \sum_{\ell_2 \in N_j(0) \cap A^D} \tilde{\theta}^C_{\ell_2}(t)$$ Since all the influencing agents are **constantly** adopting the orientation $\alpha_i$, we have that: $$\tilde{\theta}^C_j(t+1) = \frac{1}{n_j(0)} \sum_{\ell_1 \in N_j(0) \cap A^F} \tilde{\theta}^C_{\ell_1}(t) + \frac{1}{n_j(0)} \sum_{\ell_2 \in N_j(0) \cap A^D} \alpha_i =$$ $$= \frac{1}{n_j(0)} \sum_{\ell_1 \in N_j(0) \cap A^F} \tilde{\theta}^C_{\ell_1}(t) + \frac{m_j(0)}{n_j(0)} \alpha_i$$ Taking the limit $t \rightarrow \infty$ in both sides results in the following: $$\alpha = \frac{1}{n_j(0)} \sum_{\ell_1 \in N_j(0) \cap A^F} \alpha + \frac{m_j(0)}{n_j(0)} \alpha_i \Rightarrow$$ $$\Rightarrow n_j(0)\alpha = k_j(0)\alpha + m_j(0)\alpha_i \Rightarrow$$ $$\Rightarrow (n_j(0) - k_j(0))\alpha = m_j(0)\alpha_i \Rightarrow \boxed{\alpha = \alpha_i}$$ where the last transition follows from the fact that $n_j(0) = k_j(0) + m_j(0)$. ### Continuous-Time Case {#sec:ct-fixed} **We will first consider Equation \[eq:global-orient-linear\]**. Similarly to Lemma \[lemma:connected-component-normalized-laplacian\], Equation \[eq:global-orient-linear\] induces a heading system for each connected component of the influencing neighbors graph at time step $0$. We shall phrase this formally in the following lemma: \[lemma:connected-component-global-orient-linear\] Let $C$ be some connected component of $\mathcal{\tilde{G}}(0)$. We denote by $\tilde{\theta} ^ C (t)$ the orientations vector which corresponds to the flocking agents in $C$. Then, $C$ induces a topology $\tilde{\mathcal{G}}(0)(C)$ (according to Definition \[def:induced-subgraph\]), with a Laplacian matrix $\tilde{L} ^ C(t)$ for which $\dot{\tilde{\theta}} ^ C (t+1) = -\tilde{L} ^ C (t) \tilde{\theta} ^ C (t)$ according to Equation \[eq:global-orient-linear\]. The following theorem gives us the orientation the influencing agents should adopt in order to make the flocking agents in some connected component converge to their desired orientation. \[theorem:orientation-linear-influence-same-orient\] Consider a **fixed topology** network $\mathcal{\tilde{G}}$ of agents (both flocking an influencing) given by Equation \[eq:global-orient-linear\], with a Laplacian matrix $\tilde{L}$. Let $C$ be some connected component of $\mathcal{\tilde{G}}$. Let $\alpha_i$ be the orientation the agents associated with this connected component should converge to. Let $\theta(0)$ be fixed. Assuming that $m(C)$ influencing agents are inserted into this connected component, **all** the influencing agents should **constantly** adopt the orientation $\alpha_i$ in order for the flocking agents to converge to $\alpha_i$. Considering Lemma \[lemma:connected-component-global-orient-linear\], note that the solution of the heading system induced by the connected component $C$ is as follows: $$\tilde{\theta}^C(t+1) = e^{- t \tilde{L}^C} \cdot \tilde{\theta}^C(0)$$ Thus, a consensus is reached in discrete-time, if the limit $\lim_{t \rightarrow \infty} e^{- t \tilde{L}^C}$ exists. By *Theorem 3* in @olfati2004consensus, this limit exists. Therefore, we denote $\alpha := \lim_{t \rightarrow \infty} \tilde{\theta}^C_j(t)$, for a flocking agent $a_j \in A^F$, which corresponds to the vertex $j$ in the connected component $C$. Clearly, this means that: $\lim_{t \rightarrow \infty} \dot{\tilde{\theta}}_j ^ C (t) = 0$. Considering Subsection \[sec:flocking-model\]-model, we note that $k_j(0) \geq 1$ since $C$ is a connected component. Moreover, since the topology is fixed, $k_j(t)=k_j(0)$ and $m_j(t)=m_j(0)$ for any time step $t$. In particular, $N_j(0)=N_j(t)$ for any time step $t$. Necessarily, there exists a flocking agent for which some influencing agent lies within its neighborhood. Without loss of generality, we assume that $a_j$ is such a flocking agent, i.e., $m_j(t) \geq 1$. Let $\tilde{A} ^ C$ be the adjacency matrix which corresponds to the topology induced by the connected component $C$. The following holds according to Equation \[eq:global-orient-linear\] and Lemma \[lemma:global-orient-linear-matrix\]: $$\dot{\tilde{\theta}}_j ^ C (t+1) = \sum_{\ell_1 \in N_j(0) \cap A^F} \tilde{A} ^ C[j,\ell_1] (\tilde{\theta}^C_{\ell_1}(t) - \tilde{\theta}^C_j(t)) +$$ $$+\sum_{\ell_2 \in N_j(0) \cap A^D} \tilde{A} ^ C[j,\ell_2] (\tilde{\theta}^C_{\ell_2}(t) - \tilde{\theta}^C_j(t))$$ Since all the influencing agents are **constantly** adopting the orientation $\alpha_i$, we have that: $$\dot{\tilde{\theta}}_j ^ C (t+1) = \sum_{\ell_1 \in
{'source': 'arXiv_out/2010'}