
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: 45pm (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 multihop 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: 45pm (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 taskoriented studies such as motion coordination, formation operations and formation robustness.
 Silviu Craciunas, University of Salzburg, Tuesday, November 30th, 2010
Time and Location: 45pm (540 Cory)
Programmable Temporal Isolation for RealTime Systems
We introduce a novel scheduling paradigm for hard realtime uniprocessor
systems, called Variablebandwidth Server (VBS), that enables adaptation of
software processes to varying realtime 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 VBSscheduled
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 frequencyscaling 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 realtime 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: 45pm (540 Cory)
Large Scale Surveillance and Aggressive Coordination in MultiRobot 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 highresolution data over large areas, process that data in a decentralized way, and act on the environment to affect a desired largescale change. In this talk I will describe two recent advances in multirobot 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 multirobot 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: 45pm (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 NPHard and an original polynomial 2approximation 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: 45pm (540 Cory)
Optimal Control of Switched Systems:
An Embedding Approach with Application
To a WMR and RealTime Model Predictive Control of a dcdc 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 realtime model predictive control of a dcdc 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 centeraligned 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: 11am12pm (540 Cory)
Digital Signal Processing with Protein Molecules and DNA Strands
Digital signal processing (DSP) refers to nonterminating 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 biochemical 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 onetime 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 feedforward path or a feedback loop. Implementing a delay operation through the chemical reactions is a nontrivial task, and is one of the major contributions of our work. We describe a 3phase 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, crosstalk cancellation and equalization of proteinprotein 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: 45pm (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: 45pm (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 closedloop performance of the
networked control system. It will be argued that the underlying
schedulingcontrol problem has a nonclassical 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
eventtriggered 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: 45pm (540 Cory)
Scal: Nonlinearizable 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
klinearizability with k > 0 to also allow sequences of up to k  1
sequential operations to be reordered arbitrarily and thus execute
concurrently. With a klinearizable stack, for example, a pop
operation may not return the youngest but the kth youngest element on
the stack. It turns out that klinearizability may be tolerated by
concurrent applications such as process schedulers and web servers
that already use it implicitly. Moreover, klinearizability 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
klinearizability probabilistically. We introduce Scal, an opensource
framework for implementing klinearizable 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: 34pm (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
interleavingbased semantics for dataracefree 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
sandboxed 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: 45pm (540 Cory)
CalCS: Satisfiability Modulo Theory Solving for NonLinear Convex Constraints
Certain formal verification tasks require reasoning about Boolean combinations of nonlinear arithmetic constraints
over the real numbers. In this talk, we present a new technique for satisfiability solving of Boolean combinations
of nonlinear 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 conflictdriven learning. Moreover, whenever nonconvex 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
floatingpoint software.
 Sanjit A. Seshia, UC Berkeley, Tuesday, October 5th, 2010
Time and Location: 45pm (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 nonlinear 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), gametheoretic 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: 45pm (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 Lyapunovbased 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
twotoone 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:304: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, ChristianAlbrechtsUniversitÃ�ï¿½Ã�Â¤t Kiel, Wednesday, September 15th, 2010
Time and Location: 45pm (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 nondeterminism and deadlock.
I will present a lightweight 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: 45pm (540 Cory)
Guidance, Navigation, and Control Challenges of Aerial Microrobotics
Successful realization of insectbased aerial microrobotic vehicles faces significant hurdles due to fast dynamics, small payload capacities, and the absence of a quantitative reducedorder 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 informationtheoretic 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 insectinspired sensors and the development of a 10g flapping micro air vehicle.
Website: http://www.avl.umd.edu/
 Christoph Kirsch, University of Salzburg, Tuesday, September 7th, 2010
Time and Location: 45pm (540 Cory)
Shortterm Memory for Selfcollecting Mutators
We propose a new memory model for heap management, called shortterm
memory, and concurrent implementations of shortterm memory for Java
and C, called selfcollecting mutators. In shortterm memory, objects
on the heap expire after a finite amount of time, which makes
deallocation unnecessary. Selfcollecting 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 selfcollecting
mutators. As shown by our experimental results on several benchmarks,
selfcollecting mutators performs competitively with garbagecollected
and explicitly managed systems. Unlike garbagecollected systems,
selfcollecting mutators does not introduce pause times and provide
constant execution time of all operations, independent of the number
of reachable objects, and constant shortterm memory consumption after
a steady state has been reached. Selfcollecting mutators can be
linked against any unmodified C code introducing a perobject space
overhead of one word and negligible runtime overhead. Shortterm
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.
Website: http://tiptoe.cs.unisalzburg.at/shorttermmemory/
 Mikael Johansson, KTH  Royal Institute of Technology, Tuesday, August 31st, 2010
Time and Location: 45pm (540 Cory)
Reliable RealTime Sensor Networking for Control
It is wellknown that communication delays and packet losses impair the achievable performance of closedloop control systems. At the same time, it is also wellknown that there is an inherent tradeoff between communication latency and reliability. In this talk, we will develop scheduling policies for unreliable multihop 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 closedform 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 latencyoptimal 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 tradeoff 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 losslatency region for any given multihop 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.
Resources
