 Figure 1—A
combination of entry/exit-door and interior-motion information gives the needed results. |
Dreaming of those smart buildings of the future? Well, it’s time to wake up. Beau’s powerful machine-learning software figures out building occupancy patterns, yet it’s simple and small enough to run on any microcontroller.
If you’re like me, you’ve been waiting a long time for the arrival of the smart building. In theory, our homes and offices will be outfitted with intelligent lighting and energy management systems that can learn our habits and adapt to our needs.
Many people have done research on advanced building-control software using the PC, or some other "large" platform, intent on building a truly intelligent system. However, there haven’t been that many applications deployed in the marketplace.
In this article, I want to show you a software technique that exhibits machine learning but in a small and simple implementation that can run on any microcontroller. The algorithm attempts to understand the comings and goings of people and to anticipate when they might arrive next so that it can provide advance heating, cooling, lighting, and so forth.
This type of intelligent building software was first used, I believe, in certain HVAC controllers as far back as 1987. Used mostly in the lodging industry, these types of controllers are designed to squeeze every ounce of energy savings while providing adequate comfort. In many cases, the occupants don’t even realize that energy management is taking place.
For this particular application, the software is divided into two major components. The first component, the Occupancy Detection Unit (ODU), must recognize not only when the area is actively occupied and when it is not occupied, but also when the area is occupied by inactive occupants, who may be resting or sleeping.
The other component is a Pattern Learning Unit (PLU) that records the occupancy history for the area and attempts to predict the next arrival.
The ODU provides the information that the PLU uses to predict future activity. While it may seem like a no-brainer to detect occupancy in software (assuming hardware input like a motion detector), the task is tougher than it looks if you want to do it well. In fact, it’s difficult to know for certain that no one is in the area.
The problem is this: when motion activity ceases for a period of time, how do you know what has happened? Are the occupants gone? Or is there someone there who is simply inactive? The trick to solving this problem is by detecting two different types of activity—interior activity and entry/exit activity.
As shown in Figure 1, you can accomplish this task by monitoring the door(s)of an area (via door switches used in the security industry) and also monitoring the interior of the area via motion detection. Any time an entry/exit door is opened, this signals a potential change of occupancy.
| Figure 1—A
combination of entry/exit-door and interior-motion information gives the needed results. |
As Figure 2 illustrates, it’s not hard to figure out whether people are coming or going. If there is no motion detection following activity at the door, then someone must have left.
a)
b)
Figure 2—From the timing relationships, it’s easy to see when occupants leave or arrive. a—In the leaving situation, an overlap can occur which must be accounted for in software. b—This graph shows an arrival. |
Conversely, if motion detection simply ceases without any door activity, then the area is not really unoccupied. Instead, the occupants must have retired to an inactive state even though they are still in the building or area.
Clearly, the accuracy of this method is tied directly to the quality of motion-detector coverage—the more the better. For a typical house or small office, simply covering the main traffic area gives good results. Using motion detection in every room gives near-perfect performance.
In the algorithm, the search process starts when the entry/exit door is used. After the door closes, we look for motion for a period of time. If there is motion activity, then clearly someone is still on the premises. If not, then you may declare the area unoccupied.
The time period used can vary, but a good figure is in the ten-minute range. The delay period is a tradeoff. Too little time and you find that the area is frequently declared unoccupied, only to have this decision reversed a short time later when an occupant emerges from some back room. Too much delay time and energy savings are reduced while the algorithm waits for occupants who may never appear.
One issue that affects the ODU is the phenomenon of slow motion-detector release. As you might imagine, the occupancy-detection algorithm is going to start looking for motion detection as soon as the door closes. The problem is that some motion detectors stay tripped for a relatively long time after motion ceases (up to 6 or 8 s). This causes a problem when the slow motion detector is located near the entry/exit door.
While leaving, the occupant trips the detector, opens the door, steps out, and closes the door. Unfortunately, the motion detector is still triggered even though the occupant has stepped out and closed the door! You can see this in Figure 2a as the overshoot relative to the door timing.
This problem forced me to add a blanking window to the algorithm so that the real search for motion is delayed by a few seconds. Typically, a value of 6 s works well. Any more than that and the algorithm often fails to detect when someone arrives and passes through the motion-sensing area too quickly.
When that happens, the system sees the arrival but turns around and looks for evidence of someone leaving (remember, door operation starts the test process). When the system sees no motion activity, except what took place during the blanking period, it assumes that the person left again. So, the blanking window has to be set carefully.
Another type of problem can also arise. A false unoccupied state can be declared when someone leaves the area while another person, who has been inactive all along, remains hidden from motion detection. Clearly, because of this weakness, the technique should be used with great care.
Many types of automatic responses (e.g., arming a security system) should not be implemented. While the system’s performance can be increased by adding more motion detection, there is still always the possibility (especially where occupants may be sleeping) of a misfire. So don’t use this technique recklessly.
Once the ODU has a pretty good idea of the occupancy state, you can put this information to good use. The PLU makes a continuous record of the occupancy state using a simple encoding means.
Three bytes contain a total of 24 bits, each of which can represent the occupied or unoccupied status for any one hour in a day. Using this method, any one-day record can be encoded in three bytes and an entire week’s worth of data takes only 21 bytes. Later, I’ll show you how this encoding method makes it easy to compare occupancy patterns.
As I mentioned before, in this particular implementation, the system does not even know what the actual time is. It simply starts recording time from powerup and notes the passing of hour, day, and week increments. As shown in Figure 3, a record for any given "day" indicates clearly what the occupancy pattern was for that day.
 Figure 3—Here’s a typical occupancy history record for a 24-h period. This system doesn’t even know what the actual time is. It simply starts recording at powerup and rolls over 24 h later. Each day-long record is matched against previous records. |
The core technique at work in the PLU is to take the record for the same day of the previous week and use it to predict the occupancy for the current day. It’s well worth keeping a week’s worth of records since human habits center around a weekly pattern.
The process of putting the data to work is straightforward. Once every hour, at the same moment when the current occupancy state is recorded in today’s record, the record for that same day in the previous week is evaluated.
At this moment of truth, the algorithm looks ahead in the record to see if there is any expected occupancy. It only needs to see a couple of bits in the data from the previous week—the ones that indicated the occupancy state in the next 2-h slots.
These bits tell us if the area was occupied a week earlier during the upcoming couple hours. If so, then it’s likely to happen again. If the system senses an unoccupied state, then it need only check for either of the upcoming two hours to indicate an expected occupancy, and voilą—we have anticipation.
Note that, using this method, there is a resolution of 1 h, which means that accuracy is ± 1 h. That’s why the anticipator looks at the next 2 h of last week’s record. If it only looks 1 h ahead, it could err on the minus side all the way down to (almost) zero anticipation. Using 2 h gives it a performance range of 1–3 h of anticipation.
The range could easily be decreased by using a higher resolution system-wide. For example, records could indicate half-hour increments instead, which double the RAM usage but be otherwise identical in function, yielding an anticipation range from 30 to 90 min. The beauty of this method is that any resolution can be used and the implementation remains pretty much the same.
At this point, it may seem like the PLU was relatively easy to construct. Unfortunately, the algorithm is still not very smart.
Even though it can "predict" the arrival of occupants with some success, it records and acts on any and all patterns that arise, regardless of how atypical they may be. To build a sturdy machine that only recognizes "typical" patterns, a more complex mechanism is required.
The software approach that transcends the basic PLU is a sophisticated "fuzzy" recognizer that verifies the ordinariness of a pattern before committing it to memory. Note that the term "fuzzy" is used here loosely and does not refer to the use of fuzzy logic as an engineering approach. In this context, "fuzzy" means that the software is able to recognize patterns even when patterns don't match exactly.
The algorithm also has the ability to recognize when the building is unoccupied for an extended period (vacation detection) and suspends all pattern recording and anticipation until the building becomes normally occupied again. The original patterns are retained until they are needed again.
The fuzzy recognizer’s basic approach is a series of comparisons that each day’s record is put through in an attempt to gauge its validity. Figure 4 shows how previous records are stored in memory.
|
Long-term memory (LTM) is a permanent record, one week long. If a current record passes muster, it can replace the existing record for that particular weekday in LTM.
Additionally, there are five slots for temporary records. These are records that did not match anything at the time they appeared. The temporary records are key in the process of learning new patterns. Anytime a current pattern matches the same temporary pattern for two weeks running, the system assumes that it’s seeing a new schedule for that weekday.
 Figure 5—This
block diagram shows the overall strategy. The current day’s record is compared to
various patterns in an attempt to find the best match. It looks first for a close match
with the most likely element—that day’s record in LTM. Failing that, it looks
next for a sufficiently high score with any of the temporary records. |
Figure 5 shows a block diagram of the matching process. Each day’s record is compared to the same day’s record in LTM using a pattern-matching process. As shown in Figure 6, the two patterns are compared bit by bit with the total number of like bits being noted.
a)
b)
Figure 6—When patterns are compared, each bit position is checked and the number of matching bits are counted to yield a score. Shifting the patterns one bit to the left and to the right tells us if the patterns are similar but simply offset by an hour or so. |
Clearly, if all 24 bits are the same, the patterns are exactly alike. The tricky part is recognizing patterns that are very similar but not exactly alike.
The approach used here was to shift the patterns one bit position relative to each other and then measure the score again. This technique tells us if the patterns are similar except for being offset somewhat.
As you can see in Figures 6a and 6b, the shifting process can yield higher scores for patterns that really are similar, while producing nothing for patterns that aren’t all that much alike. Shifting both to the left and to the right and then looking for a score of at least 23 out of 24 gives a good assurance of a similar pattern.
If the record is not deemed similar enough to the LTM record for that weekday, then it is compared to the five different temporary records. The comparison with the temporary records is similar to that for LTM records, except that the shifting process is not employed and the current record is compared to all five temporary records with the score of each comparison being noted.
The highest-scoring comparison that scores at least 18 is taken as a match. A current record that fails to match any record is deemed a new temporary record, overwriting the oldest one in memory.
If a given record does match a temporary record, a quick check is performed to see if the same thing happened last week. If so (i.e., the record has matched the same miscellaneous record for two weeks running), then that record wins a place as the new permanent memory (i.e., LTM) for that weekday.
I should note here that the algorithm also checks for a completely unoccupied state during the current record’s 24-h period. Whenever there is a match with the unoccupied profile, a counter is incremented. If this happens for three consecutive days, then all system learning is suspended (i.e., vacation detection).
Through this pattern-matching process, a delicate balance is created. If a pattern is similar to patterns for that weekday in the past, then the new pattern is immediately adopted as permanent. This system allows for quick adjustment to changes like Daylight Savings Time.
If the pattern is not similar enough to adopt immediately, then it is compared to previous unusual patterns. If there is a match with one of these for at least two weeks running, then that pattern is taken as the permanent record.
The result of this process is that slight changes to patterns are adopted immediately, while anomalous patterns are ignored, unless they persist for several weeks. In that case, they are adopted as the new permanent record.
The system performed very well during informal testing. As expected, the algorithm learns occupancy patterns within a maximum of three weeks. When changes to the schedule are slight, the system the following week.
When presented with a markedly different pattern, the software waits a couple weeks, as designed, before adopting the new pattern into its permanent record. Because the algorithm is still verifying the validity of a pattern on the second week, it’s too late to act on it even if it passes the test, so the third week is when the anticipator responds to a new pattern.
Although the algorithm performs well, it has one weak spot. When the patterns contain a large number of alternately occupied and unoccupied periods, as shown in Figure 7, the algorithm is threatened by what I call the "comb problem." The problem is that the shifting process used in the matching algorithm can yield a high score for patterns that look similar (like two combs) but that are almost opposite in timing from each other.
|
Needless to say, this mode of operation is not likely to occur because of the rarity of a comb-like pattern arising in normal circumstances. And in practice, even if the comb problem were to appear, it may be irrelevant because the anticipator looks ahead for some time.
In other words, if the area were seeing very frequent occupancy changes, the anticipator ends up expecting arrival pretty much all the time. Fortunately, this is the behavior you want out of the system anyway, so the comb problem is fairly benign. However, I feel that it’s important to point out this theoretical weakness.
In case you are interested in setting up a similar system, you can download the source code for the PLU. However, I didn’t include code for the ODU. It is intertwined with the application software and would have been difficult to use in that form.
The PLU takes only a few hundred lines of assembler code, which translates to about 750 bytes of storage on your typical 8-bit micro. In terms of execution time, the worst-case condition takes about 1800 instructions.
On an 8031 running at 12 MHz, that equates to about 5 ms to run the PLU thread. This light load is further eased by the fact that the bulk of the PLU thread only runs once per day for an execution overhead of roughly 0.0000057%. So, the PLU can be easily integrated into an application without adding too much of a burden on system resources.
Hopefully, now you see how straightforward it is to set up intelligent building-control applications, and you’re ready to take us into those smart buildings we’ve heard so much about for so long.
Beau Wadsworth has been designing embedded systems since 1983. His company designs and manufactures products on an OEM basis for the security and home automation industry. You may reach Beau at (423) 689-8851 or via E-mail at b_wadsworth@nxs.net.
The source code for the PLU is available via the Circuit Cellar Web site.
