Daniel Zelazo

Mathias Bürger, Daniel Zelazo, Frank Allgöwer

This paper presents a class of passivity-based cooperative control problems that have an explicit connection to convex network optimization problems. The new notion of maximal equilibrium independent passivity is introduced and it is shown that networks of systems possessing this property asymptotically approach the solutions of a dual pair of network optimization problems, namely an optimal potential and an optimal flow problem. This connection leads to an interpretation of the dynamic variables, such as system inputs and outputs, to variables in a network optimization framework, such as divergences and potentials, and reveals that several duality relations known in convex network optimization theory translate directly to passivity-based cooperative control problems. The presented results establish a strong and explicit connection between passivity-based cooperative control theory on the one side and network optimization theory on the other, and they provide a unifying framework for network analysis and optimal design. The results are illustrated on a nonlinear traffic dynamics model that is shown to be asymptotically clustering.

Shiyu Zhao, Daniel Zelazo

This paper studies distributed maneuver control of multi-agent formations in arbitrary dimensions. The objective is to control the translation and scale of the formation while maintaining the desired formation pattern. Unlike conventional approaches where the target formation is defined by relative positions or distances, we propose a novel bearing-based approach where the target formation is defined by inter-neighbor bearings. Since the bearings are invariant to the translation and scale of the formation, the bearing-based approach provides a simple solution to the problem of translational and scaling formation maneuver control. Linear formation control laws for double-integrator dynamics are proposed and the global formation stability is analyzed. This paper also studies bearing-based formation control in the presence of practical problems including input disturbances, acceleration saturation, and collision avoidance. The theoretical results are illustrated with numerical simulations.

Shiyu Zhao, Daniel Zelazo

The problem of distributed control and estimation for multi-agent systems with limited sensing capabilities is a practical challenge motivated by incomplete and imperfect sensing. This article addresses an important case where each agent in a network can only sense the relative bearings to their nearest neighbors. The study of this topic is motivated mainly by the rapid development of bearing-only sensors such as optical cameras or sensor arrays. This article provides a tutorial review on this topic focusing on the problems of formation control and network localization. A key component of this review is a presentation of the recently developed bearing rigidity theory, which defines a necessary architectural feature of multi-agent systems aiming to solve these two problems. This article presents a high-level summary of recently developed algorithms solving these problems, various simulation examples, and discussions pointing to the relevant literature and important remaining challenges in this area.

Miel Sharf, Daniel Zelazo

In this paper, we propose a network-optimization framework for the analysis of multi-agent systems with passive-short agents. We consider the known connection between diffusively-coupled maximally equilibrium-independent passive systems, and network optimization, culminating in a pair of dual convex network optimization problems, whose minimizers are exactly the steady-states of the closed-loop system. We propose a network-based regularization term to the network optimization problem and show that it results in a network-based feedback using only relative outputs. We prove that if the average of the passivity indices is positive, then we convexify the problem, passivize the agents, and that steady-states of the augmented system correspond to the minimizers of the regularized network optimization problem. We also suggest a hybrid approach, in which only a subset of agents sense their own output, and show that if the set is nonempty, then we can always achieve the same correspondence as above, regardless of the passivity indices. We demonstrate our results on a traffic model with non-passive agents and limited GNSS reception.

Giulia Michieletto, Angelo Cenedese, Daniel Zelazo

This work focuses on the bearing rigidity theory, namely the branch of knowledge investigating the structural properties necessary for multi-element systems to preserve the inter-units bearings when exposed to deformations. The original contributions are twofold. The first one consists in the definition of a general framework for the statement of the principal definitions and results that are then particularized by evaluating the most studied metric spaces, providing a complete overview of the existing literature about the bearing rigidity theory. The second one rests on the determination of a necessary and sufficient condition guaranteeing the rigidity properties of a given multi-element system, independently of its metric space.

Hao Chen, Daniel Zelazo, Xiangke Wang et al.

This work analyzes the convergence properties of signed networks with nonlinear edge functions. We consider diffusively coupled networks comprised of maximal equilibrium-independent passive (MEIP) dynamics on the nodes, and a general class of nonlinear coupling functions on the edges. The first contribution of this work is to generalize the classical notion of signed networks for graphs with scalar weights to graphs with nonlinear edge functions using notions from passivity theory. We show that the output of the network can finally form one or several steady-state clusters if all edges are positive, and in particular, all nodes can reach an output agreement if there is a connected subnetwork spanning all nodes and strictly positive edges. When there are non-positive edges added to the network, we show that the tension of the network still converges to the equilibria of the edge functions if the relative outputs of the nodes connected by non-positive edges converge to their equilibria. Furthermore, we establish the equivalent circuit models for signed nonlinear networks, and define the concept of equivalent edge functions which is a generalization of the notion of effective resistance. We finally characterize the relationship between the convergence property and the equivalent edge function, when a non-positive edge is added to a strictly positive network comprised of nonlinear integrators. We show that the convergence of the network is always guaranteed, if the sum of the equivalent edge function of the previous network and the new edge function is passive.

Shiyu Zhao, Daniel Zelazo

This paper addresses the problem of bearing-based network localization, which aims to localize all the nodes in a static network given the locations of a subset of nodes termed anchors and inter-node bearings measured in a common reference frame. The contributions of the paper are twofold. Firstly, we propose necessary and sufficient conditions for network localizability with both algebraic and rigidity theoretic interpretations. The analysis of the localizability heavily relies on the recently developed bearing rigidity theory and a special matrix termed the bearing Laplacian. Secondly, we propose a linear distributed protocol for bearing-based network localization. The protocol can globally localize a network if and only if the network is localizable. The sensitivity of the protocol to constant measurement errors is also analyzed. One novelty of this work is that the localizability analysis and localization protocol are applicable to networks in arbitrary dimensional spaces.

Miel Sharf, Daniel Zelazo

This work studies the effects of a weak notion of symmetry on diffusively-coupled multi-agent systems. We focus on networks comprised of agents and controllers which are maximally equilibrium independent passive, and show that these converge to a clustered steady-state, with clusters corresponding to certain symmetries of the system. Namely, clusters are computed using the notion of the exchangeability graph. We then discuss homogeneous networks and the cluster synthesis problem, namely finding a graph and homogeneous controllers forcing the agents to cluster at prescribed values.

Miel Sharf, Daniel Zelazo

The theory of network identification, namely identifying the (weighted) interaction topology among a known number of agents, has been widely developed for linear agents. However, the theory for nonlinear agents using probing inputs is far less developed, relying on dynamics linearization, and thus cannot be applied to networks with non-smooth or discontinuous dynamics. We use global convergence properties of the network, which can be assured using passivity theory, to present a network identification method for nonlinear agents. We do so by linearizing the steady-state equations rather than the dynamics, achieving a sub-cubic time algorithm for network identification. We also study the problem of network identification from a complexity theory standpoint, showing that the presented algorithms are optimal in terms of time complexity. We demonstrate the presented algorithm in two case studies with discontinuous dynamics.

Solomon Goldgraber Casspi, Daniel Zelazo

This letter presents a geometric input-output analysis of distance-based formation control, focusing on the phenomenon of steady-state signal blocking between actuator and sensor pairs. We characterize steady-state multivariable transmission zeros, where fully excited rigid-body and deformational modes destructively interfere at the measured output. By analyzing the DC gain transfer matrix of the linearized closed-loop dynamics, we prove that for connected, flexible frameworks, structural transmission zeros are strictly non-generic; the configuration-dependent cross-coupling required to induce them occupies a proper algebraic set of measure zero. However, because extracting actionable sensor-placement rules from these complex algebraic varieties is analytically intractable, we restrict our focus to infinitesimally rigid formations. For these baselines, we prove that the absence of internal flexes forces the zero-transmission condition to collapse into an explicit affine hyperplane defined by the actuator and the global formation geometry, which we term the spatial locus of transmission zeros. Finally, we introduce the global transmission polygon--a convex polytope constructed from the intersection of these loci. This construct provides a direct geometric synthesis rule for robust sensor allocation, guaranteeing full-rank steady-state transmission against arbitrary single-node excitations.

Christos K. Verginis, Daniel Zelazo, Dimos V. Dimarogonas

This paper considers the integration of rigid cooperative manipulation with rigidity theory. Motivated by rigid models of cooperative manipulation systems, i.e., where the grasping contacts are rigid, we introduce first the notion of bearing and distance rigidity for graph frameworks in SE(3). Next, we associate the nodes of these frameworks to the robotic agents of rigid cooperative manipulation schemes and we express the object-agent interaction forces by using the graph rigidity matrix, which encodes the infinitesimal rigid body motions of the system. Moreover, we show that the associated cooperative manipulation grasp matrix is related to the rigidity matrix via a range-nullspace relation, based on which we provide novel results on the relation between the arising interaction and internal forces and consequently on the energy-optimal force distribution on a cooperative manipulation system. Finally, simulation results on a realistic environment enhance the validity of the theoretical findings.

Shiyu Zhao, Zhiyong Sun, Daniel Zelazo et al.

This paper addresses the problem of constructing bearing rigid networks in arbitrary dimensions. We first show that the bearing rigidity of a network is a generic property that is critically determined by the underlying graph of the network. A new notion termed generic bearing rigidity is defined for graphs. If the underlying graph of a network is generically bearing rigid, then the network is bearing rigid for almost all configurations; otherwise, the network is not bearing rigid for any configuration. As a result, the key to construct bearing rigid networks is to construct generically bearing rigid graphs. The main contribution of this paper is to prove that Laman graphs, which can be generated by the Henneberg construction, are generically bearing rigid in arbitrary dimensions. As a consequence, if the underlying graph of a network is Laman, the network is bearing rigid for almost all configurations in arbitrary dimensions.

Dwaipayan Mukherjee, Daniel Zelazo

The present paper investigates the robustness of the consensus protocol over weighted directed graphs using the Nyquist criterion. The limit to which a single weight can vary, while consensus among the agents can be achieved, is explicitly derived. It is shown that even with a negative weight on one of the edges, consensus may be achieved. The result obtained in this paper is applied to a directed acyclic graph and to the directed cycle graph. Graph theoretic interpretations of the limits are provided for the two cases. Simulations support the theoretical results.

Shiyu Zhao, Daniel Zelazo

This paper studies the problem of stabilizing target formations specified by inter-neighbor bearings with relative position measurements. While the undirected case has been studied in the existing works, this paper focuses on the case where the interaction topology is directed. It is shown that a linear distributed control law, which was proposed previously for undirected cases, can still be applied to the directed case. The formation stability in the directed case, however, relies on a new notion termed bearing persistence, which describes whether or not the directed underlying graph is persistent with the bearing rigidity of a formation. If a target formation is not bearing persistent, undesired equilibriums will appear and global formation stability cannot be guaranteed. The notion of bearing persistence is defined by the bearing Laplacian matrix and illustrated by simulation examples.

Shiyu Zhao, Daniel Zelazo

This paper studies the problem of multi-agent formation maneuver control where both of the centroid and scale of a formation are required to track given velocity references while maintaining the formation shape. Unlike the conventional approaches where the target formation is defined by inter-neighbor relative positions or distances, we propose a bearing-based approach where the target formation is defined by inter-neighbor bearings. Due to the invariance of the bearings, the bearing-based approach provides a natural solution to formation scale control. We assume the dynamics of each agent as a single integrator and propose a globally stable proportional-integral formation maneuver control law. It is shown that at least two leaders are required to collaborate in order to control the centroid and scale of the formation whereas the followers are not required to have access to any global information, such as the velocities of the leaders.

Shiyu Zhao, Daniel Zelazo

A fundamental problem that the bearing rigidity theory studies is to determine when a framework can be uniquely determined up to a translation and a scaling factor by its inter-neighbor bearings. While many previous works focused on the bearing rigidity of two-dimensional frameworks, a first contribution of this paper is to extend these results to arbitrary dimensions. It is shown that a framework in an arbitrary dimension can be uniquely determined up to a translation and a scaling factor by the bearings if and only if the framework is infinitesimally bearing rigid. In this paper, the proposed bearing rigidity theory is further applied to the bearing-only formation stabilization problem where the target formation is defined by inter-neighbor bearings and the feedback control uses only bearing measurements. Nonlinear distributed bearing-only formation control laws are proposed for the cases with and without a global orientation. It is proved that the control laws can almost globally stabilize infinitesimally bearing rigid formations. Numerical simulations are provided to support the analysis.

Shiyu Zhao, Daniel Zelazo

This paper studies the distributed control and estimation of multi-agent systems based on bearing information. In particular, we consider two problems: (i) the distributed control of bearing-constrained formations using relative position measurements and (ii) the distributed localization of sensor networks using bearing measurements. Both of the two problems are considered in arbitrary dimensional spaces. The analyses of the two problems rely on the recently developed bearing rigidity theory. We show that the two problems have the same mathematical formulation and can be solved by identical protocols. The proposed controller and estimator can globally solve the two problems without ambiguity. The results are supported with illustrative simulations.

Daniel Zelazo, Antonio Franchi, Heinrich H. Bülthoff et al.

This work proposes a fully decentralized strategy for maintaining the formation rigidity of a multi-robot system using only range measurements, while still allowing the graph topology to change freely over time. In this direction, a first contribution of this work is an extension of rigidity theory to weighted frameworks and the rigidity eigenvalue, which when positive ensures the infinitesimal rigidity of the framework. We then propose a distributed algorithm for estimating a common relative position reference frame amongst a team of robots with only range measurements in addition to one agent endowed with the capability of measuring the bearing to two other agents. This first estimation step is embedded into a subsequent distributed algorithm for estimating the rigidity eigenvalue associated with the weighted framework. The estimate of the rigidity eigenvalue is finally used to generate a local control action for each agent that both maintains the rigidity property and enforces additional con- straints such as collision avoidance and sensing/communication range limits and occlusions. As an additional feature of our approach, the communication and sensing links among the robots are also left free to change over time while preserving rigidity of the whole framework. The proposed scheme is then experimentally validated with a robotic testbed consisting of 6 quadrotor UAVs operating in a cluttered environment.