Presentations from Previous Semesters
Previous topic  |  This topic  |  Next topic
Previous article  |  This article  |  Next article

Fall 2010 Seminars
Jan Reineke, 20 Jan 2011
Last updated: 13 Sep 2011

Fall 2010 seminars

Kris Pister, UC Berkeley, Tuesday, December 14th, 2010
Time and Location: 4-5pm (540 Cory)

Synchronized Wireless Sensor Networks - Applications, Standards, and Technology

This talk will cover some existing commercial applications of synchronized wireless sensor networks, the relevant standards, and the underlying technology for time synchronization. RMS synchronization error across commercial multi-hop mesh networks is in the tens of microseconds, headed to a fraction of a microsecond.

Changbin Yu, Australian National University, Tuesday, December 7th, 2010
Time and Location: 4-5pm (540 Cory)

Graph Rigidity Theory for Formation Control

This talk considers problems of control of multiagent formations that can be modeled by undirected or directed graphs. The graphical model can capture specific design considerations from each of sensing, communication and control architectures, or a mixture of them. The characterization using these formation graphs and the associated control laws thus can be applied in autonomous mobile robotic networks of various types.

Central to this talk is the development and application of graph rigidity theory. Subject to time constraints, a wide range of issues will be covered: from fundamental problems like formation modeling and characterization of formation information structures to task-oriented studies such as motion coordination, formation operations and formation robustness.

Silviu Craciunas, University of Salzburg, Tuesday, November 30th, 2010
Time and Location: 4-5pm (540 Cory)

Programmable Temporal Isolation for Real-Time Systems

We introduce a novel scheduling paradigm for hard real-time uniprocessor systems, called Variable-bandwidth Server (VBS), that enables adaptation of software processes to varying real-time constraints while maintaining temporal isolation. In the VBS process model, processes are sequences of individual actions with an action being a given piece of process code. Processes and actions are temporally isolated from one another in the sense that the variance in response times of the same action of a given process is bounded independently of any other concurrently running processes in the system.

As the variance of action response times is also influenced by the scheduler overhead, we introduce a framework for overhead accounting in VBS-scheduled systems. Overhead introduced by the scheduling algorithm may be accounted for either by decreasing process execution speed to maintain CPU utilization, or by increasing CPU utilization to maintain process execution speed. Both methods can be combined by handling an arbitrary fraction of the total scheduler overhead with one method and the rest with the other.

We also show that it is possible to reduce CPU power consumption with VBS by CPU voltage and frequency scaling. Scaling to lower frequencies is possible whenever there is CPU slack in the system. We propose a frequency-scaling VBS algorithm that exploits CPU slack to minimize operating frequencies with maximal CPU utilization while maintaining temporal isolation. This may lead to improvements in power consumption while hiding the real-time effects of frequency scaling. Additionally, we present more advanced methods with which additional power may be saved by redistributing computation time of individual process actions if the system has knowledge of future events.

Mac Schwager, UPenn/MIT, Thursday, November 18th, 2010
Time and Location: 4-5pm (540 Cory)

Large Scale Surveillance and Aggressive Coordination in Multi-Robot Systems

Groups of robots working collaboratively have the potential to change the way we sense and interact with our environment at large scales. They can be autonomously deployed over ecosystems or cities to collect high-resolution data over large areas, process that data in a decentralized way, and act on the environment to affect a desired large-scale change. In this talk I will describe two recent advances in multi-robot control. First I will describe a scalable, decentralized control algorithm for deploying groups of robotic cameras to collectively monitor an environment. I will present the results of experiments carried out with three quadrotor robots indoors and five quadrotors outdoors using the controller. Next I will discuss time delays in multi-robot networks, and their limiting effect on the aggressiveness of the robots' actions. I will describe an analytical relationship between network update rate, network topology, and control aggressiveness in a formation control scenario. Experimental results with three quadrotor robots probing the limits of control aggressiveness will be presented.

Alix Munier Kordon, Universit���© Pierre et Marie Curie, Paris, Tuesday, November 16th, 2010
Time and Location: 4-5pm (540 Cory)

A new Approach for Minimizing Buffer Capacities with Throughput Constraint for Embedded System Design

The design of streaming (e.g. multimedia or network packet processing) applications must consider several optimizations such as the mimimization of the whole surface of the memory needed on a Chip. The minimum throughput of the output is usually fixed. In this paper, we present an original methodology to solve this problem.

The application is modelled using a Marked Timed Weighted Event Graphs (in short MTWEG), which is a subclass of Petri nets. Transitions correspond to specific treatments and the places model buffers for data transfer. It is assumed that transitions are periodically fired with a fixed throughput. This formalism is equivalent to Synchonous DataFlow Graphs.

The problem is first mathematically modelled using an Integer Linear Program. We then study for a unique buffer the optimum throughput according to the capacity. A first polynomial simple algorithm computing the minimum surface for a fixed throughput is derived when there is no circuit in the initial MTWEG, which corresponds to a wide class of applications. For general MTWEG, the problem is NP-Hard and an original polynomial 2-approximation algorithm is presented. For practical applications, the solution computed is very close to the optimum.

This is joint work with Mohamed Benazouz and Olivier Marchetti.

Ray DeCarlo, Purdue University, Friday, November 12th, 2010
Time and Location: 4-5pm (540 Cory)

Optimal Control of Switched Systems: An Embedding Approach with Application To a WMR and Real-Time Model Predictive Control of a dc-dc Boost Converter

This talk reviews results that show for quite a general class of hybrid optimal control problems containing both controlled and memoryless autonomous switches, the switched (hybrid) optimal control problem can be formulated so that the computational complexity of the problem is no greater than that of smooth optimal control problems. After defining the switched optimal control problem (SOCP), we elucidate its embedding (a relaxation) into a continuously parameterized family of problems defined as the embedded (switched) optimal control problem (EOCP). We argue that the SOCP is best solved by first solving the EOCP. The key idea behind this claim is that the trajectories of a switched system are dense in the trajectories of the embedded system. Sufficient and necessary conditions for solvability of the EOCP are given. The necessary conditions (via a generalized Hamiltonian) can be seen as a generalized Maximum Principle without explicit assumptions on fixing the number or sequence of mode switchings.

Two examples are presented. The first example considers a wheeled mobile robot (WMR) equipped with a rechargeable batters which powers electric drives on each wheel that propel the WMR in one mode of operation or recharge the battery in a second mode, resulting in a total of four modes. The objective is to use MPC for traction control to stabilize the WMR to a predefined set while subject to wheel slippage. The second example applies the embedding theory to the problem of real-time model predictive control of a dc-dc boost converter. After describing the model and performance index, a solution methodology is set forth which on hardware solves the EOCP using an active set method in less than 50 s. The EOCP solution is projected onto an approximating SOCP solution. The switching control of the approximating SOCP solution is applied in real time using center-aligned PWM with a 15.8 KHz clock in the context of a two partition MPC window. Both simulation and experimental results will be presented.

Keshab K. Parhi, University of Minnesota, Minneapolis, Wednesday, November 10th, 2010
Time and Location: 11am-12pm (540 Cory)

Digital Signal Processing with Protein Molecules and DNA Strands

Digital signal processing (DSP) refers to non-terminating computations where computations are carried out repetitively on incoming samples. Digital signal processing has been applied in audio, speech, video, image, and wired and wireless applications. This talk will focus on signal processing of proteins using bio-chemical reactions. Past work on signal processing of chemical reaction networks (CRNs) at Stanford, Berkeley and LBL has provided a foundation for this effort. Our work differs in two respects. First, our work is based on digital signal processing as opposed to analog. Second, this work is based on synthesis as opposed to analysis of CRNs. In this talk, we review simple chemical computations that are one-time computations that terminate. All DSP computations are iterative, and require realization of delay elements. The delay operation refers to transfer operation from one protein to another protein. The delay element can be part of a feed-forward path or a feedback loop. Implementing a delay operation through the chemical reactions is a non-trivial task, and is one of the major contributions of our work. We describe a 3-phase synchronization scheme, referred to as RGB scheme, as a robust method of synchronization in biochemical reactions. The RGB scheme is then used to synthesize biochemical reactions for simple FIR and IIR digital filters. Ordinary differential equations based solutions are presented for the synthezied biochemical reactions. A substrate is then considered for realizing these chemical reactions by DNA strands, based on work at Caltech. Simulation results of the chemical reactions using DNA strands are then presented to prove robustness and effectiveness of the proposed approach. An example is shown to illustrate that the RGB scheme can also be used as a clock in synchronous CRNs. Several limitations are then addressed, and ongoing efforts are described. Applications of the proposed methodology for biosensing, drug delivery, cross-talk cancellation and equalization of protein-protein reactions are then outlined.

This is a joint work with colleague Prof. Marc Riedel, graduate student Hua Jiang, and undergrad student Sasha Karam.

Yu Ru, University of California, San Diego, Tuesday, November 9th, 2010
Time and Location: 4-5pm (540 Cory)

Monitoring and Diagnosis of Complex Systems

In complex systems (e.g., electric grids, computer networks, automobiles), a single faulty behavior could cause cascading failures in a very short period and potentially lead to unpredictable results. In addition, due to complicated interactions between subsystems, monitoring and diagnosis of such systems can be extremely challenging, but they are very important to ensure safety operations. Such systems can be abstracted as discrete event systems (DESs) at a high level. This talk focuses on two related topics: monitoring and diagnosis of a given DES equipped with limited sensors, and configuring a set of sensors of minimal cost in a given DES to achieve accurate monitoring and immediate fault diagnosis. Different methods/results are proposed to address these two problems and the talk concludes by highlighting future research directions.

Karl H. Johansson, KTH, Thursday, November 4th, 2010
Time and Location: 4-5pm (540 Cory)

Wireless Control

There is a growing deployment of wireless networks in industrial control systems. Lower installation costs and easier system reconfigurations for wireless devices can have a major influence on the future application of distributed control and monitoring. There is however a lack of theory for understanding if and how the allocation of communication resources should be integrated with the control application. In this talk, we will discuss how the access scheme for the wireless medium can influence the closed-loop performance of the networked control system. It will be argued that the underlying scheduling-control problem has a non-classical information structure. Appropriate models for medium access control protocols will be introduced. It will be shown how these protocols can be tuned for various wireless control applications. We will also see that by making event-triggered transmissions based on decisions taken locally at the sensor and actuator nodes, it is possible improve the design and to limit the use of the communication resources. The talk will be illustrated by several examples from ongoing projects with Swedish industry. The presentation is based on joint work with collaborators at KTH.

Christoph Kirsch, University of Salzburg, Tuesday, November 2nd, 2010
Time and Location: 4-5pm (540 Cory)

Scal: Non-linearizable Computing Breaks the Scalability Barrier

We propose a relaxed version of linearizability and a set of load balancing algorithms for trading off adherence to concurrent data structure semantics and scalability. We consider data structures that store elements in a given order such as stacks and queues. Intuitively, a concurrent stack, for example, is linearizable if the effect of push and pop operations on the stack always occurs instantaneously. A linearizable stack guarantees that pop operations return the youngest stack elements first, i.e., the elements in the reverse order in which the operations that pushed them onto the stack took effect. Linearizability allows to reorder concurrent (but not sequential) operations arbitrarily. We relax linearizability to k-linearizability with k > 0 to also allow sequences of up to k - 1 sequential operations to be reordered arbitrarily and thus execute concurrently. With a k-linearizable stack, for example, a pop operation may not return the youngest but the k-th youngest element on the stack. It turns out that k-linearizability may be tolerated by concurrent applications such as process schedulers and web servers that already use it implicitly. Moreover, k-linearizability does provide positive scalability in some cases because more operations may be executed concurrently but may still be too restrictive under high contention. We therefore propose a set of load balancing algorithms, which significantly improve scalability by approximating k-linearizability probabilistically. We introduce Scal, an open-source framework for implementing k-linearizable approximations of concurrent data structures, and show in multiple benchmarks that Scal provides positive scalability for concurrent data structures that typically do not scale under high contention.

Hans Boehm, HP Labs, Friday, October 22nd, 2010
Time and Location: 3-4pm (540 Cory)

Programming language memory models: What do shared variables mean?

Although multithreaded programming languages are common, there has been a surprising amount of confusion surrounding the basic meaning of shared variables. There is finally a growing consensus, both that programming languages should by default guarantee an interleaving-based semantics for data-race-free programs, and on what that should mean. We discuss the motivation for, and both implementation and user consequences of, this guarantee.

Unfortunately, it is also increasingly clear that such a guarantee, though useful, is insufficient for languages intended to support sand-boxed execution of untrusted code. The existing solution in Java is only partially satisfactory. The solution to this problem is far less clear. We briefly outline one promising approach.

Pierluigi Nuzzo, UC Berkeley, Tuesday, October 12th, 2010
Time and Location: 4-5pm (540 Cory)

CalCS: Satisfiability Modulo Theory Solving for Non-Linear Convex Constraints

Certain formal verification tasks require reasoning about Boolean combinations of non-linear arithmetic constraints over the real numbers. In this talk, we present a new technique for satisfiability solving of Boolean combinations of non-linear constraints that are convex. Our approach applies fundamental results from the theory of convex programming to realize a satisfiability modulo theory (SMT) solver that uses a lazy combination of SAT and a theory solver. A key step in our algorithm is the use of complementary slackness and duality theory to generate succinct infeasibility proofs that support conflict-driven learning. Moreover, whenever non-convex constraints are produced from Boolean reasoning, we provide a procedure that generates conservative approximations of the original set of constraints by using geometric properties of convex sets and supporting hyperplanes. We have validated our solver, CalCS, on several benchmarks including formulas generated from bounded model checking of hybrid automata and static analysis of floating-point software.

Sanjit A. Seshia, UC Berkeley, Tuesday, October 5th, 2010
Time and Location: 4-5pm (540 Cory)

Integrating Induction, Deduction, and Structure for Verification and Synthesis

Even with impressive advances in formal methods over the last few decades, some problems in automatic verification and synthesis remain challenging. Examples include controller synthesis of hybrid systems with non-linear dynamics, and the verification of quantitative properties of software such as execution time. In this talk, I will present a new approach to automatic verification and synthesis based on a combination of inductive methods (learning from examples) and deductive methods (logical inference and constraint solving) using hypotheses about system structure.

Our approach integrates techniques such as satisfiability solving and theorem proving (SAT/SMT), game-theoretic online learning, learning polyhedra, numerical simulation, and fixpoint computation. I will illustrate this combination of inductive and deductive methods for three problems: (i) the synthesis of switching logic for hybrid systems; (ii) program synthesis applied to malware deobfuscation, and (iii) the verification of quantitative properties of embedded software.

Christopher Mayhew, UC Santa Barbara, Tuesday, September 21st, 2010
Time and Location: 4-5pm (540 Cory)

Hybrid Control for Topologically Constrained System

Many systems in engineering evolve on topologically complex manifolds that preclude the existence of globally asymptotically stabilizing continuous feedback control laws. Moreover, there exists no discontinuous global stabilizer that is robust to measurement noise for such systems. When one is willing to relax the admissible control policy to be hybrid, robust global asymptotic stabilization becomes possible.

In this talk, we present a Lyapunov-based hybrid control strategy that assures global asymptotic stabilization of a wide class of systems, provided that a "synergistic" family of Lyapunov functions is available. While synergistic families may be difficult to come by in general, we present useful findings for mechanical systems having rotational degrees of freedom, including the attitude of a rigid body. Finally, the attitude of a rigid body is often parametrized in terms of unit quaternions, which provide a globally nonsingular, yet two-to-one representation. This creates the need to stabilize a disconnected set of two points in the parametrization space. When such a parametrization is used, it is possible to induce an undesirable unwinding behavior, where the control law forces an unnecessary full rotation of the rigid body. We present a hybrid controller that achieves global asymptotic stability of rigid body attitude that is robust to measurement noise while avoiding unwinding.

Veselin Skendzic, Schweitzer Engineering Laboratories, Thursday, September 16th, 2010
Time and Location: 3:30-4:30pm (540 Cory)

Reinventing Our Energy Future: Smart Grid, Synchrophasors, and the Global Need for Absolute Time

Efficient use of energy is one of the core problems facing our civilization. A typical human can thrive on a 1,200 calorie diet, which is roughly equivalent to the amount of energy (gasoline) that the same person uses for a simple 0.7 mile commute.

Electric power system (arguably the largest machine ever built) has allowed us to transfer the energy at will, with exceptional reliability and high efficiency. It has also allowed us to waste more, and has made us highly dependent on its services, becoming directly linked to the growth of our society. Ensuring our growth has become synonymous with finding new ways to grow and improve the electric power system capabilities. This seminar looks at some of the key drivers behind the �¢ï¿½ï¿½Smart Grid�¢ï¿½ï¿½ initiative and presents several new technologies (global communications, Synchrophasors and absolute time) being developed to operate the new grid.

Reinhard von Hanxleden, Christian-Albrechts-Universit���¤t Kiel, Wednesday, September 15th, 2010
Time and Location: 4-5pm (540 Cory)

Lightweight, Deterministic Concurrency and Preemption in C and Java

The control flow of reactive systems typically entails not just the sequential control flow found in traditional programming languages, such as conditionals and loops, but also exhibits concurrency and preemption. How to express this adequately in an imperative language such as C or Java is a notoriously difficult problem. Threads and associated synchronization primitives are widely used, but entail significant overhead and easily lead to non-determinism and deadlock.

I will present a light-weight approach to embed reactive, deterministic control flow in traditional sequential imperative programming languages. The approach is inspired by coroutines and the synchronous model of computation. A prototypical implementation for C, called Synchronous C (SC), is freely available. An adaptation for Java is currently under development.

Sean Humbert, University of Maryland, Thursday, September 9th, 2010
Time and Location: 4-5pm (540 Cory)

Guidance, Navigation, and Control Challenges of Aerial Microrobotics

Successful realization of insect-based aerial microrobotic vehicles faces significant hurdles due to fast dynamics, small payload capacities, and the absence of a quantitative reduced-order description of the flight mechanics. Moreover, the stringent size, weight, and power (SWaP) constraints render traditional sensing and processing approaches unusable. Insect nervous systems, which function under similar constraints, offer a promising alternative. In these small organisms, spatially distributed arrays of simple sensors that pool localized measurements are processed in parallel by sensory interneurons that converge onto relatively small numbers of motor neurons responsible for controlling locomotion. In addition to this unique approach for rapid extraction of information for stability augmentation and navigation, behavioral analysis and measurements from high speed videography indicate that insects leverage passive aerodynamic mechanisms attendant to flapping motions to further minimize sensing and feedback requirements. This talk will address (a) a control- and information-theoretic framework in which to analyze the advantages of this unique sensorimotor architecture; (b) reduced order models of flapping flight dynamics and analysis of high speed videography of insect gust response to understand the passive aerodynamic stability mechanisms; and (c) hardware implementations of insect-inspired sensors and the development of a 10g flapping micro air vehicle.


Christoph Kirsch, University of Salzburg, Tuesday, September 7th, 2010
Time and Location: 4-5pm (540 Cory)

Short-term Memory for Self-collecting Mutators

We propose a new memory model for heap management, called short-term memory, and concurrent implementations of short-term memory for Java and C, called self-collecting mutators. In short-term memory, objects on the heap expire after a finite amount of time, which makes deallocation unnecessary. Self-collecting mutators requires programmer support to control the progress of time and thereby enable reclaiming the memory of expired objects. We informally describe a simple translation scheme for porting existing programs to self-collecting mutators. As shown by our experimental results on several benchmarks, self-collecting mutators performs competitively with garbage-collected and explicitly managed systems. Unlike garbage-collected systems, self-collecting mutators does not introduce pause times and provide constant execution time of all operations, independent of the number of reachable objects, and constant short-term memory consumption after a steady state has been reached. Self-collecting mutators can be linked against any unmodified C code introducing a per-object space overhead of one word and negligible runtime overhead. Short-term memory may then be used to remove explicit deallocation of some but not necessarily all objects.

Joint work with Martin Aigner, Andreas Haas, and Ana Sokolova.


Mikael Johansson, KTH - Royal Institute of Technology, Tuesday, August 31st, 2010
Time and Location: 4-5pm (540 Cory)

Reliable Real-Time Sensor Networking for Control

It is well-known that communication delays and packet losses impair the achievable performance of closed-loop control systems. At the same time, it is also well-known that there is an inherent trade-off between communication latency and reliability. In this talk, we will develop scheduling policies for unreliable multi-hop mesh networks that allow to attain the optimal performance of networked control loops. To understand the application requirements of industrial monitoring and control, we first study a simple estimation problem under unreliable communication. This allows us to derive a closed-form expression of how the optimal estimation error variance depends on communication latency and loss. We then shift focus to transmission scheduling and present optimal policies for minimizing the latency of data collection and command dissemination operations. We observe that these latency-optimal policies can be unreliable in the presence of packet losses and that higher reliability can be obtained at the expense of longer delay. To characterize the trade-off between latency and loss, we develop joint routing and scheduling policies that maximize reliability under a hard deadline constraint. The solution to this problem allows us to trace the achievable loss-latency region for any given multi-hop mesh network and, hence, the achievable performance of a control loop closed over the network. Implications of our results on current and emerging standards are discussed and experimental validation results are presented. The talk is based on joint work with students, postdocs and colleagues at KTH and SICS.


Previous topic  |  This topic  |  Next topic
Previous article  |  This article  |  Next article
You are not logged in 
©2002-2018 U.C. Regents