Problem 677677 · hard · Level 06 Heuristics & Optimization

Spotting the Open Window From the Heating Log

moving horizon · least squares · parameter estimation · change detection · numpy · time-varying system

A smart thermostat learns how fast a room loses heat, so that it can warn when something changes, such as a window left open. Every 10 minutes it logs the room temperature temps[k] (°C), the outside temperature outside[k] and the heater power power[k] (kW). Its model of one interval is

temps[k+1] - temps[k] = alpha * (outside[k] - temps[k]) + beta * power[k]

where alpha is the share of the indoor-outdoor difference lost per interval (larger when a window is open) and beta the warming per kW. Both are unknown, and alpha may change at any moment.

Every interval k = 0, ..., n-2 gives one equation: the row [outside[k] - temps[k], power[k]] times [alpha, beta] should equal temps[k+1] - temps[k]. A single least-squares fit over the whole log mixes the closed-window and open-window hours into one compromise value. A moving-horizon estimate fits only the latest window intervals: for every end interval e = window-1, ..., n-2, fit the rows k = e-window+1, ..., e with numpy.linalg.lstsq(A, b, rcond=None)[0] and keep its alpha.

Write heat_loss(temps, outside, power, window, threshold) that returns a tuple of three things:

  1. the list of windowed alpha estimates, one per end interval e in order;
  2. the first end interval e whose estimate is greater than threshold (the alarm), or None;
  3. the alpha of one fit over all n - 1 intervals.

Examples

Input:  temps   = [20.0, 19.65, 19.01, 19.57, 20.16, 20.61, 20.29, 20.81, 17.62, 15.23, 14.6, 14.12, 12.91, 11.72]
        outside = [5.5, 6.3, 6.2, 7.0, 6.1, 5.5, 6.7, 5.1, 5.6, 6.2, 6.4, 5.9, 6.8, 6.0]
        power   = [1.0, 0.0, 3.0, 3.0, 3.0, 1.0, 3.0, 0.0, 0.0, 3.0, 3.0, 1.0, 0.0, 1.0]
        window = 4, threshold = 0.1
Output: ([0.049673159653830595, 0.048254277515437344, 0.04692080954517276, 0.04681870522815676, 0.15630106853037584,
          0.1697877877741976, 0.18975416580259025, 0.20147884879297087, 0.19766618434423375, 0.19338519108648972],
         7, 0.11472053705929443)
Explanation: the window was opened during interval 7. The first four windows (ending at e = 3 to 6) agree
on alpha = 0.05; the window ending at e = 7 already contains the first open-window interval and jumps to
0.16, which raises the alarm. The last windows hold only open-window data and settle near 0.2. The
single fit over the whole log says 0.115, wrong for both halves.

Input:  temps = [20.0, 19.0, 18.5], outside = [10.0, 10.0, 10.0], power = [0.0, 1.0, 0.0], window = 2, threshold = 0.05
Output: ([0.09999999999999995], 1, 0.09999999999999995)

Some tests use room_log(n, seed), defined for you, which returns a simulated log (temps, outside, power) of n samples in which a window opens somewhere in the middle. To see the change, press Run with plot(heat_loss(*room_log(300, 1), 20, 0.08)[0], kind="step").

Constraints

  • 3 <= len(temps) == len(outside) == len(power) <= 10**4 (the last outside and power are not used)
  • 2 <= window <= len(temps) - 1; every window in the tests has a unique least-squares solution
  • no estimate in the tests is within 1e-6 of threshold
  • answers are compared with a tolerance of 1e-6

Goals

  • Estimate a model parameter by least squares over a sliding window of recent samples
  • See why one fit over the whole log gives a value that is true of neither part when the parameter changes
  • Raise an alarm the first time the windowed estimate crosses a threshold
Starting Python…