A. Stephen Morse

Shaoshuai Mou, A. Stephen Morse, Mohamed Ali Belabbas et al.

By an undirected rigid formation of mobile autonomous agents is meant a formation based on graph rigidity in which each pair of "neighboring" agents is responsible for maintaining a prescribed target distance between them. In a recent paper a systematic method was proposed for devising gradient control laws for asymptotically stabilizing a large class of rigid, undirected formations in two dimensional space assuming all agents are described by kinematic point models. The aim of this paper is to explain what happens to such formations if neighboring agents have slightly different understandings of what the desired distance between them is supposed to be or equivalently if neighboring agents have differing estimates of what the actual distance between them is. In either case, what one would expect would be a gradual distortion of the formation from its target shape as discrepancies in desired or sensed distances increase. While this is observed for the gradient laws in question, something else quite unexpected happens at the same time. It is shown that for any rigidity-based, undirected formation of this type which is comprised of three or more agents, that if some neighboring agents have slightly different understandings of what the desired distances between them are suppose to be, then almost for certain, the trajectory of the resulting distorted but rigid formation will converge exponentially fast to a closed circular orbit in two-dimensional space which is traversed periodically at a constant angular speed.

Shaoshuai Mou, Ji Liu, A. Stephen Morse

A distributed algorithm is described for solving a linear algebraic equation of the form $Ax=b$ assuming the equation has at least one solution. The equation is simultaneously solved by $m$ agents assuming each agent knows only a subset of the rows of the partitioned matrix $(A,b)$, the current estimates of the equation's solution generated by its neighbors, and nothing more. Each agent recursively updates its estimate by utilizing the current estimates generated by each of its neighbors. Neighbor relations are characterized by a time-dependent directed graph $\mathbb{N}(t)$ whose vertices correspond to agents and whose arcs depict neighbor relations. It is shown that for any matrix $A$ for which the equation has a solution and any sequence of "repeatedly jointly strongly connected graphs" $\mathbb{N}(t)$, $t=1,2,\ldots$, the algorithm causes all agents' estimates to converge exponentially fast to the same solution to $Ax=b$. It is also shown that the neighbor graph sequence must actually be repeatedly jointly strongly connected if exponential convergence is to be assured. A worst case convergence rate bound is derived for the case when $Ax=b$ has a unique solution. It is demonstrated that with minor modification, the algorithm can track the solution to $Ax = b$, even if $A$ and $b$ are changing with time, provided the rates of change of $A$ and $b$ are sufficiently small. It is also shown that in the absence of communication delays, exponential convergence to a solution occurs even if the times at which each agent updates its estimates are not synchronized with the update times of its neighbors. A modification of the algorithm is outlined which enables it to obtain a least squares solution to $Ax=b$ in a distributed manner, even if $Ax=b$ does not have a solution.

Lili Wang, Ji Liu, A. Stephen Morse et al.

A simply structured distributed observer is described for estimating the state of a discrete-time, jointly observable, input-free, linear system whose sensed outputs are distributed across a time-varying network. It is explained how to construct the local estimators which comprise the observer so that their state estimation errors all converge exponentially fast to zero at a fixed, but arbitrarily chosen rate provided the network's graph is strongly connected for all time. This is accomplished by exploiting several well-known properties of invariant subspaces plus several kinds of suitably defined matrix norms.

Daniel Fullmer, Lili Wang, A. Stephen Morse

A distributed algorithm is described for finding a common fixed point of a family of $m>1$ nonlinear maps $M_i : \mathbb{R}^n \rightarrow \mathbb{R}^n$ assuming that each map is a paracontraction and that such a common fixed point exists. The common fixed point is simultaneously computed by $m$ agents assuming each agent $i$ knows only $M_i$, the current estimates of the fixed point generated by its neighbors, and nothing more. Each agent recursively updates its estimate of the fixed point by utilizing the current estimates generated by each of its neighbors. Neighbor relations are characterized by a time-dependent directed graph $\mathbb{N}(t)$ whose vertices correspond to agents and whose arcs depict neighbor relations. It is shown that for any family of paracontractions $M_i, i \in \{1,2,\ldots,m\}$ which has at least one common fixed point, and any sequence of strongly connected neighbor graphs $\mathbb{N}(t)$, $t=1,2,\ldots$, the algorithm causes all agent estimates to converge to a common fixed point.

Fengjiao Liu, A. Stephen Morse

It is well known that the "fixed spectrum" {i.e., the set of fixed modes} of a multi-channel linear system plays a central role in the stabilization of such a system with decentralized control. A parameterized multi-channel linear system is said to be "structurally complete" if it has no fixed spectrum for almost all parameter values. Necessary and sufficient algebraic conditions are presented for a multi-channel linear system with dependent parameters to be structurally complete. An equivalent graphical condition is also given for a certain type of parameterization.

Fengjiao Liu, A. Stephen Morse

One version of the concept of structural controllability defined for single-input systems by Lin and subsequently generalized to multi-input systems by others, states that a parameterized matrix pair $(A, B)$ whose nonzero entries are distinct parameters, is structurally controllable if values can be assigned to the parameters which cause the resulting matrix pair to be controllable. In this paper the concept of structural controllability is broadened to allow for the possibility that a parameter may appear in more than one location in the pair $(A, B)$. Subject to a certain condition on the parameterization called the "binary assumption", an explicit graph-theoretic characterization of such matrix pairs is derived.

Fengjiao Liu, A. Stephen Morse

Conditions for the existence of a fixed spectrum \{i.e., the set of fixed modes\} for a multi-channel linear system have been known for a long time. The aim of this paper is to reestablish one of these conditions using a new and transparent approach based on matroid theory.

Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse et al.

The paper develops a technique for solving a linear equation $Ax=b$ with a square and nonsingular matrix $A$, using a decentralized gradient algorithm. In the language of control theory, there are $n$ agents, each storing at time $t$ an $n$-vector, call it $x_i(t)$, and a graphical structure associating with each agent a vertex of a fixed, undirected and connected but otherwise arbitrary graph $\mathcal G$ with vertex set and edge set $\mathcal V$ and $\mathcal E$ respectively. We provide differential equation update laws for the $x_i$ with the property that each $x_i$ converges to the solution of the linear equation exponentially fast. The equation for $x_i$ includes additive terms weighting those $x_j$ for which vertices in $\mathcal G$ corresponding to the $i$-th and $j$-th agents are adjacent. The results are extended to the case where $A$ is not square but has full row rank, and bounds are given on the convergence rate.