Fast Demand Response: ColorPower 2.0

I'm quite happy to take the cap off of this paper: at long last, the paper on the ColorPower 2.0 paper, Fast Precise Distributed Control for Energy Demand Management, is officially published, and I can put it up as well.  The pictures have been up before, in these two posts, and now you can learn all the key ideas about how we're doing our distributed energy management.

This builds on the prior work from Vinayak Ranade's thesis and paper in SASO 2010, where we showed that fast distributed control of energy demand was possible.  The controller we used in that paper was terrible, though, and we acknowledged that right there in the paper---it just wasn't the focus then, and we hadn't had a chance to study that aspect of the problem well.

Over the last year, however, first my colleague Jeff Berliner at BBN figured out the right representation for understanding the control problem, and then I was able to turn that into an algorithm to actually do the control correctly.  Together, and with the help of Kevin Hunter, we refined it into the shining gem presented in this paper: the ColorPower 2.0 algorithm (can you tell I'm excited about it?).  We simulated it at all sorts of scales, with all sorts of problems, and it always stands up well---and better, matches our theoretical predictions nicely too.  Plus the experiments produce beautiful looking figures like these, showing the convergence and quiescence times of the algorithm for abrupt changes of target:

The bottom line: we've got a system that should be able to shape the energy consumption of millions of consumer devices in only a few dozen seconds.  Now we just have to get it out of the lab and into the field. Come talk to us if you want to use it, though, since it's also protected by patents...

Today is a Good Day to Demo

One of the things I always feel indebted to Jonathan Bachrach for is how pretty Proto looks.  When we were first developing the language together, he was the one who hacked together the original simulator with OpenGL, based on the previous work he'd done with multimedia processing languages.  So Proto's simulator got built by somebody to whom appearance really mattered, and with an artists touch and attention to detail.  And so, to me at least, the simulations we make look gorgeous, and I just love playing with them.

Well, today I got to show off my toys in the SASO demo session.  This spring, I put together a set of self-stabilizing algorithms for robot team formation. Kyle Usbeck and Jeff Cleveland then helped turn these into a nice demonstration---well, it was a contest entry originally, but SASO didn't get enough entries, so they just rolled us into the demo session.  In any case, the robots form up into little "snakes" for each team, and go crawling randomly around in 2D or 3D in wonderfully distracting colorful patterns.

Kyle and Jeff made a nice movie showing off the algorithms, and how they're resilient to pretty much any way you can think of the break them---adding robots, destroying robots, moving robots, changing goals and communication properties, etc.:

The upshot of all of this today is that I got to talk myself hoarse in front of a projector for two hours while lots of folks enjoyed the beauty of our simulation, and hopefully even got to understand a bit about Proto and the continuous space abstractions that made it all so easy to do.

If you want to play with this stuff too, feel free: you can read about it and download it all here.

How resilient is it anyway?

As engineers and scientists, we worry a lot about how well the things we build hold up.  Anything that goes out into the real world will suffer all sorts of buffets from unexpected interactions with its environment, strange behaviors by its users, idiosyncratic failures of components, and myriad other differences between theory and reality.  So we care a lot about knowing how resilient a system is, but don't currently have any particularly good way of measuring it.

Oh, there's lots of ways to measure resilience in particular aspects of particular systems.  Like if I'm building a phone network, I might want to know how frequently a call fails---either by getting dropped or failing to connect in the first place.  I might also measure how call failures increase when there are too many people into one place (like a soccer match) or when atmospheric conditions degrade (like a thunderstorm) or when a phone goes haywire and starts broadcasting all the time.

But these sorts of measures leave a lot to be desired, since they only look at particular aspects of a system's behavior and don't have anything to say about what happens when we link systems together to form a bigger system.  That's why I'm interested in generic ways to measure the resilience of a system.  My hope is that if we can design highly resilient components, then when they're connected together to former bigger components, that we will be more easily able to ensure that those larger components are resilient as well.  

Even better is if we can get compositional proofs, so that we know that certain types of composition are guaranteed to produce resilient systems---just as there are compositions of linear systems that produce linear systems and digital systems that produce digital systems, etc.  This is the type of foundation that lays the groundwork  for explosions in the complexity and variety of artifacts that we can engineer, just like we've seen previously in digital computers or clockwork mechanical systems.  I want to see the same thing happen for systems that live in more open worlds, so that we can have an infrastructure for our civilization that helps to maintain itself and that can tolerate more of the insults that we crazy humans throw at it.

But first, small and humble steps.  In order to be able to even formulate these problems of resilience sanely, we need to better quantify what this "resilience" thing might mean.  In my paper in the Workshop on Evaluation for SASO workshop at IEEE SASO, I take a crack at the problem, proposing a way to quantify "graceful degradation" using dimensionless numbers.  The notion of graceful degradation is an important one for understanding resilience, because it gets at the notion of margins of error in the operation of a system.  When you push a system that degrades gracefully, you start seeing problems in its behavior long before it collapses.  For example, on an overloaded internet connection that shows graceful degradation, things start going slower and slower, rather than going directly from fast communication to none at all.

In my paper, I propose that we can measure how gracefully a system degrades in a relatively simple manner.  Consider the space formed by all the parameters describing the structure of a system and of the environment in which it operates.  We break that space into three parts: the acceptable region where things are going well, the failing region where things have collapsed entirely, and the degraded region in between.

If we draw a line slicing through this space, then we get a sequence of intervals of acceptable, degraded, and failing behavior.  We can then compare the length of the acceptable intervals and the degraded intervals on their borders.  The longer the degraded intervals that separate acceptable and failing intervals, the better the system is.  So in order to know the weakest point of a system, we just look for the lowest ratio between degraded and acceptable on any line through the space.

What this metric really tell us is how painful is the tradeoff between speed of adaptation and safety of adaptation.  The lower the number, the easier it is for changes to drive the system into failure before it can effectively react, or for the system to accidentally drive itself off the cliff.  The higher the number, the more there is a margin for error.

So, here's a start.  There are scads of open questions about how to apply this metric, how to understand what it's telling us, etc., but it may be a good point to start from, since it can pull out the weak points of a system and tell us what they are...

Enter SASO 2012

This week is the 6th annual SASO: the IEEE Conference on Self-Adaptive and Self-Organizing Systems.  If any conference is my "home conference" at the moment, this is probably it.  The attendees of this moderate size (~100 people) single track conference tend to be all over the map in terms of interests and applications, but there is one thing that clearly unites us: a dissatisfaction with the brittleness of ordinary complex systems engineering, and a desire to address it by making the systems smarter in some way.

It makes for a very diverse and rather messy conference, with a lot more proof-of-concept and early work than finished systems or grand results.  There's also a lot of folks out there in the greater scientific world with really flaky ideas about how to go about this type of resilient engineering---lots of magical thinking of the form "it smells kinda like Nature, and Nature is awesome, so it must be awesome too!"  The conference has tightened itself up quite a bit over time, though, and by now the quality of the papers is generally pretty good.  My Ph.D. advisor, Gerry Sussman, once told me that he judges the quality of a conference by how long he remembers something that he learned there, and in that sense SASO does quite well for me.

I'm much looking forward to SASO this year, the more so because I'm going to be quite busy talking about interesting things.  In particular, the highlights of the conference for me are:

1. Monday, I will be talking about metrics for graceful degradation in the Workshop on Evaluation of SASO Systems
2. Tuesday, I will be chairing a session in the morning and giving a demo of our self-stabilizing robot team formation algorithms in the afternoon.
3. Wednesday, I will be presenting my work on the ColorPower algorithm for distributed energy demand management.
4. Finally, on Thursday, I'll be sitting on a panel on New Research Directions, talking about my views on the need for nature-inspired systems to move beyond one-off applications and toward the extraction of principles and laws.

And then there's colleagues to catch up with and other talks to see... it will be a busy week, and also my first time away from home without Harriet since she was born.  But fear not, dear reader, I shall salve my wounds and fatigue by writing some extra blog posts about all of the cool things I get up to this week.

Pretty BioCompiler GRN Diagrams

One of the pieces of work I'm rather proud of is my Proto BioCompiler.  Back in 2008, as I was hanging around at the synthetic biology lunches at MIT, I realized that there was a nice tight mapping between the genetic regulatory network diagrams that the biologists were drawing and the dataflow computation graphs that I was using to express the semantics of Proto.  Basically, in biology you can represent a computation with a bunch of reactions evolving in parallel over continuous time, with the products of one reaction being used as the inputs for others.  Similarly, in Proto my model of computing had a bunch of operations evolving in parallel over continuous space and time, with the outputs of one operation being used as the inputs for others.

So after giving a couple of exploratory talks in the lunch meetings, I wrote up the ideas in this paper in the first spatial computing workshop, and then went ahead and and actually built the thing a couple years later.  We've been refining it ever since, and the lovely thing about the BioCompiler is that it takes all of the guesswork out of designing biological computations.  Most of the really effective genetic regulations that we can engineer with right now are repression, which means that designs are typically implemented in negative logic.  For example, "A and B" might be implemented as "not either not A or not B", which is just much harder for us poor humans to think about, and means that, for me at least, anything over a few regulatory elements is almost certain to contain mistakes in the first design.  When you're dealing with biological experiments, where it can be weeks from design to the very first test, you really don't want to get it wrong the first time.

So the BioCompiler lets us just sidestep that whole mess: you write the program in normal red-blooded American positive logic, and it turns all inside out on its own and then optimizes.  Won't work for every program, but for the range that it knows how to work in, it's beautiful.  In an instant, out of the BioCompiler comes the new design and also a simulation file for testing it in silico.

The only problem is that the output of the BioCompiler looks like this:

BioCompiler supposedly "human readable" output for an XOR circuit

or, worse, like this:

Just the top bit of the machine-readable XML generated by BioCompiler for an SR-latch circuit

Bleah.  Sure, there's a genetic regulatory network buried in there, but to actually communicate it to another human we need to turn that soup into a diagram, and that's not only a pain but another really good way to introduce errors into the works.

No more.  I just recently sat down with the manual for GraphViz and figured out how to do build complicated custom nodes, with which a diagram can be created.  Then I hacked a new output option into the biocompiler, for creating GraphViz diagrams.  The result is still a bit rough on the artistic front, but intelligible and can turn into an SVG file for editing.  Booyah!

Diagram of a circuit for computing ordering relations

In Which Jake Questions the Free Market

One of the things that makes my work with Zome different from a lot of other approaches to modulating energy demand is that we aren't trying to solve the problem by using price-signalling or any other sort of market-based approach.

Market-based approaches are the dominant line of thinking for how to control demand, and when you are first approaching the problem, the reasoning behind it makes sense:

• A lot of things in our society manage supply/demand relations pretty well by markets, where changes in supply lead to changes in price that lead to change in demand, until equilibrium is reached.  This is total Econ 101 material.
• At the macro-scale, power in the US grid is pretty much entirely managed by markets, and that works pretty well (if you ignore the whole Enron thing).
• Pilot studies where you give people information about power prices (e.g., through a red light that glows when the price is high), and they moderate their demand, or you give the same information to appliance controllers (e.g., thermostats with a budget and a cooling goal) and they shift their use accordingly.

I don't trust it though.  You see, I just think that price is a pretty lousy and impoverished signal, and there's no reason to restrict ourselves to that when we're running an algorithm on computers.  If you commit to using a market-based approach, you're throwing out pretty much the whole world of distributed algorithms and other engineered self-organization approaches.  And most engineered systems don't use markets for good reason---they're a lot of complex hassle to get right, give you lots of ways to shoot yourself in the foot with unexpected emergent effects, and really just beg for exploitation if you get any real money involved.

If you assume you have to solve the problem with a market, you probably can (I'm pretty sure market-based approaches are Turing complete, if you allow complex enough structures and derivatives), but you might have to twist the problem into a pretzel to do so.

So I tend instead to think the right way to approach a complex distributed control problem like energy demand shaping is to start by solving the distributed control problem, and then figure out how to match it well with external incentives.  Maybe the answer will be a market, but usually it won't, just because markets are only one tiny corner of a really big design space.

And I might be on the way to saying something much more definitive about it.  Just recently, when looking at how the Zome approach compares to price-signalling approaches, I noticed that it's really easy for a distributed demand response market to end up completely failing and always being very far from equilibrium.  And this result just might be more general...

Making the cover of ACS Synthetic Biology

Just a brief note today... the current issue of ACS Synthetic Biology, which includes our papers on our TASBE tool-chain for designing organisms and our MatchMaker algorithm for selecting genetic regulatory elements, has the following lovely cover image and blurb:

This cover depicts bio-design automation’s transformative effect on synthetic biology. DNA design increasingly will be a computational effort culminating in software “toolchains” which cover the specification, design, and assembly of novel biological systems.

Dear reader, I am proud, because that image is an illustration inspired by our TASBE tool-chain paper. That is all.

Publish and Perish

Dear reader, if I can beg your indulgence for a little while, I'd like to do some philosophical maundering for a bit.  Before my paternity leave, I'd been through a hard stretch of "publish and perish" recently (we had a bit of a perfect storm of anticipated deadlines, unanticipated deadlines, and requests for revision) and so the nature of publication and science has been much upon my mind.

One of the standard maxims of science that every scientist knows is "publish or perish"---if you don't get your ideas out there, you can't have an impact.  Of course, there's all the other meanings of that statement as well, having to do with career and funding and all that, but I personally tend to look at it through the filter of the impact of my ideas.

Here, I find the philosophy of Bruno Latour compelling (though I disagree strongly with him in certain other areas): in their anthropology of science, he and Woolgar present a "cycle of credit" that summarizes the scientific world as an economic enterprise.  Scientists then act as investors, building research capital by transforming one type of scientific resource into another.

The cycle (filtered through my interpretation and mutation-inserting memory) is roughly:

Position and publications give a reputation that can be used to secure funding.  Funding allows the production of scientific data.  Data in turn supports the production of publications, and so on around the cycle, with established researchers likely to have significant research capital moving through all stages at the same time.

Where, you may ask, are ideas in there?  Why at every link!  That's the broader job of the scientist.  The standard image of science being merely about production of data and testing of hypotheses is only part of the picture, though a cornerstone on which the whole enterprise rests.  Drop any of the other ingredients out as well, though, and the whole enterprise founders.

I know that some might find this "economic" view of science as crass and unsavorily political.  I don't think so, though, because I think about science as being not just about knowledge, but able knowledge that matters in some way.  Oh, it doesn't necessarily have to matter any time soon, and it doesn't necessarily need to be practical---some things are worth knowing simply because it shapes our understanding of the universe that we live in (an aside: one of my undergraduate degrees is in theoretical mathematics.  I always assumed that things like abstract algebra, topology, and measure theory would be purely useless in the "real world," but enjoyed them simply for the sheer power they gave over the abstract world.  To my great surprise, I now rely on pretty much all of the theoretical mathematics I even learned.).  So when I look at the cycle of scientific credit, I see each of these steps as marking the motion of ideas outward.  Data is how you know your ideas are meaningful, publications are how you spread them to others where they will have an impact, and position and funding are amplifiers that the world gives you as it starts believing your ideas are worthwhile.

What I do notice is missing from Latour's cycle, however, is a clear location for professional service, like organizing or public outreach or teaching.  For myself, at least, that's been a very important part of keeping forward momentum, as well as something I think is really important if you take the "impact of knowledge" view of science that I do.  Service doesn't really fit the diagram neatly: in my experience, it tends to stem from publications, funding, and itself and it feeds into all of these by indirect means.  But I think it doesn't really fit because it's largely a different type of reputation---but, well, any model only takes you so far.

So: publish or perish.  True, I suppose, but I prefer it when it's for the right reason.  Not for fear of perishing, but because I've got things that I have learned that I need to communicate and an audience I want to communicate them to.  And that, I suppose, is why I'm not snobbish when it comes to Impact Factor of my publication venues.  There are places I publish because there are people I want to talk to, others I publish because I want to broadcast an idea, and others simply because I want to archive a key (but possibly obscure) result for later reference.  Only for broadcasting an idea does impact factor really matter---the others are all about getting a strong enough peer validation and placing the ideas where the right group of people will be able to easily find them.  Publish or perish?  We'll see what what happens, but I'm content as long as I'm neither hiding nor overselling the things that I accomplish.

On the Evaluation of Space-Time Functions

Back in May, I discussed my ongoing obsession with first class space-time functions---programs that can be dynamically created, moved around, and operate on one another, even though they're being run distributed over many devices scattered across space and time.

We've now made another step forward, with the publication of a new paper, On the Evaluation of Space-Time Functions.  This paper is an extension of last year's Spatial Computing Workshop paper, generalizing the results to be not just about Proto, but in fact any distributed computing system (of which Proto is simply our prototypical example).

I'm rather proud of this paper, and think it's a fairly readable discussion of these concepts---though still not for the faint of heart.

Presenting In Absentia

One of the lovely things about having good colleagues: just because you're having a major life event doesn't mean everything has to grind to a complete halt.  For the month preceding my daughter's expected due date, I was grounded---not travelling anywhere, in case she should decide to come early.


That time also overlapped with a couple of conference presentations, and fortunately my colleagues were able to go in my place.  Aaron Adler took over my invitation to present on our synthetic biology tools at the Biological Systems Design meeting at ISMB, a major computational biology conference,
and Hala Mostafa presented our paper, A Manifold Operator Representation for Adaptive Design, at the Generative & Developmental Systems track of the GECCO evolutionary computation conference.

From their reports, it sounds like both meetings went very well, and that our work was well received.  Frankly, though, I'm quite glad I didn't take the risk of missing my daughter's birth.  Professional life continues, and there will be many more chances for me to travel in the future---and perhaps even take a baby with me, if she turns out to be social and a good traveller.