Computing stuff tied to the physical world

The Knapsack problem

In Musings on Jun 20, 2013 at 00:01

This is related to the power consumption puzzle I ran into the other day.

The Knapsack problem is a mathematical problem, which is perhaps most easily described using this image from Wikipedia:


Given a known sum, but without information about which items were used to reach that sum (weight in this example), can we deduce what went in, or at least reason about it and perhaps exclude certain items?

This is a one-dimensional (constraint) knapsack problem, i.e. we’re only dealing with one dimension (weight). Now you might be wondering what this has to do with anything on this weblog… did I lose my marbles?

The relevance here, is that reasoning about this is very much like reasoning about which power consumers are involved when you measure the total house consumption: which devices and appliances are involved at any point in time, given a power consumption graph such as this one?

Screen Shot 2013-06-17 at 09.35.49

By now, I know for example that the blip around 7:00 is the kitchen fridge:

Screen Shot 2013-06-17 at 09.35.49

A sharp start pulse as the compressor motor powers up, followed by a relatively constant period of about 80 W power consumption. Knowing this means I could subtract the pattern from the total, leaving me with a cleaned up graph which is hopefully easier to reason about w.r.t. other power consumers. Such as that ≈ 100 W power segment from 6:35 to 7:45. A lamp? Unlikely, since it’s already light outside this time of year.

Figuring out which power consumers are active would be very useful. It would let us put a price on each appliance, and it would let us track potential degradation over time, or things like a fridge or freezer needing to be cleaned due to accumulated ice, or how its average power consumption relates to room temperature, for example. It would also let me figure out which lamps should be replaced – not all lamps are energy efficient around here, but I don’t want to discard lamps which are only used a few minutes a day anyway.

Obviously, putting an energy meter next to each appliance would solve it all. But that’s not very economical and also a bit wasteful (those meters are going to draw some current too, you know). Besides, not all consumers are easily isolated from the rest of the house.

My thinking was that perhaps we could use other sensors as circumstantial evidence. If a lamp goes on, the light level must go up as well, right? And if a fridge or washing machine turns on, it’ll start humming and generating heat in the back.

The other helpful bit of information, is that some devices have clear usage patterns. I can recognise our dishwasher from its very distinctive double power usage pulse. And the kitchen boiler from it’s known 3-minute 2000 W power drain. Over time, one could accumulate the variance and shape of several of these bigger consumers. Even normal lamps have a plain rectangular shape with fairly precise power consumption pattern.

Maybe prolonged data collection plus a few well thought-out sensors around the house can give just enough information to help solve the knapsack problem?

  1. Seems doable, like you said anything that consumes energy is going to show some sign of it. I expect a room node as-is can detect the usage of almost every appliance out there. The fridge and dishwasher heat would work easily. Lights are light. Boiler is heat again. I can’t think of anything offhand that doesn’t put out light, heat, or both while consuming a meaningful amount of power. Even that laser printer, if you hack it open and stuff a temperature sensor in it somewhere. Very curious to see what comes next in this series!

  2. If you measure voltage and current separately, you should be able to distinguish at least resistive (heater, old style lamp) and capacitive or inductive loads (compressor in a fridge). Modern switching power supplies probably look “interesting” when measured this way so maybe you could detect those too.

  3. There’s already quite a lot of academic research in this field stemming either from algorithm research as well as privacy concerns. If you want to go that way I’d suggest to dig there a bit starting for example from this paper (including some cited work):

  4. A chap called Jack Kelly is thinking about student projects on similar lines:

    And yes, what osma says: it’s at least a two dimensional knapsack problem when you have the real and imaginary components of the current. If, as I think, switch-mode supplies tend not to take a nice smooth sine curve there’s probably more information still available.

  5. When I first saw the picture I thought you were having hand luggage problems on Ryan air!

  6. Working in the frequency domain on EMI seems to be quite interesting for this type of classification as described in this paper :

Comments are closed.