The Blog of Ian Mercer.

Multiple hypothesis tracking

Cover Image for Multiple hypothesis tracking

My home automation system collects a lot of data from the 250+ sensors in it. These sensors feed my complex state machine logic to decide which rooms are occupied and which lights to put on or turn off. It works well, but it's not perfect so it errs on the side of leaving lights on longer than it needs to in rooms that you've passed through. It also doesn't learn your habits, it just has some tried and tested state machine transitions that work really well for most situations. So for many years I've been considering what kind of machine learning I could apply in order to say for certain which rooms are occupied and which are not and how many people are in each room.

This is a very hard problem for ML because it isn't just a sequence, is temporal data: it's not just the sequence [A-B-C] that matters but the time between each of those events and those intervals are hard to classify. In some cases we care about triggers happening seconds apart, in some minutes apart, in some ~24 hours apart, a week apart or even a year apart. And in most cases those intervals aren't precise, some days you get up early, some days you don't. So good luck just throwing that at an RNN and hoping that it will spot the birthday celebration state that happens once a year for each person in the house.

It's also a hard problem because the data is fairly sparse. A front door for example might be opened just a couple of times a week. So although I have 150GB+ of historical data for my system there are still fairly few instances of some events like 'holiday party' to analyze.

But the hardest problem is that none of this data is labeled: nobody has annotated every event and state transition with a label that says "4 people in home, 1 in kitchen, 1 in study and 2 in living room" which might allow a machine learning algorithm to be trained, and I'm certainly not going to sit here for a month capturing a label for each transition even if the house could chat to me and ask "what state are we in now" which I guess it could.

And so, after years of research and reading papers on machine learning to find a solution, I kept ending back on the research around Multiple Hypothesis Tracking. I began prototyping my own version many years ago but finally, driven by the lack of labeled data for machine learning, I went ahead and finished it. And it works!

In essence MHT works by maintaining a list of hypotheses, each of which has an associated probability and a set of numbers saying how many people it thinks are in each room. Whenever it receives a sensor event in a given room it updates this list using probabilities for the possible transitions that this sensor event could imply.

For home automation these transitions are (in order from most likely to least likely):

  • Someone already in this room just moved again
  • Someone moved from a neighboring room to this room
  • Someone jumped from a room elsewhere to this room bypassing some other rooms where sensors might not have tripped
  • Someone spontaneously appeared in this room (Star Trek transporter!) because they arrived from somewhere outside the system, or we had failed to track them earlier, or the system had just restarted

Fortunately my home automation system treats the house as a graph so it understands which rooms are neighbors and even how many steps any given room is from all the other rooms in the house.

// Get a sorted list of rooms by distance
// (a tuple of room and distance from the first room)
var roomsByDistance = room.RoomsByDistance

On a regular interval it also recalculates all the probabilities assuming that in any room where no motion has been detected there is now a reduced probability that there is someone in that room. Eventually after a long time that room is marked not-occupied but typically it drops off the list much sooner as the system detected somone moving from it to another room.

Of course, after just a few iterations this list of possible scenarios gets impossibly long. Each sensor event spins off three or more new hypotheses. So, as is typical in this method, my algorithm trims the list of hypotheses removing all the unlikely ones. For example, on testing it thought, after just a few minutes that there might be four people in the bedroom but the associated probability of 10⁻¹⁵ corresponded roughly to the likelihood of an alien invasion starting in the bedroom so that hypothesis was trimmed.

Here's a worked example, starting from the empty set, or null hypothesis where the house is certain that nobody is home and triggering a single sensor repeatedly.

START
    p(1) {}
ONE MOVE
    p(0.81) {Office:1}
    p(0.19) {}

After the first motion detection it is fairly certain that there is one person in the office (81% chance) and gives a fairly low probablity for the house being empty (19%) which reflects that this could just be a false alarm.

SECOND MOVE
    p(0.9638271) {Office:1}
    p(0.0361) {}
    p(7.29E-05) {Office:2}

After the second motion detection it becomes even more certain that there is someone in the office, but also thinks that there could be two people there (the space alien materialized scenario, or maybe there really were two people there and we just didn' notice). The aggregate probability of the office being occupied is now up to 0.9639.

THIRD MOVE
    p(0.992981355561) {Office:1}
    p(0.006859) {}
    p(0.000159637878) {Office:2}
    p(6.561E-09) {Office:3}

After the third motion event it's now very certain that there is one person in the office (0.99298) and even more certain that there is one or more people in the office (sum = 0.993141) and very certain that the house is not empty.

Status

After just one day I'm fairly confident that this approach is working well and that it's going to be much better than my old Occupied=true/false approach which required absolute certainty that a room was empty for a very long time before shutting lights off there. If you are home alone now you can walk around and the probability that you are in a given room is very high and the probability that you are somewhere else is very low. As you follow a path through the house you reinforce your position and the probability goes up even though you are moving rooms.

Next steps

Moving from true/false to probabilistic values for occupancy (and maybe other features in the house) is going to bring a huge change in the way my system works. Lights will be able to turn off much more rapidly in rooms that are no longer occupied as the system will have tracked you from one room to another.

But it also raises lots of new issues:

    Q: How certain do you need to be to turn a light on? 
    A: not very certain, just do it (except in bedroom where the opposite holds!). 

    Q: How certain do you need to be to turn a light off?
    A: much more certain, you don't want to put people in the dark

Closing thoughts

The application of this approach to home automation could have many interesting business aspects to it also. I will be able to tell you the probability of each room being occupied on each day of the week and the overall chance that the house is occupied for any hour of the day.

  • What if your insurance premium was calculated on that basis?
  • Could that letter from the energy company that says I'm using too much electricity factor in the fact that I work from home and realize that actually I'm actually in one of the least energy consuming homes (per occupied hour) in the neighborhood?
  • Could an alarm system based on this give the operator (and you) a probability with each alarm call 19% chance there's an intruder in the basement which might save a lot of false alarms and needless call out for the police?

Related Stories

Cover Image for Time Series Data Compression

Time Series Data Compression

This new technique to compress the time series data collected by my home automation system seems to be working really well.

Ian Mercer
Ian Mercer
Cover Image for Home Automation

Home Automation

I've been working on home automation for over 15 years and I'm close to achieving my goal which is a house that understands where everyone is at all times, can predict where you are going next and can control lighting, heating and other systems without you having to do or say anything. That's a true "smart home".

Ian Mercer
Ian Mercer
Cover Image for Bluetooth Tracking Project

Bluetooth Tracking Project

My year long Bluetooth project that won the $20,000 HCI and Microsoft competition during lockdown has continued to grow and now reliably tracks how many people are in the house and outside and can locate any device down to room level.

Ian Mercer
Ian Mercer
Cover Image for Digital Twins are never identical

Digital Twins are never identical

Digital Twin are an online representation of a real world object, a copy of its properties in the digital world and a way to send updated and commands to it. In effect I've been making them for years but now they have a trendy name.

Ian Mercer
Ian Mercer
Cover Image for Home Automation Sensors

Home Automation Sensors

An overview of the many sensors I've experimented with for home automation including my favorite under-floor strain gauge, through all the usual PIR, beam and contact sensors to some more esoteric devices like an 8x8 thermal camera.

Ian Mercer
Ian Mercer
Cover Image for Collinearity test for sensor data compression

Collinearity test for sensor data compression

One way to reduce the volume of sensor data is to remove redundant points. In a system with timestamped data recorded on an irregular interval we can achieve this by removing co-linear points.

Ian Mercer
Ian Mercer
Cover Image for 3d Printed ESP32 Brick

3d Printed ESP32 Brick

ESP32 provides a great platform for sensors around the house but by the time you've added a USB power brick, cable and enclosure it's quite messy. I wanted a device that I could just plug in with no exposed wires and no mounting needed so I designed one in OpenSCAD.

Ian Mercer
Ian Mercer
Cover Image for Bluetooth Sensing for Home Automation

Bluetooth Sensing for Home Automation

Bluetooth sensing for home automation is a great proxy for people counting as it can detect and locate each cellphone in the house. iBeacons attached to tools, cars and pets can provide a 'find my anything' feature too.

Ian Mercer
Ian Mercer
Cover Image for Light sensors for Home Automation

Light sensors for Home Automation

Having at least one light sensor is critical for any home automation system that controls lightng. Lights need to be turned on when it's dark not at specific times of day, especially here in Seattle when it can be dark and cloudy at any time of day.

Ian Mercer
Ian Mercer
Cover Image for Microwave Doppler Sensors (RCWL-0516)

Microwave Doppler Sensors (RCWL-0516)

Microwave doppler sensors can be found in some alarm sensors but there are also available very cheaply as a separate component. They offer exceptional range but suffer from false triggers requiring a probailistic approach to people sensing.

Ian Mercer
Ian Mercer
Cover Image for Optical-beam sensors

Optical-beam sensors

Optical-beam sensors are reliable and can cover a long-distance such as across a garage or aisle-way. When they include multiple-beams they have good false-trigger rejection.

Ian Mercer
Ian Mercer
Cover Image for PIR Sensors for Home Automation

PIR Sensors for Home Automation

PIR sensors are cheap and easy to use but they suffer from slow response times and low repeat rates.

Ian Mercer
Ian Mercer
Cover Image for Strain-gauges

Strain-gauges

Strain-gauges are my top-rated sensor for home automation because they are invisible, reliable and can be tuned to detect people and ignore pets.

Ian Mercer
Ian Mercer
Cover Image for Event blocks

Event blocks

Home automation systems need to respond to events in the real world. Sometimes it's an analog value, sometimes it's binary, rarely is it clean and not susceptible to problems. Let's discuss some of the ways to convert these inputs into actions.

Ian Mercer
Ian Mercer
Cover Image for Logistic function - convert values to probabilities

Logistic function - convert values to probabilities

Another super useful function for handling sensor data and converting to probabilities is the logistic function 1/(1+e^-x). Using this you can easily map values onto a 0.0-1.0 probability range.

Ian Mercer
Ian Mercer
Cover Image for ATAN curve for probabilities

ATAN curve for probabilities

In a home automation system we often want to convert a measurement into a probability. The ATAN curve is one of my favorite curves for this as it's easy to map overything onto a 0.0-1.0 range.

Ian Mercer
Ian Mercer
Cover Image for Bluetooth

Bluetooth

One of my inventions recently won a $20k global competition for applications that could help in a pandemic. It uses Bluetooth to count people.

Ian Mercer
Ian Mercer
Cover Image for Probabilistic Home Automation

Probabilistic Home Automation

A probabilistic approach to home automation models the probability that each room is occupied and how many people are in that room.

Ian Mercer
Ian Mercer
Cover Image for A state machine for lighting control

A state machine for lighting control

An if-this-then-that style rules machine is insufficient for lighting control. This state machine accomplishes 90% of the correct behavior for a light that is controlled automatically and manually in a home automation system.

Ian Mercer
Ian Mercer
Cover Image for Home Automation States

Home Automation States

Understanding the many different 'states' a house can have is critical to creating great home automation

Ian Mercer
Ian Mercer
Cover Image for Graphing gigabytes of home automation data with tableau

Graphing gigabytes of home automation data with tableau

Some interesting charts from the gigabytes of data my home automation system produces

Ian Mercer
Ian Mercer
Cover Image for iBeacons for Home Automation

iBeacons for Home Automation

My investigations into using iBeacons for home automation

Ian Mercer
Ian Mercer
Cover Image for iBeacon meetup in Seattle - January 2015

iBeacon meetup in Seattle - January 2015

My notes on the iBeacon meetup in Seattle held in January 2015

Ian Mercer
Ian Mercer
Cover Image for Home Automation Systems as a Graph

Home Automation Systems as a Graph

Using nodes and links to represent a home and all the devices in it

Ian Mercer
Ian Mercer
Cover Image for N-Gram Analysis of Sensor Events in Home Automation

N-Gram Analysis of Sensor Events in Home Automation

Using n-gram analysis to spot patterns in sensor activations

Ian Mercer
Ian Mercer
Cover Image for Xamarin Forms Application For Home Automation

Xamarin Forms Application For Home Automation

Building a Xamarin Forms application to control my home automation system

Ian Mercer
Ian Mercer
Cover Image for The Internet of Hubs (and things)

The Internet of Hubs (and things)

Maybe it should be called the Internet of Hubs instead

Ian Mercer
Ian Mercer
Cover Image for Showing home status with just a single RGB LED

Showing home status with just a single RGB LED

Multicolored LEDs can convey a lot of information in a small space

Ian Mercer
Ian Mercer
Cover Image for A wireless sensor network using Moteino boards

A wireless sensor network using Moteino boards

The diminutive Arduino boards include a powerful transmitter/receiver

Ian Mercer
Ian Mercer
Cover Image for The home as a user interface

The home as a user interface

Ian Mercer
Ian Mercer

A RESTful API for sensor data

POSTing data to a home automation system from Arduino devices

Ian Mercer
Ian Mercer
Cover Image for The Internet of Boilers

The Internet of Boilers

An experiment to measure every aspect of an HVAC / boiler system

Ian Mercer
Ian Mercer

VariableWithHistory - making persistence invisible, making history visible

A novel approach to adding history to variables in a programming language

Ian Mercer
Ian Mercer
Cover Image for A Quantified House - My Talk to the Seattle Quantified Self Meetup

A Quantified House - My Talk to the Seattle Quantified Self Meetup

My talk to the Seattle Quantified Self meetup

Ian Mercer
Ian Mercer

Integrating an Android phone into my home automation system

Some new features for my home automation using an Android phone

Ian Mercer
Ian Mercer
Cover Image for The Internet of Dogs

The Internet of Dogs

Connecting our dog into the home automation

Ian Mercer
Ian Mercer
Cover Image for GreenGoose Review

GreenGoose Review

A review of the now defunct GreenGoose sensor system

Ian Mercer
Ian Mercer
Cover Image for Home power meters revisited

Home power meters revisited

Ian Mercer
Ian Mercer
Cover Image for Home Automation Calendar Integration

Home Automation Calendar Integration

Ian Mercer
Ian Mercer

Smart home energy savings - update for 2010

Ian Mercer
Ian Mercer
Cover Image for A smart power strip

A smart power strip

Ian Mercer
Ian Mercer
Cover Image for What does a Smart House do at Halloween?

What does a Smart House do at Halloween?

My favorite home automation features for Halloween

Ian Mercer
Ian Mercer
Cover Image for Home Automation Top Features

Home Automation Top Features

Ian Mercer
Ian Mercer
Cover Image for Weather Forecasting for Home Automation

Weather Forecasting for Home Automation

Ian Mercer
Ian Mercer
Cover Image for How can I tell if my house is smart?

How can I tell if my house is smart?

Ian Mercer
Ian Mercer

Home Automation Block Diagram

Ian Mercer
Ian Mercer

World's Smartest House Demonstration

Ian Mercer
Ian Mercer

Future proof your home with a new conduit system?

Running conduit can be expensive but maybe you don't need one to every room

Ian Mercer
Ian Mercer
Cover Image for New Home Automation Server

New Home Automation Server

Ian Mercer
Ian Mercer
Cover Image for World's Smartest House

World's Smartest House

Over 15 years of experimentation with home automation

Ian Mercer
Ian Mercer
Cover Image for HX711 Strain Gauge Pulsor Sensors

HX711 Strain Gauge Pulsor Sensors

Using Pulsor sensors with an HX711 for homeautomation.

Ian Mercer
Ian Mercer
Cover Image for World's Smartest House Videos

World's Smartest House Videos

A collection of videos about my smart home efforts

Ian Mercer
Ian Mercer
Cover Image for Pressure Sensors for Home Automation

Pressure Sensors for Home Automation

Pressure sensors can detect HVAC system operation and could potentially detect clogged filters.

Ian Mercer
Ian Mercer