Brian D. O. Anderson

Zhiyong Sun, Myoung-Chul Park, Brian D. O. Anderson et al.

Most rigid formation controllers reported in the literature aim to only stabilize a rigid formation shape, while the formation orientation is not controlled. This paper studies the problem of controlling rigid formations with prescribed orientations in both 2-D and 3-D spaces. The proposed controllers involve the commonly-used gradient descent control for shape stabilization, and an additional term to control the directions of certain relative position vectors associated with certain chosen agents. In this control framework, we show the minimal number of agents which should have knowledge of a global coordinate system (2 agents for a 2-D rigid formation and 3 agents for a 3-D rigid formation), while all other agents do not require any global coordinate knowledge or any coordinate frame alignment to implement the proposed control. The exponential convergence to the desired rigid shape and formation orientation is also proved. Typical simulation examples are shown to support the analysis and performance of the proposed formation controllers.

Mengbin Ye, Minh Hoang Trinh, Young-Hun Lim et al.

In this paper, and inspired by the recent discrete-time model in [1,2], we study two continuous-time opinion dynamics models (Model 1 and Model 2) where the individuals discuss opinions on multiple logically interdependent topics. The logical interdependence between the different topics is captured by a `logic' matrix, which is distinct from the Laplacian matrix capturing interactions between individuals. For each of Model 1 and Model 2, we obtain a necessary and sufficient condition for the network to reach to a consensus on each separate topic. The condition on Model 1 involves a combination of the eigenvalues of the logic matrix and Laplacian matrix, whereas the condition on Model 2 requires only separate conditions on the logic matrix and Laplacian matrix. Further investigations of Model 1 yields two sufficient conditions for consensus, and allow us to conclude that one way to guarantee a consensus is to reduce the rate of interaction between individuals exchanging opinions. By placing further restrictions on the logic matrix, we also establish a set of Laplacian matrices which guarantee consensus for Model 1. The two models are also expanded to include stubborn individuals, who remain attached to their initial opinions. Sufficient conditions are obtained for guaranteeing convergence of the opinion dynamics system, with the final opinions generally being at a persistent disagreement. Simulations are provided to illustrate the results.

Yang Liu, Christian Lageman, Brian D. O. Anderson et al.

We study the approach to obtaining least squares solutions to systems of linear algebraic equations over networks by using distributed algorithms. Each node has access to one of the linear equations and holds a dynamic state. The aim for the node states is to reach a consensus as a least squares solution of the linear equations by exchanging their states with neighbors over an underlying interaction graph. A continuous-time distributed least squares solver over networks is developed in the form of the famous Arrow-Hurwicz-Uzawa flow. A necessary and sufficient condition is established on the graph Laplacian for the continuous-time distributed algorithm to give the least squares solution in the limit, with an exponentially fast convergence rate. The feasibility of different fundamental graphs is discussed including path graph, star graph, etc. Moreover, a discrete-time distributed algorithm is developed by Euler's method, converging exponentially to the least squares solution at the node states with suitable step size and graph conditions. The exponential convergence rate for both the continuous-time and discrete-time algorithms under the established conditions is confirmed by numerical examples. Finally, we investigate the performance of the proposed flow under switching networks, and surprisingly, switching networks at high switching frequencies can lead to approximate least square solvers even if all graphs in the switching signal fail to do so in the absence of structure switching.

Yuzhen Qin, Ming Cao, Brian D. O. Anderson

This paper presents new sufficient conditions for convergence and asymptotic or exponential stability of a stochastic discrete-time system, under which the constructed Lyapunov function always decreases in expectation along the system's solutions after a finite number of steps, but without necessarily strict decrease at every step, in contrast to the classical stochastic Lyapunov theory. As the first application of this new Lyapunov criterion, we look at the product of any random sequence of stochastic matrices, including those with zero diagonal entries, and obtain sufficient conditions to ensure the product almost surely converges to a matrix with identical rows; we also show that the rate of convergence can be exponential under additional conditions. As the second application, we study a distributed network algorithm for solving linear algebraic equations. We relax existing conditions on the network structures, while still guaranteeing the equations are solved asymptotically.

Yang Liu, Youcheng Lou, Brian D. O. Anderson et al.

This paper presents a first-order {distributed continuous-time algorithm} for computing the least-squares solution to a linear equation over networks. Given the uniqueness of the solution, with nonintegrable and diminishing step size, convergence results are provided for fixed graphs. The exact rate of convergence is also established for various types of step size choices falling into that category. For the case where non-unique solutions exist, convergence to one such solution is proved for constantly connected switching graphs with square integrable step size, and for uniformly jointly connected switching graphs under the boundedness assumption on system states. Validation of the results and illustration of the impact of step size on the convergence speed are made using a few numerical examples.

Baoqi Huang, Tao Li, Brian D. O. Anderson et al.

In this paper, we study performance limits of sensor localization from a novel perspective. Specifically, we consider the Cramer-Rao Lower Bound (CRLB) in single-hop sensor localization using measurements from received signal strength (RSS), time of arrival (TOA) and bearing, respectively, but differently from the existing work, we statistically analyze the trace of the associated CRLB matrix (i.e. as a scalar metric for performance limits of sensor localization) by assuming anchor locations are random. By the Central Limit Theorems for $U$-statistics, we show that as the number of the anchors increases, this scalar metric is asymptotically normal in the RSS/bearing case, and converges to a random variable which is an affine transformation of a chi-square random variable of degree 2 in the TOA case. Moreover, we provide formulas quantitatively describing the relationship among the mean and standard deviation of the scalar metric, the number of the anchors, the parameters of communication channels, the noise statistics in measurements and the spatial distribution of the anchors. These formulas, though asymptotic in the number of the anchors, in many cases turn out to be remarkably accurate in predicting performance limits, even if the number is small. Simulations are carried out to confirm our results.

Myoung-Chul Park, Zhiyong Sun, Minh Hoang Trinh et al.

In this paper, we propose a distance-based formation control strategy that can enable four mobile agents, which are modelled by a group of single-integrators, to achieve the desired formation shape specified by using six consistent inter-agent distances in a 2-dimensional space. The control law is closely related to a gradient-based control law formed from a potential function reflecting the error between the actual inter-agent distances and the desired inter-agent distances. There are already control strategies achieving the same objective in a distance-based control manner in the literature, but the results do not yet include a global as opposed to local stability analysis. We propose a control strategy modified from the existing gradient-based control law so that we can achieve almost global convergence to the desired formation shape, and the control law uses known properties for an associated formation shape control problem involving a four-agent tetrahedron formation in 3-dimensional space. Simulation results verifying our analysis are also presented.

Toshiharu Sugie, Brian D. O. Anderson, Zhiyong Sun et al.

This paper considers a formation shape control problem for point agents in a two-dimensional ambient space, where the control is distributed, is based on achieving desired distances between nominated agent pairs, and avoids the possibility of reflection ambiguities. This has potential applications for large-scale multi-agent systems having simple information exchange structure. One solution to this type of problem, applicable to formations with just three or four agents, was recently given by considering a potential function which consists of both distance error and signed triangle area terms. However, it seems to be challenging to apply it to formations with more than four agents. This paper shows a hierarchical control strategy which can be applicable to any number of agents based on the above type of potential function and a formation shaping incorporating a grouping of equilateral triangles, so that all controlled distances are in fact the same. A key analytical result and some numerical results are shown to demonstrate the effectiveness of the proposed method.

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.

Zhiyong Sun, Hector Garcia de Marina, Brian D. O. Anderson et al.

In this paper, we discuss quantization effects in rigid formation control systems when target formations are described by inter-agent distances. Because of practical sensing and measurement constraints, we consider in this paper distance measurements in their quantized forms. We show that under gradient-based formation control, in the case of uniform quantization, the distance errors converge locally to a bounded set whose size depends on the quantization error, while in the case of logarithmic quantization, all distance errors converge locally to zero. A special quantizer involving the signum function is then considered with which all agents can only measure coarse distances in terms of binary information. In this case, the formation converges locally to a target formation within a finite time. Lastly, we discuss the effect of asymmetric uniform quantization on rigid formation control.

Bomin Jiang, Zhiyong Sun, Brian D. O. Anderson et al.

Most current results on coverage control using mobile sensors require that one partitioned cell is associated with precisely one sensor. In this paper, we consider a class of coverage control problems involving higher order Voronoi partitions, motivated by applications where more than one sensor is required to monitor and cover one cell. Such applications are frequent in scenarios requiring the sensors to localize targets. We introduce a framework depending on a coverage performance function incorporating higher order Voronoi cells and then design a gradient-based controller which allows the multi-sensor system to achieve a local equilibrium in a distributed manner. The convergence properties are studied and related to Lloyd algorithm. We study also the extension to coverage of a discrete set of points. In addition, we provide a number of real world scenarios where our framework can be applied. Simulation results are also provided to show the controller performance.

Junfeng Wu, Guodong Shi, Brian D. O. Anderson et al.

In this paper, we investigate probabilistic stability of Kalman filtering over fading channels modeled by $\ast$-mixing random processes, where channel fading is allowed to generate non-stationary packet dropouts with temporal and/or spatial correlations. Upper/lower almost sure (a.s.) stabilities and absolutely upper/lower a.s. stabilities are defined for characterizing the sample-path behaviors of the Kalman filtering. We prove that both upper and lower a.s. stabilities follow a zero-one law, i.e., these stabilities must happen with a probability either zero or one, and when the filtering system is one-step observable, the absolutely upper and lower a.s. stabilities can also be interpreted using a zero-one law. We establish general stability conditions for (absolutely) upper and lower a.s. stabilities. In particular, with one-step observability, we show the equivalence between absolutely a.s. stabilities and a.s. ones, and necessary and sufficient conditions in terms of packet arrival rate are derived; for the so-called non-degenerate systems, we also manage to give a necessary and sufficient condition for upper a.s. stability.

Bomin Jiang, Brian D. O. Anderson, Hatem Hman

For a group of cooperating UAVs, localizing each other is often a key task. This paper studies the localization problem for a group of UAVs flying in 3D space with very limited information, i.e., when noisy distance measurements are the only type of inter-agent sensing that is available, and when only one UAV knows a global coordinate basis, the others being GPS-denied. Initially for a two-agent problem, but easily generalized to some multi-agent problems, constraints are established on the minimum number of required distance measurements required to achieve the localization. The paper also proposes an algorithm based on semidefinite programming (SDP), followed by maximum likelihood estimation using a gradient descent initialized from the SDP calculation. The efficacy of the algorithm is verified with experimental noisy flight data.

Manou Rosenberg, Mengbin Ye, Brian D. O. Anderson

The Euclidean Steiner tree problem, normally posed in two dimensions, seeks to connect a set of prescribed terminal nodes by placing additional nodes, known as Steiner points, with edges connecting such nodes either to another Steiner point or a terminal node, and with the placements minimising the sum of all the edge lengths of the associated tree. We consider a problem in which we start with a known solution to a Steiner tree problem, and the terminal positions are then perturbed. A first-order approximation theorem is established for efficiently updating the Steiner point positions to recover a Steiner tree solution after the perturbations to terminal nodes. Numerical examples illustrate the effectiveness of our approach (including a stepwise application for large perturbations) as well as its limitations.

Lorenzo Zino, Mengbin Ye, Brian D. O. Anderson

We study a continuous-time dynamical system of nodes diffusively coupled over a hierarchical network to examine the efficiency and performance tradeoffs that organizations, teams, and command and control units face while achieving coordination and sharing information across layers. Specifically, after defining a network structure that captures real-world features of hierarchical organizations, we use linear systems theory and perturbation theory to characterize the rate of convergence to a consensus state, and how effectively information can propagate through the network, depending on the breadth of the organization and the strength of inter-layer communication. Interestingly, our analytical insights highlight a fundamental performance tradeoff. Namely, networks that favor fast coordination will have decreased ability to share information that is generated in the lower layers of the organization and is to be passed up the hierarchy. Numerical results validate and extend our theoretical results.

Zhiyong Sun, Marcus Greiff, Anders Robertsson et al.

We consider the problem of cooperative motion coordination for multiple heterogeneous mobile vehicles subject to various constraints. These include nonholonomic motion constraints, constant speed constraints, holonomic coordination constraints, and equality/inequality geometric constraints. We develop a general framework involving differential-algebraic equations and viability theory to determine coordination feasibility for a coordinated motion control under heterogeneous vehicle dynamics and different types of coordination task constraints. If a coordinated motion solution exists for the derived differential-algebraic equations and/or inequalities, a constructive algorithm is proposed to derive an equivalent dynamical system that generates a set of feasible coordinated motions for each individual vehicle. In case studies on coordinating two vehicles, we derive analytical solutions to motion generation for two-vehicle groups consisting of car-like vehicles, unicycle vehicles, or vehicles with constant speeds, which serve as benchmark coordination tasks for more complex vehicle groups. The motion generation algorithm is well-backed by simulation data for a wide variety of coordination situations involving heterogeneous vehicles. We then extend the vehicle control framework to deal with the cooperative coordination problem with time-varying coordination tasks and leader-follower structure. We show several simulation experiments on multi-vehicle coordination under various constraints to validate the theory and the effectiveness of the proposed schemes.

Zhiyong Sun, Qingchen Liu, Na Huang et al.

This paper discusses cooperative stabilization control of rigid formations via an event-based approach. We first design a centralized event-based formation control system, in which a central event controller determines the next triggering time and broadcasts the event signal to all the agents for control input update. We then build on this approach to propose a distributed event control strategy, in which each agent can use its local event trigger and local information to update the control input at its own event time. For both cases, the triggering condition, event function and triggering behavior are discussed in detail, and the exponential convergence of the event-based formation system is guaranteed.

Zhiyong Sun, Hector Garcia de Marina, Brian D. O. Anderson et al.

This paper considers a collaborative tracking control problem using a group of fixed-wing unmanned aerial vehicles (UAVs) with constant and non-identical speeds. The dynamics of fixed-wing UAVs are modelled by unicycle-type equations with nonholonomic constraints, assuming that UAVs fly at constant altitudes in the nominal operation mode. The controller is designed such that all fixed-wing UAVs as a group can collaboratively track a desired target's position and velocity. We first present conditions on the relative speeds of tracking UAVs and the target to ensure that the tracking objective can be achieved when UAVs are subject to constant speed constraints. We construct a reference velocity that includes both the target's velocity and position as feedback, which is to be tracked by the group centroid. In this way, all vehicles' headings are controlled such that the group centroid follows a reference trajectory that successfully tracks the target's trajectory. A spacing controller is further devised to ensure that all vehicles stay close to the group centroid trajectory. Trade-offs in the controller design and performance limitations of the target tracking control due to the constant-speed constraint are also discussed in detail. Experimental results with three fixed-wing UAVs tracking a target rotorcraft are provided.

James S. Russell, Mengbin Ye, Brian D. O. Anderson et al.

A GPS-denied UAV (Agent B) is localised through INS alignment with the aid of a nearby GPS-equipped UAV (Agent A), which broadcasts its position at several time instants. Agent B measures the signals' direction of arrival with respect to Agent B's inertial navigation frame. Semidefinite programming and the Orthogonal Procrustes algorithm are employed, and accuracy is improved through maximum likelihood estimation. The method is validated using flight data and simulations. A three-agent extension is explored.

Hector Garcia de Marina, Zhiyong Sun, Ming Cao et al.

In formation control, triangular formations consisting of three autonomous agents serve as a class of benchmarks that can be used to test and compare the performances of different controllers. We present an algorithm that combines the advantages of both position- and distance-based gradient descent control laws. For example, only two pairs of neighboring agents need to be controlled, agents can work in their own local frame of coordinates and the orientation of the formation with respect to a global frame of coordinates is not prescribed. We first present a novel technique based on adding artificial biases to neighboring agents' range sensors such that their eventual positions correspond to a collinear configuration. Right after, a small modification in the bias terms by introducing a prescribed rotation matrix will allow the control of the bearing of the neighboring agents.

James Russell, Mengbin Ye, Brian D. O. Anderson et al.

This paper presents a novel approach for localising a GPS (Global Positioning System)-denied Unmanned Aerial Vehicle (UAV) with the aid of a GPS-equipped UAV in three-dimensional space. The GPS-equipped UAV makes discrete-time broadcasts of its global coordinates. The GPS-denied UAV simultaneously receives the broadcast and takes direction of arrival (DOA) measurements towards the origin of the broadcast in its local coordinate frame (obtained via an inertial navigation system (INS)). The aim is to determine the difference between the local and global frames, described by a rotation and a translation. In the noiseless case, global coordinates were recovered exactly by solving a system of linear equations. When DOA measurements are contaminated with noise, rank relaxed semidefinite programming (SDP) and the Orthogonal Procrustes algorithm are employed. Simulations are provided and factors affecting accuracy, such as noise levels and number of measurements, are explored.

Guodong Shi, Brian D. O. Anderson, U. Helmke

We study distributed network flows as solvers in continuous time for the linear algebraic equation $\mathbf{z}=\mathbf{H}\mathbf{y}$. Each node $i$ has access to a row $\mathbf{h}_i^{\rm T}$ of the matrix $\mathbf{H}$ and the corresponding entry $z_i$ in the vector $\mathbf{z}$. The first "consensus + projection" flow under investigation consists of two terms, one from standard consensus dynamics and the other contributing to projection onto each affine subspace specified by the $\mathbf{h}_i$ and $z_i$. The second "projection consensus" flow on the other hand simply replaces the relative state feedback in consensus dynamics with projected relative state feedback. Without dwell-time assumption on switching graphs as well as without positively lower bounded assumption on arc weights, we prove that all node states converge to a common solution of the linear algebraic equation, if there is any. The convergence is global for the "consensus + projection" flow while local for the "projection consensus" flow in the sense that the initial values must lie on the affine subspaces. If the linear equation has no exact solutions, we show that the node states can converge to a ball around the least squares solution whose radius can be made arbitrarily small through selecting a sufficiently large gain for the "consensus + projection" flow under fixed bidirectional graphs. Semi-global convergence to approximate least squares solutions is demonstrated for general switching directed graphs under suitable conditions. It is also shown that the "projection consensus" flow drives the average of the node states to the least squares solution with complete graph. Numerical examples are provided as illustrations of the established results.

Brian D. O. Anderson, Guodong Shi, Jochen Trumpf

We study continuous-time consensus dynamics for multi-agent systems with undirected switching interaction graphs. We establish a necessary and sufficient condition for exponential asymptotic consensus based on the classical theory of complete observability. The proof is remarkably simple compared to similar results in the literature and the conditions for consensus are mild. This observability-based method can also be applied to the case where negatively weighted edges are present. Additionally, as a by-product of the observability based arguments, we show that the nodes' initial value can be recovered from the signals on the edges up to a shift of the network average.