A Context-Aware Proactive Controller for Smart Environments Frank Krüger∗ Gernot Ruscher Sebastian Bader Thomas Kirste Universität Rostock, Albert-Einstein-Str. 21, 18059 Rostock, Germany ∗ corresponding author: frank.krueger2@uni-rostock.de ABSTRACT To proactively support users in instrumented environments, we need In this paper we describe an implicit user interface for smart en- to infer their intentions, the goals behind their current activities. vironment control: We make our system guess how to assist the Here we use a rather technical notion of intention: given descrip- user(s) proactively. Our controller is based on two formal descrip- tions of complex actions, like giving a presentation or preparing tions: One that describes user activities, and another that specifies a meal. If we detect the user performing some sub-tasks of these the devices in the environment. Putting both together, we can syn- complex action, we assume that his goal is to perform the complex thesize a probabilistic model, the states of which resemble activities action completely. A controller such as described requires all calcu- performed by the user(s) and are annotated with sequences of de- lation to be executed in realtime. It is therefore necessary to move vice actions, with the latter to be executed in cases particular activ- time consuming operations like planning processes from runtime to ities have been recognized. The resulting system is purely reactive compile time. Thus, we can create a purely reactive controller with and can be executed in real time. time-bounded complexity, able to control the environment in every possible situation. Categories and Subject Descriptors As illustrating example in this paper we use the task of giving a H.5 [User Interfaces]: Input Devices and Strategies presentation inside our smart meeting room. This environment is introduced below. The graphical representation of this task is given General Terms in Figure 1. Here the task of giving a presentation decomposes to a Theory sequence of sub-tasks. The user starts the presentation with enter- ing the room and moving to the front of the room. When the pre- sentation is finished the user moves to the door to leave the room. Keywords A more detailed description of this example is given in section 3. intention recognition, HMM, planning, smart environments 2. PRELIMINARIES 1. INTRODUCTION The controller described below is based on semantic models of the As computers become smaller and smaller, the vision of ubiquitous user and its environment. For our system we currently employ for- computing becomes true. At the same time, smart environments mal action descriptions and task models which are compiled into a contain a large number of devices and become thus more and more probabilistic model. All necessary concepts are briefly introduced complex. Thus, configuration as well as correct usage gets more below. time consuming and error prone. Exploring new ways to control these invisible devices is a challenge addressed by current research Hidden Markov Models (HMMs) [7] are probabilistic models, that [2]. Our approach is to create an entirely reactive system to control allow to infer a state of a system that is not observable directly, all devices of the environment by inferring the intentions of the but through noisy or ambiguous sensor data. An HMM defines a user. The system gives support by controlling the devices the way probabilistic model, that consists of a finite number of states, each the user would do to achieve his goals. We use a semantic modeling containing a probability distribution function over sensor observa- of the user and the environment to assure that the support is sound tion, that allow to conclude the system state given sensor data. To and complete, in the sense that the environment is able to support describe temporal behavior of a system an HMM specifies proba- the user correctly in every recognizable situation. bilities for state transitions. HMMs are state of the art methods for activity recognition. Depending on the available sensors, we can detect the current activ- ity of users. For example, an indoor positioning system can be used to detect whether a user is entering the room and heading for the presentation stage. As customary in activity and intention recog- nition, we use probabilistic models. Such models can cope with noisy and contradictory sensor data and allow nonetheless to infer the most likely sequence of actions or complex intention. Here, we use Dynamic Bayesian Networks [6], such as HMM’s for prob- Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA 1. Give Presentation 2. Enter 4. Move 8. Leave >> >> 5. Present >> 7. Move Door >> Room Front Room effect: (and (ison projector1) effect: (and (not (ison projector1)) (isdown canvas1)) (not (isdown canvas1))) Figure 1: Simplified CTML model describing a typical presentation within our smart environment abilistic modeling. Calculating a probability distribution over the Projector1 on true false current state with respect to the observed sensor data as well as the Canvas1 down previous state is known as filtering. Doing this requires a model, true TT TF that describes both, the behavior of the user and the sensor data false FT FF observable. In addition of recognizing the activity these methods allow to predict future activities, in this case intentions, of the user. Table 1: The cartesian product of all device states forming the world state. Complex behaviors of (groups of) users can formally be described using CTTE [5] or CTML-models [9], which basically are a hier- archical description of tasks. Sub-tasks can be set into a temporal environment as well as the middleware controlling the devices of relation of each other. CTML utilizes temporal operators as the the environment are described in [3] sequence operator (»), the order independence operator (|=|), the concurrent operators (|||) and others that are not used with the ex- Since the experimental environment may be used as smart meeting amples in this paper. The Collaborative Task Modeling Language room, a typical application is giving a presentation. In this scenario (CTML) is especially designed for smart environments and offers the user first enters the room. For our example we assume that the features for team modeling, location modeling, device modeling room contains one projector and one canvas. After the user moves and domain modeling. As described in section 4, we can transfer to the front of the room where the canvas is located, he prepares the such a description into a probabilistic model allowing to recognize environment for his presentation. Therefore he has to plug in the the current complex action, and thus allowing to infer the overall notebook, set up the projector and lower the canvas. After this is intention of a sequence of actions. done the user starts his talk and finishes it by moving to the door. Finally the user leaves the room. This example is kept simple to In the planning domain definition language (PDDL) [8], device illustrate the main points. The real environment is comprised of actions are formalized as 4-tuples: hName, Parameters, Precon- eight projectors and eight canvases. ditions, Effectsi. Based on such a formal description we can use standard AI planning techniques to infer a plan (sequence of ac- The task specification in Figure 1 contains a detailed description of tions) leading from the current to the desired state of the world. this example. The annotated effects (illustrated as clouds) describe Figure 2 and 3 show examples for PDDL descriptions. the desired state of the environment for the following sub-tasks. As description language for task models we use CTML, as described in 3. AN APPLICATION EXAMPLE section 2. The graphical representation of the task model omits the The environment where most of our experiments take place is the description of the observation data and the priority function. The so called Smart Appliance Lab. This room is instrumented with world state in this example is given in Table 1 and only consists various sensors such as the location tracking system Ubisense [1]. of the two devices. Each of them has a binary state, in case of the Thus, the location of different users is given by the environment. projector it is either turned on or turned off. The canvas can be up Other parts of our experimental environment are actuators such as or down. projectors and canvases. Here both sensors and actuators are called devices. Software counterparts of all these devices are provided by Our goal is now to build a controller that recognizes the current the middleware implemented for this environment. These software state of the user and executes corresponding device actions that devices enable us to gain the status of each device inside the room makes the annotated effects come true. By executing these action to create a world state. The world state of our environment is thus sequences that system automatically assists the user in achieving comprised of the sensor observations and the device states. The his goals. Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA (:action canvasdown :parameters (?c - canvas) : annotated annotated extended Executable Task Model HMM HMM :precondition (not (isdown ?c)) :effect (isdown ?c )) World State Figure 2: A PDDL specification of the CanvasDown action. (:action projectoron :parameters (?p - projector) : Figure 5: The workflow for creating the controller. :precondition (not (ison ?p)) :effect (ison ?p)) tor. Therefore we have to generate sequences of devices actions for each possible situation. This is done by taking each world state as Figure 3: A PDDL specification of the ProjectorOn action. start situation for a planner and the desired subset of the world state, described by the effects of the annotated HMM state as goal. To re- alize this the planner takes device action specifications, as shown in 4. A CONTEXT-AWARE PROACTIVE CON- Figure 2 and Figure 3. Result of this planning step is a sequence of TROLLER device actions for each possible world state that has to be executed to create the effects specified in the original annotated task model This section explains how to combine formal descriptions of the en- in Figure 1. vironment and the user behavior into a purely reactive probabilistic model. First the description of the user is compiled into a proba- The next two sections describe how to use these world state device bilistic model allowing to recognize the user’s intentions. Then, we action sequence pairs to generate the controller. Both approaches enrich this model by annotating the states with actions, executable follow the workflow given in Figure 5. by the environment. While running the system, and based on the current state of the environment one of the states will be most likely. The actions attached to the state are then simply executed, result- 4.2 Unfolding HMM states ing in a system supporting the user while achieving his high-level In order to create the distinction of the different world states as goals. HMM states, it is necessary to unfold annotated HMM states by using the different world states. Therefore we replace the anno- In the following sections we discuss two different possibilities of tated HMM state by extended HMM states that are generated from enriching the model with device actions. The first is to generate each possible world state and the state itself. In our example Move different HMM states for each possible world state. The latter is to Front will be replaced by each element of the cartesian product of annotate the corresponding state with sequences of device actions the world state to ensure that each observation of a world state cor- for all possible world states. A plan for the current world state is responds to one HMM state. Here Move Front is replaced by four then accessible by taking the world state as key for a lookup table new HMM states, each representing a possible world state. Only resulting in the corresponding plan. the HMM state that covers the complete effects has a transition to the HMM state generated from the following sub-task. In our ex- 4.1 From Symbolic to Probabilistic Models ample only the Move Front TT state, that assumes that the projector We start with the annotated task model from Figure 1, which con- is on and the canvas is down has this transition. sists of a task model and effects annotated to sub-tasks. Each effect is a subset of the world state. It consists of the cartesian product This allows to attach plans to the states in the probabilistic model of all device states. We apply the transformation given in [4]. This that needs to be executed in that state as follows: Every annotated is done by parsing the syntax tree of the annotated task model and user state is combined with every world state, that is a combination applying the inference rules for each of the temporal operators. The of all states of the devices. This world state is used as precondition states of the resulting annotated HMM correspond to tasks of the for device actions during compilation process. task model with corresponding effects. The whole model captures all possible (with respect to the task model) sequences to complete Figure 4 contains the extended HMM that was generated from the the root task. task model in Figure 1 combined with the world state defined in Table 1. Please note that self-transitions as well as probabilities for We extend the original task model by annotating tasks with their transitions or observations are omitted in the graphical representa- effects with respect to the world state. The effect of the annotated tion. task should be true after executing the task. This can be done by either the user or the controller. Figure 1 contains the additional The generated HMM contains so called slices, that consists of all effect specification for the Move Front and the Move Door sub- states generated from one sub-task from the CTML specification. tasks. In our scenario the effect of the state Move Front is that the One slice itself was created from the cartesian product of the world environment is prepared for the presentation, namely the canvas is state. The intra-slice states differ from each other only by the pos- down and the projector is on. sible observations of the world state. The names of the intra-slice states illustrated in Figure 4 contain the true/false value given in Ta- To ensure the effects of an annotated HMM state become true, the ble 1. Every state of the slice has an incoming intra-slice transition controller has to execute device actions depending on the current with a probability given by the number of states. Only the states world state. The canvas has to be lowered if it is up but if the that create the effects given in task model description have a out- projector is already turned on we can omit turning on the projec- going inter-slice transition with very high probability. It is possible Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA Move Move CanvasUp (canvas1) Front Present Front ProjectorOff (projector1) TT TT Move Move Front CanvasDown (canvas1) Front ProjectorOff (projector1) FT FT Enter Initial Room Move Move CanvasDown (canvas1) Leave Front Front ProjectorOn (projector1) Room FF FF Move Move Front Front TF TF ProjectorOn (projector1) CanvasUp (canvas1) Figure 4: The extended HMM created from the task model and the world state. that there are more than one state that covers the same effect due to missing effects to single devices of the world. The probabilities Initial Enter Move Move Leave Room Front Front Room of the intra-slice transitions are just given by the number of target states. Inter-slice transitions are generated with respect to the tem- poral operator of the sub-tasks. The probability of transitions are TT TT CanvasUp (canvas1) ProjectorOff (projector1) generated by the normalized weight of the single sub-tasks. TF ProjectorOn (projector1) TF CanvasUp (canvas1) CanvasDown (canvas1) FF FF 4.3 Lookup table ProjectorOn (projector1) FT CanvasDown (canvas1) FT ProjectorOff (projector1) Another approach to enrich the HMM with device action sequences for user assistance is to create a lookup table for necessary device actions and attach it to the corresponding annotated HMM state. As in the first approach the device action sequences depend on the Figure 6: The generated HMM extended by lookup tables for current world state and need to be generated by a planner that uses the plans. the specified effects as goals. Attaching this device action sequence - world state pairs to the annotated HMM state provides a lookup table at runtime. Using the world state, consisting of all device very much states, because it creates states for every possible world states the table provides the pre-generated device action sequence state. Here the distinction of the world state is done at the state that has to be executed in order to make the specified effects to the level. The idea of unfolding HMM states by using every possible environment become true. world state is appropriate if the state of a device is not reliable or noisy. In our scenario the states Move Front and Move Door are extended by lookup tables for user assistance. The table annotated to the The second approach is to move the distinction of the world states Move Front state contains device action sequences that ensure that from different HMM states with attached plans to one HMM state the projector is turned on and the canvas is down. The Move Door that contains a table of multiple plans, one for each possible world HMM state is annotated with a table of device action sequences state. The number of HMM states is independent from the world that ensure that given any world state the projector is turned off state, which avoids a very high number of states. This approach and the canvas is up. Figure 6 contains a graphical representation is applicable whenever the world state is known definitely. This of the generated extended HMM. Probability distribution functions means that each device state is observable without any noise or as well as state transition probabilities are omitted for reasons of inconsistency. clarity. 5. THE EXECUTION ENVIRONMENT 4.4 Choosing one method We developed an execution framework for Bayesian inference that The previous sections describe two approaches to attach pre-generated is able to perform fast online filtering of HMM’s and particle fil- plans to states of a probabilistic model, namely an HMM. Both ap- ters. By separating the model description from the implementation proaches generate realtime capable systems, that do not have to of the algorithms we designed a highly reusable framework. This solve planning problems such as finding a sequence of device ac- framework enables users to embed parameterized filters into differ- tions to support the user. The first approach creates an HMM with ent environments. This enables us to integrate the generated con- Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA troller into the software structure described above. Users of this Acknowledgements environment only need to implement problem specific details. Frank Krüger’s work in the MA XIMA project as well as Gernot Ruschers’s work in the MA IKE project are both supported by Wirt- A probabilistic model for filtering in our framework has to be im- schaftsministerium M-V at expense of EFRE and ESF. plemented in C++. One has to describe three different parts. First a specification of the state space, that is in the case of an HMM rep- 7. REFERENCES resented by a set of states. Second the transition probabilities from [1] http://www.ubisense.de, JUN 2009. each state to another, represented as matrix of probabilities. Third [2] Ubicomp ’10: Proceedings of the 12th ACM international a probability distribution of sensor observations for each state. To conference on Ubiquitous computing, New York, NY, USA, provide a more intuitive tool for describing HMM’s we introduced 2010. ACM. 608109. a description language that supports a simple way to describe HMM [3] S. Bader, G. Ruscher, and T. Kirste. Decoupling smart based models. environments. In S. Bader, T. Kirste, W. G. Griswold, and A. Martens, editors, Proceedings of PerEd2010, Copenhagen, The compilation process creates the state space of our controller SEP 2010. from the single sub-tasks of the user model combined with each possible device state combination. The transition probabilities are [4] C. Burghardt, M. Wurdel, S. Bader, G. Ruscher, and T. Kirste. given by the probabilities of the model generated only by the sub- Synthesising generative probabilistic models for high-level tasks as described in [4] and the observation probability distribu- activity recognition. In Activity Recognition in Pervasive tions of the original approach are extended by an observation of the Intelligent Environments. Atlantis Press, Paris, France, 2010. device states in the extended state. A model specified in the way To appear. needs sensor data and the world state as input and provides a se- [5] G. Mori, F. Paterno, and C. Santoro. Ctte: Support for quence of device actions as output. These device actions need to be developing and analyzing task models for interactive system executed in order to support the user. design. IEEE Transactions on Software Engineering, 28:797–813, 2002. [6] K. P. Murphy. Dynamic Bayesian Networks: Representation, 6. SUMMARY AND OPEN PROBLEMS Inference and Learning. PhD thesis, University of California, In this paper we showed that a context-aware controller for smart Berkeley, CA, USA, 2002. environments can be created from a combination of semantic mod- [7] L. R. Rabiner. A tutorial on hidden markov models and els of the user and the environment. The controller is based on selected applications in speech recognition. In Proceedings of bayesian inference where the model was generated from task-based the IEEE, pages 257–286, 1989. specification of users together with a precondition and effect spec- [8] S. Russell and P. Norvig. Artificial Intelligence: A Modern ifications of each device forming the environment. Sensor data as Approach. Prentice Hall, 3 edition, 2009. well a accumulated world state serve as input, a device action se- quence, that needs to be executed as output of the inference pro- [9] M. Wurdel, D. Sinnig, and P. Forbrig. CTML: Domain and cess. We introduced two ideas to merge task based user models and Task Modeling for Collaborative Environments. J. UCS, precondition and effects specification of the environment to create 14(19):3188–3201, 2008. probabilistic models that assist the user. Further research should include smart environment evaluation of the controller described here. Both approaches should be evaluated and the results should be compared for different devices and sce- narios. This includes tests for maximum manageable complexity of the state space as well as minimal complexity that creates suf- ficient user support. Due to the compile time planning process we are able to pre-generate action sequences. This allows to find mod- eling problems such as deadlocks at compile time. Our approach in this paper utilizes HMM’s for inference. However, since the state space may explode and exact inference will not be suitable, we can change the inference algorithm to Monte Carlo based methods such as particle filters. These methods are already supported by the exe- cution environment described above. The controller introduced here is described as central service. It is possible to decentralize this approach to the usage of multiple services, each of them describing a subspace of the model. By comparing the likelihood of multiple services, it is be possible to choose either an action sequence of one agent or a combination of multiple sequences that do not disturb each other. Another point that should be analyzed is how both systems be- have if only the most probable device action sequences will be pre- planned. If the system reaches a state that does not contain a device action sequence the plan has to created at runtime. The realtime behavior of this extension has to be examined. Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA