3rd Northeast Control Workshop Program

speaker	Advisor	School	Title
Ahuja, Sunil	Clarence W. Rowley	Princeton University	Reduced-order models for feedback control of separation in fluids
Arsie, Alessandro	Emilio Frazzoli	MIT	Efficient routing with no explicit communications
Bai, He	John T. Wen Murat Arcak	RPI	A Decentralized Design for Group Alignment and Synchronous Rotation without Inertial Frame Information
Biyik Emrah	Murat Arcak	RPI	Gradient Climbing in Formation via Extremum Seeking and Passivity-Based Coordination Rules
Cao, Ming	A. Stephen Morse	Yale University	Station keeping in the plane with range-only measurements
Como, Giacomo	Sekhar Tatikonda	Yale University	The Role of Feedback in Increasing Capacity and Decreasing Latency in Markov Communication Channels
Gupta, Vijay	Nuno C. Martins	University of Maryland	Stabilization using multiple sensors over erasure channels
Elhamifar, Ehsan	Rene Vidal	Johns Hopkins University	Observability of Jump Linear Systems with Inputs
El-Hawwary, Mohamed	Manfredi Maggiore	University of Toronto	Passivity-based Stabilization of Non-Compact Sets
Lan, Tian	Mung Chiang	Princeton University	How Unfair Can A Network Be?
Loizou, Savvas	Vijay Kumar	University of Pennsylvania	Biologically Inspired Landmark Based Navigation
Lopes, Gabriel	Daniel Koditschek	University of Pennsylvania	Navigation Functions for Kinematic and Dynamical Nonholonomically Constrained Mechanical Systems
Preciado,Victor Manuel	George C. Verghese	MIT	Moment-based Spectral Analysis of Stochastic Complex Networks
Shah, Parikshit M	Pablo Parrilo	MIT	Polynomial Stochastic Games via Sum-of-Squares Optimization
Shen, Yang	Ioannis Paschalidis	Boston University	Optimizing Noisy Funnel-like Functions on the Euclidean Group with Applications to Protein Docking
Swain, Dan	Naomi E. Leonard	Princeton University	Alternating Spatial Patterns for Coordinated Group Motion
Tahbaz-Salehi, Alireza	Ali Jadbabaie	Universitiy of Pennsylvania	Conditions for achieving consensus over random networks
Zavlanos, Michael	George Pappas	Universitiy of Pennsylvania	dynamic assignment in distributed motion planning with local coordination
Zhong, Minyi	Christos Cassandras	Boston University	Distributed Coverage Control in Sensor Network Environments with Polygonal Obstacles

Abstracts:

Princeton University

Leading edge vortices (LEVs) have been observed to provide high lift in bio-fliers at relatively low Reynolds numbers, and provide inspiration for development of micro air vehicles (MAVs). However, these vortices are unstable at practical speeds of interest and their stabilization is a key to the development of these vehicles.

Our approach is to derive reduced order models of the dynamics of these LEVs that would be tractable for feedback control design. We derive models
of the flow linearized about given steady states, either stable or unstable. The method used is an approximate balanced truncation method which is tractable for large dimensional systems. We present models of 2-D incompressible flow past a flat plate, and use them to develop feedback control laws to stabilize unstable steady states. We also develop observers to reconstruct the flow field using a small number of pressure sensors on the flat plate.

We consider a class of dynamic vehicle routing problems, in which a number of mobile agents in the plane must visit target points generated over time by a stochastic process. It is desired to design motion coordination strategies in order to minimize the expected time between the appearance of a target point and the time it is visited by one of the agents. We propose control strategies that, while making minimal or no assumptions on communications between agents, provide the same level of steady-state performance achieved by the best known decentralized strategies. In other words, we demonstrate that inter-agent communication does not improve the efficiency of such systems, but merely affects the rate of convergence to the steady state.
Furthermore, the proposed strategies do not rely on the knowledge of the details of the underlying stochastic process. Finally, we show that our proposed
strategies provide an efficient, pure Nash equilibrium in a game theoretic formulation of the problem, in which each agent's objective is to maximize the
number of targets it visits. Simulation results are presented and discussed. Some remarks are given in the case in which the agents dynamic is nonholonomic.

Group Alignment and Synchronous Rotation without Inertial Frame Information: A Decentralized Design

He Bai , John T. Wen, Murat Arcak

RPI

We study a motion coordination problem where the objective is to achieve identical orientation and synchronous rotation for a group of rigid bodies. Unlike existing designs which assume that the the inertial frame is available to each agent, we develop a passivity-based design which relies only on relative attitude information with respect to neighboring agents.We also consider the situation where the reference angular velocity is available only to the leader, and propose a distributed adaptive controller with which the other agents reconstruct this reference velocity.

Gradient Climbing in Formation via Extremum Seeking and Passivity-Based Coordination Rules

Emrah Biyik, Murat Arcak

RPI

We consider a gradient climbing problem where the objective is to steer a group of vehicles to the extrema of an unknown scalar field distribution while keeping a prescribed formation. We address this task by developing a scheme in which the leader performs extremum seeking for the minima or maxima of the field, and other vehicles follow according to passivity-based coordination rules. The extremum-seeking approach generates approximate gradients of the field locally by "dithering" sensor positions. We show that if there is sufficient time-scale separation between the fast dither and slow gradient motions of the leader vehicle, the followers only respond to the gradient motion, and filter out the dither component, while keeping the prescribed formation.

Station keeping is the practice of keeping a mobile autonomous agent in a prescribed position in the plane which is determined by prescribed distances from two or more landmarks. We are interested in solutions to the station keeping problem in which the only signals available to the mobile agent are noisy range measurements from the land marks. Using concepts from switched adaptive control theory plus a special parameterization of the class of 2-by-2 nonsingular matrices, a tractable and provably correct solution is given to the three landmark station keeping problem. The performance of the overall system degrades gracefully in the face of increasing measurement and miss-alignment errors, provided the measurement errors are not too large.

Order fulfillment is a multi-billion dollar business. Existing solutions range from the highly automated--whose cost effectiveness is inversely related to their flexibility--to people pushing carts around in warehouses manually filling orders--which is very flexible but not very cost effective. In this talk I will describe a radical new approach to order fulfillment that is both flexible and cost effective. The key idea is to use hundreds of networked, autonomous vehicles to do the walking. More details may be found at www.kivasystems.com

Consider a discrete-time, linear time-invariant process, two sensors and one controller. The process is observed by the sensors, which are connected to the controller via links that can be modeled as erasure channels. If a link transmits successfully then a finite-dimensional vector of real numbers is conveyed from the sensor to the controller. If an erasure event occurs, then any information conveyed over the link is lost. This paper addresses the problem of designing the maps that specify the processing at the controller and at the sensors for stabilizing the process in the bounded second moment sense. When the information is lost
over the links either in an independent and identically distributed (i.i.d.) or Markovian fashion over time, we derive necessary and sufficient conditions for the existence of maps such that the process is stabilized. Such conditions are expressed as inequalities involving the parameters of the plant and the probabilities of link fading and provide the least conservative stabilization conditions. We also indicate how our approach can be used if more than two sensors are available, if the
sensors can cooperate and if the acknowledgment signals are also transmitted over erasure channels. The analysis also carries over to the case when the single channels are replaced by networks of erasure channels.

The Role of Feedback in Increasing Capacity and Decreasing Latency in Markov Communication Channels

The information theoretic value of feedback in channel coding is a long studied problem. Shannon ('56) showed that feedback cannot increase the capacity of a memoryless channel. However it is known that feedback can help improve latency at rates below capacity. Burnashev ('76) proved a simple formula relating latency and error for the case of discrete memoryless channels.

In this talk we show how tools from stochatic control can be used to compute the capacity of Markov channels with feedback. In this case feedback increases capacity. In addition, we extend Burnashev's result relating latency to error to this setting. The main technical tool we use to solve this problem is the convex-analytic approach to Markov decision processes with average cost criterion.

We analyze the observability of the continuous and discrete states of discrete-time jump linear systems (JLS) with deterministic inputs. We consider several definitions of indistinguishability and observabilty for JLS. For each definition, we derive conditions on the parameters of the constituent linear systems under which the states of the JLS are observable. When the discrete state sequence is arbitrary, our conditions involve relationships among the Markov parameters of the JLS. When the discrete state sequence is such that there is a minimum separation between consecutive switches, our conditions are simple rank tests that exploit the geometry of the observability subspaces and can be related to the Markov parameters of the individual linear systems.

We investigate the stabilization of closed sets for passive nonlinear systems which are contained in the zero level set of the storage function.

Gabriel Lopes *, Daniel Koditschek **

*University of Michigan, **University of Pennsylvania

In this work we address problems of robot navigation with nonholonomic motion constraints and perceptual cues arising from onboard visual servoing in partially engineered environments. First, we propose a hybrid procedure that adapts to the constrained motion setting the standard feedback controller arising from a navigation function in the fully actuated case. Second, we explore the possibility of adapting this class of hybrid feedback controllers for kinematic systems to their dynamical counterparts.

University of Maryland

In this expository talk, based on joint work with Eric Justh and Fumin Zhang, I discuss the use of certain geometrical ideas in steering particles. I shall show that methods based on moving frames and their interactions are effective in manipulating moving patterns of particles into other moving patterns.

A central problem in networking is how to allocate rates to individual flows fairly and efficiently. The problem has been formulated as a network utility maximization (NUM) problem for a class of $\alpha$-fair utility functions. In practical networks, due to the non-convexity in resource allocation and multi-user scheduling, we accept the possibility that only suboptimal solutions to the NUM problem may be computable, and thus the resulting unfair rate allocation could affect network performance in several different aspects. In this work, we study the tradeoff between fairness (or optimality) and
various network performance metrics. First, we generalize the previous notion of $\alpha$-fairness to more accurate measures that numerically quantify the amount of unfairness of a rate allocation policy. Our new fairness definitions, implicitly incorporating the optimality gap in the NUM problems, allow us to compare fairness criteria of different rate allocation policies. Second, we analyze the tradeoff between fairness and various network performance metrics, such as link utilization, total throughput and stability. Flow-level stability regions for unfair rate allocation policies are considered.

University of Pennsylvania

In this talk I show controllers that I developed for the control of individual or groups of vehicles based only on sensors that provide bearing information. The inspiration for this work is derived from the observation that many ant species use landmark retinal positions to navigate without having any range information. This is specially relevant to vision-based controllers for vehicles because cameras provide very good bearing information but relatively poor range information. A provably correct bearing-only navigation controller and a methodology for tracking that lends itself to control of formations are presented. The proposed feedback controllers are shown to have analytically guaranteed properties. The effectiveness of the proposed controllers is demonstrated through computer simulations.

A wide variety of dynamical processes on networks can be studied from the point of view of the eigenvalue distribution of a certain matrix representation of the network topology. Examples of these processes are random walks, gossip algorithms, consensus problems, and synchronization of oscillators. The objective of our work is to perform a spectrum-based analysis for large-scale complex networks, and to analyze the implications for dynamical processes on these networks. We model the topology of the complex network by a probabilistic description; therefore, the spectral analysis of the network topology is equivalent to determining the
eigenvalue distribution of an ensemble of random matrices. We borrow techniques from spectral graph theory and random matrix theory to perform an in-depth study of the moments of the spectral distribution, based on probabilistic graphical properties of the network. We also show how, from the moment sequence, one can deduce bounds for many spectral properties of interest.

Stochastic games are an important class of games that generalize Markov decision processes to game theoretic scenarios. We consider finite state two-player zero-sum stochastic games over an infinite time horizon with discounted rewards. The players are assumed to have infinite strategy spaces and the payoffs are assumed to be polynomials. In this paper we restrict our attention to a very special class of games for which the single-controller assumption holds. It is shown that minimax equilibria and optimal strategies for such games may be obtained via semidefinite programming.

Yang Shen, Ioannis Paschalidis

Boston University

Proteins interact with each other and other chemical entities in the cell to form complexes. These interactions play a central role in a number of vital functions of the cell such as metabolic control, gene regulation and signal transduction. One of the fundamental and challenging problems in computational structural biology is theprotein docking problem defined as determining the 3-dimensional structure of a bound complex in atomic detail from the atomic coordinates of the unbound component molecules.

Formulated as an optimization problem, the final stages of protein docking can be viewed as optimizing a very noisy funnel-like function on the space of rigid body motions, the (special) Euclidean group SE(3). We have recently introduced a stochastic global optimization method, called Semi-Definite programming based Underestimation (SDU), that constructs a convex quadratic under-estimator to the free energy funnel based on a sample of energy function evaluations and uses the quadratic under-estimator to guide future sampling. In this presentation I'll show that the parameterization of SE(3) has a significant impact on the efficiency of SDU and introduce a parameterization that dramatically reduces the number of very costly energy function evaluations. The resulting algorithm represents a significant gain (more than an order of magnitude) in computational efficiency compared to state-of-the-art Monte Carlo-based algorithms used for the same purpose.

Daniel T. Swain, Naomi Ehrich Leonard, Iain D. Couzin, Albert Kao, and Rodolphe Sepulchre

Motivated by recent observations of ﬁsh schools, we study coordinated group motion for individuals with oscillatory speed. Neighbors that have speed oscillations with common frequency, amplitude and average but different phases, move together in alternating spatial patterns, taking turns being towards the front, sides and back of the group. We propose a model and control laws to investigate the connections between these spatial dynamics, communication when sensing is range or direction limited and convergence of coordinated group motions.

In this paper we consider the consensus problem for stochastic switched linear dynamical systems. For discretetime and continuous-time stochastic switched linear systems, we present necessary and sufficient conditions under which such systems reach a consensus almost surely. In the discrete-time case, our assumption is that the underlying graph of the system at any given time instance is derived from a random graph process, independent of other time instances. These graphs can be weighted, directed and with dependent edges. For the continuous-time case, we assume that the switching is governed by a Poisson point process and the graphs characterizing the topology of the system are independent and identically distributed over time. For both such frameworks, we present necessary and sufficient conditions for almost sure asymptotic consensus using simple ergodicity and probabilistic arguments. These easily verifiable conditions depend on the spectrum of the average weight matrix and the average Laplacian matrix for the discrete-time and continuous-time cases, respectively.

Workshop Program

Plenary Speakers:

May 15:

Prof. Raffaello D'Andrea

Cornell University, Ithaca, NY / Kiva Systems

May 16:

Prof. P.S. Krishnaprasad

Institute of Systems Research,
University of Maryland, College Park, MD

Presentations:

Abstracts:

Workshop Program

Plenary Speakers:

May 15:

Prof. Raffaello D'Andrea

Cornell University, Ithaca, NY / Kiva Systems

May 16:

Prof. P.S. Krishnaprasad

Institute of Systems Research, University of Maryland, College Park, MD

Presentations:

Abstracts:

Institute of Systems Research,
University of Maryland, College Park, MD