Magnus Egerstedt

Magnus Egerstedt
Are you Magnus Egerstedt?

Claim your profile, edit publications, add additional information:

Contact Details

Name
Magnus Egerstedt
Affiliation
Location

Pubs By Year

Pub Categories

 
Mathematics - Optimization and Control (16)
 
Computer Science - Robotics (9)
 
Computer Science - Multiagent Systems (5)
 
Mathematics - Combinatorics (2)
 
Computer Science - Computer Science and Game Theory (2)
 
Mathematics - Dynamical Systems (1)

Publications Authored By Magnus Egerstedt

2017Feb

In multi-robot systems where a central decision maker is specifying the movement of each individual robot, a communication failure can severely impair the performance of the system. This paper develops a motion strategy that allows robots to safely handle critical communication failures for such multi-robot architectures. For each robot, the proposed algorithm computes a time horizon over which collisions with other robots are guaranteed not to occur. Read More

Safety Barrier Certificates that ensure collision-free maneuvers for teams of differential flatness-based quadrotors are presented in this paper. Synthesized with control barrier functions, the certificates are used to modify the nominal trajectory in a minimally invasive way to avoid collisions. The proposed collision avoidance strategy complements existing flight control and planning algorithms by providing trajectory modifications with provable safety guarantees. Read More

Multi-agent coordination algorithms with randomized interactions have seen use in a variety of settings in the multi-agent systems literature. In some cases, these algorithms can be random by design, as in a gossip-like algorithm, and in other cases they are random due to external factors, as in the case of intermittent communications. Targeting both of these scenarios, we present novel convergence rate estimates for consensus problems solved over random graphs. Read More

This paper describes the Robotarium -- a remotely accessible, multi-robot research facility. The impetus behind the Robotarium is that multi-robot testbeds constitute an integral and essential part of the multi-robot research cycle, yet they are expensive, complex, and time-consuming to develop, operate, and maintain. These resource constraints, in turn, limit access for large groups of researchers and students, which is what the Robotarium is remedying by providing users with remote access to a state-of-the-art multi-robot test facility. Read More

This paper concerns a first-order algorithmic technique for a class of optimal control problems defined on switched-mode hybrid systems. The salient feature of the algorithm is that it avoids the computation of Fr\'echet or G\^ateaux derivatives of the cost functional, which can be time consuming, but rather moves in a projected-gradient direction that is easily computable (for a class of problems) and does not require any explicit derivatives. The algorithm is applicable to a class of problems where a pointwise minimizer of the Hamiltonian is computable by a simple formula, and this includes many problems that arise in theory and applications. Read More

This paper presents a formal framework for collision avoidance in multi-robot systems, wherein an existing controller is modified in a minimally invasive fashion to ensure safety. We build this framework through the use of control barrier functions (CBFs) which guarantee forward invariance of a safe set; these yield safety barrier certificates in the context of heterogeneous robot dynamics subject to acceleration bounds. Moreover, safety barrier certificates are extended to a distributed control framework, wherein neighboring agent dynamics are unknown, through local parameter identification. Read More

Compositional barrier functions are proposed in this paper to systematically compose multiple objectives for teams of mobile robots. The objectives are first encoded as barrier functions, and then composed using AND and OR logical operators. The advantage of this approach is that compositional barrier functions can provably guarantee the simultaneous satisfaction of all composed objectives. Read More

In this technical note, we study the controllability of diffusively coupled networks from a graph theoretic perspective. We consider leader-follower networks, where the external control inputs are injected to only some of the agents, namely the leaders. Our main result relates the controllability of such systems to the graph distances between the agents. Read More

We present a framework for asynchronously solving convex optimization problems over networks of agents which are augmented by the presence of a centralized cloud computer. This framework uses a Tikhonov-regularized primal-dual approach in which the agents update the system's primal variables and the cloud updates its dual variables. To minimize coordination requirements placed upon the system, the times of communications and computations among the agents are allowed to be arbitrary, provided they satisfy mild conditions. Read More

This paper describes the development of the Robotarium -- a remotely accessible, multi-robot research facility. The impetus behind the Robotarium is that multi-robot testbeds constitute an integral and essential part of the multi-agent research cycle, yet they are expensive, complex, and time-consuming to develop, operate, and maintain. These resource constraints, in turn, limit access for large groups of researchers and students, which is what the Robotarium is remedying by providing users with remote access to a state-of-the-art multi-robot test facility. Read More

This paper describes a framework for multi-robot coordination and motion planning with emphasis on inter-agent interactions. We focus on the characterization of inter-agent interactions with sufficient level of abstraction so as to allow for the enforcement of desired interaction patterns in a provably safe (i.e. Read More

In this paper we formulate the homogeneous two- and three-dimensional self-reconfiguration problem over discrete grids as a constrained potential game. We develop a game-theoretic learning algorithm based on the Metropolis-Hastings algorithm that solves the self-reconfiguration problem in a globally optimal fashion. Both a centralized and a fully distributed algorithm are presented and we show that the only stochastically stable state is the potential function maximizer, i. Read More

We present and analyze a computational hybrid architecture for performing multi-agent optimization. The optimization problems under consideration have convex objective and constraint functions with mild smoothness conditions imposed on them. For such problems, we provide a primal-dual algorithm implemented in the hybrid architecture, which consists of a decentralized network of agents into which centralized information is occasionally injected, and we establish its convergence properties. Read More

We present an optimization framework for solving multi-agent nonlinear programs subject to inequality constraints while keeping the agents' state trajectories private. Each agent has an objective function depending only upon its own state and the agents are collectively subject to global constraints. The agents do not directly communicate with each other but instead route messages through a trusted cloud computer. Read More

In this paper, we present a communication-free algorithm for distributed coverage of an arbitrary network by a group of mobile agents with local sensing capabilities. The network is represented as a graph, and the agents are arbitrarily deployed on some nodes of the graph. Any node of the graph is covered if it is within the sensing range of at least one agent. Read More

Multi-agent networks are often modeled as interaction graphs, where the nodes represent the agents and the edges denote some direct interactions. The robustness of a multi-agent network to perturbations such as failures, noise, or malicious attacks largely depends on the corresponding graph. In many applications, networks are desired to have well-connected interaction graphs with relatively small number of links. Read More

This paper presents an approach to externally influencing a team of robots by means of time-varying density functions. These density functions represent rough references for where the robots should be located. To this end, a continuous-time algorithm is proposed that moves the robots so as to provide optimal coverage given the density functions as they evolve over time. Read More

New architectures and algorithms are needed to reflect the mixture of local and global information that is available as multi-agent systems connect over the cloud. We present a novel architecture for multi-agent coordination where the cloud is assumed to be able to gather information from all agents, perform centralized computations, and disseminate the results in an intermittent manner. This architecture is used to solve a multi-agent optimization problem in which each agent has a local objective function unknown to the other agents and in which the agents are collectively subject to global inequality constraints. Read More

A network of locally interacting agents can be thought of as performing a distributed computation. But not all computations can be faithfully distributed. This paper investigates which global, linear transformations can be computed using local rules, i. Read More

This paper focuses on the consensus and formation problems of multiagent systems under unknown persistent disturbances. Specifically, we propose a novel method that combines an existing consensus (or formation) algorithm with a new controller. The new controller has an integral action that produces a control input based on an error signal locally projected onto the column space of the graph Laplacian. Read More

In this paper we explore the relationship between dual decomposition and the consensus-based method for distributed optimization. The relationship is developed by examining the similarities between the two approaches and their relationship to gradient-based constrained optimization. By formulating each algorithm in continuous-time, it is seen that both approaches use a gradient method for optimization with one using a proportional control term and the other using an integral control term to drive the system to the constraint set. Read More

Let $G$ be a graph of minimum degree at least two with no induced subgraph isomorphic to $K_{1,6}$. We prove that if $G$ is not isomorphic to one of eight exceptional graphs, then it is possible to assign two-element subsets of $\{1,2,3,4,5\}$ to the vertices of $G$ in such a way that for every $i\in\{1,2,3,4,5\}$ and every vertex $v\in V(G)$ the label $i$ is assigned to $v$ or one of its neighbors. It follows that $G$ has fractional domatic number at least $5/2$. Read More

In this paper we study the controllability of networked systems with static network topologies using tools from algebraic graph theory. Each agent in the network acts in a decentralized fashion by updating its state in accordance with a nearest-neighbor averaging rule, known as the consensus dynamics. In order to control the system, external control inputs are injected into the so called leader nodes, and the influence is propagated throughout the network. Read More

This paper considers the problem of computing the schedule of modes in a switched dynamical system, that minimizes a cost functional defined on the trajectory of the system's continuous state variable. A recent approach to such optimal control problems consists of algorithms that alternate between computing the optimal switching times between modes in a given sequence, and updating the mode-sequence by inserting to it a finite number of new modes. These algorithms have an inherent inefficiency due to their sparse update of the mode-sequences, while spending most of the computing times on optimizing with respect to the switching times for a given mode-sequence. Read More